目前进度：
| A |
B |
C |
D |
E |
F |
| solved contest |
solved contest |
solved contest |
solved contest |
not solved |
solved later |
A. Sasha and the Beautiful Array
简要翻译
给定一个数组 $a$，可以随意交换元素，最大化 $\sum_{i=2}^{n} (a_i - a_{i-1})$。
思路解析
$\sum_{i=2}^{n} (a_i - a_{i-1}) = a_n - a_1$，所以最大值减最小值即可。
代码
Code
```cpp
#include<algorithm>
#include<cstdio>
using namespace std;
namespace Input{
const int BuffLen=1<<20;
char buf[BuffLen|2],*p1=buf,*p2=buf;
inline char getc(){
if(p1==p2)
p1=buf,
p2=buf+fread(buf,1,BuffLen,stdin);
return p1==p2?EOF:*p1++;
}
inline bool isdgt(const char op){return op>='0'&&op<='9';}
long long read(){
static long long res;static char op,f;
for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
return f?-res:res;
}
}
using Input::read;
typedef long long ll;
const int N=300010;
ll a[N],n;
void work(){
n=read();
ll mina=1000000000,maxa=0;
for(int i=1;i<=n;++i)
a[i]=read(),
mina=min(mina,a[i]),
maxa=max(maxa,a[i]);
printf("%lld\n",maxa-mina);
}
signed main(int argc,char **argv){
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
int T=Input::read();
while(T--)work();
return 0;
}
```
B. Sasha and the Drawing
简要翻译
给定一个 $n \times n$ 的方格网，求最少的填色块数，使得至少 $k$ 条对角线上有被染色的格子。
正方向（左上-右下方向）与负方向各有 $2n - 1$ 条对角线，所以 $k \leq 4n - 2$。
思路解析
首先，每多 $1$ 个填色块，有颜色的对角线个数最多 $+2$。
我们可以先给第 $1$ 行的方格填色，这样每次填色增加的对角线都没有重复。
接下来画个图，发现正方向和负方向的对角线各被统计了 $n$ 条。
而在第 $n$ 行，除了 $(n,1)$ 与 $(n,n)$，其他方格填色仍然能使有颜色的对角线个数 $+2$。
对于 $(n,1)$ 和 $(n,n)$，选它们的贡献只有 $1$。
所以 $k \leq 2(2n - 2)$ 时，答案为 $\lceil \frac{k}{2} \rceil$。如果 $4n - 4 < k \leq 4n - 2$，则答案为 $k - 2n + 2$。
代码
Code
```cpp
#include<algorithm>
#include<cstdio>
using namespace std;
namespace Input{
const int BuffLen=1<<20;
char buf[BuffLen|2],*p1=buf,*p2=buf;
inline char getc(){
if(p1==p2)
p1=buf,
p2=buf+fread(buf,1,BuffLen,stdin);
return p1==p2?EOF:*p1++;
}
inline bool isdgt(const char op){return op>='0'&&op<='9';}
long long read(){
static long long res;static char op,f;
for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
return f?-res:res;
}
}
using Input::read;
typedef long long ll;
void work(){
ll n=read(),k=read();
if(k<=(n*4-4))
printf("%lld\n",(k+1)>>1);
else
printf("%lld\n",k-2*n+2);
}
signed main(int argc,char **argv){
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
int T=Input::read();
while(T--)work();
return 0;
}
```
C. Sasha and the Casino
简要翻译
Sasha 去赌场玩，可以下赌若干次。每局赌注的金额为正整数且不超过 Sasha 现有资金。
设赌注金额为 $y$，若赢了可以得到 $(k - 1) \cdot y$，若输了则失去 $y$。
赌场有一个特殊机制：连输 $x$ 局后下一局必赢。当然，赌场里有很多手脚，不违反机制的情况下可以操控任意一局的输赢。
Sasha 的启动资金为 $a$，问适当策略下 Sasha 能否赚到无限多的钱。
思路解析
因为前 $x+1$ 局里一定有一局赢，所以我们只要考虑在这个区间赢一局能否赚到。
如果可以，那么钱就能一直变多；如果不能，那么赌场就可以在适当的时间让你赢一局（中断连败），同时你还亏钱，不可能越赌越多。
设 $y$ 为本次下注的最小金额，$z$ 为此次下注之前已经输了的钱。
如果这次赢了，那么必须赚到，所以 $(k - 1) \cdot y > z \Rightarrow y = \lfloor \frac{z}{k-1} \rfloor + 1$。
本次下注金额不能超过现有资金，有 $y \leq a - z$。
输了 $z$ 变为 $z + y$，到下一轮。
如果第 $x+1$ 轮仍有 $y \leq a - z$，说明 Sasha 一定能回本且赚钱。
代码
Code
```cpp
#include<algorithm>
#include<cstdio>
using namespace std;
namespace Input{
const int BuffLen=1<<20;
char buf[BuffLen|2],*p1=buf,*p2=buf;
inline char getc(){
if(p1==p2)
p1=buf,
p2=buf+fread(buf,1,BuffLen,stdin);
return p1==p2?EOF:*p1++;
}
inline bool isdgt(const char op){return op>='0'&&op<='9';}
long long read(){
static long long res;static char op,f;
for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
return f?-res:res;
}
}
using Input::read;
typedef long long ll;
bool work(){
ll k=read(),x=read(),a=read(),z=0;
for(int i=1;i<=x+1;++i){
ll y=z/(k-1)+1;
if(i==1)y=1;
if(y>a-z)return false;
z+=y;
}
return true;
}
signed main(int argc,char **argv){
// freopen("order.in","r",stdin);
// freopen("order.out","w",stdout);
int T=Input::read();
while(T--)
puts(work()?"YES":"NO");
return 0;
}
```
D. Sasha and a Walk in the City
简要翻译
给定一棵树，求如下点集的数量：
若将点集中的点染黑，任意一条树上简单路径中黑点不超过两个。
思路解析
类似树上 dp 的做法。
当一个点 $x$ 不能被选中，一定是以下两种情况之一：
-
有至少两个子树，它们中有选中点。这两个黑点的路径上包括了 $x$，$x$ 不能选。
-
有一个子树，其中某两个选中点构成父子关系。从 $x$ 到更深的那个黑点的路径上有两个黑点，$x$ 不能选。
设 $f_x$ 为 $x$ 子树内不存在父子关系的点集方案数， $g_x$ 为 $x$ 子树内存在父子关系的点集方案数。
考虑 $x$ 子树内不存在父子关系。若不选 $x$，其儿子 $y$ 之间的方案相互独立，可以相乘。然后再加上一个只选 $x$ 的方案。
$$
f_x = \prod_{y \in \mathrm{son}(x)} f_y + 1
$$
再考虑 $x$ 子树内存在父子关系。若不选 $x$，其儿子 $y$ 的 $f_y$ 至多选一个；若选 $x$，则其儿子的 $g_y$ 至多选一个。相加即可。
从 $g_y$ 到 $f_x$ 时，对于每个儿子 $y$，若子树选了空集，那么选了 $x$ 也不构成父子关系，所以应该加 $g_y - 1$。
$$
g_x = \sum_{y \in \mathrm{son}(x)} (f_y + g_y - 1)
$$
最后输出 $f_1 + g_1$ 即可。
代码
Code
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
namespace Input{
const int BuffLen=1<<20;
char buf[BuffLen|2],*p1=buf,*p2=buf;
inline char getc(){
if(p1==p2)
p1=buf,
p2=buf+fread(buf,1,BuffLen,stdin);
return p1==p2?EOF:*p1++;
}
inline bool isdgt(const char op){return op>='0'&&op<='9';}
long long read(){
static long long res;static char op,f;
for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
return f?-res:res;
}
}
using Input::read;
typedef long long ll;
const int N=300010;
const ll mod=998244353;
vector<int> ver[N];
int fa[N],n;
ll f[N],g[N];
void clear(){
for(int i=1;i<=n;++i)
ver[i].clear(),
fa[i]=0,
f[i]=g[i]=0;
}
void dfs(int x){
f[x]=1;
g[x]=0;
for(int y:ver[x]){
if(y==fa[x])continue;
fa[y]=x;
dfs(y);
f[x]=(f[x]*f[y])%mod;
g[x]=(g[x]+g[y]+f[y]+mod-1ll)%mod;
}
f[x]=(f[x]+1ll)%mod;
}
void work(){
n=read();
int root=1;
for(int i=1,x,y;i<n;++i){
x=read();y=read();
ver[x].emplace_back(y);
ver[y].emplace_back(x);
}
dfs(1);
printf("%lld\n",(f[1]+g[1])%mod);
clear();
}
signed main(int argc,char **argv){
// freopen("order.in","r",stdin);
// freopen("order.out","w",stdout);
int T=Input::read();
while(T--)work();
return 0;
}
```
F. Sasha and the Wedding Binary Search Tree
简要翻译
给定一颗二叉搜索树（BST）和值域 $[1, C]$,其中一些节点的权值未定，权值可以重复，求不同的 BST 方案数。
只要有一个节点的权值不同，就认为是不同的方案。
思路分析
对 BST 中序遍历，应该得到一个非严格递增的序列 $a$。
所以对于序列一段未定的权值，它们应该是非严格递增的。
对于一段未定权值，如果两端的确定权值为 $a_l, a_r$，则相当于在 $[a_l, a_r]$ 中选 $(r-l-1)$ 个数。
权值可以重复，应用隔板法可以得到方案数应为
$$
\binom{a_r - a_l + 1 + r - l - 1}{r - l - 1}
$$
对于序列两端的未定权值，设 $a_0 = 1, a_{n+1} = C$ 即可。
因为 $a_r - a_l$ 和 $C$ 同阶，不能预处理阶乘来计算组合数。
（这里想了好久怎么办）
最后发现由于 $\sum (r - l) = n + 1$，所以可以用朴素的 $\Theta(m)$ 方法求 $\binom{n}{m}$，总复杂度为 $\Theta(n)$。
至于取模，用 $x^{-1} \equiv x^{p-2} \bmod p$ 即可。
时间复杂度 $\Theta(n)$。
代码
Code
```cpp
#include<algorithm>
#include<cstdio>
using namespace std;
namespace Input{
const int BuffLen=1<<20;
char buf[BuffLen|2],*p1=buf,*p2=buf;
inline char getc(){
if(p1==p2)
p1=buf,
p2=buf+fread(buf,1,BuffLen,stdin);
return p1==p2?EOF:*p1++;
}
inline bool isdgt(const char op){return op>='0'&&op<='9';}
long long read(){
static long long res;static char op,f;
for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
return f?-res:res;
}
}
using Input::read;
typedef long long ll;
const int N=500010;
const ll mod=998244353;
int lc[N],rc[N],val[N];
int a[N],num;
int n;ll inf;
void clear(){
for(int i=1;i<=n;++i)
lc[i]=rc[i]=-1,
val[i]=-1,
a[i]=0;
num=0;
}
void dfs(int x){
if(~lc[x])dfs(lc[x]);
a[++num]=val[x];
if(~rc[x])dfs(rc[x]);
}
ll qpow(ll x,ll y){
ll ans=1;
for(;y;y>>=1ll,x=(x*x)%mod)
if(y&1ll)
ans=(ans*x)%mod;
return ans;
}
ll C(ll n,ll m){//(n(n-1)(n-2)...(n-m+1))/(m!)
ll p=1,q=1;
for(ll i=1;i<=m;++i)
p=(p*(n+1-i))%mod,
q=(q*i)%mod;
return p*qpow(q,mod-2)%mod;
}
void work(){
n=read();inf=read();
for(int i=1;i<=n;++i)
lc[i]=read(),
rc[i]=read(),
val[i]=read();
dfs(1);
ll ans=1;
a[0]=1;a[n+1]=inf;
for(int i=1,lst=0;i<=n+1;++i)
if(~a[i]){
ans=ans*C(a[i]-a[lst]+i-lst-1ll,i-lst-1ll)%mod;
lst=i;
}
printf("%lld\n",ans);
clear();
}
signed main(int argc,char **argv){
// freopen("order.in","r",stdin);
// freopen("order.out","w",stdout);
int T=Input::read();
while(T--)work();
return 0;
}
```