codeforces Round 1021-1030（部分题解）

有些好的题解就直接复制过来了，所以部分非作者所写题解
持续更新中…

Round 1021 (Div. 2)

B.Sasha and the Apartment Purchase（货舱选址变种）

C.Sports Betting（思维）

发现对于同一天$a_i$预测的结果只要00,01,10,11，所以只要任意一天的预测人数>=4，那么就是Yes。
还有一种情况就是当前位置的人数为2或3，以$cnt(a_i)==2$为例，那么我们不妨预测为01和11，第一天必对一种，然后看第二天，$如果cnt(a_i+1)==2$，那么分别预测01，00，我们看到了，如果第二天是1，那么成功，如果第二天是0，那么第三天比对一种，肯定是可以成功的。
假设$cnt(a_i+1)==1$，我们让预测结果为01，然后$cnt(a_i+2)==1$预测结果也是01，知道再次遇到$cnt(a_i+k)>=2$即可。

Round 1022 (Div. 2)

D.Needle in a Numstack（二分+循环节+交互题）

这是一个互动问题。

给定正整数$n,k（n<=1e5,k<=50）$，两个未知数组 A 和 B满足。
$|A|+|B|=n$，数组的总长度为 n。
$|A|\ge k，|B|\ge k$，每个数组的长度至少为 k。
数组只包含从 1 到 k 的数字。

如果从数组 A 和 B 中任选 k 个连续元素，它们都将是不同的。
先把数组 A 的元素写入数组 C，然后再把数组 B 写入数组C。
可以提出<=250个问题来询问 $C_i$ 是多少
您需要找出数组 A 和 B 的长度，或者报告无法唯一确定它们的长度。

因为任意任选 k 个连续元素，它们都将是不同的，所以数组A,B必有周期位k的循环节。
数组左起右起分别是两个周期为$k$的循环节，我们可以通过这个求出唯一的分界点
首先用 $2k$ 次查询记录首尾两个循环节。然后用一个$pos$数组记录下中间段且满足在两个循环节中对应元素值不同的位置（即可能的分界点）。
在 $pos$ 中二分 mid 并查询第 $mid$ 位上的值判断属于左循环节还是右循环节，从而逼出可能的答案区间 $[l,r]$。当且仅当 $l+1=r$ 时有唯一解。

Round 1023 (Div. 2)

A. LRC and VIP

给定大小为$n$的序列，问你能不能把这个序列分成两个序列，两个序列的 $gcd$ 不同，因为$gcd<=n$个数的最大值，所以我们只需要选出最大值放到其中的一个序列中即可，注意判断是否全为最大值。

B.Apples in Boxes

题意：$n$ 个数，两个人博弈。每轮一个人选择使得一个$a_i$减一。如果操作后极差大于k则输。如果所有$a_i$都是零那么则无法操作，无法操作的人输。求第一个人能不能赢。

为了保证极差小于等于 k。减最小值肯定不优。那么不减最小值就只能减其它数，随着其它数变小，极差也只会变小。所以如果一开始第一个人不输，则会一直到所有数都变成零才结束，此时如果总和是奇数第一个人就赢。一开始就输的情况就是最大值减一后极差大于 k，或者最大值有多个且极差大于 k
。

C. Maximum Subarray Sum

题意：给你数组 $a$，有些地方没填。你需要填上后使得最大子段和等于 k 。
先判断无解
有解的情况下，我们只需要选一个填的位置，其他位置填上$-inf$即可。

D. Apple Tree Traversing（树的直径）

题意：给你一棵树。每次选择一条路径，路径端点为 $u,v$。这条路径不能包含选择过的点。如果把 $cnt,u,v$ 三个整数加入答案，$cnt$ 是路径上的点数，然后把路径上的点标记为选择过。求字典序最大的答案。

每次找到没有遍历过的树的直径，然后把直径上的所有结点去掉，把树变成森林，然后再处理森林即可，时间复杂度$O(N\ast sqrtN)$。

Round 1024 (Div. 2)

A. Dinner Time

题意：给你 $n,m,p,q$ 看是否存在 长度为n的数组满足和为m且任何长度为p的子数组和为q。
首先如果 $p|n$ 那么只需要判断 $n/p\ast q==m$ 是否满足即可
如果 $p$ 不整除 $n$ 那么有 $k\ast p+x=m$ ($x$的长度是$n/p$的余数) ，那么最后一段怎么满足呢，只需要前面那段等于 $-$x 即可，然后往前推一定能满足题意.

D Quartet Swapping（思维+逆序对）

给定一个长度为 $n$ 的排列 $a$ ${}^{\text{∗}}$。你可以进行以下操作任意次数（包括零次）：

• 选择一个下标 $1\le i\le n-3$。然后，同时交换 $a_i$ 和 $a_{i+2}$，以及 $a_{i+1}$ 和 $a_{i+3}$。换句话说，排列 $a$ 将从 $[\dots ,a_i,a_{i+1},a_{i+2},a_{i+3},\dots ]$ 变为 $[\dots ,a_{i+2},a_{i+3},a_i,a_{i+1},\dots ]$。

请确定通过任意次上述操作后能得到的字典序最小的排列 ${}^{\text{†}}$。

可以分成奇数下标和偶数下标的两个序列。
找规律可以发现一个数跳偶数次不改变另一序列的顺序，奇数次会改变，所以我们只需要将前m-2小的数排到前面，然后看每个数跳了奇数次还是偶数次，如果为奇数就交换后两个，否则不交换。

Round 1025 (Div2)

A. It’s Time To Duel

N个人排成一排只和相邻的人战斗，有人会撒谎，让你判断不可能的局面

对于1：不能全是1，因为 n - 1 场战斗最多有 n - 1 个玩家赢。
对于0：相邻两项不能都是0，因为战斗总是有人赢，有人输。

B Slice to Survive（棋盘切割）

一个人负责调整棋子位置，一个人切棋盘。
切棋盘每次只能切掉一边，所以 横向的切 跟 纵向的切 是独立的。
调整棋子位置的人，把棋子放到中间最优，因为这样可以最小化 各种方向切的损失。（偶数个格子就没办法了，总有一边损失大 1 格）。
切棋盘的人，每次切掉的 行数（列数）越多越好。

对于怪物的初始位置，只能影响第一次切。因为结果可以在 log 时间内计算出，我们各个方向都切一遍取最大值也是可以接受的。

设 $n$ 为行（列）的数量。$n$ 为偶数时，能切掉 $n/2$，还剩下 $n/2$；$n$ 为奇数时，能切掉 $n/2$，还剩下 $(n+1)/2$。模拟这个切的过程，即 $ceil[log(n)]+ceil[log(m)]$

C1. Hacking Numbers (Easy Version)（交互，数学）

交互题目，每次可以进行以下询问

给定一个$x$(我们不知道)，目的是把这个 $x（<=1e9）$变成 $n$ （询问不超过7次）

    digit();//x -> [1-81]digit();//-> [1-16]add(-8);//-> [1-8]add(-4);//-> [1-4]add(-2);//-> [1-2]add(-1);//-> 1mul(n);ans();

C2. Hacking Numbers (Mid Version)

很明显如果一个数能被9整除，那么这个数的数位和也能被9整除，先对x乘9，
$x(<=9e9)$ 然后对$x$进行一次 $digit()(x->[9,89])$，再进行一次$digit()(x->9)$，最后$add(n-9)$即可。

C3. Hacking Numbers (Hard Version)

mul(999999999);
digit();
if(n!=81)add(n-81);
ans();

D D/D/D

可以发现对于偶数路径的点，都可以通过多次折回来到达，所以只要存在一个大偶数$n$，即可到达$dist$为$2,4,6,8\dots ,n-2,n$的所有点，奇数同理，对于一个大奇数$n$，可到达$dist$为$1,3,5,7\dots ,n-2,n$的所有点，所以只需要跑一遍 $bfs$（注意每个状态的奇偶性）即可，然后判断能组成的最大偶数和奇数。

E. Binary String Wowee

组合计数+动态规划(待补)

Round 1026（Div2）

C Racing（线段交）

根据当前的位置算出一个范围，检查该范围是否合法，然后从后往前递推出每次选择的操作。

D. Fewer Batteries（二分答案+dp check）

电池数越多，那么可以到达终点的可能性越大，所以可以二分电池数，$check$ 的时候在 $DAG$ 上做一次简单 $dp$ 即可算出

Round 1027 (Div. 3)

D. Come a Little Closer’（multiset模拟）

题意：在方格图上给出一堆坐标，你有一次操作机会可以将其中一个坐标移到任意地方，要求你最小化矩阵面积（所有点都要在矩阵内或矩阵上）
使用 $multiset$ 分别存储x坐标和y坐标，遍历删除某个点，计算当前矩阵的面是多大，具体就是$(mxx-mnx+1)\times (mxy-mny+1)$，特判一下该面积是否等于 $n-1$，如果是那就是$min((mxx-mnx+2)\times (mxy-mny+1)，（mxx-mnx+1)\times (mxy-mny+2))$。

F. Small Operations（约数+暴力dp）

这道题很妙，可以让$x$和$y$除去他们的$gcd$，我们只需要将$x$除去然后再乘上$y$即可了。
怎么求呢？我们可以通过埃氏筛的思想将所有数$(1-N)$的约数求出来，然后使用dp，求出 $x$ 和 $y$ 最少可以用多少个他们的约数凑出来，注意转移的时候有每次乘上的数$<=k$，最后的结果就是 $f[x]+f[y]$

    auto work = [&](int x){//x的所有因子个数int m = g[x].size();vector<int> f(m,inf);f[0]=0;//第一个是1for(int i=0;i<m;i++){for(int j=i+1;j<m;j++){if((g[x][j]%g[x][i]==0)&&(g[x][j]/g[x][i]<=k)){f[j]=min(f[j],f[i]+1);}else if(g[x][j]/g[x][i]>k){break;}}}return f[m-1]==inf?-1:f[m-1];};

Round 1028(Div2)

B. Gellyfish and Baby’s Breath（指数比较）

注意到性质 $2^n==2^n-1+2^n-1$，所有我们只要求最大的前缀 $a_j$ 和 $b_{i-j}$即可，如果相同的话比较第二个数的大小即可。

C. Gellyfish and Flaming Peony（gcd+暴力dp）

题意：给你一个数组，每次选两个数，使得其中数变成它们的 $gcd$。求所有数变成一样的最小操作数。
显然最后变成的数是整个数组的 $gcd$。那么应该选最少的数使得可以得到数组的 $gcd$，那么其它数和这个数操作就一步到位了。问题变为选择最少的数使得它们的$gcd$ 等于数组的 $gcd$。观察到 $a_i<=5e3$。可以
$f[i][j]$表示前 $i$ 个 $gcd$为 $j$最少选几个数。使用滚动数组优化一下内存可以通过。

    vector<int> f(mx+1,inf);f[a[1]]=1;for(int i=2;i<=n;i++){for(int j=1;j<=mx;j++){if(f[j]==inf)continue;f[__gcd(a[i],j)]=min(f[__gcd(a[i],j)],f[j]+1);}f[a[i]]=1;}cout<<n-1+f[gd]-1<<'\n';

Round 1029 (Div. 3)

E.Lost Soul（思维+set）

给你两个长度均为n的整数数组a和b。

你可以任意次数执行以下操作：

选择一个索引$i(1\le i\le n-1)$，将$a_i$设为$b_{i+1}$，或者将$b_i$​设为$a_{i+1}$ 。

在执行任何操作之前，你可以选择一个索引$(1\le i\le n-1)$，从两个数组中同时移除$a_i$和 $b_i$ 。这种移除操作最多只能进行一次。

对于两个长度为m的数组c和d，它们的“匹配数”指的是满足$c_j=d_j$ 的位置$j（1\le j\le m）$的数量。
你的任务是计算通过操作能达到的最大匹配数。

题解：
1.当 $a_i=b_i$ 的时候，可以让前i个数相等。
2.当$a_i=a_{i+1}$或$b_i=b_{i+1}$的时候，也可以让前i个数相等。
3.我们发现当删除某一个位置i的时候，可以改变后续对前面的影响，即$b_{i+1}->a_{i-1}$或者$a_{i+1}->b_{i-1}$，那么，当我们枚举到某个位置$i$的时候，$a_{i-1}$或$b_{i-1}$可以变成$[i+1,n]$的任何一个$a_j，b_j$，那么这次的答案就是 i-1
在所有情况下取最大值即可。

Round 1030 (Div. 2)

B.Make It Permutation（思维+找规律）

题意：给你一个$n\ast n$的矩阵，$A_{i,j}=j$。你每次可以选择某一行将其一个子区间翻转。最多操作2*n次。求每一列都是排列的操作方案。
让斜着的每一排都相等即可。
反转第一行的$[1,n]$
让 $i$ 在$[2,n]$的时候翻转$[1,i-1]和[i,n]$即可

C很板子的题，按位贪心即可，D.题直接模拟

Educational Round 179 (Rated for Div. 2)

A Energy Crystals

题意：三个数，每次操作使得一个数增加任意数。但要保证任意两个数都有一个数大于等于另一个数的一半。求三个数都变成 x 的最少操作数。

首先把一个数变成 1，那么发现，之后每操作两步就能使得最大值乘二加一。那么需要
的操作数把最大值变成 2*logx ，然后两次操作把另外两个数变成 x，加上一开始的一步，就是 2 * logx +3。

B.Fibonacci Cubes （思维+几何）

CD很简单不写了