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
似乎就过了
https://atcoder.jp/contests/abc299/tasks
6面骰子(1…6), 正整数R
每次投骰子, X=历史所有骰子的和, 如果 X-R是 1e9的倍数, 操作退出
求 退出时, Exp(次数C), mod 998244353
R [1,1e9)
2s
1024mb
p(t,k)= t次 和=1e9 k + R, 且 < k的时刻没有达到等于
$\displaystyle ans = \sum_{t=1}^{\infty} \sum_{k\in [\frac{t-R}{10^9},\frac{6t-R}{10^9}]} p(t,k)t$
或者能否 p[s] = 和达到s的概率
这样看起来似乎可以矩阵转移，快速幂 合并？
https://atcoder.jp/contests/abc298/tasks
H行W列
有s[i][j]个草莓
每次切割，把一个剩余块横向或纵向切成两块
t次切割后，让 一块最多草莓 - 一块最少草莓 尽量小
h,w [1,6]
s[i,j] [0,10^16]
6s
1024mb
dp[l,r,t,b,t] = set<pair<min,max> >
因为min越大 max可能也会增大，所以min max应该 成对
这样状态数比较大
注意到状态合并
左侧[min,max] =>
若右侧 l >= min, 取 min(max,右侧r)
若左侧 r <= max, 取 max(min,右侧l)
否则 l < min and max < r 则是 [l,r]
但这样也很大