https://atcoder.jp/contests/abc304/tasks
给长2n的数组A,让元素配成n对，每对做xor得到长n的序列B
求 max(sorted(B)[n/2+1])
n 1e5
ai [0,2^30]
5s
1024mb
xor + max 常见思路从高位向低位贪心,
对于第b位
min(count 0, count 1) 就是能构成1 的方案数
如果 min >= n/2 +1, 那么 就是 从 b位是0和是1的分成两组，其中各选出一个，还需要对低位进行处理啊
如果 min < n/2+1, 那么就是b位无法成为1,那么0和1分成两组，这两组内部选两个排序
这两个都并不好处理，因为第n/2+1大在这过程中不光没有消掉，而且还会增加维度
https://atcoder.jp/contests/abc303/tasks
n包, i个x[i]钱
每次3选1
两人交替, 分别是X,Y, 求X-Y 的双方最优操作后的值，一个要最大，一个要最小
n 3000
xi,a,b,c,d, 1e9
2.5s
1024mb
如果没有后两种
那就是经典的dp[l][r] = 从当前开始最优差值
dp[l][r] = max(x[l] - dp[l+1][r], x[r] - dp[l][r-1])
现在多了两种批量的情况
例如其中第二个方案就是 x[l...i] + x[j...r] - A - dp[i+1][j-1], len(l..i)+len(j..r) == B
但是注意到可以变换一下
x[l...r] - x[i+1..j-1] - A - dp[i+1][j-1], len(l..i)+len(j..r) == B
令 ndp[i..j] = x[i..j] + dp[i..j]
dp[l..r] = max(x[l] - dp[l+1][r],x[r]-dp[l][r-1],x[l..r] - A/C - ndp[i+1..j-1])
不妨设 第一种是 支付E=0元，取得F=1个
dp[l..r] = x[l..r] - min(A/C/E + ndp[i+1..j-1,A/C/E])
因此 需要一个 能够快速查询
[l...r]区间内 A/C/E + min(ndp[len(l..r)-B/D/F]) 即可
minndp[l..r] 可以通过minndp[l-1..r-1] 维护小根堆转移得到
https://atcoder.jp/contests/abc302/tasks
n点树,无向边,点上 有 写有数字Ai的球 和写有数字Bi的球
令 v = 2..n 个独立问题
n 2e5
ai,bi [1,n]
2s
1024mb
考虑把1选做根
那么每次查询的就是 当前点到根的路径上每次 选一个数， 选出数字 max(distinct)
显然 ans[u] - ans[fa[u]] \in [0,1]
如果单次求， 就是做并查集， 对于是树的 贡献 = 边
对于 不是树的（边 >= 点) 贡献是点
听起来 需要一个 可持久化 并查集?
点+点 = 树(+1)
点+树 = 树(+1)
点+图 = 图(+1)
树+树 = 树(+1)
树+图 = 图(+1)
图+图 = 图(+0)
树内部 = 图(+1)
图内部 = 图(+0)
https://atcoder.jp/contests/abc301/tasks
三维空间 n个人, 整点坐标(xi > 0,yi,zi), 两两坐标不同
需要选点p(x<0,y,z) , 在 x正向拍照
p,A,B共线，则后面的人不被拍到
想办法找点p 让被拍到的人的人尽量小， 求最小被拍到的人
n 50
x [1,1000]
y,z [-1000,1000]
4s
1024mb
二维空间几何都还不熟，这里来个3维的
但为什么看起来 逻辑很简单，只是实现不知道
既然N 只有50, 那么就是 暴力选4个点， 这样两条线找交点
这样再去枚举交点
一个特殊情况是有一条线上 有很多点，那么这条线上任意一个位置都可以
那么问题来了，如何找三维空间中的交点
感觉就是先抛弃 第3维，直接计算(x,y)的交点, 再验证z?
似乎卡着时间过了, 一次TLE一个点，一次AC
https://atcoder.jp/contests/abc300/tasks
<= n 的，且所有质因子 <= p的数的个数
n 1e16
p 100
4s
1024mb
dfs(上限, 质数列表idx) = sum dfs(上限/ 质数[idx]^pwr, idx-1)
然后对于底部做cache
然而并不理想，有cache和没cache 1e15都需要 8~12s,
跟别说1e18
另一个角度是，既然题目都告诉了最大的范围的答案大约是2e10, 所以它大也不算大,
所以考虑meet-in-middle
似乎就过了