非传统题型

好哒，总结一下，今天上午讲的主要是非传统题型。
我喜欢这种题型！
好的，我们来看一看
A） Hamilton https://vjudge.net/contest/645884#problem/A
巧妙的转换：把矩阵当作临接矩阵，题目转化为寻找图上一条哈密顿路，使得其颜色接近纯色（纯黑、纯白、纯黑拼纯白），然后用加值发不断试图插入新的值。
B） GCD Queries https://vjudge.net/contest/645884#problem/B
非常好的一道交互题，存在一个0—n-1的排列，要求在2n次gcd询问之内求得0的位置（输出2个值，0在其中一个）
考虑维护两个数a，b，在3~n范围内枚举i，
设u=gcd(a,i),v=gcd(b,i),
若u=v -> i!=0
u>v -> b!=0
u<v -> a!=0
因为gcd(0,x)=x>=gcd(i,x)
这样我们可以在2n次询问之内排除掉n-2个位置，剩下2个输出。
C）Mapa https://vjudge.net/contest/645884#problem/C
巧妙的交互题，我们考虑，输入N对整数组成键值对，要求将这N对对应关系一一压缩，缩成一个长度<=3000的01串，容易发现它可以传递3000bit的信息，又因为题目中x<=10的9次方，所以我们需要30bit来传递一个数，N<=100,所以每对数我们只能传递一个数字，怎么办？
然后这里我们意识到，我们只需要传递一个对应关系，令输入键可以得到值就好了。
这里我们需要引入一个重要的知识点：拉格朗日插值，它可以让我们根据给定的n个(x,y)，得出过每个点的（n-1）次函数，从0~n-1，我们传递n个系数，组成一个n-1次函数，恰好可以达到我们的要求。
怎么写？我回头学习一下再考虑。
D）想法
根据题意，我们有N个题目与M个不同的想法。
我们由想法组成题目，题目与想法之间的依赖关系组成一条树。
对于组合出来的题目，我们要求知道每个题目涉及了几个想法。
由题目，N与M很大，如果我们考虑暴力，时间复杂度可以达到M²级别。
题目中有提到答案误差不超过25%为正确，所以我们考虑随机。
我们对于每个组合出的问题，储存它的前i个叶子节点，我们为每个叶子节点随机分派权值。根据期望，若第K小权值为Fk,随机上限为MAX，则Fk/MAX=k/ans,其中ans就是我们要求的答案。
我们令k=50，多随机几套权值，就可以得到答案。
E） Secure Password
呃后面不贴网址了，比赛总网址：https://vjudge.net/contest/645884
题意：对方有一个长度为N的序列，每项为Ai，N<=1000,Ai<=2⁶³-1，我们可以向他询问13次，了解任意个Ai的或和。要求对于每个Ai，求出除它以外的其他项的或和。
题解：首先考虑一种简单情况，假设我们可以询问20次，该如何求解。首先我们为每个项编号，用二进制表示出来，容易发现可以在2的十次方之内编号。然后我们每次对一个二进制位询问，询问这一位为0的数的或和与为1的数的或和。总计询问20次，然后对于每个Ai，我们把与i的二进制位不同的数全都或起来，就得到了题目要求的值了。
然后进行分析，我们本质上是对这N<=1000个数编组，对每个组内的值求或，要求是可以通过组的组合，组合出每一个不包括i的或和。
Trick：C{13，6}=1713>1024，所以我们对每个点赋一个13位中有6位是一的二进制数，对于13次询问，我们每次询问这位为1的数的或和。在输出时，我们对于每一个有一个二进制位与i不同的或和或起来，就是我们需要的答案。

按照二进制位询问，\(10\) 位，每一位问这一位为 \(0\) 的所有下标的 or，问这一位为 \(1\) 的所有下标的 or。那么与 i 不同的下标必然存在一个二进制位与它不同，询问时我们枚举每一位，假设 i 这一位为 c，那么把这一位为 1-c 的答案 or 起来。
为什么我们要询问 0？不询问 0，那么互为子集的数之间有影响。
注意到 \({13\choose 6}=1716>1000\)，我们取所有 13 位的含有 6 个 1 的二进制数作为每个位置的编号（与 i 不同的位置一定在某个 i 为 0 的位为 1）。因此我们只需枚举每一位，询问这一位为 1 的所有下标的 or。询问时枚举每个 i 对应的数不含有的位，把这些位的答案 or 起来。
F）Sanae and Giant Robot
根据题意，我们有两个长度为N的序列，ai与bi,我们的目的是将ai的每一位都转化为bi,与此同时，我们有m个区间,(li,ri)，我们可以将这段区间内的ai全部转化为bi当且仅当sum ai (li~ri)=sum bi(li~ri)
我们可以设置一个数组ci=ai-bi,并做一个前缀和操作。对于每个区间li~ri,我们可以进行区间覆盖当且仅当c(li)=c(ri)，将其间ci全部化为c(ri)。这里我们就意识到，当cr!=0时，操作毫无意义。所以我们寻找cr=0的点，并bfs寻找其他ci=0的点，进行区间覆盖。
G）8染色
N点M边的无向图进行染色，要求用8种颜色，保证每条边两侧点的颜色不同。
8染色是典型的NPC问题，不能在多项式时间复杂度内计算，但是我们有一个已知可行的答案，需要将它压缩成一个长度为L的01串传递过去。L<=m/2.我们发现，其实我们只需要知道度数大于等于8的点的颜色就够了。
设这种点数量为X，8x<=2M,x<=M/4;但是每个颜色必须用3个二进制位去表示，这样我们就需要3M/4个二进制位了，怎么办？
我们可以对与于每个8度点，都将1、2；3、4；5、6；7、8号颜色压缩成一种。这样问题就转化为2染色问题，可解。那么每个颜色需要2个二进制位，刚好可以用完M/2个bit。
这里我们也认识到了解决数据传输问题的两种策略：减少发送信息的数量，减少每个信息的内容。
I）Weights
N个砝码，质量ai,要求一次放入1个砝码，达成题目要求的左右倾斜变化，（平衡时可以视为同时满足左右要求），输出每次放上的砝码编号和托盘编号。
我们考虑轮流放上左右左右的砝码，先对每个砝码排序，我们依据题意，若最开始左偏，就先确定一个圆形（表示放在左边），然后观察下一个要求，若是右偏，就在圆形大小顺序的右侧画上一个方形表示右偏；若是左偏，就在圆形左侧画上一个方形，表示右盘放一个小砝码。最终我们得到一串交替的圆方，表示每个顺序的砝码放在了左侧还是右侧。按照确定的顺序放置就可以了。