目录
- Contest Link
- Problem A Glory Addicts
- Problem B Prefix Sum Addicts
- Problem C Even Number Addicts
- Problem D Permutation Addicts
- Problem E Balance Addicts
- Problem F Connectivity Addicts
Contest Link
Problem A Glory Addicts
题意
有 \(n\) 个技能，其中有一些是冰系的，有一些是火系的。
第 \(i\) 个技能伤害是 \(b_i\)。如果在释放一个技能后立刻释放与之不同系的技能，则后面释放的那个技能伤害翻倍。
求能造成的最大总伤害。
多组数据，数据组数 \(1 \leq T \leq 10^5,1 \leq n ,\sum n\leq 10^5,1 \leq b_i \leq 10^9\)
题解
首先，如果全是冰系或者火系，那么答案就是 \(b_i\) 的和。
否则一定交错放置更优。设有 \(x\) 个火系，\(y\) 个冰系，分类讨论第一个是冰系还是火系。
如果第一个是火系，那么分别有 \(\min(x-1,y),\min(x,y)\) 个火系和冰系技能可以 double，肯定贪心地选最大的来 double。
反过来也类似。
# include <bits/stdc++.h>
const int N=100010,INF=0x3f3f3f3f;
int n,T;
std::vector <int> S[2];
int op[N];
long long sum;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
T=read();
while(T--){
n=read(),sum=0,S[0].clear(),S[1].clear();
for(int i=1;i<=n;++i) op[i]=read();
for(int i=1;i<=n;++i){
int x=read();
S[op[i]].push_back(x),sum+=x;
}
std::sort(S[0].begin(),S[0].end(),std::greater <int> ());
std::sort(S[1].begin(),S[1].end(),std::greater <int> ());
if(!S[0].size()||!S[1].size()){
printf("%lld\n",sum);
continue;
}
int alen=S[0].size(),blen=S[1].size();
int as=std::min(blen,alen-1),bs=std::min(alen,blen);
long long tb=0,cb=0;
for(int i=0;i<as;++i) tb+=S[0][i];
for(int i=0;i<bs;++i) tb+=S[1][i];
bs=std::min(alen,blen-1),as=std::min(alen,blen);
for(int i=0;i<as;++i) cb+=S[0][i];
for(int i=0;i<bs;++i) cb+=S[1][i];
printf("%lld\n",sum+std::max(tb,cb));
}
return 0;
}
Problem B Prefix Sum Addicts
题意
给定一个长度为 \(k\) 的整数序列 \(s_{n-k+1},s_{n-k+2},\cdots,s_n\)。问是否存在一个合法的整数序列 \(a_1,a_2,\cdots,a_n\) 满足：
- \(a_1 \leq a_2 \leq \cdots \leq a_n\)
- \(\forall n-k+1\leq i \leq n,\sum \limits_{i=1}^{i} a_i = s_i\)
多组数据，数据组数 \(1 \leq T \leq 10^5,1 \leq n,\sum n\leq 10^5,1 \leq k \leq n, -10^9 \leq s_i \leq 10^9\)
题解
首先可以根据 \(s\) 计算出 \(a\) 的后 \(k-1\) 位，并判断是否满足条件。
如果通过了前面的判断，那么现在 \(a_{n-k+2}\) 已知，前 \(n-k+1\) 位最大能取到 \(a_{n-k+2}\)。如果 \((n-k+1)a_{n-k+2} < s_{n-k+1}\)，那么肯定不合法，反之一定合法，因为大了可以改小，小了却不能改大。
Problem C Even Number Addicts
题意
有 \(n\) 个整数 \(a_1,a_2,\cdots,a_n\)，Alice 和 Bob 轮流操作，每次取走一个数。当所有数都被取完之后，如果 Alice 手上的数和为奇数，则 Alice 获胜，否则 Bob 获胜。
问谁有必胜策略。
多组数据，\(1 \leq T \leq 100,1 \leq n \leq 100,-10^9 \leq a_i \leq 10^9\)
题解
首先每个数都可以变为 \(0\) 或 \(1\)。
注意到 \(n\) 只有 \(100\)，DP 模拟即可。
事实上，有单组数据 \(O(n)\) 的做法。如果有 \(a\) 个 \(0\)，\(b\) 个 \(1\)，那么：
- 当 \(b \equiv 2 \pmod 4\) 时，Bob 一定赢。他只需要跟着 Alice 选就行了。唯一可能会出现意外的情况是 Alice 选了最后一个 \(0\)。此时 Bob 选 \(1\)，Alice 也只能跟着选，于是最后每个人都拿到了 \(\dfrac b2\) 个 \(1\)。
- 当 \(b \equiv 3 \pmod 4\) 时，Alice 一定赢。Alice 只需要先手选掉 \(1\)，剩下的局面和上面的类似，只不过这一次，Alice 会拿到 \(\dfrac{b}{2}+1\) 个 \(1\)：这是一个偶数。
- 当 \(b \equiv 0 \pmod 4\) 时，Alice 一定赢。Alice 只需要先手选掉 \(0\)，然后跟着 Bob 选。如果先手没有 \(0\) 能选不会影响，和上面的证明类似。
- 当 \(b \equiv 1 \pmod 4\) 时，谁选第一个 \(1\) 问题就变成了第三种情况，于是谁都不想选第一个 \(1\)。因此，如果有偶数个 \(0\)，则 Bob 赢，反之 Alice 赢。
Problem D Permutation Addicts
题意
对于 \(1 \sim n\) 的排列 \(a\) 和参数 \(k\)，长度为 \(n\) 的 \(b\) 数组按照如下方式生成：
- 如果 \(a_i \leq k\)，则 \(b_{a_i}\) 的值为满足 \(1\leq j < i\) 且 \(a_j > k\) 的 \(a_j\) 中，\(j\) 最大的 \(a_j\)；不存在则为 \(0\)
- 如果 \(a_i > k\)，则 \(b_{a_i}\) 的值为满足 \(1 \leq j < i\) 且 \(a_j \leq k\) 的 \(a_j\) 中，\(j\) 最大的 \(a_j\)；不存在则为 \(0\)
现在给定 \(b\) 数组，求一组 \(a\) 和 \(k\) 的合法解。保证至少存在一组解。
多组数据，\(1 \leq T \leq 10^5,1 \leq n,\sum n \leq 10^5,0 \leq b_i \leq n+1\)
题解
考虑 \(b_i\) 向 \(i\) 连边，表示 \(i\) 必须出现在 \(b_i\) 后面。注意到限制关系构成一棵树，且 \(0\) 和 \(n+1\) 不会同时出现。
我们要求的就是树的一个 BFS 序。首先注意到，节点 \(x\) 最多有一棵子树大小不为 \(1\)。这是因为如果 \(x \leq k\)，那么 \(x\) 的所有儿子的编号都大于 \(k\)，从而 \(x\) 的所有儿子的儿子编号都小于等于 \(k\)。如果 \(x\) 的所有孙子的父亲不唯一，那么显然矛盾：这些孙子之前第一个大于 \(k\) 的数显然只能有一个。
\(x>k\) 也成立。因此，我们 BFS 时先访问子树大小为 \(1\) 的节点，再从其它子树递归即可。
Problem E Balance Addicts
题意
给定一个长度为 \(n\) 的序列 \(a\)，问有多少种将这个序列划分成若干段的方式，满足：
- 设划分成了 \(k\) 段，每段的和分别依次为 \(s_1,s_2,\cdots,s_k\)，则 \(s\) 是一个回文序列。
答案对 \(998244353\) 取模。
多组数据，\(1 \leq T \leq 10^5,1 \leq n,\sum n\leq 10^5,0 \leq a_i \leq 10^9\)
题解
考虑递归计算。设区间 \([l,r]\) 的答案为 \(f(l,r)\)。分类讨论：
-
如果 \([l,r]\) 全是 \(0\)，答案就是 \(2^{r-l}\)。
-
如果 \([l,r]\) 有长度均不为 \(0\) 的全 \(0\) 前缀和后缀，设其长度分别为 \(x,y\)，则答案为
\[f(l+x,r-y) \times \sum \limits_{k=0}^{\min(x,y)} \dbinom xk \dbinom yk \] -
如果不满足上面的条件，那么我们可以找到最小的 \(i\) 以及与其对应的最大的 \(j\) 使得 \(a_l+a_{l+1}+\cdots a_i = a_r+a_{r-1}+\cdots+a_j > 0\)。
-
如果 \(i=r\)，那么答案为 \(1\)。
-
否则，如果 \([i+1,j-1]\) 全是 \(0\)，答案就是 \(2^{j-i}\)。注意此时第一个 \(0\) 前面和最后一个 \(0\) 后面都可以成为分界点。
-
否则，设 \([i+1,j-1]\) 分别有长度为 \(x,y(x,y>0)\) 的全 \(0\) 前后缀，则可行的分界点分别是第一个 \(0\) 之前和每一个 \(0\) 之后。于是答案为
\[f(i+x,j-y) \times \sum \limits_{k=0}^{\min(x+1,y+1)} \dbinom {x+1}{k} \dbinom {y+1}{k} \]
-
如果计算组合数的复杂度为 \(O(1)\)，那么总时间复杂度 \(O(n)\)。
Problem F Connectivity Addicts
题意
有一张 \(n\) 个点的图，给定每个点的度数 \(d_i\)，但是边的具体分布未知。
你可以询问不超过 \(n\) 次，每次询问给定一个点 \(u\)，如果这是第 \(k\) 次询问点 \(u\)，那么你会得到第 \(k\) 个和 \(u\) 相连的点的编号。
你需要染色这些点，要求对于每一种颜色 \(c\)：
- 颜色为 \(c\) 的点的导出子图联通；
- 设 \(s_c\) 是这些点的度数（\(d_i\)）之和，\(n_c\) 是这些点的个数，那么 \(s_c \leq n_c^2\)。
多组数据，\(1 \leq T,n,\sum n \leq 1000\)
题解
考虑每次找到度数最大的未染色点。依次遍历相邻点，如果所有相邻点都未染色，则染上一种新的颜色；否则，将前面的未染色点（包括自身）染上与第一个已染色相邻点相同的颜色。
考虑该策略什么时候会失效。联通性是显然的；难点在于判断是否会出现 \(s_c > n_c^2\)。
事实上，这是不可能的。首先观察到，当启用一种新颜色 \(c\) 时，\(s_c \leq n_c^2\) 显然是成立的。这是因为，设 \(c\) 中度数最大的点为 \(x\)，那么启用新颜色 \(c\) 时，会将 \(x\) 及其领域染上颜色 \(c\)。此时 \(n_c = d_x+1\)。因为 \(x\) 邻域中的点度数均不超过 \(d_x\)，于是 \(s_c \leq (d_x+1)d_x \leq (d_x+1)^2 \leq n_c^2\)。
当新的点加入颜色 \(c\) 的连通块中时，\(n_c\) 增加了 \(1\)，而 \(s_c\) 增加了至多不超过 \(d_x\)。因此，上面的等式将继续成立。
时间复杂度 \(O(n^2)\)。
# include <bits/stdc++.h>
const int N=1010,INF=0x3f3f3f3f;
int d[N],c[N];
bool vis[N];
int n;
int T;
int cnt;
std::queue <int> q;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
inline int mkc(int x){
printf("? %d\n",x);
fflush(stdout);
return read();
}
int main(void){
T=read(),d[0]=-1;
while(T--){
n=read(),cnt=0;
for(int i=1;i<=n;++i) d[i]=read();
memset(vis,false,sizeof(vis));
memset(c,0,sizeof(c));
for(;;){
int ch=0,col=0;
for(int i=1;i<=n;++i) if(!vis[i]&&d[i]>d[ch]) ch=i;
if(!ch) break;
std::vector <int> S={ch};
for(int i=0;i<d[ch];++i){
int v=mkc(ch);
if(c[v]){
col=c[v];
break;
}
S.push_back(v);
}
if(!col) col=++cnt;
for(auto v:S) c[v]=col,vis[v]=true;
}
printf("! ");
for(int i=1;i<=n;++i) printf("%d ",c[i]);
puts(""),fflush(stdout);
}
return 0;
}