技术教程 编程教程 Codeforces & Atcoder神仙题做题记录 正文

Codeforces & Atcoder神仙题做题记录

2023-06-12,,

鉴于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$凸包的内部点的子集，所以$S\cup T$的凸包是$S$。所以它的贡献为$S\cup T$有凸包。

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

AGC019B

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

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

综上，答案为$1+s[x]\neq 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)\rightarrow (w,u)$，所以考虑对每一个弱联通分量建一个三分图（逃），如果能建出来且三个分量中都有点，则为$cnt_0\times cnt_1+cnt_1\times cnt_2+cnt_2\times 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 = ;

 int n, ans, q[N], front, rear;

 char s[N], t[N];

 int main(){

     scanf("%d%s%s", &n, s + , t + );

     if(!strcmp(s + , t + )){puts(""); return ;}

     int cur = n;

     for(Rint i = n;i;i --){

         if(t[i] == t[i - ]) continue;

         while(cur && (cur > i || s[cur] != t[i])) -- cur;

         if(!cur){puts("-1"); return ;}

         while(front < rear && q[front] - (rear - front) >= i) ++ front;

         if(cur != i) q[rear ++] = cur;

         ans = max(ans, rear - front + );

     }

     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 = , mod = 1e9 + ;

 inline void add(int &a, int b){a += b; if(a >= mod) a -= mod;}

 int n, cur, tmp, t, a[N], c[N], f[][][];

 int cnt[N];

 int main(){

     scanf("%d", &n); n <<= ;

     for(Rint i = ;i <= n;i ++)

         scanf("%d", a + i);

     for(Rint i = ;i <= n;i += ){

         if(a[i] != - && a[i + ] != -) cnt[a[i]] = cnt[a[i + ]] = ;

         else if(a[i] == - && a[i + ] == -) ++ tmp;

         else if(a[i] != -) cnt[a[i]] = ;

         else cnt[a[i + ]] = ;

     }

     for(Rint i = ;i <= n;i ++)

         if(cnt[i] == ) c[++ t] = ;

         else if(cnt[i] == ) c[++ t] = ;

     f[][][] = ;

     for(Rint i = t;i;i --){

         cur ^= ;

         memset(f[cur], , sizeof f[cur]);

         for(Rint j = ;j <= (n >> ) && j <= t;j ++)

             for(Rint k = ;k <= (n >> ) && k <= t;k ++){

                 if(c[i] == ){

                     add(f[cur][j][k + ], f[cur ^ ][j][k]);

                     if(j) add(f[cur][j - ][k], f[cur ^ ][j][k]);

                 } else if(c[i] == ){

                     add(f[cur][j + ][k], f[cur ^ ][j][k]);

                     if(j) add(f[cur][j - ][k], f[cur ^ ][j][k]);

                     if(k) add(f[cur][j][k - ], (LL) f[cur ^ ][j][k] * k % mod);

                 }

             }

     }

     int ans = f[cur][][];

     for(Rint i = ;i <= tmp;i ++)

         ans = (LL) ans * i % mod;

     printf("%d\n", ans);

 }

AGC030F

AGC030E

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

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

注意如果$S_1\neq 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 = ;

 int n, n1, n2, ans, _a[N], _b[N], *a = _a + , *b = _b + ;

 char s1[N], s2[N];

 int main(){

     scanf("%d%s%s", &n, s1 + , s2 + );

     if(s1[] != s2[]) a[++ n1] = ;

     for(Rint i = ;i < n;i ++){

         if(s1[i] != s1[i + ]) a[++ n1] = i;

         if(s2[i] != s2[i + ]) b[++ n2] = i;

     }

     for(Rint i = n1 + ;i <= ;i ++) a[i] = n;

     for(Rint i = n2 + ;i <= ;i ++) b[i] = n;

     ans = 1e9;

     for(Rint i = -n1;i <= n2;i ++) if(!(i & )){

         int tmp = ;

         for(Rint j = -;j <= ;j ++)

             if(i + j >= - && i + j <= ) tmp += abs(a[i + j] - b[j]);

             else {

                 if(i + j < -) tmp += b[j];

                 else tmp += n - b[j];

             }

         ans = min(ans, tmp);

     }

     printf("%d", ans);

 }

AGC030E

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 = ;

 int n, k, a[N][N];

 inline void AMOD(int &x){++ x; if(x >= n) x = ;}

 int main(){

     scanf("%d", &k);

     n = min(k, );

     for(Rint i = ;i < n;i ++){

         int x = , y = i;

         for(Rint j = ;j < n;j ++){

             a[x][y] = i;

             AMOD(x); AMOD(y);

         }

     }

     for(Rint i = n;i < k;i ++){

         int x = , y = i - n;

         for(Rint j = ;j < n;j ++){

             if(y & ) a[x][y] = i;

             AMOD(x); AMOD(y);

         }

     }

     printf("%d\n", n);

     for(Rint i = ;i < n;i ++){

         for(Rint j = ;j < n;j ++)

             printf("%d ", a[i][j] + );

         putchar('\n');

     }

 }

AGC030C

AGC040C

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

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

APC001F

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

数据范围：$n\le 10^5,w\le 15$

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

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

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

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

AGC035E

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

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

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

数据范围：$1\le k\le n\le 150,10^8\le m\le 10^9$

AGC025D

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

    $0\le x_i,y_i<2N$
    $\forall i,j\in [0,N^2),k=0,1,(x_i-x_j)^2+(y_i-y_j)^2\ne D_k$

数据范围：$1\le N\le 300,1\le D_1,D_2\le 2\times 10^5$.

AGC020D

题目描述：设$f(A,B)$，其中$A,B\in \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]$这个子串。

数据范围：$1\le Q\le 10^3,1\le A_i,B_i\le 5\times 10^8,1\le C_i\le D_i\le 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【被屏蔽】，如果他们中有一个人开心，那么两个人都会变开心，否则啥事都不会发生。问经过有限天之后能不能让所有人都开心。

数据范围：$1\le n,m\le 10^9,0\le b\le \min(n,10^5),0\le g\le \min(m,10^5)$

CF578E

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

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

Codeforces & Atcoder神仙题做题记录的相关教程结束。

《Codeforces & Atcoder神仙题做题记录.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!