和 xry111 、zzs 组队

xry111: https://icpc.xidian.wiki/person/xry111/misc/2021-ieeextreme

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

Rigged Dice

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

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

Language Learning

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

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

Maximum Exploitation

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

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

Secret Boxes

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

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

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

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

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

* The Tortoise and The Hare

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

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

* Big Matrix Small Determinant

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

之后都是zzs搞得

Xtreme Teleportation

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

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

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

* Xtreme Winners

开始用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);}

自以为很短，简直小丑

* Polygon

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

Coloring Tiles

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

裸的轮廓线dp

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

Image Convolution

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

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