green_gold_dog, array and permutation
算法本质
思维
题目大意
给定长度n的数组a[]，现在需要构造长度n的排列p[]，存在数组c[i] = a[i]-p[i]，使得c[]中不同元素个数最大化。
输出p[]信息。
思路推演
c[]并不要求顺序、p[]也可以完全自定义，发挥空间是很大的。
先想一想是否可以达到n个不同值，然后发现通过对p[]元素大小的调配就可以做到。
XOR Palindromes
算法本质
思维
题目大意（抽象）
给定01串s，定义数字x为美丽：
- 存在某个方案，反转
s中的x位（不能同一位反转）能使得s成为回文串
输出一个长度n+1的01字符串t，枚举i从0至s.size()，若i是美丽的，则t[i]=1，反之为0。
思路推演
首先将s对称的来看——s[i]和s[n-i]视作一对（0下标）
记录两者不同的对数为cnt。
这部分是必须且只能操作1次的，剩余的对都可以操作0次或2次——除了当n为奇数时，存在一个数的对，其可以操作0次或1次。
所以可以分类讨论：
n是奇数
最小操作数：cnt，最大操作数：n-cnt，其中间数都是可行的n是偶数
最小操作数：cnt，最大操作数：n-cnt，其中间数，与cnt模2同值的数可行
Salyg1n and the MEX Game
算法本质
思维
题目大意
Alice和Bob玩游戏，初始给定无重复数字、大小n的集合set，随后Alice先手两人轮流行动，但是各自的规则有所不同：
- Alice
插入一个范围[0, 1e9]的数字，不可与集合数字重复 - Bob
删除集合某个数字，保证严格小于Alice上次插入的数字
注意，游戏当Bob无法操作或者Alice执行了其n+1回合时结束，这意味一定是Alice走后结束游戏，set最终大小是n+1。
交互题，Alice由玩家扮演，输出每回合策略，尽量使得set的MEX值最大。
思路推演
既然的MEX值，则0的存在一定关键。
- 最开始无0
则Alice的最后一步一定是放0，可以接着思考一下1是否存在的情况，随即发现——若Alice一开始不补0，则最后值至多为1。所以补0一定是最优解 - 最开始有0
稍加模拟可以发现，因为是Alice走最后一步，所以无论Bob如何破坏，Alice都可以即使修补，所以只需要把最开始的数字用于提高MEX值即可，随后Bob如何行动Alice就跟随行动即可
Cyclic Operations
算法本质
思维
题目大意
初始存在长度n的全0数组a[]，给定长度n的数组b[]，其元素大小范围[1~n]，接下来希望通过若干次以下操作使得a[]变为b[]：
- 构造一个元素各不相同的长度
k的数组c[]，元素大小范围[1~n]，使得a[c[i]] = c[i%k+1]（同时改变）
输出是否可行。
思路推演
思考操作本质，其与i无关，更像构建一个循环数组，且a[]的元素可以覆盖的。
这使我们想到，所有可行的b[]，其最后一次操作的元素都未被覆盖。
通过观察其特征，发现其组成了一个简单k环——借助于此可以发现，操作的本质就是构建一个简单k环，只不过结果可以被覆盖，询问b[]是否可以被构建出来。
通过模拟可以发现，除了长度k的环，其他长度的环都无法构建出来，但是任何链是可以构建的。
考虑到题目特征，使用拓扑跑一下图，最后仅剩下简单环，再检查环的长度即可。
Salyg1n and Array (hard version)
算法本质
思维
题目大意
已知偶数n k，存在长度n的元素未知数组a[]，玩家仅可执行操作：
? p
询问a[p ~ p+k-1]的异或和，随机a[p ~ p+k-1]的顺序会反转
在至多57次询问后，输出a[1~n]的异或和。
1 <= k <= n <= k^2 <= 2500思路推演
当k是n的因数时，显然简单，考虑k非n公因数的情况，那核心就是异或结果的部分相消。
从简单样例出发，比如3 2，同时可以看一下为什么要保证n k都是偶数。
模拟时可以发现，我们仅能得到a1^a2 a2^a3 a1^a3，是无法得到a1^a2^a3。
稍加思考可以发现，对于n=3而言，以元素个数的加法来看，最合理的构建方法是：3=2+1，这个2可以由一次操作得到，而1无法得到。
随后思考6 4，合理的构建方式是：6=4+2，4也可以由一次操作得到，这个2如何得到呢。
我们唯一的手段只有异或结果的部分相消，因为每个基本操作的异或元素个数都是k，所以相消存在对称性。
先不考虑反转的情况，若存在a b c d e，则一次操作得到a^b^c^d，另一次操作得到b^c^d^e，两者异或得到a^e，这样就是2个元素了。
接着考虑反转，惊喜发现a b c d e在类似上面操作后，其分布可以视作a e b c d，我们可以得到a^e的结果——这意味在得到2个元素的异或值的同时，我们将这两个元素边缘化了！
假设目前n=2b、k=2a，且k < n < 2k
接下来严谨的求解：
对于2b的长度来说，一个比较好的方案是：2b = 2a + 2(b-a)
重点是处理这个2(b-a)，依照上面的思路，将整体的前b长度提取出来，顺序分成3个部分：b-a 2a-b b-a，这三个部分分别称之为A B C
1.
先基础操作得到A^B的值，因为A+B部分需要反转，反转后将这部分顺序分成2个部分：b-a 2a-b，分别称之为A' B'
2.
随后基础操作得到B'^C的值，总体上顺序可以视作A' C B'，因为其内部顺序在之后的操作中无关紧要
由于A^B = A'^B'，所以可以得到A'^C的值
其中A'和C的长度都是b-a，这样就将多余的2(b-a)放在边缘了，后面部分仅需分成k长度的部分即可对于上述n >= 2k的情况，同样类似操作即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
void ask(int x) {cout<<"? "<<x<<endl;}
void hui(int x) {cout<<"! "<<x<<endl;}
inline void solve()
{
cin>>n>>k;
int ci=n/k, yu=n%k;
int ans=0;
for (int i=1; i<ci; i++) // 前面保留 k+yu个元素
{
int pos=i*k + yu + 1;
ask(pos);
ans ^= in();
}
int res=0;
ask(1);
res ^= in();
if (yu>0)
{
int b=(k+yu)/2, a=k/2;
ask(1+b-a);
res ^= in();
ask(2*b-2*a+1);
res ^= in();
}
ans ^= res;
hui(ans);
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)