前言：VP了一把，rk731，如果赛上有这发挥就好了。
果然，D是分水岭，一直都是。
Unit Array
题面：
给定一个长度为 \(n (1 \le n \le 100)\) 的序列 \(a\)，所有元素均为 \(1\) 或 \(-1\)。我们称 \(a\) 是一个好序列，当且仅当同时满足以下两个条件：
- \(a_1 + a_2 + ... + a_n \geq 0\)；
- \(a_1 \cdot a_2 \cdot...\cdot a_n = 1\)。
你可以对序列进行若干次修改，每次修改可以把序列中的 \(-1\) 改成 \(1\) 或从 \(1\) 改成 \(-1\)。
给定一个序列，问最少需要几次修改使它变成一个好的序列。
题解：显然，我们只需要将负数改为正数。设有 \(c_1\) 个 1，有 \(c_2\) 个0，则我们需要调整后 \(c'_1\ge c'2,c'2\bmod 2=0\)
满足第一个条件，需要代价 \(\max (0,\lceil\frac{c_1-c_2}{2}\rceil)\)，而第二个条件，在满足第一个条件后再判断是否合法，不合法就再减一个1.
Maximum Strength
题面：
每一种材料的力量由一个十进制整数表示。
对于一个武器，由两种材料构成。假如第一种材料的力量为 \(X = \overline{x_1x_2 \dots x_n}\)，第二种材料的力量为 \(Y = \overline{y_1y_2 \dots y_n}\)，那么这个武器的力量为 \(\sum_{i = 1}^n |x_i - y_i|\)，也就是 \(|x_1 - y_1| + |x_2 - y_2| + \dots + |x_n - y_n|\)。
如果两个数字长度不一样，则要将短的数字用前导零补成相同长度。
现在，你拥有无数个力量在 \([L, R]\) 中的材料。你想要选出两个材料做出一个力量最大的武器。请你求出你设计出的武器力量的最大值。
题解：
乍一看，毫无思路，但我们显然是尽量让每一位的差变小才对。
对于最高的已经确定的几位，我们直接跳过，然后找到第一个 \(l_i\neq r_i\) 的。
此时，注意到我们可以划分两个数的上下界，然后下一位令较大数为0，较小数为9，此后的所有位全部可以用0,9两个数交替了。
所以答案为：\(d+9(n-i)\)
Game with Reversing
题面：
小 L 和小 S 在玩游戏。他们有两个长度均为 \(n(1 \le n \le 10^5)\) 的字符串 \(S, T\)，小 L 和小 S 轮流操作，小 L 先手。
小 L 的回合，他可以选择 \(1 \to n\) 中的一个整数 \(i\)，再选择串 \(S\) 或 \(T\)，把其中的第 \(i\) 个字符改成任意一个字符 \(c\)。
小 S 的回合，她可以选择 \(S\) 或 \(T\)，并将它进行翻转。
如果两个串 \(S, T\) 经过若干次操作后相等，则游戏立即结束。小 L 希望总操作次数最小，小 S 希望总操作次数最大。两人都采取最优策略，问最终操作次数。
题解：千年难遇的水C题。
注意到，小L可以修改任意字符，他有两个选择：在不翻转的状态下相同，翻转后相同。
这里我们分别计算出 \(c_1=\sum_{i=1}^n[s_i\neq t_i],c_2=\sum_{i=1}^n[s_i\neq t_{n-i+1}]\)。
对于第一种情况，小 L 至少需要 \(c_1\) 次操作把字符变成相同的，然后若 \(c_1\bmod 2=1\)，则小S作的翻转没有意义，答案为 \(2c_1-1\)，否则需要小S再翻回来。故最终答案为 \(2c_1-(c_1\bmod 2)\)
Survey in Class
题面：
有 \(n\) 个学生同时对课堂内容进行了预习。有 \(m\) 个问题，第 \(i\) 个人预习的问题是一个区间，可以用 \([l_i,r_i]\) 表示。每当老师问出一个问题，如果一个人不会，它的分数就会 \(-1\)，否则 \(+1\)。注意，分数可能为负。
现在你要问一些不重复的问题，最大化学生分数的极差，并输出这个值。
有意思的问题，不过比较简单。
首先，我们将其放在数轴上，视作线段，则对于选了 \(c\) 个点，线段 \(i\) 里有 \(p_i\) 个点，则得分为 \(p_i-(c-p_i)=2p_i-c\)，而极差 \(d_{\max}=(2p_i-c)_{\max}-(2p_i-c)_{\min}=2(p_{\max}-p_{\min})\)
所以， \(d\) 与问了几道题完全没有任何关系。我们只需要求 \(\Delta p\) 的最大值即可。
问题化为：在数轴上选若干个点，使得点最多的线段减去点最少的线段的差最大。
显然，必定存在一种最优方案，点最少的线段里没有点。
证明：当两线段不交时，显然。
当两线段相交时，必定是相交部分的点，而这个点会被做差抵消掉，故无用。
换句话说，我们要求：
其中 \(f(i,j)\) 是两线段相交长度。
处理 \(f\) 复杂度太高，考虑优化。我们如果枚举线段 \(i\) 则只需要处理与它相交最少的线段。分类讨论：
- 不相交：这显然是最好
- \(i\) 左侧与 \(j\) 相交。这样的话，相交线段的右端点自然是越小越好，我们记录所有线段里右端点最小的数，记作 \(R\)
- \(i\) 右侧与 \(j\) 相交，类比上一个，相交线段的左端点自然是越大越好，我们记录所有线段里左端点最小的数，记作 \(L\)
- \(i\) 包含 \(j\)。这种情况可以直接被处理掉。
我们直接处理最大线段长 \(mx\) 和 最小线段长 \(mn\)，这种情况下答案绝不会大于 \(mx-mn\)，可以直接将其计入答案。因为如果最大线段和最小线段是前三种情况，答案会被更新掉
那么，做法显然：
int main(){
ios::sync_with_stdio(false);
read(t);
while(t--){
read(n);read(m);
for(int i=1;i<=n;i++)read(a[i].l),read(a[i].r);
int mx=0,mn=0x3f3f3f3f,L=-1,R=0x3f3f3f3f;
for(int i=1;i<=n;i++){
R=min(R,a[i].r),L=max(L,a[i].l);
mx=max(mx,a[i].r-a[i].l+1);
mn=min(mn,a[i].r-a[i].l+1);
}
int ans=mx-mn;
for(int i=1;i<=n;i++){
ans=max(ans,a[i].r-a[i].l+1-min(max(0,a[i].r-L+1),max(0,R-a[i].l+1)));
}
ans<<=1;
cout<<ans<<"\n";
}
}
MEX of LCM
题面：
给定一个长度为 \(n\) 的序列 \(a\)，一个正整数 \(x\) 被称为「可爱的」，当且仅当在序列 \(a\) 中，不存在一个子段所有元素的 最小公倍数 等于 \(x\)。求最小的「可爱数」。
题面一句话，思想两个字：暴力。
注意到，第 \(1\sim n+1\) 个质数至少有一个不会作为某个子段的 \(lcm\) 出现，理由是若 \(lcm\) 为一个质数，则说明该子段全部为这个数，而最小子段只有 \(n\) 个，而且注意到，当子段左端点固定时，右端点扩张，\(lcm\) 单调不减。所以答案上界为第 \(n+1\) 个质数，\(n\) 取最大值 \(3\times 10^5\)，则 \(3\times 10^5+1\) 个质数为 \(4256233\)，大于它的全部舍掉。
对于求解存在性的答案，可以通过估计答案上界的办法减少复杂度，mex问题是一个典型。
那么，我们只需要求出所有不大于 \(4256233\) 的 \(lcm\) 即可，我们考虑递推，由小段到大段求解。
这里我们记 \(f(l,r)=lcm(a_l,a_{l+1}…,a_r)\)，记 \(g_i=\lbrace f(i,i),f(i,i+1)…f(i,n)\rbrace\)，则 \(g_i=\lbrace a_i\rbrace\cup \lbrace lcm(a_i,x),x\in g_{i+1}\rbrace\)
我们暴力自后向前转移即可。时间复杂度为什么是对的？因为由 \(i\) 到 \(n\) 的路上，\(lcm\) 要么不变，要么至少乘2，而这最多乘 \(\log_2 4256233\) 次。
而注意到求 \(lcm\) 需要 \(\gcd\)，所以时间复杂度是 \(O(n\log ^2V)\)，足以通过本题。
但真的没有优化空间了吗？
我们依次合并 \(lcm(f(i+1,i+1),a_i),lcm(f(i+1,i+2),a_i)……\)，注意到 \(f(i,j)|f(i,j+1)\)，所以 \(\gcd(f(i+1,i+k),a_i)=\gcd(\gcd(f(i+1,i+k+1),a_i),f(i+1,i+k))\)。
由此，我们从 \(f(i+1,n)\) 到 \(f(i+1,i+1)\) 合并，均摊一次转移执行一次 \(\gcd\)，时间复杂度降为 \(O(n\log V)\)。
注意空间可能有点卡，这里可以滚掉。
int t,a[N],n,f[2][105],g[N<<1],d[2],tot,vis[N<<1];
const int lim=4300000;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
signed main(){
read(t);
while(t--){
read(n);tot=d[0]=d[1]=0;
for(int i=1;i<=n;i++)read(a[i]);
for(int i=n;i;i--){
int x=i&1,y=a[i];d[x]=0;
for(int j=1;j<=d[x^1];++j){
ll k=1ll*a[i]*f[x^1][j]/(y=gcd(y,f[x^1][j]));
if(k<=lim&&k!=f[x][d[x]]){
f[x][++d[x]]=k;g[++tot]=k;
}
}
if(f[x][d[x]]!=a[i]&&a[i]<=lim)f[x][++d[x]]=g[++tot]=a[i];
}
for(int i=1;i<=tot;i++)vis[g[i]]=1;
for(int i=1;i<=lim;i++)if(!vis[i]){
print(i);puts("");break;
}
for(int i=1;i<=tot;i++)vis[g[i]]=0;
}
}
Typewriter
题面：
最近，Polycarp收到了一台特殊的打字机作为礼物！不幸的是，这台打字机有一个相当奇怪的设计。
这台打字机由 \(n\) 个单元组成，从左到右编号为 \(1\) 到 \(n\) ，还有一个移动的小车。打字机的每个单元包含 \(n\) 个不同的整数，从 \(1\) 到 \(n\) ，每个单元 \(i\) 最初包含整数 \(p_i\) 。在所有操作之前，小车位于第一个单元上，它的缓冲区没有任何内容。当前小车所在的单元称为当前单元。
小车可以执行以下五种操作：
- 如果当前单元不为空，就将其中的整数放入小车的缓冲区（缓冲区最多只能容纳一个整数）。
- 如果小车的缓冲区不为空，就将其中的整数放入当前单元（如果当前单元为空）。
- 如果小车的缓冲区和当前单元都含有整数，就交换缓冲区中的整数和当前单元中的整数。
- 将小车从当前单元 \(i\) 移动到下一个单元 \(i+1\) （如果 \(i<n\) ），缓冲区中的整数保持不变。
- 将小车重置，即将其移动到第一个单元，缓冲区中的整数保持不变。
Polycarp对这个打字机非常感兴趣，所以他请你帮助他理解它，并回答他 \(q\) 个问题：
- 执行一个循环左移 \(k_j\) 的操作。
- 执行一个循环右移 \(k_j\) 的操作。
- 反转序列。
在每个查询之前和之后，Polycarp想要知道为了将数字分配到它们的单元（使数字 \(i\) 最终位于第 \(i\) 个单元），需要多少次小车重置的最小次数。
注意，Polycarp只想知道需要多少次小车重置来整理数字的位置，但实际上并不进行分配。（也即询问间互相影响）
帮助Polycarp找到每个查询的答案！