IEEExtreme 2021

和 xry111 、zzs 组队

总结起来就是躺平了，总共25个题，就写了6个题，其中还有一个是zzs施舍的

Rigged Dice

两个骰子，一个正常，另一个随机数的比例是 1:1:1:1:1:2，两人掷完累计不同交换骰子，1000轮，问哪个不正常。

模拟就好，看哪个骰子分多。

等价与一个序列，求本质不同子序列数，且选数下标满足 (|p_i-p_{i-1}| > K)

zzs提供的做法：从后向前dp，记录每个数在满足 (j-i>K) 前提下最新出现的下标。如果一个数要选，那一定选能选的最靠前的，否则会有重复计数。

给一个非负矩阵，求框0~2个 (X imes Y) 或 (Y imes X) 子矩阵，不相交，且和最大

枚举行列为分界线，上面选一个，下面选一个就好

交互题，有一个排序 (p)，询问 (a,b,c,d)，要求互不相同，回答 (p_a+p_b ? p_c + p_d)，(?) 为 (>)、(=) 或 (<)。最后要给出这个排列。(N=5,10,20,40,80,160,320,640,1280,1500)，要求 (Qle 30000)

如果知道两个数只差 (1)，就可以对其他的数排序，考虑找到最大的两个数，就可以排序，(Q) 差不多就是 (nlog n) 级别的。

找最大的两个数：维护不超过4（最后是不到4）个数的集合，每次加数，到一定级别就单循环询问一遍，赢得两个人得分，把得分少的去掉，这样发现可能辨别不出来最大的几个数。之后选择再做一次，找到最小的几个数。再合并这样就应该能辨别出来

然后写个cmp用merge_sort排一遍，用stl的sort稳定超。

最后应该比较极限，调了半天参数，交互器也不是个确定的，多交几次就过了。

一张五向图，给 (S,T)，找一个点使得删掉这个点后 (S,T) 依旧联通，但是最短路最长。

写了个在最短路上删点得暴力，之后都是 zzs 搞的

想了个和每个元素都是 0/1 等价，然后发现样例过不了。

之后都是zzs搞得

有一个有边权的树，边权可能为负，多组询问问 (x,y) ，求最大的 (L)，使得存在一个序列 (a_i) 使得 (a_1=x,a_n=y)，(dist(a_i,a_{i+1}) ge L)，(nge 2)

一开始做法是先能找到离每个点最远的点（写了点分树，后来发现对于每个点都要找，可能不需要），然后以为只会迭代两三层就可以，但是这样全是负权的图就能卡掉，后来想到更恶心的就是正负全相间的图。

之后换了个思路，如果暴力去做就是找到任意两个点之间的距离，作为新边，进行最大生成树，在路径上查最小值即可。沿用这个思路，把每个点离它最远的点记为关键点，用这些关键点到每个点见的距离作为新边，最大生成树，就能得到 83.3% 分。之后再乱搞也没更多。

开始用c写了

main(i){char s[97];gets(s);for(i=0;s[0]^"TKMSCDcvTTwWTA"[i];++i);if(!i){for(;s[4]^" NEo"[i];++i);i="AIJM"[i]-'A';}printf("%d",i+1);}

自以为很短，简直小丑

可以先通过平面方程转换成二维的问题，就是多边形的类欧，然后感觉边界情况很多，自己和很萎，就一直没写

用 2-4 种颜色染 (N imes Mle 75) 的矩阵，有些点不能染，其他点必须染，且四方格里相同颜色数不能达到 (3)

裸的轮廓线dp

最后要把4的情况改成位运算，要不然编译器不优化代码

二维的带通配符的匹配问题，记得Claris讲过

xry111 写二维卷积，当时我还萎着，还剩三分钟的时候发现还没有提交，上演了生死时速把暴力写了。