Codeforces Round 1047 (Div. 3)
Dashboard - Codeforces Round 1047 (Div. 3) - Codeforces
怎么 ABCDE 全是数学 / 数字游戏题。
CodeForces-2137A Collatz Conjecture
对一个 \(x\) 进行如下操作 \(k\) 次：
- 如果 \(x\) 为偶数，则将其变为 \(x/2\)；
- 否则，令 \(x\) 变为 \(3x+1\)。
给定最终的结果 \(y\)，求初始的 \(x\)。若有多解，输出一种即可。
\(1\le T\le400\)，\(1\le k,y\le20\)。
直接输出 \(y\cdot2^k\) 即可。
CodeForces-2137B Fun Permutation
给定一个 \(1,2,\cdots,n\) 的排列 \(p\)。构造一个 \(1,2,\cdots,n\) 的排列 \(q\)，使得 \(\gcd(p_i+q_i,p_{i+1}+q_{i+1})\ge3\) 对于任意 \(1\le i<n\) 都成立。
\(1\le T\le10^4\)，\(2\le n,\sum n\le2\cdot10^5\)。
设 \(n\) 的一个因数为 \(k\)（\(k\ge3\)），那么可以将 \(1,2,\cdots,n\) 分成 \(n/k\) 组，每 \(k\) 个数为一组。
对 \(k\) 取模余数为 \(0\) 的，将其与其本身匹配；余数为 \(m\)（\(1\le m<k\)）的，将其与余数为 \(k-m\) 的匹配。
这样，每个数都有与其互相匹配的唯一的一个数，且二者的和为 \(k\) 的倍数。
将 \(q_i\) 赋值为与 \(p_i\) 匹配的数，故 \(p_i+q_i\) 一定为 \(k\) 的倍数。
特别地，如果 \(n=2\)，则直接令 \(1\) 匹配 \(2\)，\(2\) 匹配 \(1\) 即可。
题解区：构造 \(q_i=n+1-p_i\) 即可。
CodeForces-2137C Maximum Even Sum
给定整数 \(a,b\)，进行任意次下面的操作：
- 选择一个 \(b\) 的因数 \(k\)，令 \((a,b)\) 变为 \((ak,b/k)\)。
求出 \(a+b\) 的最大偶数值。\(1\le T\le10^4\)，\(1\le a,b\le a\cdot b\le 10^{18}\)。
奇数 + 奇数 或者 偶数 + 偶数 都可以凑成奇数。显然，\(ab\) 的质因数是守恒的。分类讨论：
- 如果 \(a\) 为奇数：
- 如果 \(b\) 为奇数：则二者均不可能变为偶数，故最大的 \(k\) 即为 \(b\)，答案为 \(ab+1\)。
- 如果 \(b\) 为偶数：
- 如果 \(b\) 为 \(4\) 的倍数：则 \(b\) 可以分给 \(a\) 一个 \(2\)，这样二者均变为偶数，故最大的 \(k\) 为 \(b/2\)，答案为 \(ab/2+2\)。
- 否则：无解，因为 \(a\) 和 \(b\) 总有一个是奇数，另外一个是偶数。
- 如果 \(a\) 为偶数：
- \(b\) 一定需要为偶数，因此 \(b\) 为奇数则无解，\(b\) 为偶数则最大的 \(k\) 为 \(b/2\)，答案为 \(ab/2+2\)。
由于限制了 \(a\cdot b\) 的范围，故不需要开 __int128。
CodeForces-2137D Replace with Occurrences
对于一个长度为 \(n\) 的序列 \(a\)，令 \(f(x)\) 表示 \(x\) 在 \(a\) 中的出现次数。
给定一个长度为 \(n\) 的序列 \(b\)，构造序列 \(a\)，使得 \(1\le a_i\le n\) 且 \(f(a_i)=b_i\)，\(i=1,2,\cdots,n\)。若无解，输出 \(-1\)。
\(1\le T\le10^4\)，\(1\le n,\sum n\le2\cdot10^5\)，\(1\le b_i\le n\)。
贪心地进行构造。显然用来填充序列 \(a\) 的数字具体是什么值并不重要，重要的是 \(a_i\) 的出现次数一定等于 \(b_i\)。
比如：
- 有 \(3\) 个数的 \(b_i\) 为 \(3\)，那么在对应的 \(a_i\) 填入相同的 \(3\) 个数；
- 有 \(4\) 个数的 \(b_i\) 为 \(2\)，那么在对应的 \(a_i\) 填入 \(2\) 组数，每组包含 \(2\) 个相同的数，且各组之间不能重复。
可以发现，\(b_i\) 的出现次数一定为 \(b_i\) 的倍数。
设 \(tot\) 表示当前用来填数的最大数是多少，\(num(c)\) 表示出现次数为 \(c\) 的数用什么填充，\(rem(c)\) 表示 \(num(c)\) 还剩多少个位置没填。
直接扫一遍 \(b\) 序列，填数过程如下：
- 如果当前 \(rem(b_i)=0\)，则用一个新的数来填：\(tot\) 加一，更新 \(num(b_i)\) 为 \(tot\)，并重置 \(rem(b_i)=b_i-1\)。
- 否则，填入 \(num(b_i)\)，同时 \(rem(b_i)\) 减一。
最后验证合法性：如果存在 \(rem\) 不等于 \(0\)，则说明有数没恰好填完，故不合法。每次至多 \(tot\) 加一，故使用的数不可能超过 \(n\)。
Submission #337917883 - Codeforces
CodeForces-2137E Mexification
给定一个长度为 \(n\) 的序列 \(a\)，和一个整数 \(k\)。进行 \(k\) 次下列操作：
- 对所有下标 \(i\)，在同一时刻令 \(a_i\) 变为 \(\operatorname{mex}\{a_1,a_2,\cdots,a_{i-1},a_{i+1},\cdots,a_n\}\)。
求 \(k\) 次操作后 \(a\) 中元素的和。\(1\le T\le10^4\)，\(2\le n,\sum n\le2\cdot10^5\)，\(1\le k\le10^9\)，\(0\le a_i\le n\)。
模拟发现，经过 3 次以上操作，\(a\) 的值就会变成周期为 \(2\) 的循环。
证明：设排序后的序列 \(a\) 形如 \((0\times c_0,1\times c_1,\cdots)\)，其中 \(x\times c_x\) 表示 \(x\) 重复 \(c_x\) 次。设 \(p\) 表示第一个 \(c_x=0\) 的数字 \(x\)。
那么：
- 对于小于 \(p\) 的所有 \(x\)：
- 如果 \(c_x=1\)，那么把 \(x\) 去掉后的 mex 就是 \(x\)；
- 如果 \(c_x>1\)，那么把一个 \(x\) 去掉后的 mex 就是 \(p\)。
- 对于大于 \(p\) 的所有 \(x\)，把一个 \(x\) 去掉后的 mex 就是 \(p\)。
因此第一次操作后的 \(a\) 变为 \(a_1=(\cdots,p\times c)\)，其中 \(0,1,\cdots,p-1\) 中每个数出现 \(0\) 或 \(1\) 次。
重复上述操作，第二次操作后变为 \(a_2=(0,1,\cdots,p'-1,p'\times c')\)，其中 \(p'\) 为 \(a_1\) 中 \(0,1,\cdots,p-1,p+1\) 中第一个出现 \(0\) 次的，而 \(0,1,\cdots,p'-1\) 每个数恰好出现 \(1\) 次。
再重复上述操作，第三次操作后变为 \(a_3=(0,1,\cdots,p'-1,(p'+1)\times c')\)，其中 \(0,1,\cdots,p'-1\) 每个数恰好出现 \(1\) 次。
再继续操作，不难发现 \(a_{2k}=a_2,a_{2k+1}=a_3\)，\(k=2,3,\cdots\)。
因此暴力模拟 \(k=1,2,3\) 的情况，然后 \(k\) 为偶数则等价于 \(k=2\)，奇数则等价于 \(k=3\)。
mex 序列的处理，可以根据上述证明中的做法直接 \(O(n)\) 求出。Submission #337641758 - Codeforces
CodeForces-2137F Prefix Maximum Invariance
定义：对于长度为 \(m\) 的两个序列 \(x,y\)，设长度为 \(m\) 的序列 \(z\) 满足 \(\max\{x_1,\cdots,x_i\}=\max\{z_1,\cdots,z_i\}\)，\(i=1,\cdots,m\)，设 \(f(x,y)\) 表示 \(y\) 与任何 \(z\) 重合的位置数的最大值，即 \(f(x,y)=\max_z\{\sum_{i=1}^m[y_i=z_i]\}\)。
给定两个长度为 \(n\) 的序列 \(a,b\)，求 \(\sum_{l=1}^n\sum_{r=l}^nf(a[l..r],b[l..r])\)。
\(1\le T\le10^4\)，\(1\le n,\sum n\le2\cdot10^5\)，\(1\le a_i,b_i\le2n\)。
CodeForces-2137G Cry Me a River
A 和 B 在玩一个游戏，游戏在一个有向无环图上进行，其中节点为蓝色或红色。规则如下：
- 指定一个起点 \(u\)，A 和 B 轮流沿图中的有向边行动。
- 如果到达了无出边的节点，则 A 胜利。
- 如果到达了红色的节点，则 B 胜利。
- 如果到达的节点既是红色的，又没有出边，则 B 胜利。
给定一个 \(n\) 节点 \(m\) 条边的有向无环图，初始所有节点为蓝色。进行 \(q\) 次操作，操作分为两种：
1 u：将节点 \(u\) 变成红色，保证在操作之前节点 \(u\) 为蓝色。2 u：A 和 B 从起点 \(u\) 开始玩游戏，假设两人都以最优的方式行动，输出 A 是否能获得胜利。\(1\le T\le10^4\)，\(2\le n,\sum n,m,\sum m,q,\sum q\le2\cdot10^5\)。