比赛在\(9\)月\(25\)日，从\(9:00\)到\(12:00\)，3h四题。
一开始用10min看了题，之后就还是选择开T1
T1：
给两个序列\(\{a_n\},\{b_n\}\\\)，每次可以选择两个数\(i,j(i\not=j)\)，把\(a_i\)赋值为\(a_i+a_j\)或\(|a_i-a_j|\\\)，判断能否经过若干次操作后成为序列\(\{b_n\}\\\)，多组数据，\(T\leq 10,n\leq10^5\)
操作后序列最大公约数不变，所以两个序列的最大公约数一定要相等。
最大公约数相同时构造方案：
先经过若干次操作后得到最大公约数，再把其余所有位置减成\(0\)，最后做“辗转相除法求最大公约数”的逆运算即可。
时间复杂度\(O(Tn \gcd())\)
\(9:18\)做完后开T2
T2：
给一个\(n\times m\)的矩阵\(C\)，你需要构造一个序列\(\{a_n\}\)满足\(0\leq a_i\leq m,\sum\limits_{i=1}^na_i\leq m\\\)，定义\(b_i=\max\limits_{j=1}^{a_i}C_{i,j},a_i=0\)时\(b_i=0\)，你需要最大化\(\{b_n\}\)中的第\(k\)大值，\(\\n,m\leq1000,C_{i,j}\leq10^9\)
二分，对每行预处理前缀最大值，二分找到第一个大于等于\(\operatorname{mid}\)的位置作为该行的权值，按权值从小到大排序，判断前\(k\)个权值之和是否小于等于\(m\)
时间复杂度\(O(nm+n\log n\log V)\)
\(9:30\)就写完了前两题，有点慌，用10min写了T2的对拍，之后开T3
T3：
\(n\times m\)的矩形，每个位置只能填\(0,1,2,3\)，有些位置填过了，\(\\\)要求每个\(2\times2\)的子矩形内填的数的和模四余一，\(\\\)判断是否有合法方案并构造一种，多组数据，\(T\leq 10,n,m\leq10^3\\\)，部分分:\(10\%,n\times m\leq 10\\\)，另外\(60\%\)每行每列最多填了一个
想了一会，没想到正解，部分分都拿了，\(10:30\)才开T4
T4:
有\(n\)个圆，第\(i\)个圆的圆心坐标为\((x_i,y_i)\)，执行\(m\)次操作，每次操作以\((0,0)\)为起点画一条经过\((a,b)\)的射线，拿走直线上离原点最近的圆，求拿走的所有圆的半径的平方之和，\(n,m\leq 10^5,1\leq b,y_i,r_i\leq 10^5,|a|,|x_i|\leq10^5\)，这些数都是整数，任意两个圆的距离大于等于\(2\)，部分分：\(70\%\)每条射线只过一个圆，其中\(30\%\)满足\(n,m\leq3000\)
想到应该可以把每个圆先按离原点距离从小到大排序，对应的射线斜率范围求出来，将其和询问的斜率其离散化，用线段树来维护加圆、查询、删圆
注：由于\(a\)可以取\(0\)，所以考场上我算的是斜率的倒数
线段树的\([l,r]\)的节点就用vector存下\([l,r]\)共同有的圆，删除就用lower_bound删，单点查询就查询线段树上经过的节点中编号最小的圆就行。
但是，调了1h，第二个样例一直输出0，感觉是求范围的炸了，马上打了个\(30\%\)就结束了。
T2已经拍了\(8\times10^4\)组了，不会错了吧。
估分：\(100+100+70+30=300\)，希望别挂
事实证明，T4应该用set，但是已经无所谓了（这次考的又没用）