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个点后剩余能得到的最大值, 但转移和范围 感觉都没想法
https://atcoder.jp/contests/abc245/tasks
N个点, 第i个人颜色是Ki
其中一些点是好的点
初始没有边
有m个可选边, 第i个可以花费 Ci 让ui和vi连一条边(无重边自环)
对于每个点, 独立的求最小代价 让它和一个异色好点连通, 或报告不可能
N 1e5
M 1e5
既然是每个到异色好点最短距离, 那么路径上一定都是同色或非好点
目前思路是 按一个颜色的个数能不能根号分治
另一个是记录到每个点最小代价不同色的两个最近点
考虑用Floyd+提前退出? 问题是 时间复杂度怎么估计和保证