https://atcoder.jp/contests/abc250/tasks
平面凸n边形
选非相邻点切割
求min( 8 abs(size/4 - eated))
就是选一些点, 围成的凸多边形 min(8abs(size * 3/4 - 选定凸多边形 ))
只切一次!!!!!!!!!!!!!!!!!!!!
n 1e5
x,y [-4e8,4e8]
2s
1024 mb
没做过多少计算几何相关的题目
一个想法是, 假设一个点会被保留, 想做前i个点, 第i个点保留的 最大, 小于目标的面积, 但似乎没有局部性
因为看起来像有相互冲突的背包
如果不是1/4, 是1/2呢, 我似乎1/2也不会做
干,读错题, 只切一次………….
https://atcoder.jp/contests/abc249/tasks
n个卡, 每张有正面ai,背面bi
求让正面的 xor 和 <= K时, 背面 xor和 最大
求最大值
n 1000
k (1<<30)
ai,bi [0,1<<30)
对于xor和不等式没啥想法
一个是 对结果从高位到低位去贪心
比如 第i位 结果xor为1
那么 假设当前集合中, 对应b的i位为1的选奇数个, i位为0的选偶数个
但如何控制与Ai 的关系
第二个方向就是 xor 是不是有线性基, 但是如何把线性基的 结果大小 和 对应的xor和 尽量大
第三个就是N只有1000, 有啥n^2 的方法
dp[i][j], 前i的j个, 感觉”个数” 和目标之间没啥关系
https://atcoder.jp/contests/abc248/tasks
n点无向树
点i上有值ai
C(u,v) = 简单路径u..v上 点个数 乘 点上ai的gcd
求所有点对的 C的和,mod 998244353
n 1e5
ai [1,1e5]
8s
2048mb
显然暴力算 至少要 n^2
注意到的是 Ai很小, 如果能变成 不同gcd结果的贡献值的和 就好了
有点想做容斥, 但容斥的代价函数并不能用当前gcd
如果选定一个点必定经过, 那么可能的gcd都是它的因数, 虽然这里log了,但是要找路径还是n, 这样依然是n^2 以上
再看贡献count(u..v) * gcd(a[u]...a[v])
可以转化成, u 会贡献了覆盖了u的线段次数, 每次都是u的因子
那么每个 v1…u…v2 在u上的贡献是 gcd(gcd(v1..u),gcd(v2..u)), 且v1,v2 不在u的同一个分叉上
f[child v0] = sum c0[g] x^g
f[child v1] = sum c1[g] x^g
sf[v1,v2] = f[v1] + f[v2]
ans += sf[0..i-1] * f[vi] (k[gcd(g0,g1)] += k0[g0] * k1[g1]`
= ((E+f[0]+f[1]+…+f[i]) ^ 2 - E^2 - f[0]^2 -f[1]^2 -…-f[i]^2)/2
换根dp ???
https://atcoder.jp/contests/abc247/tasks
n个人第i个, 有值Ai,Bi,Ci
考虑从中选一些
满足Ai,Bi两两不同
对于所有可能的构成 人数 = 1…k
求最大的Ci的和
n 3e4
ai, bi, [1,150]
ci [1,1e9]
2s
1024mb
emmmm, 这个ai,bi 这么小, 但感觉又像费用流+限流?
ai,bi建立点
S->ai 每个1容量,0代价
bi->T, 每个1容量,0代价
中间就是ai->bi, -Ci 代价, 然后限流让总代价小
然后为了不能让代价为负, 所以全部+Max(Ci)
最后答案 - flow * max(Ci)?
似乎就没了
https://atcoder.jp/contests/abc246/tasks
n点,1为根的树
除了根,点i上面还有值Ai
棋子初始在1
移动到叶子后结束
分数=结束游戏时棋子所在位置的值
甲要让分尽量大, 乙要让分尽量小
求分
n 2e5
ai 1e9
6s
1024mb
一眼感觉树上dp, 因为乙要让分尽量小, 所以每次乙一定操作的是当前所在的剩余树上的点
但感觉不一定操作最近的
比如
1 | 0 |
那么,最大答案是1, 乙第一次移动的是左边某个叶子的100, 因为如果不是这样, 那么甲向左走,可以得到>=100 > 1
没啥想法对于局部性, dp[i][j] = 点i为根的树已经删了j个点后剩余能得到的最大值, 但转移和范围 感觉都没想法