2 月所有 vp 记录
EastPorridge
·
·
个人记录
忽然意识到二月只有 28 天，我一直以为它有 30 天。
不知道为什么很有罪恶感，明明那两天又不是我偷的，但我好像没时间了。
2016-2017 ACM-ICPC CHINA-Final
B - Hemi Palindrome
定义一个 01 串若其奇数位为回文或者其偶数位为回文 为好串，求长度为 n 字典序第 k 小的好串，没有则输出 NOT FOUND!。
从高位往低位处理，容斥奇回文串 + 偶回文串 - 奇偶回文串，写个形如数位 dp 的东西就可以了，注意的细节有点多。
C - Mr. Panda and Strips
一个长度为 n 的序列，取其中的两个不相交子串拼接起来，或只选择一段，使得最后得到序列中的每一个数字都不重复，问这个序列最长是多少。
第二个方案显然可以拆成第一个方案，我可以闲的蛋疼，把一段不重复的序列拆开，再拼起来，所以只考虑第一种情况。
一个区间 dp，f_{l,r} 表示 [l,r] 这个区间，最长的元素不重复子串的长度是多少，这个可以 O(n^2) 的预处理合法子串，再 O(n^2) 的 dp，式子就是
f_{i,j}=\max(f_{i,j},f_{i+1,j},f_{i,j-1})
虽然是 $O(n^3)$ 的，但它合法方案很少，所以跑的很快。
### D - Ice Cream Tower
给 $n$ 个块蛋糕，叠 $k$ 层，要求大的蛋糕在下面，下面的大小要是上面的 $2$ 倍及以上，问最多可以做多少个这样的合体蛋糕。
我去，廊桥分配。
二分，我们能做 $\text{mid}$ 个合法蛋糕，从小到大排序，钦定前 $\text{mid}$ 个就是这个蛋糕的顶，贪心的往后取就可以了，不能一个蛋糕一个蛋糕的做，拿完第一个顶之后的底无法分配，但取前 $\text{mid}$ 作为顶一定是优的。
### G - Pandaria
给一个有 $n$ 的点 $m$ 条边的无向图，每条边有对应的边权，每个点有一个颜色。
$q$ 次询问，问每次从一个点出发，经过边权不超过 $w$ 的边，所能到达的点中，颜色出现次数做多且颜色编号最小的是什么颜色。
边权不超过，kruskal 重构树建出来，往上**倍增**找点权不超过 $w$ 的点，剩下的是个区间众数，写个线段树合并，没必要真的建图，建 kruskal 重构树的时候顺便线段树合并就可以了，找众数的最小点，可以直接线段树上二分，或者额外开个 tag，pushup 的时候讨论一下。
我觉得这题写 dsu on tree 怪怪的，建出来的东西是个满二叉树，自己把自己的复杂度卡到上界，感觉不如线段树合并。
```cpp
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
inline int read()
{
int x=0; char c=getchar(); bool f=0;
for(;c<'0' || c>'9';c=getchar()) f|=(c=='-');
for(;c>='0' && c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x=f ? -x : x;
}
int max(int a,int b) {return a > b ? a : b;}
const int N=2e5+10,M=20*N;
struct node
{
int u,v,w;
bool operator < (const node &o) const {
return w < o.w;
}
} ; std::vector<node> e;
int n,m,cnt,tot,a[N],ls[M],rs[M],mx[M],val[M],ans[N],rt[N],fa[20][N],w[N],f[N],lt,q;
int find(int x) {if(f[x] != x) f[x]=find(f[x]); return f[x];}
void pushup(int u)
{
mx[u]=max(mx[ls[u]],mx[rs[u]]);
(mx[u] == mx[ls[u]]) ? val[u]=val[ls[u]] : val[u]=val[rs[u]];
}
void modify(int &u,int l,int r,int x)
{
if(! u) u=++cnt,ls[u]=rs[u]=0; if(l == r) return mx[u]=1,val[u]=l,void();
int mid = (l + r) >> 1;
if(x <= mid) modify(ls[u],l,mid,x);
else modify(rs[u],mid+1,r,x);
pushup(u);
}
int merge(int x,int y,int l,int r)
{
if(! x || ! y) return x|y;
if(l == r) mx[x]+=mx[y];
else
{
int mid = (l + r) >> 1;
ls[x]=merge(ls[x],ls[y],l,mid);
rs[x]=merge(rs[x],rs[y],mid+1,r);
pushup(x);
}
return x;
}
int main()
{
int T; T=read();
for(int cas=1;cas<=T;cas++)
{
printf("Case #%d:\n",cas);
e.clear(); e.shrink_to_fit();
lt=cnt=0; memset(fa,0,sizeof fa); memset(w,0,sizeof w);
n=read(); m=read(); tot=n; memset(rt,0,sizeof (int)*(2*n+5));
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=2*n;i++) f[i]=i;
for(int i=1,u,v,c;i<=m;i++)
{u=read(); v=read(); c=read(); e.emplace_back(node{u,v,c});}
std::sort(e.begin(),e.end());
for(int i=1;i<=n;i++) modify(rt[i],1,n,a[i]),ans[i]=val[rt[i]];
for(auto it : e)
{
int x=find(it.u),y=find(it.v); if(x == y) continue ;
w[++tot]=it.w; f[x]=f[y]=fa[0][x]=fa[0][y]=tot;
rt[tot]=merge(rt[x],rt[y],1,n); ans[tot]=val[rt[tot]];
}
for(int j=1;j<=19;j++) for(int i=1;i<=tot;i++) fa[j][i]=fa[j-1][fa[j-1][i]];
q=read();
while(q -- )
{
int u=read(),c=read(); u^=lt; c^=lt;
for(int j=19;j>=0;j--) if(fa[j][u] && w[fa[j][u]] <= c) u=fa[j][u];
printf("%d\n",ans[u]); lt=ans[u];
}
}
return 0;
}
```
### J - Mr.Panda and TubeMaster
给一张 $n\times m$ 的方格，每个方格放可以放 $4$ 种类型的直角管道，并给出几个重要点，保证每个重要点都存在管道，且管道围成一个环。现给出每个管道连接两个方格能赚的钱，输出最多赚多少钱，若不存在方案输出 `impossible`。
一眼费用流的感觉。
我们可以把每个格子拆成两个点，一个表示横向的，一个表示纵向的，相邻的格子横向和纵向连边，我们把横向点当成入点，纵向点当成出点，然后相邻的入点连向出点，入点和出点之间连边表示的是如果流这条边，那么这个格子不放，那么有限制的格子就不连这条边，跑费用流即可。
------------
## [AtCoder Regular Contest 155](https://atcoder.jp/contests/arc155)
最后 $30$ 秒极限斩杀 E，笑死我了。
### A - ST and TS Palindrome
通过龙哥的找规律，最后形成的回文串，应该是一堆一段一段的相同子串拼起来的，再分 $7$ 种情况讨论一下，我还没补呢，哭了。
### B - Abs Abs Function
$$|| x-a|-b|=\min (|x-(a-b)|,|x-(a+b)|)$$
set 维护一下 $a_{i} \pm b_{i}$，lower_bound 就可以了。
### E - Split and Square
感觉就挺线性基的，如果 $S$ 中包含 $0$，则在任意情况下，$S$ 都是 $f(S)$ 的子集，一次只能通过分离奇偶元素的方式消去一个基底，最多也只能消去一个，此时 $f(S)$ 的大小就是 $S$ 的线性基大小。
如果不包含 $0$ 呢？同时异或两遍不就有 $0$ 了吗，直接按照有 $0$ 的做就可以了。
------------
## [AtCoder Beginner Contest 233](https://atcoder.jp/contests/abc233)
### F - Swap and Sort
我们可以转化成图论问题，将给的 $u,v$ 交换变成建边，如果 $i$ 和 $a_i$ 不在一个连通分量，我们直接对不起，做不到。
否则，我们在它规定的次数内一定能找到符合条件的序列，无论操作多少次。
找一颗生成树出来，dfs 处理一下就可以了。
### G - Strongest Takahashi
龙哥来了，全秒了。
设 $f_{x_1,y_1,x_2,y_2}$ 表示这个矩阵抹去所有黑点的最少次数，直接枚举切割点，记忆化搜索即可。
### Ex - Manhattan Christmas Tree
看到题给我笑嘻了，曼哈顿距离转切比雪夫距离，变成取 $\max$ 之后就是个二维数点，直接主席树或者二维树状数组，over。
------------
## [2022 ICPC Gran Premio de Mexico 1ra Fecha](https://codeforces.com/gym/103708)
### A - Anya's gifts
给序列分成两堆，权值让堆内各自异或的值，使得加一起的权值最大。
如果二进制下，一个位置 $1$ 出现的次数是奇数，分成两堆，总有一堆是奇数，它的贡献是固定的，把这种分离出来；剩下的偶数，分成两堆，异或结果一定相同，线性基处理即可。
### B - Building 5G antennas
字典序最小，肯定是 $1$ 开始的，如果一个点，能从其他店 $j_1$ 步转移过来，它绝对不会从 $j_2(j_2 > j_1)$ 步转移过来，直接剪枝 dfs 即可。
### D - Different Pass a Ports
从一个点出发 $k$ 次能到达的方案数就是邻接矩阵的 $k$ 次方，矩阵快速幂即可。
龙哥 $O(nk)$ 碾过去了，我大受震撼。
### E - Erudite of words
有 $m$ 个字母，问你长度为 $n$ 的，恰好有 $k$ 个不同字母组成的单词有多少个。
龙哥秒了，我不会。
设 $f_i$ 表示有 $i$ 个字母有且必然出现时的方案数，答案就是 $f_k \times C_{m}^{k}$。
转移式子就是
$$f_i= i^n - \sum_{j=1}^{i-1} (f_j \times C_{i}^{j})$$
$i^n$ 表示 $i$ 个字母随意摆放，后面容斥掉 $1 \sim i-1$ 的方案，这种题永远是我的问题，哭了。
### J - Jeffrey's ambition
最大独立集，直接网络流即可。
------------
## [AtCoder Regular Contest 154](https://atcoder.jp/contests/arc154)
### A - Swap Digit
两数的和相等，那么两数相差越大，乘积越小。所以问题转化为最大化两数之差。
我不知道大家为什么都知道这个结论，后来想了一下，证明直接二次函数就可以了，这个东西是个凹的，那没事了。
### B - New Place
每次往前放，$a$ 序列肯定是 $1 \sim \text{tmp}$ 的操作区间，$\text{tmp+1} \sim n$ 是 $b$ 的**子序列**，这个性质很好用，直接二分就可以了。
### D - A + B > C ?
神仙题啊，$1+1 > x$ 在 $x \ne 1$ 的时候一定成立，通过这个性质，我们可以 $O(n)$ 的定位 $x=1$ 的位置，然后就变成了 $p_x +1 > p_k$，就是 $p_x \ge p_k$ 一堆偏序关系，直接询问的过程归并就可以了，太酷了。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,a[N],p[N],nw=1; char s[10];
bool cmp(int x,int y)
{
cout<<"? "<<x<<' '<<nw<<' '<<y<<endl;
cin>>s; return *s == 'N';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
for(int i=2;i<=n;i++)
{
cout<<"? "<<i<<' '<<i<<' '<<nw<<endl;
cin>>s; if(*s == 'N') nw=i;
}
for(int i=1;i<=n;i++) p[i]=i;
stable_sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++) a[p[i]]=i;
cout<<"! "; for(int i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl;
return 0;
}
```
------------
## [AtCoder Regular Contest 153](https://atcoder.jp/contests/arc153)
### B - Grid Rotations
原来在同一列的，操作完还在同一列；原来在同一行的，操作完还在同一行，根据这个性质，直接压掉一维。考虑对所有行号做一套所有的操作，得到新的行号。
然后就得到了一个 splay 的题，龙哥手撕了，数据结构大师。
### C - ± Increasing Sequence
我们可以先构造出来 $1 \sim n-1$ 的 $\text{sum} = 0$ 的情况，令 $p_n = -\text{sum}$ 即可。
此时，若不满足 $p_{n-1} < p_n$ 考虑在一处 $\sum a_i$ 恰好等于 $1$ 的位置，将前面的所有值减去 $\infty$，给 $p_n$ 加上 $\infty$，此时整个序列合法。
若没有合法方案则一定不合法。
### D - Sum of Sum of Digits
待补。
------------
## [AtCoder Beginner Contest 239](https://atcoder.jp/contests/abc239)
### E - Subtree K-th Max
$k \le 20$，写个双向队列，对于每个点只维护前 $20$ 大的数即可。
### F - Construct Highway
考虑贪心，由于有已经存在的边，所有 $n$ 个点变成了若干个联通块，而且存在的边的两个端点的度数应该减 $1$。
显然，每个联通块所需要的度是所有点的度数和，对于度数为 $1$ 的联通块，肯定是连度数大于等于 $2$ 的联通块才最好，所以我们可以根据度数是否为 $1$ 进行分组，分成度数为 $1$ 的组和度数大于等于 $2$ 的组。
对于一个度数大于等于 $2$ 的联通块，假设他的度数为 $d$，我们只需要拿 $d-1$ 个度数为 $1$的点去匹配，然下的那一个度数，就放到度数为 $1$ 的那组里面，用于别的度数大于等于 $2$ 的组的匹配，并查集实现。
### G - Builder Takahashi
拆点最小割方案。
第一次写求方案的题，在跑完网络流的残留网络上标记还能到达的点，看它与它自己拆出来的点是否能到达，不能就证明流量满了，没啥难的说。
### Ex - Dice Product 2
一堆东西凑在一起的。
设 $f_i$ 为到达 $i$ 的期望次数，
$$f_i=1+\frac{1}{n} \sum_{j=1}^{n} f_{\left\lceil\frac{i}{j}\right\rceil}$$
$$f_i=\frac{n}{n-1}+\frac{1}{n-1} \sum_{j=2}^{n} f_{\left\lceil\frac{i}{j}\right\rceil}$$
里面是个整除形式，通过整除分块告诉我们取值不超过 $2 \times \sqrt n$ 种，预处理即可。
时间复杂度 $O(\sqrt n)$。
------------
## [AtCoder Grand Contest 048](https://atcoder.jp/contests/agc048)
### B - Bracket Score
任意合法括号对，一定是一个奇位置和一个偶位置匹配出来的，证明的话就直接把相邻位置的依次消掉就可以了。
我们钦定所有位置都是小括号，先累计小括号贡献，再将这个位置换成大括号增加的权值放入 奇/偶 位置对应的堆里。
在 $ > 0$ 的时候取出这个位置的奇偶往出替换，增加权值就可以了。
### C - Penguin Skating
考虑两个企鹅的间隔，把间隔当成滑块，每次把一个滑块左右移动，如果两个滑块相碰则合并。
贪心考虑，构出在位置 $i$ 的块的移动的次数是 $\max(i+1,r)- \min(i,l)-1$。
### D - Pocky Game
哈哈，我不会。
考虑一种情况，如果我有一堆比剩下的堆的总和都大，我可以一次拿一个，一直这样操作，把对面耗死，对面后手进入现在我的这个堆，我可以一次拿完，不给他机会。
所以这个游戏就会变成要么拿一个，要么一次拿完，任何中间情况都会导致后手不优。
理解一下，就是如果对手堆大，我肯定需要快速的进入下一堆去追进度，否则我肯定一个一个拿去磨时间。
设个状态 $f_{i,j,k}$ 表示在区间 $[i,j]$ 中，当前堆剩 $k$ 个的状态，发现 $k$ 大于一定数以后都一样，直接写成 $f_{i,j}$ 表示先手行动，至少需要为多少才能使先手必胜，$g_{i,j}$ 表示后手。
$$
f_{l, r}=\left\{\begin{array}{ll}
1 & a_{r}<g_{l+1, r} \\
f_{l, r-1}-g_{l+1, r}+a_{r}+1 & a_{r} \geq g_{l+1, r}
\end{array}\right.
$$
这题太好了。
------------
## [AtCoder Regular Contest 125](https://atcoder.jp/contests/arc125)
有人陪我打比赛哎，我好开心。
### B - Squares
拆成平方差公式，遍历 $x-k$ 时 $x+k$ 的取值在 $[1,\lfloor \frac{n}{i} \rfloor ]$，这个东西一看就是根号的，直接做。
### C - LIS to Original Sequence
得出在 $A_{i}$ 到 $A_{i+1}$ 之间肯定是递减的序列，且不属区间 $\left[A_{i}, A_{i+1}\right]$，这样保证了 LIS 不会增大。然后题目要构造字典序最小，我们就将能放在 $A_{i},A_{i+1}$ 之间的数放一个最小的放在中间，其余的以降序放在 $A_{n}$ 之后。
哈哈，我不会。
### D - Unique Subsequence
求“正着走子序列自动机得到的下标字典序最小的子序列位置”，与“反着走得到的下标字典序最大的位置”是一样的子序列。
### E - Snack
这铁定是个一堆边的形如二分图的网络流，直接跑应该不行，预处理提前增广不知道有没有救，写成模拟网络流，没试，不知道。
我们可以给菓子从小到大排个序，最大流转化成最小割问题，枚举每个前缀割掉的边，后半部分显然单调，二分找出这个前缀割边下的最大收益，取 $\min$。
------------
## [AtCoder Beginner Contest 249](https://atcoder.jp/contests/abc249)
### D - Index Trio
写成 $a_i = a_j \times a_k$ 的形式，后面这个东西显然很调和级数，直接乘就可以了。
### E - RLE
设 $f_{i,j}$ 表示用前 $i$ 个字符压出 $j$ 长度的字符串的方案。
$$f_{i,j}=\sum_{k=1}^{i} f_{k-1, j-\log_{10}^{i-k+1}-1} \times 25$$
鉴定为前缀和优化 dp。
### F - Ignore Operations
显然，如果出现操作 $1$，则前面所有的操作全部白干，所以我们要消肯定先消操作 $1$，设当前消去的操作 $1$ 为 $x$，则我们还可以消去 $k-x$ 个操作 $2$，正的肯定留下，所以就是找出前 $k-x$ 小的负操作，权值线段树就可以了，还要整个后缀和。
### G - Xor Cards
被 RyexAwl 大贤者推轮椅推过来了，他真的很强。
把 $(a,b)$ 压成一个数字，就变成求整个数字前 $30$ 位小于 $k$，后 $30$ 位的最大异或。
$C[i]$ 表示当前线性基的第 $i$ 位，对于任何 $i$ 一定满足 $C[1] \oplus C[2] \oplus ... \oplus C[i]$ 只考虑高于 $\text{highbit}(C[i])$ 的位，其一定是 $\le k$ 的。考虑 $k$ 的限制，如果 $k$ 的第 $i$ 位为 $1$，我可以找个 $[1,i-1]$ 位与 $k$ 相同，第 $i$ 位为 $0$ 的数，后面的就可以随便选了，剩下的就是个线性基异或最大值。
------------
## [AtCoder Regular Contest 143](https://atcoder.jp/contests/arc143)
### B - Counting Grids
这个 B，好难。
$$
\sum_{x=1}^{n^{2}} n^{2} \times\left(\begin{array}{l}
x-1 \\
n-1
\end{array}\right) \times(n-1) ! \times\left(\begin{array}{c}
n-x \\
n-1
\end{array}\right) \times(n-1) ! \times\left(n^{2}-2 n+1\right) !
$$
我推出来应该长这样。
### C - Piles of Pebbles
石子可以变成模 $(x+y)$ 意义下的，然后根据 $x,y$ 的大小关系讨论就可以了。
### D - Bridges
把 $i$ 和 $i+n$ 考虑缩点，然后原图上的桥边最小就等于新图上的强连通分量数量最小，给每条边定向考虑即可。
我不知道我为什么要这样做，但就是要这样做。
------------
## [Codeforces Round #848 (Div. 2)](https://codeforces.com/contest/1778)
### D - Flexible String Revisit
那个分手时祝愿一样的题，$f_i$ 表示减少一个牌到达 $f_{i-1}$ 的期望次数
有 $\frac{i}{n}$ 的翻对，有 $\frac{n-i}{n}$ 的概率翻错，翻错还要再翻回来到 $f_i$，再到 $f_{i-1}$，所以
$$f_i = (f_{i+1} + f_i + 1) \times \frac{n-i}{n} + \frac{i}{n}$$
$$f_i = \frac{(n-i) \times f_{i+1} + n} {i}$$
最后设两个字符串不同的有 $cnt$ 个，答案就是 $\sum_{i=1}^{cnt} f(i)$。
### E - The Tree Has Fallen!
可以求出以 $1$ 为根时的线性基，用形如换根 dp 的方式换就可以了，我调不出来，哈哈。
------------
## [Codeforces Round #838 (Div. 2)](https://codeforces.com/contest/1762)
### F - Good Pairs
写的我想紫砂。
最后的合法子序列一定是单调上升或下降，或者两个相同的数。
设 $f_i$ 表示 $i$ 为左端点的子区间个数，$j$ 为 $i$ 一次最远能达到的右端点
$$f_{i}=f_{j}+\operatorname{calc}\left(i,n,a_{i}+1,a_{j}\right)$$
其中 $\operatorname{calc}(l, r, x, y)$ 表示有多少个 $i$ 满足 $l \leq i \leq r$ 且 $x \leq a_{i} \leq y $。
鉴定为线段树上二分，正着做一遍再倒着做一遍即可。