喵喵题(ATCoder)
1. 【奇特构造】[ARC146D] >=< *2663
这个标题好可爱（
题意
求构造满足以下所有 \(k\) 个条件长度为 \(n\) 值域为 \([1,m]\) 的序列 \(A\) 使得对于每一个条件 \((x_i,y_i)\) 满足其三者之一：
- \(A_{p_i}<x_i\) 且 \(A_{q_i}<y_i\) ；
- \(A_{p_i}=x_i\) 且 \(A_{q_i}=y_i\) ；
- \(A_{p_i}>x_i\) 且 \(A_{q_i}>y_i\) 。
\(1\le n,m,k\le 2\times 10^5\) 。
破题点
转化为小于等于符号。则条件为 \(A_{p_i}\le x_i \and A_{q_i}\le y_i\) 要么同时成立，要么同时不成立，最小化每个元素。
很明显每个元素越小，它越有可能满足条件。所以类似于图论的条件遍历，我先把和 \(1\) 有关的所有约束条件更新，条件最终成功了就 break 掉。如果条件失败了要更新新的，边数不超过 \(4k\) 条，总共时间复杂度就是 \(O(n+k)\)。
很奇怪的贪心啊。
题解
下面是官方题解的思路：
碰到操作的时候，对于条件 \(i\) ，等价于 \(A_{P_i}\le X-1\) 当且仅当 \(A_{Q_i}\le Y-1\) 而且 \(A_{P_i}\le X\) 当且仅当 \(A_{Q_i}\le Y\) 。可以把它拆成两个约束条件看。所以我们只要让 \(A_{P_i}\) 和 \(A_{Q_i}\) 要么都符合条件（指分别小于等于 \(X,Y\)）要么都不符合条件即可。
首先初始 \(A\) 所有元素为 \(1\) 。不断约束使得 \(A\) 符合条件。
然后对于一个个条件不断更新：如果 \(A_{P_i}\) 大于 \(X_i\) ，那么 \(A_{Q_i}\) 就更新为 \(\max(A_{Q_i},Y_i+1)\) 。同理 \(A_{Q_i}\) 大于 \(Y_i\) 也对 \(A_{P_i}\) 做类似处理。
最后判断一下在 \(M\) 的值域之内即可。
这样做的正确性显然：增量法，假设之前已经构造出了最优解，这两个元素无疑是最小的。如果符合条件就无需变动，否则就取一个对于两者都最小的不符合值域的值。
所以就可以 \(O(n+k)\) 做了。
具体细节需要位置从小到大，用队列循环更新，这样能够保证最优化。
2. 【数学结论】[ARC147D] Sets Scores *2145
题意
构造 \(n\) 个集合，其中的数范围 \([1,m]\)，相邻两个集合之间有且仅有一个不同的数。
定义这 \(n\) 个集合的分数为 \(∏\limits_{i=1}^{m}cnt(i)\)，\(cnt(i)\) 为 \(i\) 数字出现的次数。求所有可能的构造方案分数之和。
没有看到题解的时候我想了很久，没什么出路。后来题解分析了一下方案，豁然开朗。
破题点
研究每个元素的变化，以此推出出现次数。接着利用出现和未出现的次数来解决问题。
解题思路
首先可以发现相邻两个只相差一个数，记录这个数，设其为 \(x_i\)。
这个数有什么用呢？观察到 \(x_i\) 就是在第 \(i+1\) 个集合中对于数 \(x_i\) 状态的改变。即 \(i\) 位置有，\(i+1\) 位置就没有了；或者 \(i\) 位置没有，\(i+1\) 位置就有了。
因为确定了一个长度为 \(n-1\) 的序列 \(x\)，所以只需要确定第一个位置上的集合，权值就出来了。
设 \(a_x\) 为第一个集合中包含 \(x\) 时，所有的集合包含 \(x\) 的个数，同理可以设置 \(b_x\) 为第一个集合中不包含 \(x\) 时，剩下的集合包含 \(x\) 的个数。
于是我们就有了确定了第一个集合之后，所有方案对于它的贡献：\(∏\limits_{i=1}^{m}{(a_i+b_i)}\)。
然后，因为 \(x\) 序列固定，又知道 \(x_i\) 的性质，所以决定它出现次数的，只有某个数在第一个集合中出现与否：如果出现了，就选择 \(a_i\)；否则选择 \(b_i\)。经过一番观察，我们发现 \(a_i+b_i=n\)。
（其实就是阴阳互补的思想）
对于一个可行的 \(x\) 序列，它的取值和上一个毫无关系，它的个数就是 \(m^{n-1}\) 个。
所以对于全局的答案，就是 \(n^m\times m^{n-1}\)。
这题在思考的时候，觉得有点困难，没有深入挖掘性质。同时欠缺了观察和设计状态。
希望之后解这种数学题的时候，能够思维与观察、性质相结合。
另外，对于解这种英文题，理解切忌偏差。
3. 【奇特最短路】[ARC150C] Path and Subsequence *1802
题意
一张 \(n\) 个点 \(m\) 边的图，点有点权 \(A_i\) ，求找出一条 \(1\to n\) 的路径使得 \(B\) 序列不是路径上所有点权组成的序列的子序列。\(n\le 10^5\) 。
破题点
首先走简单路径一定更优；其次可以泛化边权思想，对于最小化 dist 的性质也得用上。
题解
可以观察到这样的路径取简单路径一定比走一遍或者两遍环会更优。因为走环相当于把一段操作序列复制一遍，复制一遍更容易出现子序列。
观察子序列自动机算法，它是到了某个位置匹配到 \(B\) 的第几位，越高越好。
因为本题之中要不能使该路径匹配，进而推出从起点到了某一个点匹配 \(B\) 中的位置越小越好。
所以设置 \(d[x]\) 为从 \(1\) 到达 \(x\) 路径最少匹配到 \(B\) 的第 \(d[x]\) 位。转移易，使用 dijkstra 算法计算最短路即可。
const I maxn=1e5+10,maxm=4e5+10;
I d[maxn],n,m,k,a[maxn],b[maxn];
I Ey[maxm],NX[maxm],HD[maxn],Ec;
void conn(I x,I y){
Ey[++Ec]=y;NX[Ec]=HD[x];HD[x]=Ec;
}priority_queue<pair<I,I> >pq;
bool bz[maxn];
int main(){
in(n,m,k);
for(I i=1,x,y;i<=m;++i){
in(x,y);
conn(x,y);
conn(y,x);
}for(I i=1;i<=n;++i)in(a[i]);
for(I i=1;i<=k;++i)in(b[i]);
b[k+1]=-inf;
memset(d,0x3f,sizeof(d));
d[1]=(a[1]==b[1])?1:0;
pq.push(make_pair(-d[1],1));
while(pq.size()){
I x=pq.top().second,y,z;pq.pop();
if(bz[x])continue;
bz[x]=1;
for(I i=HD[x];i;i=NX[i]){
y=Ey[i];
if(d[y]>d[x]+(z=(a[y]==b[d[x]+1]?1:0))){
d[y]=d[x]+z;
pq.push(make_pair(-d[y],y));
}
}
}puts(d[n]==k?"Yes":"No");
return 0;
}
4. 【缩点包治百病】[ABC286G] Unique Walk *2135
题意
有一张 \(n\) 个点 \(m\) 条边的无向图，已知 \(k\) 条边为关键边，需要经过恰好一次，能否满足条件。
破题点
非关键边不限次数，那么就当作一个点内部反复横跳。
所以缩成一个连通块，内部有关键边就当自环，也可以忽略。
然后欧拉通路即可。
题解
缩点包治百病（不是），在这题大有作用。
因为非关键边不限次数，所以对于所有非关键边所连接的点集缩成一个连通块。这里可以使用并查集计算。
然后发现这张图只剩下关键边了。
现在就要求遍历所有边恰好一次。
于是求解欧拉通路可行性就搞定啦。
const I N=2e5+10;
I ey[N],ex[N],n,m,k,f[N],cnt,d[N];
bool b[N];
I getf(I x){
return x==f[x]?x:f[x]=getf(f[x]);
}int main(){
in(n,m);
for(I i=1;i<=n;++i)f[i]=i;
for(I i=1;i<=m;++i)in(ex[i],ey[i]);
in(k);
for(I i=1,x;i<=k;++i)in(x),b[x]=1;
for(I i=1;i<=m;++i)if(!b[i])f[getf(ex[i])]=getf(ey[i]);
for(I i=1;i<=n;++i)f[i]=getf(i);
for(I i=1;i<=m;++i)if(b[i]){
++d[getf(ex[i])];
++d[getf(ey[i])];
}for(I i=1;i<=n;++i)if(d[i]&1)++cnt;
if(cnt>2)puts("No");
else puts("Yes");
return 0;
}
5. 【凸壳决策】[ABC289G] Shopping in AtCoder store *2109
题意
有 \(n\) 位顾客，有 \(m\) 种商品，初始价值为 \(c_i\)，顾客 \(i\) 选择第 \(j\) 种商品当且仅当 \(b_i+c_j\ge p_j\)。其中 \(b,c\) 已给定，求给每种商品定价 \(p\) 使得销售额最大化。
破题点
发现不能 \(O(n^2)\) 暴力做，先钦定顺序，确定单调性，然后发现是 \(j(b_j+c_i)\) 这样的一个东西。
拆开，发现是一个一次函数，维护个下凸壳即可。
题解
可以按照 \(b\) 从大到小排序，对于每个商品 \(i\) 枚举购买它的人数 \(j\)，那么答案就是 \(j(b_j+c_i)\)。
比赛时被坑了一会是因为这个答案并不满足单调性，所以考虑另外的思路。
拆开这个价值，原式就是 \(j\cdot c_i+j\cdot b_j\)，这个时候假设 \(j\) 是可以已知的数据，而把 \(c_i\) 设成 \(x\) 即未知的数据，那么式子就转化成了 \(K_jx+B_j\) 的形式（令 \(K_j=j,B_j=j\cdot b_j\)）。
对于一个给定的 \(c_i\) 我们需要求得对于所有一次函数的最大值，这个可以使用半平面交维护一个下凸壳。
下凸壳的维护，只需要维护一个斜率递增的直线集合即可，对于一条斜率更大的直线我们可以按照单调性判掉交点在其右边的所有线段。
可以去做这个题目，P3194 [HNOI2008]水平可见直线。
对于本题只需要先算出凸壳上相邻两条直线的交点，然后按照交点集二分这个 \(c_i\) 对应的是第几条线段即可。
时间复杂度 \(O(n\log n+m\log n)\)。
const I N=2e5+10;
I b[N],n,m,q[N],t;
LL k[N];
double jdx(I i,I j){
return -1.0*(k[i]-k[j])/(i-j);
}double lb[N];
int main(){
in(n,m);
for(I i=1;i<=n;++i)in(b[i]);
sort(b+1,b+n+1,greater<I>());
for(I i=1;i<=n;++i){
k[i]=1ll*b[i]*i;
while(t>1&&jdx(q[t-1],i)<=jdx(q[t-1],q[t]))--t;
q[++t]=i;
}for(I i=2;i<=t;++i){
lb[i]=jdx(q[i-1],q[i]);
}lb[t+1]=inf;
for(I i=1,c,id;i<=m;++i){
in(c);
id=upper_bound(lb+1,lb+t+2,c)-lb-1;
printf("%lld ",1ll*(c+b[q[id]])*q[id]);
}
return 0;
}
6. 【树形DP板子】[ABC287F] Components *2034
破题点
按照给定顺序做树形背包，可以做到 \(O(n^2)\)（这个 trick 叫做 Square-Order Tree DP）。
题解
代码和和动态规划的式子想必大家都已经很清楚了，但是为什么是 \(O(n^2)\) 呢？
求证： \(O(\sum\limits_{i=1}^n \sum\limits_{j\in son(i)} siz(j)\times (1+\sum\limits_{k\in visited\_son(i)} siz(k)))=O(n^2)\)。
考虑一个这样的事实，对于 \(i\) 从左到右扫描儿子 \(j\)，但是已经遍历过的儿子不会再对当前 \(i\) 的答案造成贡献。
考虑 \(siz(used)\times siz(j)\) 的时间复杂度意义，可以说是对于 \(j\) 子树之中的每个节点，枚举其左边遍历过的儿子并且贡献答案。
而这个 DP 顺序使得左边遍历过的儿子不会重复遍历，所以对于每个节点，其左边已经遍历过的所有节点个数不会超过 \(O(n)\) 级别，所以时间复杂度就是 \(O(n^2)\) 级别的。
7. 【上下界板子】[ABC285G] Tatami *2566
题意
\(n\times m\) 的矩阵，使用 \(1\times 1\) 或者 \(1\times 2\) 的小矩形填满。\(1\le n,m\le 300\)。
已知一些点要求被 \(1\times 1\) 或者 \(1\times 2\) 的小矩形覆盖。求使用这两种矩形填满矩阵的可行性。
破题点
省流：上下界网络流+方格取数建模，完事。
题解
分析：其实就是要求所有标记 \(2\) 数字的位置能够匹配到相邻四联通的矩形。
于是我们黑白染色这张图，然后所有起点连接所有白点，所有黑点连接终点，所有流量都是 \(1\)。
然后对于左侧的白点，如果右侧有相邻且可行的黑点，那么就连接一条边到黑点，流量为 \(1\)。
判断可行性就判断残量网络：每个标记 \(2\) 的节点左端或者右端有 \(1\) 的流即可。
但是，该做法在考场上 WA 了 \(11\) 个点，所以需要证伪或者改进。
这个做法为什么是错的呢？因为在这张二分图上面最大流跑出来往往不是完美匹配，而最大流不能保证经过所有的标记 \(2\) 的节点，它只能保证最大流，如果经过标记 \(2\) 节点时候占用了一些节点使得无法跑满最大流，它就会毫不犹豫地放弃标记 \(2\) 节点，但是实际上可以牺牲最大流而满足所有 \(2\) 的条件。
那么我们强制限定标记 \(2\) 节点到 \(T\) 或者从 \(S\) 到它的所有边的最小流量为 \(1\)，最大流量也为 \(1\)；其他边的最小流量为 \(0\)，最大流量为 \(1\) 即可。即可使用上下界有源汇可行流解决问题。
有源汇通常转成无源汇可行流，即从 \(T\) 向 \(S\) 连接一条上限流量为无穷大、下限流量为 \(0\) 的边即可。
假设每条边的上限流量是 \(u(i,j)\)，下限流量为 \(d(i,j)\)，我们需要给每条边定一个流量 \(f(i,j)\)，使得流量平衡且在限制内。
那么不妨考虑每条边已经流了 \(d(i,j)\) 的流量，所以只能多流 \(u(i,j)-d(i,j)\) 的流量。
设一个节点 \(x\) 初始入流流量减去初始出流流量的流量差 \(W\)。
如果 \(W=0\)，就什么也无需修改。
如果 \(W<0\)，说明出流量过大。为了维护图的正确性，需要把 \(x\) 连接一个附加的汇点 \(T'\)，流量为 \(-W\)。这样的意义是为了提高 \(x\) 的入流量：从 \(x\) 走到 \(T'\) 显然比绕别的弯路要容易，所以在满足条件的情况之下，跑最大流的时候就一定会给入流流量提高 \(-W\)，换而言之，让 \(x\) 流正确的流不是它缺什么就给什么，而是提高对它的要求。
如果 \(W>0\)，说明入流量过大。为了维护图的正确性，需要把新建的源点 \(S'\) 连接 \(x\)，流量为 \(W\)。这样的意义就是为了扩大 \(x\) 的出流量：证明同理。
于是我们对于 \(S'\) 到 \(T'\) 跑最大流，枚举 \(S'\) 的所有出边，观察到如果这几条边都不能跑满，那么就是失败；对于 \(T'\) 也是同理。为什么连没有跑满就算失败呢？因为它连基础的源汇点赋予它的使命——流量平衡都无法满足，只能退而求其次，这种图，怎么能说它是可行的呢？
本题之中，需要改变一些建图方式。
只有 \(S\) 到所有白点的边才有可能有下界 \(d\)，所以枚举标记为 \(2\) 的白点，\(W\) 值就是 \(1\)，所以 \(S'\) 向它连接一条容量为 \(1\) 的边；
只有所有黑点到 \(T\) 的边才有可能有下界 \(d\)，所以枚举标记为 \(2\) 的黑点，\(W\) 值是 \(-1\)，所以它向 \(T'\) 连接一条容量为 \(1\) 的边；
其他边的连接状况和流量状况都不变。
最后连接 \(T\) 和 \(S\) 容量为无穷大，\(T\) 的 \(W\) 值为所有标记为 \(2\) 的黑点数量（设之为 \(sum2\)），那么连接 \(S'\) 和 \(T\) 点，容量为 \(sum2\)。
对于 \(S\) 点的 \(W\) 值就是所有标记为 \(2\) 的白点数量的相反数（设之为 \(sum1\)，且 \(sum2-sum1=\)矩阵中 \(2\) 的个数），容量为 \(-sum1\)。
对 \(S'\) 到 \(T'\) 跑最大流，然后对于 \(S'\) 流出的、\(T'\) 流入的，看看有没有流满。
时间复杂度是 \(O((HW)^{1.5})\)，可以通过。（这里用了 ATcoder 的网络流）
const I N=1e5+10,M=1e7+10;
I n,m,id;
I s,t;
const I dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
I r,c,cntb,cntw,s0,t0;
I g(I x,I y){
return (x-1)*c+y;}
I a[301][301];
#define cconn G.add_edge
int main(){
in(r,c);
for(I i=1;i<=r;++i){
for(I j=1;j<=c;++j){
while(!isgraph(CH))CH=getchar();
a[i][j]=CH;CH=getchar();}}
s0=r*c+1;t0=r*c+2;s=r*c+3;t=n=r*c+4;
atcoder::mf_graph<I>G(n+1);
for(I i=1;i<=r;++i)
for(I j=1;j<=c;++j){
if((i+j)&1)continue;
if(a[i][j]=='1')continue;
for(I k=0,x,y;k<=3;++k){
x=i+dx[k];
y=j+dy[k];
if(x<1||x>r||y<1||y>c)continue;
if(a[x][y]=='1')continue;
cconn(g(i,j),g(x,y),1);
}
}
for(I i=1;i<=r;++i)for(I j=1;j<=c;++j){
if(a[i][j]=='2'){
if((i+j)&1)cconn(g(i,j),t,1),++cntb;
else cconn(s,g(i,j),1),++cntw;
}else if(a[i][j]=='?'){
if((i+j)&1)cconn(g(i,j),t0,1);
else cconn(s0,g(i,j),1);
}}
cconn(s,t0,cntb);
//调一下 bug
cconn(s0,t,cntw);
cconn(t0,s0,inf);
I res=G.flow(s,t);
if(res!=cntb+cntw)return puts("No"),0;
puts("Yes");
return 0;
}
做这道题的时候还是很艰辛的，先是改了两个 bug ，然后发现 TLE 了，于是改成了题解的构造，发现 WA 了，于是改回了原来的构造，苦思冥想，估计是我自己 dinic 常数的问题，于是改成了 ATcoder Library 的网络流，最终 AC 了。
人傻常数大实锤了。
8. 【NTT 板子】[ABC291G] OR Sum *2176
题意
有两个长度为 \(N\) 的序列 \(A,B\)，可以给 \(A\) 序列向左循环移动若干位，求 \(\sum (A_i|B_i)\) 的最大值。\(N\le 5\times 10^5\) 而 \(0\le A_i,B_i\le 31\)。
破题点
转化转化转化，转化成卷积的形式，然后直接 NTT 卷积，差不多得了。
题解
发现 or 操作有点点困难，那么我们就把两个序列取反，然后求 and 的最小值。
尝试形式化枚举每个移动数量的过程，比如枚举一个移位 \(j\)，再枚举一个 \(i\) 计算答案。
这种位数特别少的题，就先枚举二进制位 \(k\)，对于每一位分别处理。设 \(a,b\) 分别为序列 \(A,B\) 的第 \(k\) 位取反。
然后就是两个 0/1 序列合并操作，我们需要求出一个答案数组 \(c\)，\(c_j=\sum a_i\times b_{(i+j)\% n}\)。
我们可以把 \(b\) 复制一遍，去掉取模 \(n\)，问题就变成了求 \(c_j=\sum a_i\times b_{i+j}\)。
这个形式还不是我们熟悉的形式，我们应该熟悉的形式是 \(c_{i+j}=\sum a_i\times b_j\)。
怎么办呢？拿 \(k\) 替换 \((i+j)\)，问题就变成了 \(c_{k-i}=\sum a_i\times b_k\)。
左边式子 \(i\) 符号负的不好看，问题就变成了 \(c_{k+i}=\sum a_{-i}\times b_k\)。
右边下标为负数的很不好看，因为我们需要存储 \(a\) 数组，所以把 \(a\) 数组反转得到 \(a'\) 了，就是原来的存储 \(a_{-i}\) 的数组右移 \(n-1\) 位。
令 \(p=n-1-i\)，原式= \(c_{k+p}=\sum a'_{p}\times b_k\)。由上可知，多项式实际的值只有 \([n-1,2n-2]\) 的这 \(n\) 位才有效。
发现就是多项式的形式，直接卷积即可。
时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
typedef int I;
I main(){I n;
scanf("%d",&n);
vector<I>a(n),b(n),c(n),d(n<<1),e,f(n);
for(I i=0;i<n;++i)scanf("%d",&a[i]);
for(I i=0;i<n;++i)scanf("%d",&b[i]);
for(I k=0;k<5;++k){
for(I i=0;i<n;++i)d[i]=(~b[i]>>k)&1,d[i+n]=d[i],c[n-1-i]=(~a[i]>>k)&1;
e=atcoder::convolution(c,d);
for(I i=0;i<n;++i)f[i]+=(n-e[i+n-1])<<k;}
printf("%d\n",*max_element(f.begin(),f.end()));
return 0;
}
9. 【暴力乱搞】[ABC321E] Complete Binary Tree *1627
题意：求大小为 \(N\) 的完全二叉树中距离 \(X\) 点为 \(K\) 的点个数，多次询问。\(N,X,K\le 10^{18}\)。
破题点
堆式存储层序连续。然后暴力递归算即可。
题解
一步步来，也是换根思想的体现。
计算距离 \(x\) 节点为 \(K\) 的节点个数，可以利用完全二叉树的性质。
最左边的往左走，最右边的往右走，如果最左边的走出边界，答案就是 \(0\)；
最右边的走出边界就和 \(n\) 取个 \(\min\)。最后输出 \(r-l+1\) 就完事了。
考虑往上走，也是换根的体现。
若走到了父亲 \(fa\) 节点，总共有 \(f(fa,k-1)\) 种方案，那么减去 \(f(x,k-2)\) 的方案。
然后就弄完了。
10. 【树中层层构造】[ARC161C] Dyed by Majority (Odd Tree) *1746
很好玩。
首先叶子节点的所有父亲的初始颜色一定是和叶子的目标颜色相等的。若不相等请自行扣 -1。
破题点
类似的，我们把所有叶子的初始颜色设成其父亲节点的初始颜色。
于是我们确定了最后两层的颜色，其中所有叶子节点都可以丢弃了。
观察发现其他层也有约束关系，我们可以层层抽丝剥茧把树构建起来。
题解
想想对于其他层有没有类似的做法。
先把颜色设为三种状态，\(-1\) 表示不确定，还有 \(0\) 和 \(1\)。
比如 \(p\) 节点的初始颜色先别管它，管管它子节点的颜色，先把确定的算上，不确定的强制赋上。
然后如果子节点中目标颜色不够，那么就把它的父亲节点设为目标颜色；够了就填不确定。
如果还不够，那么就自行扣 \(-1\)。
另外还有算法没搞清楚会很难受，会 WA 很多发。
#include<bits/stdc++.h>
#define fo(i,a,b) for(auto i(a),_ei(b);i<=_ei;++i)
#define gch(w) for(;w(CH);CH=getchar())
using I=int;using V=void;using LL=long long;I FL,CH;LL in(){LL a(0);FL=1;gch(!isdigit)FL=(CH=='-')?-1:1;gch(isdigit)a=a*10+CH-'0';return a*FL; }using namespace std;
const I N=2e5+10;
vector<I>e[N];
I n;
bool ansis;
I b[N],op[N];
V dfs(I x,I fa=0){I cnt[2]={},opX=op[x];
for(I y:e[x])if(y^fa){
dfs(y,x);if(~b[y])++cnt[b[y]];}
for(I y:e[x])if(y^fa){
if(b[y]==-1)b[y]=opX,++cnt[opX];}
if(cnt[opX]<cnt[!opX])ansis=0;
if(cnt[opX]==cnt[!opX]&&fa){I&fx=b[fa];
if(fx!=-1&&fx!=opX)ansis=0;
fx=opX;}
}I main(){I T=in();
while(T--){
n=in();fo(i,1,n)e[i].clear(),e[i].shrink_to_fit(),b[i]=-1;
fo(i,2,n){I x=in(),y=in();
e[x].push_back(y);e[y].push_back(x);}
fo(i,1,n){gch(!isalpha);
op[i]=(CH=='B')?1:0;
CH=getchar();}
ansis=1;dfs(1);
if(!ansis)puts("-1");
else{fo(i,1,n)putchar(b[i]?'B':'W');
puts("");}
}
return 0;
}
11. 【优美的图构造】[ARC161D] Everywhere is Sparser than Whole (Construction) *1379
有趣结论题。
首先，显然 \(nd>\binom{n}{2}\) 时候无解。
然后，证明 \(nd\le \binom{n}{2}\) 时候一定有一种构造方案有解。
破题点
若少了一个点的时候，要想要剩下的边最多，就得删去度数最小的那个点，设其度数为 \(mind\)。
则若条件不成立需要满足 \(\dfrac{nd-mind}{n-1}\ge d\)，移项，解得 \(mind\le d\)。
题解
所以，度数最小的那个点其度数必须 \(>d\)。
如何求解呢？很简单。观察因为题目给了我们 \(nd\) 的条件，所以考虑用上；
每个点连出去 \(d\) 条边。同时它至少连入一条边。
容易想到一个类似“花篮”的形状：往每个点后 \(d\) 个点都加一条边。
这样每个点的度数就为 \(2d\) 了，十分充足。
咦？我们似乎只证明了最简单的情况，只删除一个点。
只要最简单的情况不成立，其他删掉两个点或者多个点的情况一定不成立。
所以，结束了。
12. 【暴力DP？正解！】[ARC160C] Power Up *1861
一步一步来。因为这种两两选择多少合并的题目不好组合计数优化，也不好乘法原理优化，采用 DP 是一个朴素的方式。
之前我们不是做过 262144 P 那题吗，只不过那题有顺序之分而且还是最优化的，这题就是没有顺序之分采用两两合并。
破题点
想到暴力 DP：设 \(f[i][j]\) 为当前到了 \(i\) 位置有 \(j\) 个数的方案数，然后暴力转移，设我挑出 \(2k(0\le 2k\le j)\) 个数合并，那么就是 \(f[i][j]\to f[i+1][a[i]+k]\)。
这里是破题点，我想到了，可惜没有仔细想，还是看了题解发现它是对的。
细节
空间复杂度可以证明是 \(O(n)\) 级别的，用个 vector 构建，因为这是两两合并，每次都能减少一半。
时间复杂度再考虑优化一下，对于一个 \(k\) 可以统计所有的 \(j\) 的答案。
于是时空复杂度都是 \(O(n)\) 的了。
13. 【小学奥数思想】[ARC163C] Harmonic Mean *1711
一开始做这种调和计数的题目反而方向想错了，想要搞一个类似于平均值的解题思路结果没算出来，垃圾。
破题点
观察埃及分数的性质。
小学奥数学过，\(\dfrac{1}{n}=\dfrac{1}{n+1}+\dfrac{1}{n(n+1)}\)。
于是这道题就做完了。
细节
再细节一点，首先 \(n=2\) 是无解的，\(n=3\) 及其以上都可以有解（可以把最大的那个分数拆掉来满足要求）。
\(n=3\) 的解是 \(2,3,6\)，那么 \(n=4\) 的解可以把 \(3\) 拆开变成 \(4\) 和 \(12\)，那么 \(n=4\) 的解集就是 \(2,4,6,12\)。
尽可能拆比较小的数，反正 \(n\) 很小你随便乱搞都行。我写的是 \(O(tn^2\log n)\) 乱搞。
需要注意的是这个集合不可重，所以要判断一下能不能拆。
可以优化成 \(O(tn\log n)\) 的，就是把拆不了的那些数全部输出，并且从集合里面删掉。
14. 【不公平的博弈】[ARC162C] Mex Game on Tree *1655
观察 \(n\) 很小，考虑暴力枚举每个子树可不可能先手必胜。
这可不是什么博弈论大毒瘤题。
破题点
考虑如何阻碍 \(\operatorname{mex}=k\)。很明显这里有个空位，若能够操作，就把它填上。
于是 Bob 的策略就是只要能操作，就填上至少一个 \(k\)。
然后只要 Bob 不能操作就能先手获胜了。
另外这题应该可以 \(O(n\log^2 n)\) 做的。dsu 搞一搞就行。
（反手变成紫题）
15. 【递增序列的性质】[ARC153C] ± Increasing Sequence *1960
破题点
有这样一个思维套路：
两个约束条件很难满足，考虑只满足一个，之后再来慢慢满足。
这题能使大家掌握的：
在保证序列严格递增的条件下，做构造操作，通过前缀减或者后缀加实现是一种利器。
本题就是利用这两种操作，我们可以完美地构造出所需数列。
题解
首先序列严格递增这个条件相对而言，更加难维护，相比之下，求和等于 \(0\) 的情况就较为简单。
所以我们需要在构造过程之中保证序列严格递增。
先构造个 \([1,n]\) 的序列，然后答案不太可能满足要求，设之为 \(S\)。
我们手上有两种操作：一种前缀减，一种后缀加。
若 \(S>0\)，则需要把 \(S\) 降到较低的水平，这时候我们考虑 \(a_i\) 的前缀和为正数的情况，或者 \(a_i\) 的后缀和为负数的情况。
此时若有 \(j\) 使得 \(a_i\) 的前缀和为 \(1\)，那么直接对 \([1,j]\) 进行 \(S\) 次前缀减。
若有 \(j\) 使得 \(a_i\) 的后缀和为 \(-1\)，那么直接对 \([j,n]\) 进行 \(S\) 次后缀加。
若两者都没有，那么直接输出 No。
\(S<0\) 的情况也类似。只不过执行的是 \(-S\) 次前缀减（因为要保证操作次数非负）。
细节
实在不懂细节就看代码吧。代码很清爽。
代码实现上，采用前缀减/后缀加函数，简化代码实现。
另外，要开 LL 的就开 LL。
#include<bits/stdc++.h>
#define fo(i,a,b) for(auto i(a),_ei(b);i<=_ei;++i)
#define gch(w) for(;w(CH);CH=getchar())
using I=int;using V=void;using LL=long long;I FL,CH;LL in(){LL a(0);FL=1;gch(!isdigit)FL=(CH=='-')?-1:1;gch(isdigit)a=a*10+CH-'0';return a*FL; }using namespace std;
const I N=2e5+10;
I n,a[N],pv[N],sf[N],b[N];
LL s;
V ad(I st,LL x,I op){//前缀减或者后缀加，注意 x 不为负。
puts("Yes");
if(op)fo(i,1,n){
if(i>=st)printf("%lld ",i+x);//后缀加
else printf("%d ",i);}
else{
fo(i,1,n){
if(i<=st)printf("%lld ",i-x);//前缀减
else printf("%d ",i);}
}exit(0);}
I main(){n=in();
fo(i,1,n)a[i]=in(),s+=a[i]*i;
fo(i,1,n)pv[i]=pv[i-1]+a[i];
fo(i,1,n)sf[n-i+1]=sf[n-i+2]+a[n-i+1];
if(s==0)ad(1,0,0);
if(s>0){I fpv=0,fsf=0;//找符合条件的前缀和后缀
fo(i,1,n){if(pv[i]==1)fpv=i;
if(sf[i]==-1)fsf=i;}
if(!fpv&&!fsf)return puts("No"),0;
if(fpv)ad(fpv,s,0);
if(fsf)ad(fsf,s,1);}
if(s<0){I fpv=0,fsf=0;
fo(i,1,n){if(pv[i]==-1)fpv=i;
if(sf[i]==1)fsf=i;}
if(!fpv&&!fsf)return puts("No"),0;
if(fpv)ad(fpv,-s,0);
if(fsf)ad(fsf,-s,1);}
return 0;
}
16. 【化边为点建图计数】[ARC166C] LU / RD Marking *1813
考试花了一个小时，也没切。考场下看一眼题解，就切了。为啥我这么菜啊。
题意
\(H\times W\) 的矩阵，操作 \(1\) 是给一个小矩形的左、上两条边标记，操作 \(2\) 是给一个小矩形的右、下两条边标记，这两个操作需要待标记边未被标记才能进行。求最终所有可能出现的标记种类 \(\bmod\ 998244353\) 的值。
破题点
思考一下 LU 和 RD 边，它们关于空间对称。
一次是选择两条边，于是很自然地想到考虑把边转化成点，把操作 \(1\) 或者 \(2\) 转化成为连边。
观察相邻的边不能选。观察图形我们发现是 \((H+W-1)\) 条不相交的链，从右上角到左下角的不相交的链。
题解
相邻的边不能选，很明显就是斐波那契数列的结论（可以考虑 DP 证明，式子和斐波那契一样）；
则对于长度为 \(n\) 的链的答案就是 \(fib[n+1]\)（注意它可以不选）；
对于前 \(H\) 条和后 \(H\) 条链，长度无非就是 \(1,3,5,7...2H-1\)（假设 \(H\le W\)，因为空间对称性可以旋转）。利用斐波那契前缀积可以优化。
图形中还有 \(W-H\) 条长度为 \(2H\) 的链，也要利用快速幂算上。
于是就结束了。
代码实现
这里使用 ATCoder 的同余类，方便实现。
#include<bits/stdc++.h>
#include<atcoder/all>
using atcoder::modint998244353;
#define fo(i,a,b) for(auto i(a),_ei(b);i<=_ei;++i)
#define gch(w) for(;w(CH);CH=getchar())
using I=int;using V=void;using LL=long long;I FL,CH;LL in(){LL a(0);FL=1;gch(!isdigit)FL=(CH=='-')?-1:1;gch(isdigit)a=a*10+CH-'0';return a*FL; }using namespace std;
using MI=modint998244353;
const I N=2e6+10;
MI f[N],fpv[N];
MI ksm(MI x,I y){MI a(1);
for(;y;y>>=1,x*=x)if(y&1)a*=x;
return a;}
I main(){f[0]=1;f[1]=2;
fo(i,2,I(2e6))f[i]=f[i-1]+f[i-2];
fpv[1]=2;
for(I i=3;i<=I(2e6);++i,++i)
fpv[i]=fpv[i-2]*f[i];
I T=in();
while(T--){
I n=in(),m=in();
if(n>m)swap(n,m);
printf("%d\n",ksm(fpv[2*n-1],2)*ksm(f[2*n],m-n));}
return 0;
}
17. 【保守的字典序】[ARC165B] Sliding Window Sort 2 *1364
此处最水题目，但是我还是不太会做。
显然，经过操作之后，字典序不会比原序列大。
如果发现一段长度为 \(k\) 的递增序列，那么直接输出原序列，一定最优。
然后挖掘一下字典序的性质。
字典序的性质是啥，前面的位尽可能不要动，后面的位更有可能动。
破题点
感觉就是，比较保守，比较保守，比较保守，能不动的就不动。
题解
根据这个感觉我们可以确定第二条基本事实：首先，前 \(n-k\) 位不能改变。
可以确定，一个解是对于 \([n-k+1,n]\) 区间进行排序。
然而对于它排序，不一定最优。
根据前 \(n-k\) 位不能改变的原则，又能衍生两个策略：首先，维护一个终点为 \(n-k+1\) 的最长上升序列。
我们能选的左端点，就在这个序列里面。
然后，对于所选区间进行排序，我们要求整个序列的前 \(n-k\) 位不能动。
所以，对于 \([n+k,l+k-1]\) 这些位的最小值，要求大于 \(p[n-k]\)。否则的话，这个序列就变小了。
最后（说好两个，实际三个？），我们需要选择最小的左端点。
因为这个策略是保守的，不能涉及更多的点进去排序，所以最小的左端点所改变位置的可能会比较少。
所以，很简单就结束了。
这篇题解感觉就是看了几个做法自己思考思考糅合起来。
核心难点在于维护“保守”策略，我该怎么做，该从一个基本模型入手如何构造。
18. 【遇事不决就DP】[ARC081E] Don't Be a Subsequence *2081
破题点
遇事不决就 DP，顺便输出方案。
题解
这题比较板，相对而言没有那么喵。
对于原序列建立子序列自动机，然后设 \(f[i]\) 为以 \(i\) 为开头，最短的未出现在原序列的子序列有多长。
利用子序列自动机优化转移即可。输出方案比较显然。时间复杂度 \(O(n)\)。
19. 【人类智慧法】[ARC158B] Sum-Product Ratio
破题点
这类很难直接计算的题目就不要尝试拆式子了，选点最优化，人类智慧法才是最好的。
数学直觉：考虑要达到极限的答案取值，\(x\) 的绝对值要么很大，要么很小，于是考虑在 \(0\) 左右选一些数，最小和最大选一些数即可。
实测选 \(16\) 个数就行了。
[ARC165C] Social Distance on Graph
题意
给你一个无向带权图，你要给它黑白染色。定义这张图的“社交距离”为同色点两两之间的距离的最小值。
求最大化这张图的社交距离。
思路
观察只有黑白两种颜色，且无向带权图这个条件太大，不好搞。
是否能够简化“社交距离”这一条件？答案是肯定的。
- 定理1：最小的社交距离（设之为 \(md\)）一定不会超过两条边的长度。
证明很显然。若有三条边四个点的一条链，\(md\) 一定不超过两条边的长度。
再发现一个显然的性质，社交距离的下界即为最小的边的边长。显然嘛。
我就需要求一个上界。这时候，直觉告诉我应该构造一种比较稀疏的方案，使得它能满足条件。
最大化最小值？思考这个问题，转化为判定问题。
于是问题就转化成了判定性问题。
[ARC153D] Sum of Sum of Digits *2700
破题点
观察位之间的联系只和进位有关。若无进位，答案相当独立。
若是我们能把它们之间的联系破开，就有办法优化。
化难从简，需要把他们之间的联系转化掉，或者通过一些状态设计来破除掉。
考虑带进位的数位 DP（这个技巧在之前 ARC160C 见过）。
题解
状态设计上，首先一定有一维，是和当前位相关的。
其次一定有一维，是和进位相关的。
我不知道哪些数该进位哪些数不该进位，怎么办？
排序。排完序就知道哪些数该进位了。
那么设 \(f[i][j]\) 为当前搞定了前 \(i\) 位，需要进位的有 \(j\) 个。（其实状态很稀疏的）
那么 \(f[i][j]=f[i-1][k]\)
[ABC322G] - Two Kinds of Base *2876
一句话题意
记 \(f(S,a)\) 为 \(a\) 进制整数 \(S\) 的十进制值（实际上原题意中是个正整数序列 \(S\)，且满足 \(S_i<\min(a,b,10)\)）若 \(0\le a,b\le N\)，判断可行三元组 \((S,a,b)\) 满足 \(f(S,a)-f(S,b)=X\) 的个数。\(N\le 10^9,X\le 2\times 10^5\)。
破题点
\(X\) 很小，且这是进制，位数不会很大，暴力做+剪枝就完事。
题解
突破口在于这个 \(X\) 很小，且 \(1\le X\le 2\times 10^5\)，不需要判断 corner case。
而且因为 \(X\) 很小，所以大概是可以枚举进制做的。我们不妨尝试一下。
首先，\(X=f(S,a)-f(S,b)=\sum_{i=0}^{k}S_i(a^i-b^i)\)。
观察这个式子，我们发现一个基本性质！
性质1：\((a-b)\mid X\)。
证明：对于每一项而言（包括 \(i=0\) 也不例外），有 \((a-b)\mid (a^i-b^i)\)。
所以，\((a-b)\mid S_i(a^i-b^i)\)，即可推出 \((a-b)|x\)。
推论1：只需要枚举 \(X\) 的所有因子就可以判断 \(a\) 和 \(b\) 的差值。
这样无形之中就确定了时间复杂度里面有一个根号。
性质2：\(f(S,a)\) 满足进制的性质：
\(a^k>\sum_{j=0}^{k-1}(a-1)a^j\)（其中 \(a\ge 1\)）。
于是就有了推论2：\(f(S,a)-f(S,b)\) 满足进制的性质；
再理清楚一些，\((a^k-b^k)>\sum_{j=0}^{k-1}(a-1)a^j-(b-1)b^j\)。
我要在给定进制 \(bas\) 下用 \(S\) 序列表示一个数 \(X\)，很显然，\(S\) 和 \(X\) 是一一对应的。
于是就有了推论3：因为 \(f(S,a)-f(S,b)\) 满足进制的性质，所以，对于 \((a,b)\) 而言，若有解，则 \(S\) 的方案数不会太多。
推论2 有什么用呢？若是高位的一个值固定下来，那么它对低位值都是有着决定性作用的。
所以这种进制数反而是要从高位到低位一位位确定。
那么我们想想，\(X\) 很小，意味着什么？而且这是进制级别的操作。
这意味着 \(k\) 是 \(\log_2 X\) 级别的！
对于给定了 \(a,b\)，我们怎么判定构造方案呢？
利用推论2和推论3，我们给定高位，从高往低确定数字是啥，这个数字显然是唯一的。
把问题转化一下，现在有一个整数 \(X\)，有 \(k\) 种操作，每次可以给 \(X\) 消掉 \((a^{k-1}-b^{k-1})\)，这个操作可以用 \(\min(10,a,b)-1\) 次。
求把 \(X\) 消到 \(0\) 的方案数。
因为这是从高到低跑进制的东西，所以从高位到低位直接贪心，然后直接判断（最后的个位可以任意选）就行了。
抽丝剥茧，我们终于迷迷糊糊地想到了一个暴力。
枚举间隔 \(c\mid x\)，枚举 \(a\)，则 \(b=a-c\)。
时间复杂度是 \(O(N\sqrt X \log_2 X)\) 的，时间复杂度很大，怎么办呢？
换个枚举顺序。
（迷迷糊糊，不想做，换下一题）