## CF1392A > 多组询问，每次给出一个长度为 $n$ 的序列 $a$ ，对于两个相邻的且不相同的数，你可以将他们合并起来，即将这两个数替换成它们的和。 > > 注意到，你每次进行一次操作后，序列长度会 $-1$，现在你可以随意进行若干次操作，问最后序列长度最短是多少。 > > $n\le2\cdot10^5$ **显然**如果序列中的数不全相同，一定可以合并成一个数，否则无法合并。 ### CODE ```cpp #include <cstdio> #include <cctype> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e5+10; int n, a[N]; int main() { int T=read(); while (T--) { n=read(); for (int i=1; i<=n; i++) a[i]=read(); for (int i=2; i<=n; i++) if (a[i]!=a[i-1]) {printf("1\n"); goto nxt;} printf("%d\n", n); nxt:; } return 0; } ``` ## CF1392B > 给出一个长度为 $n$ 的序列 $a$ 以及一个 $k$，我们定义进行一次操作分以下两步： > > 1. 设 $d$ 表示序列中的最大值。 > 2. 对于每个 $i\in[1,n]$，将 $a_i$ 替换成 $d−a_i$。 > > 现在请你输出进行 $k$ 次操作后的序列。 > > $n\le2\cdot10^5$ 我们可以发现，做完第一次操作后，所有的数都会变为非负整数，且最小值为 $0$。 我们手动模拟几次操作 序列 $1$ 为：$0,a_1,a_2,a_3,\cdots,a_n$ 序列 $2$ 为：$a_n,a_n-a_1,a_n-a_2,a_n-a_3,\cdots,0$ 序列 $3$ 为：$0,a_1,a_2,a_3,\cdots,a_n$，我们惊奇的发现和序列 $1$ 相等。 显然这是一个循环节为 $2$ 的循环，所以最多操作两次。 ### CODE ```cpp #include <cstdio> #include <cctype> #include <algorithm> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e5+10; int n, k, a[N]; signed main() { int T=read(); while (T--) { n=read(), k=(read()-1)%2+1; for (int i=1; i<=n; i++) a[i]=read(); while (k--) { int mx=a[1]; for (int i=1; i<=n; i++) mx=max(mx, a[i]); for (int i=1; i<=n; i++) a[i]=mx-a[i]; } for (int i=1; i<=n; i++) printf("%lld ", a[i]); puts(""); } return 0; } ``` ## CF1392C > 给出一个长度为 $n$ 序列，每次可以选择一段不下降的区间 $[l,r]$，将这段区间每个数的值 $+1$。 > > 求最少需要多少次操作可以使得序列变为一个不下降的序列。 > > $n\le2\cdot10^5$ 我们考虑贪心，从后往前做，做当前某一位时保证后面的序列为不下降序列。 - 如果 $a_i\le a_{i+1}$，显然不用操作。 - 如果 $a_i>a_{i+1}$，直接把 $[i+1,n]$ 做操作，使得 $a_i=a_{i+1}$ ### CODE ```cpp #include <cstdio> #include <cctype> #include <algorithm> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } int a[200010]; int main() { int T=read(); while (T--) { int n=read(); long long ans=0; for (int i=1; i<=n; i++) a[i]=read(); for (int i=2; i<=n; i++) ans+=max(a[i-1]-a[i], 0); printf("%lld\n", ans); } return 0; } ``` ## CF1392D > $n$ 个人围成一个环。 > > 每个人会攻击他左边的人或者右边的人，用`L`或`R`表示。 > > 1. 如果一个人只受到一个人的攻击时，他必须攻击那个人。 > 2. 否则他可以攻击与他相邻的任意一个人。 > > 给出一个不一定合法的攻击状态，求至少改变多少个人的攻击状态，使得攻击状态合法。 > > $n\le2\cdot10^5$ 我们考虑什么时候会不合法，如果一个人只受到一个方向的人的攻击，且他攻击的不是攻击他的人，则他们的序列为`LLL`或`RRR`。 我们发现当且仅当存在连续长度 $\ge3$ 的相同攻击状态会不合法。 所以我们只要就最小的操作次数使得不存在连续 $3$ 个相同的。 1. 如果全部相同，且长度$\ge3$，则显然每隔 $2$ 个人取反 $1$ 个人最优，答案为 $\left\lceil\frac{n}{3}\right\rceil$。 2. 否则，我们把序列分为每段状态相同的多段，使每相邻两段状态不同，如`LLLLLL|RR|L|RRR`。（因为是环，首、尾可能相同，需要特殊处理一下），然后每一段也隔 $2$ 个取反 $1$ 个，答案为 $\sum\left\lfloor\frac{len_i}{3}\right\rfloor$ P.S. 这题还可以用DP来写，想起来会更简单一点。 ### CODE ```cpp #include <cstdio> #include <cctype> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } char a[200010]; int main() { int T=read(); while (T--) { int n=read(), p=0, tot=0, ans=0; scanf("%s", a+1); for (int i=2; i<=n; i++) if (a[i]!=a[i-1]) p=i; if (p==0) {printf("%d\n", (n>2)*(n+2)/3); continue;} int lst=1, i=p; do { if (a[i]==lst) tot++; else ans+=tot/3, tot=1, lst=a[i]; i=i%n+1; } while (i!=p); printf("%d\n", ans+tot/3); } return 0; } ``` ## CF1392E > 这是一道帅帅的交互题。 > > 给出一个正整数 $n$（ $1\le n\le 25$），你需要构造一个 $n\times n$ 的矩阵 $a$，我们称 $a$ 中第 $i$ 行第 $j$ 列的数字为 $a_{i,j}$（ $0\le a_{i,j}\le 10^{16}$）。 > > 我们定义一条“路径”为从 $a_{1,1}$ 开始，每次向下或向右走一格（不能走出去），最终到达 $a_{n,n}$ 的元素的集合。 > > 我们定义“路径和”为一条路径上所有元素的和。 > > 现在有 $q$ 组询问，每组询问包括一个整数 $x$，你需要找到一条路径，满足其路径和 $=x$，保证解存在。 > > **请注意，你给出的路径必须和答案文件中的路径一致。** 我们发现 $n$ 很小很小很小，我们可以考虑对每个数二进制分解。 使得当前走到了一个某个点，当前要走第 $i$ 个二进制位，所以下一步可以选择的为 $0$ 和 $2^i$，我们发现这两位在同一个对角线相邻的两个，如：  所以，我们只要构造对于第 $i$ 个对角线为 $0$ 和 $2^i$ 交替出现就好了，这样就可以保证对于一个数的解是唯一的了！如当 $n=6$ 时，可以构造如下矩阵：  ### CODE ```cpp #include <cstdio> #include <cctype> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } int n, a[30][30]; signed main() { n=read(); for (int i=n; i>=1; i--) for (int j=n; j>=1; j--) if (j==1 || i==n) a[i][j]=1ll<<i+j-2; else if (j==2 || i==n-1) a[i][j]=0; else a[i][j]=a[i+2][j-2]; for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) printf("%lld ", a[i][j]); printf("\n"); } fflush(stdout); int q=read(); while (q--) { int t=read(); printf("1 1\n"); int x=1, y=1; for (int i=1; i<=n+n-2; i++) { if ((t>>i&1)==(a[x+1][y]>>i&1)) x++; else y++; printf("%lld %lld\n", x, y); } fflush(stdout); } return 0; } ``` ## CF1392F > 现在有一些山发生了山体滑坡，这些山从左到右依次排布，第 $i$ 座山的高度为 $h_i$，且 $\forall i\in[1,n),h_i<h_{i+1}$。 > > 每一时刻，假如 $h_i+2\leq h_{i+1}$，那么两座山的高度会发生变化，即 $h_i+1,h_{i+1}-1$。 > > 问山体滑坡进行完后，即没有任何泥土能流动时，所有山的高度是多少。 > > $n\le 10^6$ 我们~~很容易~~发现，最后答案只有 $1$ 个相邻的是相等的，其余的都满足比前面一个大 $1$。 **证明**： > 显然，我们发现滑坡的顺序不会影响结果。 > > 所以我们考虑从左往右，假设 $h_1\to h_{i-1}$ 已经满足最多只有一个相等，每次增加一个 $i$，它会滑坡好多好多次，直到 $h_i-h_{i-1}\le2$ 我们考虑每一次滑坡。 > > - 如果左边有一对相邻 $2$ 个相同的，它会一直滑倒这对右边的，这时这一对相同会消失，有可能产生一对新的相同： > > | | | | | ${\color{Red} 1}$ | | --- | --- | --- | --- | ----------------- | | | | | | $1$ | | | | | $1$ | $1$ | | | $1$ | $1$ | $1$ | $1$ | | $1$ | $1$ | $1$ | $1$ | $1$ | > > 会变为 > > | | | | | ${\color{Red} 0}$ | | --- | --- | ----------------- | --- | ----------------- | | | | | | $1$ | | | | ${\color{Red} 1}$ | $1$ | $1$ | | | $1$ | $1$ | $1$ | $1$ | | $1$ | $1$ | $1$ | $1$ | $1$ | > > > - 如果左边没有一对相邻的是相同的，则它会移动到最左边并在最左边产生一对相同。 > > 所以，不管怎么操作，最后剩余相邻相同的一定不超过一个。 有了这个结论，我们就可以~~轻松自如如鱼得水水到渠成诚心诚意意大利面地~~做出了。 我们可以先计算出和，构造一个首项尽量大，公差为 $1$ 的等差数列，然后多出来的数把前面$+1$，使得和与原来相同。 ### CODE ```cpp #include <cstdio> #include <cctype> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e6+10; int n, a[N], s; signed main() { n=read(); for (int i=1; i<=n; i++) a[i]=read(), s+=a[i]; s-=n*(n+1)/2; a[0]=s/n; s-=a[0]*n; for (int i=1; i<=n; i++) a[i]=a[i-1]+1; for (int i=1; i<=s; i++) a[i]++; for (int i=1; i<=n; i++) printf("%lld ", a[i]); return 0; } ``` Loading... ## CF1392A > 多组询问，每次给出一个长度为 $n$ 的序列 $a$ ，对于两个相邻的且不相同的数，你可以将他们合并起来，即将这两个数替换成它们的和。 > > 注意到，你每次进行一次操作后，序列长度会 $-1$，现在你可以随意进行若干次操作，问最后序列长度最短是多少。 > > $n\le2\cdot10^5$ **显然**如果序列中的数不全相同，一定可以合并成一个数，否则无法合并。 ### CODE ```cpp #include <cstdio> #include <cctype> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e5+10; int n, a[N]; int main() { int T=read(); while (T--) { n=read(); for (int i=1; i<=n; i++) a[i]=read(); for (int i=2; i<=n; i++) if (a[i]!=a[i-1]) {printf("1\n"); goto nxt;} printf("%d\n", n); nxt:; } return 0; } ``` ## CF1392B > 给出一个长度为 $n$ 的序列 $a$ 以及一个 $k$，我们定义进行一次操作分以下两步： > > 1. 设 $d$ 表示序列中的最大值。 > 2. 对于每个 $i\in[1,n]$，将 $a_i$ 替换成 $d−a_i$。 > > 现在请你输出进行 $k$ 次操作后的序列。 > > $n\le2\cdot10^5$ 我们可以发现，做完第一次操作后，所有的数都会变为非负整数，且最小值为 $0$。 我们手动模拟几次操作 序列 $1$ 为：$0,a_1,a_2,a_3,\cdots,a_n$ 序列 $2$ 为：$a_n,a_n-a_1,a_n-a_2,a_n-a_3,\cdots,0$ 序列 $3$ 为：$0,a_1,a_2,a_3,\cdots,a_n$，我们惊奇的发现和序列 $1$ 相等。 显然这是一个循环节为 $2$ 的循环，所以最多操作两次。 ### CODE ```cpp #include <cstdio> #include <cctype> #include <algorithm> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e5+10; int n, k, a[N]; signed main() { int T=read(); while (T--) { n=read(), k=(read()-1)%2+1; for (int i=1; i<=n; i++) a[i]=read(); while (k--) { int mx=a[1]; for (int i=1; i<=n; i++) mx=max(mx, a[i]); for (int i=1; i<=n; i++) a[i]=mx-a[i]; } for (int i=1; i<=n; i++) printf("%lld ", a[i]); puts(""); } return 0; } ``` ## CF1392C > 给出一个长度为 $n$ 序列，每次可以选择一段不下降的区间 $[l,r]$，将这段区间每个数的值 $+1$。 > > 求最少需要多少次操作可以使得序列变为一个不下降的序列。 > > $n\le2\cdot10^5$ 我们考虑贪心，从后往前做，做当前某一位时保证后面的序列为不下降序列。 - 如果 $a_i\le a_{i+1}$，显然不用操作。 - 如果 $a_i>a_{i+1}$，直接把 $[i+1,n]$ 做操作，使得 $a_i=a_{i+1}$ ### CODE ```cpp #include <cstdio> #include <cctype> #include <algorithm> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } int a[200010]; int main() { int T=read(); while (T--) { int n=read(); long long ans=0; for (int i=1; i<=n; i++) a[i]=read(); for (int i=2; i<=n; i++) ans+=max(a[i-1]-a[i], 0); printf("%lld\n", ans); } return 0; } ``` ## CF1392D > $n$ 个人围成一个环。 > > 每个人会攻击他左边的人或者右边的人，用`L`或`R`表示。 > > 1. 如果一个人只受到一个人的攻击时，他必须攻击那个人。 > 2. 否则他可以攻击与他相邻的任意一个人。 > > 给出一个不一定合法的攻击状态，求至少改变多少个人的攻击状态，使得攻击状态合法。 > > $n\le2\cdot10^5$ 我们考虑什么时候会不合法，如果一个人只受到一个方向的人的攻击，且他攻击的不是攻击他的人，则他们的序列为`LLL`或`RRR`。 我们发现当且仅当存在连续长度 $\ge3$ 的相同攻击状态会不合法。 所以我们只要就最小的操作次数使得不存在连续 $3$ 个相同的。 1. 如果全部相同，且长度$\ge3$，则显然每隔 $2$ 个人取反 $1$ 个人最优，答案为 $\left\lceil\frac{n}{3}\right\rceil$。 2. 否则，我们把序列分为每段状态相同的多段，使每相邻两段状态不同，如`LLLLLL|RR|L|RRR`。（因为是环，首、尾可能相同，需要特殊处理一下），然后每一段也隔 $2$ 个取反 $1$ 个，答案为 $\sum\left\lfloor\frac{len_i}{3}\right\rfloor$ P.S. 这题还可以用DP来写，想起来会更简单一点。 ### CODE ```cpp #include <cstdio> #include <cctype> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } char a[200010]; int main() { int T=read(); while (T--) { int n=read(), p=0, tot=0, ans=0; scanf("%s", a+1); for (int i=2; i<=n; i++) if (a[i]!=a[i-1]) p=i; if (p==0) {printf("%d\n", (n>2)*(n+2)/3); continue;} int lst=1, i=p; do { if (a[i]==lst) tot++; else ans+=tot/3, tot=1, lst=a[i]; i=i%n+1; } while (i!=p); printf("%d\n", ans+tot/3); } return 0; } ``` ## CF1392E > 这是一道帅帅的交互题。 > > 给出一个正整数 $n$（ $1\le n\le 25$），你需要构造一个 $n\times n$ 的矩阵 $a$，我们称 $a$ 中第 $i$ 行第 $j$ 列的数字为 $a_{i,j}$（ $0\le a_{i,j}\le 10^{16}$）。 > > 我们定义一条“路径”为从 $a_{1,1}$ 开始，每次向下或向右走一格（不能走出去），最终到达 $a_{n,n}$ 的元素的集合。 > > 我们定义“路径和”为一条路径上所有元素的和。 > > 现在有 $q$ 组询问，每组询问包括一个整数 $x$，你需要找到一条路径，满足其路径和 $=x$，保证解存在。 > > **请注意，你给出的路径必须和答案文件中的路径一致。** 我们发现 $n$ 很小很小很小，我们可以考虑对每个数二进制分解。 使得当前走到了一个某个点，当前要走第 $i$ 个二进制位，所以下一步可以选择的为 $0$ 和 $2^i$，我们发现这两位在同一个对角线相邻的两个，如：  所以，我们只要构造对于第 $i$ 个对角线为 $0$ 和 $2^i$ 交替出现就好了，这样就可以保证对于一个数的解是唯一的了！如当 $n=6$ 时，可以构造如下矩阵：  ### CODE ```cpp #include <cstdio> #include <cctype> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } int n, a[30][30]; signed main() { n=read(); for (int i=n; i>=1; i--) for (int j=n; j>=1; j--) if (j==1 || i==n) a[i][j]=1ll<<i+j-2; else if (j==2 || i==n-1) a[i][j]=0; else a[i][j]=a[i+2][j-2]; for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) printf("%lld ", a[i][j]); printf("\n"); } fflush(stdout); int q=read(); while (q--) { int t=read(); printf("1 1\n"); int x=1, y=1; for (int i=1; i<=n+n-2; i++) { if ((t>>i&1)==(a[x+1][y]>>i&1)) x++; else y++; printf("%lld %lld\n", x, y); } fflush(stdout); } return 0; } ``` ## CF1392F > 现在有一些山发生了山体滑坡，这些山从左到右依次排布，第 $i$ 座山的高度为 $h_i$，且 $\forall i\in[1,n),h_i<h_{i+1}$。 > > 每一时刻，假如 $h_i+2\leq h_{i+1}$，那么两座山的高度会发生变化，即 $h_i+1,h_{i+1}-1$。 > > 问山体滑坡进行完后，即没有任何泥土能流动时，所有山的高度是多少。 > > $n\le 10^6$ 我们~~很容易~~发现，最后答案只有 $1$ 个相邻的是相等的，其余的都满足比前面一个大 $1$。 **证明**： > 显然，我们发现滑坡的顺序不会影响结果。 > > 所以我们考虑从左往右，假设 $h_1\to h_{i-1}$ 已经满足最多只有一个相等，每次增加一个 $i$，它会滑坡好多好多次，直到 $h_i-h_{i-1}\le2$ 我们考虑每一次滑坡。 > > - 如果左边有一对相邻 $2$ 个相同的，它会一直滑倒这对右边的，这时这一对相同会消失，有可能产生一对新的相同： > > | | | | | ${\color{Red} 1}$ | | --- | --- | --- | --- | ----------------- | | | | | | $1$ | | | | | $1$ | $1$ | | | $1$ | $1$ | $1$ | $1$ | | $1$ | $1$ | $1$ | $1$ | $1$ | > > 会变为 > > | | | | | ${\color{Red} 0}$ | | --- | --- | ----------------- | --- | ----------------- | | | | | | $1$ | | | | ${\color{Red} 1}$ | $1$ | $1$ | | | $1$ | $1$ | $1$ | $1$ | | $1$ | $1$ | $1$ | $1$ | $1$ | > > > - 如果左边没有一对相邻的是相同的，则它会移动到最左边并在最左边产生一对相同。 > > 所以，不管怎么操作，最后剩余相邻相同的一定不超过一个。 有了这个结论，我们就可以~~轻松自如如鱼得水水到渠成诚心诚意意大利面地~~做出了。 我们可以先计算出和，构造一个首项尽量大，公差为 $1$ 的等差数列，然后多出来的数把前面$+1$，使得和与原来相同。 ### CODE ```cpp #include <cstdio> #include <cctype> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e6+10; int n, a[N], s; signed main() { n=read(); for (int i=1; i<=n; i++) a[i]=read(), s+=a[i]; s-=n*(n+1)/2; a[0]=s/n; s-=a[0]*n; for (int i=1; i<=n; i++) a[i]=a[i-1]+1; for (int i=1; i<=s; i++) a[i]++; for (int i=1; i<=n; i++) printf("%lld ", a[i]); return 0; } ``` 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏