Codeforces & Atcoder神仙题做题记录

鉴于Codeforces和atcoder上有很多神题，即使发呆了一整节数学课也是肝不出来，所以就记录一下。

---

AGC033B LRUD Game

只要横坐标或者纵坐标超出范围就可以，所以我们只用看其中一维就可以了。

我们又知道，如果先手想要让它从左边出去，那么先手就会一直Left，后手就会一直Right。

所以枚举四种情况（L,R,U,D）就可以了。

---

AGC033C Removing Coins

首先我们考虑链的情况，如果选的是端点，那么有一个点没有硬币，如果选的不是端点，那么有两个点没有硬币。所以就是一个取石子问题了。两个点的情况要特殊考虑。

但是树的情况过于复杂，所以我们要选一条链来代替这整棵树，使得这条链被删完当且仅当整棵树被删完。

这条链就是这棵树的直径。

---

ABC126F XOR Matching

被ABC狠狠地虐了一发 。。。

设$a oplus b=k$且$a,b,k$互不相同，则构造$a,k,a,b,ldots,k,ldots,b$，其中$ldots$为除了$a,b,k$之外的所有数。

---

ARC080F Prime Flip

首先看到翻转一段的肯定要差分，变成了对$x_i$和$x_{i+p}$都异或1，其中$p$为3以上的质数。于是不知道为什么就想到了先配对然后每次去掉两个点。现在我们要把$x_u$和$x_v$都异或上1，肯定就是通过“一条链”从$u$到$v$。打打表就会发现：

• 若$|u-v|$为奇质数时，需要1步
• 若$|u-v|$为偶数时，需要2步（哥德巴赫猜想）
• 否则需要3步

那么就是进行配对，使得1最多，在1最多的情况下2最多。

1最多就是把奇数和偶数放在两边，差为质数的连一条边然后跑二分图。

2最多就是跑完之后把未配对的分别在一组内配对。配对完或者是剩下两个差不为奇质数的数，凑一个3.

---

ARC082E Convex Score

前方浪费好题现场。

注意到$2^{内部点个数}$是子集个数，所以我们对$(S,T)$计算贡献，其中$T$是$S$凸包的内部点的子集，所以$Scup T$的凸包是$S$。所以它的贡献为$Scup T$有凸包。

所以答案就是有凸包的子集个数。转换成没有凸包的子集个数就可以做了，时间复杂度$O(n^2log n)$

---

AGC019B

记$B[l,r]$表示$A$翻转$[l,r]$后的字符串。

我们知道，如果$s[l]=s[r]$，那么翻转$[l,r]$和$[l+1,r-1]$是一样的，无贡献。如果$s[l] eq s[r]$，且$B[l,r]= B[x,y]$，那么$B[l,r]$与$A$不相同的第一个位置就是$l$，最后一个不同的位置就是$r$，$B[x,y]$同理，所以$l=x,r=y$。

综上，答案为$1+s[x] eq s[y]$的点对个数，反面考虑就可以直接$O(n)$计算了。

---

CF623B

发现只要确定gcd是多少就可以简单计算了。

发现第一个数和第$n$个数至少有一个会留下来，枚举是$+1,-1$还是不变。那么gcd肯定是这些的质因子。

---

CF901B

自闭了。。。

根据整数的欧几里得算法，取Fibonacci数列里面的数能到达复杂度上界。

那对于多项式，$p_0=1,p_1=x,p_n=xp_{n-1}pm p_{n-2}$，那么$(p_n,p_{n-1})$就是答案。

那如何要求$p_n$的系数绝对值$le 1$呢，取$p_n=xp_{n-1}+p_{n-2}(mathrm{mod} 2)$.

感觉上是$pm$之下$mathrm{mod} 2$是不变的吧。。。但是不太会证。。。当时想到了但是不知道为什么是对的。。。

---

AGC039D

首先看一张图：

其中G为$Delta ABC$的内心，证明：G为$Delta DEF$的垂心。

证明：【略】（导角即可）

还有一个东西叫欧拉线，$overrightarrow{OH}=overrightarrow{OA}+overrightarrow{OB}+overrightarrow{OC}$。

枚举$D,E,F$计算贡献，由于是循环对称的，所以只用枚举$O(n^2)$个$D$。

---

AGC005C

虽然可能能做出来但是还是跑去看题解了。

我们知道，设$a,b$是树直径的端点，则$k=max(a_i)$是直径长度，$max_j(dis(i,j))=max(dis(i,a),dis(i,b))$。

首先看直径上面的值，如果$k$为偶数，那么直径上面为$k,k-1,ldots,k/2,k/2+1,ldots,k$，如果$k$为奇数，则为$k,k-1,ldots,(k+1)/2,(k+1)/2,ldots,k-1,k$。首先把这些值

去除掉，如果不能直接输出Impossible.

然后看直径外面的，如果$k$为偶数，那么直径外面至少为$k/2+1$，如果$k$为奇数，那么直径外面至少为$(k+1)/2+1$，检查一下是不是就可以了。

---

AGC005D

（才发现这场的F题在n年前做掉了）

（看不懂题解，溜了）

---

AGC005E

首先，答案为-1当且仅当Red能够到达两个点$u$或$v$使得$(u,v)in E_R$且$dis_B(u,v)geq 3$。

那如何判断能否到达一个点$v$呢，就是$dis_R(X,v)<dis_B(Y,v)$。

用一个dfs和一个bfs就可以找出所有Red能到达的点，如果有上面条件的点则输出-1，否则输出$dis_B$的最大值。

---

AGC006D

首先二分答案，这样序列里面就只剩下$0/1$了。

打打表，发现答案就是离中心最近的相邻两个相等的数的值。

如果是0/1相间的，特判一下。

---

AGC006C

我们发现一次操作实际上就是$x_i=frac{2x_{i+1}+2x_{i-1}-2x_i}{2}=x_{i+1}+x_{i-1}-x_i$。

这个式子之前见过一遍了，改为差分之后就相当于交换$i$和$i+1$。一共做$k$次就是先求出这个置换，然后求这个置换的$k$次方。置换的幂可以通过分解成环，然后在

每个环上做。

---

AGC006F

之前VK Cup好像lqy讲的一道题跟这个很像。

由于是$(u,v),(v,w) ightarrow (w,u)$，所以考虑对每一个弱联通分量建一个三分图（逃），如果能建出来且三个分量中都有点，则为$cnt_0 imes cnt_1+cnt_1 imes cnt_2+cnt_2 imes cnt_0$，如果能建出来而且只有两个分量有点，则什么都加不上去。如果不能建出来那么它就是一个完全图（包括自环）。

直接dfs就可以做。

---

CF1240B

发现自己想假了之后就直接停止了思考。。。

注意到离散化之后，不动的地方肯定是一个连续段而且位置单调不降。。。然后就没了。。。

---

CF1240D

要把自己做过的题记住。

AGC007F

超级神仙题。

我们画画图就会发现，$S$中相同连续的字符到$T$中相同连续的字符构成了一段折线。借一张图：

（我们定义拐点是折线中上面和右面和自己是同一个字符的格子）

那再看看，为何我们需要多次复制呢？是因为折线不能相交，左边的拐点会被右边的拐点压下去。从右到左考虑，如果这个折线的某个拐点的影响不消失，那么下一个折线必定有一个拐点是当前拐点向左向下一位。

那我们用队列维护当前折线的拐点，队列里面第$i+1$个元素（从队尾到对首）减去$i$是当前折线的从上往下第$i+1$个拐点的位置（☞第几个字符），那么在队尾加上一个数就是让前面的折线往前一位，并在后面加上一个。注意如果``q[front] - (rear - front) >= i``就说明这个拐点没用了（拐点不可能比它要后），那么答案就是队列长度最大值$+1$，因为满足当前点需要的复制次数（即行数）是拐点个数$+1$.

#include<bits/stdc++.h>
#define Rint register int 
using namespace std;
const int N = 1000003;
int n, ans, q[N], front, rear;
char s[N], t[N];
int main(){
    scanf("%d%s%s", &n, s + 1, t + 1);
    if(!strcmp(s + 1, t + 1)){puts("0"); return 0;}
    int cur = n;
    for(Rint i = n;i;i --){
        if(t[i] == t[i - 1]) continue;
        while(cur && (cur > i || s[cur] != t[i])) -- cur;
        if(!cur){puts("-1"); return 0;}
        while(front < rear && q[front] - (rear - front) >= i) ++ front;
        if(cur != i) q[rear ++] = cur;
        ans = max(ans, rear - front + 1);
    }
    printf("%d", ans);
}

---

AGC030F

对于一个排列，里面一些值已经给出，一些没有给出，设。求不同的的个数。

首先我们发现它求的是，所以要从大到小填数，方便在配对好了的计算贡献。

我们扔掉所有和并假设组的顺序无关，最后乘上的个数的阶乘就可以了。

设表示填了的数之后，没匹配的未知数有个，没匹配的已知数有个。

若第个数是已知数，那么有两种选择：匹配未知数或者不匹配。

若第个数是未知数，那么有三种选择：匹配已知数（这个有系数，因为这种选择的结果各不相同），匹配未知数，或者不匹配。

时间复杂度为$O(n^3)$

#include<bits/stdc++.h>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = 603, mod = 1e9 + 7;
inline void add(int &a, int b){a += b; if(a >= mod) a -= mod;}
int n, cur, tmp, t, a[N], c[N], f[2][303][303];
int cnt[N];
int main(){
    scanf("%d", &n); n <<= 1;
    for(Rint i = 1;i <= n;i ++)
        scanf("%d", a + i);
    for(Rint i = 1;i <= n;i += 2){
        if(a[i] != -1 && a[i + 1] != -1) cnt[a[i]] = cnt[a[i + 1]] = 2;
        else if(a[i] == -1 && a[i + 1] == -1) ++ tmp;
        else if(a[i] != -1) cnt[a[i]] = 1;
        else cnt[a[i + 1]] = 1;
    }
    for(Rint i = 1;i <= n;i ++)
        if(cnt[i] == 1) c[++ t] = 1;
        else if(cnt[i] == 0) c[++ t] = 0;
    f[0][0][0] = 1;
    for(Rint i = t;i;i --){
        cur ^= 1;
        memset(f[cur], 0, sizeof f[cur]);
        for(Rint j = 0;j <= (n >> 1) && j <= t;j ++)
            for(Rint k = 0;k <= (n >> 1) && k <= t;k ++){
                if(c[i] == 1){
                    add(f[cur][j][k + 1], f[cur ^ 1][j][k]);
                    if(j) add(f[cur][j - 1][k], f[cur ^ 1][j][k]);
                } else if(c[i] == 0){
                    add(f[cur][j + 1][k], f[cur ^ 1][j][k]);
                    if(j) add(f[cur][j - 1][k], f[cur ^ 1][j][k]);
                    if(k) add(f[cur][j][k - 1], (LL) f[cur ^ 1][j][k] * k % mod);
                }
            }
    }
    int ans = f[cur][0][0];
    for(Rint i = 1;i <= tmp;i ++)
        ans = (LL) ans * i % mod;
    printf("%d
", ans);
}

---

AGC030E

首先我们知道，如果修改$101$中间的$0$或者是$010$中间的$1$肯定是不行的，而且$000$和$111$根本不会出现，所以每次修改的格子左右两边都是不同的，相当于就是，将$1$和$0$的边界划线，每次可以将一条边界移动一格，而且要求边界的距离不超过$2$。

注意到匹配$S$和$T$的边界线的方法有$O(n)$种，每次用$O(n)$计算贡献，时间复杂度是$O(n^2)$的。

注意如果$S_1 eq T_1$，那么$S$和$T$中$0$处的边界线不能匹配，需要在$S$的前面加一条分界线。

实现上面，就是将$S$和$T$的分界线在前后各加$5000$条，然后枚举移位的条数$i$，注意$2|i$（为了保证$0$和$1​$分别对应），那么直接计算就可以了。

#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int N = 11111;
int n, n1, n2, ans, _a[N], _b[N], *a = _a + 5000, *b = _b + 5000;
char s1[N], s2[N];
int main(){
    scanf("%d%s%s", &n, s1 + 1, s2 + 1);
    if(s1[1] != s2[1]) a[++ n1] = 0;
    for(Rint i = 1;i < n;i ++){
        if(s1[i] != s1[i + 1]) a[++ n1] = i;
        if(s2[i] != s2[i + 1]) b[++ n2] = i;
    }
    for(Rint i = n1 + 1;i <= 5000;i ++) a[i] = n;
    for(Rint i = n2 + 1;i <= 5000;i ++) b[i] = n;
    ans = 1e9;
    for(Rint i = -n1;i <= n2;i ++) if(!(i & 1)){
        int tmp = 0;
        for(Rint j = -5000;j <= 5000;j ++)
            if(i + j >= -5000 && i + j <= 5000) tmp += abs(a[i + j] - b[j]);
            else {
                if(i + j < -5000) tmp += b[j];
                else tmp += n - b[j];
            }
        ans = min(ans, tmp);
    }
    printf("%d", ans);
}

---

AGC030C

你发现小数据的时候，这样填一定是对的。（$n=k=4$）

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

但是你发现$k=2n$，所以继续找规律，发现还可以这样填（$n=4,k=6$）

1 2 3 4
6 3 4 5
3 4 1 2
4 5 6 3

（就是一些斜行交叉着填两种颜色，一些只填一种颜色）

#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int N = 503;
int n, k, a[N][N];
inline void AMOD(int &x){++ x; if(x >= n) x = 0;}
int main(){
    scanf("%d", &k);
    n = min(k, 500);
    for(Rint i = 0;i < n;i ++){
        int x = 0, y = i;
        for(Rint j = 0;j < n;j ++){
            a[x][y] = i;
            AMOD(x); AMOD(y);
        }
    }
    for(Rint i = n;i < k;i ++){
        int x = 0, y = i - n;
        for(Rint j = 0;j < n;j ++){
            if(y & 1) a[x][y] = i;
            AMOD(x); AMOD(y);
        }
    }
    printf("%d
", n);
    for(Rint i = 0;i < n;i ++){
        for(Rint j = 0;j < n;j ++)
            printf("%d ", a[i][j] + 1);
        putchar('
');
    }
}

AGC040C

奇妙转化：把偶数位置上面的 AB 取反，然后就变成了不能删去 AA 和 BB.

充要条件就是 AB 数量都不超过一半。所以答案就是 $3^n-2sum_{i=lfloorfrac{n}{2} floor+1}^ninom{n}{i}2^{n-i}$

APC001F

题目描述：一个$n$ 个点的带边权的树，每次可以选择一个数 $x$ 和一条路径，将这条路径上的点都异或上 $x$，求变为全0的最少修改次数。

数据范围：$nle 10^5,wle 15$

神仙套路：将点权设为与其相连的所有边的异或和，则修改路径 $u,v$ 相当于把 $u$ 和 $v$ 的点权异或上 $x$.

没那么神仙的套路：将 $u,v$ 的一次修改当做$(u,v)$连边，那么就是要分成一堆联通块，使得每个连通块的异或和为 $0$，修改次数为 $n-$联通块个数。

首先去掉0，然后去掉相同数，于是只剩下 15 个数，枚举子集再状压dp，时间复杂度 $O(n+3^w)$。

【以下是咕咕名单，希望这个括号可以不断往下移动吧】

---

AGC035E

题目描述：有一个正整数集$S$，初始为空，然后Takahashi会做一些形如以下的操作：

1. 选择一个$1$到$n$的整数$x$，将$x$加入$S$
2. 如果$x-2in S$，去掉$x-2$
3. 如果$x+kin S$，去掉$x+k$

求能够得到的$S$的个数$mathrm{mod} m$

数据范围：$1le kle nle 150,10^8le mle 10^9$

---

AGC025D

题目描述：输入$N,D_1,D_2$，要求构造一个大小为$N^2$的点集，满足以下条件：

1. $0le x_i,y_i<2N$
2. $forall i,jin [0,N^2),k=0,1,(x_i-x_j)^2+(y_i-y_j)^2 e D_k$

数据范围：$1le Nle 300,1le D_1,D_2le 2 imes 10^5$.

---

AGC020D

题目描述：设$f(A,B)$，其中$A,Bin N_+$为满足以下条件的字符串：

1. $|f(A,B)|=A+B$

2. $f(A,B)$中有$A$个`A`和$B$个`B`

3. 满足上面条件时，要求$f(A,B)$的最长的只包含一种字符的子串尽可能短。

4. 满足上面条件时，要求$f(A,B)$的字典序尽可能小。

$Q$次询问，求$f(A_i,B_i)[C_i:D_i]$这个子串。

数据范围：$1le Qle 10^3,1le A_i,B_ile 5 imes 10^8,1le C_ile D_ile A_i+B_i,D_i-C_i<100$

---

CF516E

题目描述：有$n$个boy和$m$个girl（标号为0-based），有$b$个boy，$g$个girl开心。在第$i$天，第$i mathrm{mod} n$个boy可以和第$i mathrm{mod} m$个girl【被屏蔽】，如果他们中有一个人开心，那么两个人都会变开心，否则啥事都不会发生。问经过有限天之后能不能让所有人都开心。

数据范围：$1le n,mle 10^9,0le ble min(n,10^5),0le gle min(m,10^5)$

---

CF578E

题目描述：输入一个长度为$n$的$ ext{LR}$字符串$S$，对于一个满足下列要求的排列$p_1,p_2,ldots,p_n$：$S_{p_i}= ext{L}+[2|i]( ext{R}- ext{L})$，它的花费为$sum_{i=1}^{n-1}[p_i>p_{i+1}]$。求最小花费和可行方案。

数据范围：$nle 10^5$，保证$ ext{R}$的数量减去$ ext{L}$的数量为$0$或$1$。