B Commemorative Dice
LYF 签到题
E Imprecise Computer
题意：有一个从1到n的数列P，n小于1e6，每一轮都会将数列中每两个数比较，如果相差>1则大者胜，否则都有可能。进行两轮比较，问输入的一串数是否可能为每个数两轮比较的胜场数的差。
解：首先显然不可能有任何胜场数差>2。而且只需要考虑每个数的前一个数和后一个数即可，只有这两场会发生变化导致有差。从头向尾推，如果第一个的差为1则一定是在与第二个的比较中两轮结果不同，这种情况下：
- 第二个的差为0，则表明第二个数与第三个数比较时结果也不同，但每一轮都是胜一场败一场，或者结果都相同
- 第二个的差为1，则表明第二个数只和前面比较时结果不同
- 第二个的差为2，则表明第二个数和前面不同，和后面的结果也不同，且在一轮中两场都胜或败
如果考虑更多情况，比如到了k位置。1~k-1中只会还有0场或者1场没有着落，需要靠后面场次来契合前面的情况。如果是0，则后面的差不可能是2，因为2要到前面找一场不同的。如果后面的差是1，则解决了前面的没着落的一场或者给更后面增加了没着落的一场。
可以发现，0是可以传递前面的状态的，相当于不存在。1是改变01状态，2是规定01状态必须为1。最后状态必须是0。
（不知道怎么用语言描述了QAQ）
C Dessert Café
树神WD
J Switches
LYF （下面的是LYF写的）
题意：有n个灯和n个开关，每个灯对应多个开关，每个开关对应多个灯，按下某个开关会使得对应的灯亮暗情况发生变化。问对于每个灯k，是否存在一种开关方案，使得除了k之外的灯都暗，只有第k个灯亮。
解：把每个开关对应的灯号用二进制表示出来（如题目中输入的某一行），选择任意个开关后最终结果就是把所有行做异或之后的结果。题目也就是问用所有开关对应的数是否能异或出100..00 , 010..00 , 001..00 , … , 000..10 , 000..01每个数并输出方案，那么用异或线性基可以解决。唯一区别在于平时的异或线性基是在long long范围内的，但是这里二进制位数最多为500位，可以用类似于高精度的方法，用数组表示每个二进制，然后用循环实现异或。
ZRC:看来啥时候得学一下线性基，感觉用得挺多但是不知道是啥。
G Mobile Robot
WD&LYF 读入数据很多，有点卡常
H Needle
WD做出来FFT，ZRC在根本不知道题目什么意思的情况下用自己的板子经过WD的指示ac了
L Two Buildings
好题 整了大约四个多小时，这种类型的之前没怎么碰过，其实说破了思想还是比较简单的
题意：给$n\le1000000$个数，选取其中两个数，问两个数的和乘两个数的距离最大是多少。
$$
max{(a_i+a_j)*(j-i)}
$$
首先可以发现，对于前数而言，越靠后的就得越大才用得上；对于后数，越靠前的就得越大才用得上。否则显然能有更优的将其替代。所以可以处理出两个数组，一个是前数可能取的位置集，一个是后数可能取的位置集。
考虑选定其中一个数找另一个，发现没法做，也没有能用的数据结构。
考虑随机，发现数据范围过大且有两个变量，很难随机跑过。
考虑扫描线，大胆猜想，在处理出两个可取位置集的情况下，左数向右则必定右数不动或向右才能取到最优。证明一番（反证法）发现是正确的。然后仔细想一想就会发现性质只保证向右而并不保证单调，没法用扫描线做。
考虑二分答案，二分个鬼啊。
欸二分？
考虑分治，乍一看还是不能做。但是我们可以结合上面扫描线处的思考。对于前数的位置我们取一个mid，枚举出后数的最优位置pos，则由前面的性质，mid之前的所有前数的最优后数必然都在pos或者pos前面；mid之后的所有前数的最优后数必然都在pos或pos后面。可以分治。时间复杂度$O(n\lg n)$
LYF补 A Autonomous Vehicle
大模拟