https://atcoder.jp/contests/abc249/tasks

G - Xor Cards

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

G - GCD cost on the tree

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

G - Dream Team

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

G - Game on Tree 3

n点,1为根的树

除了根,点i上面还有值Ai

棋子初始在1

  1. 乙 选一个非根点,修改值Ai = 0
  2. 甲 把棋子移动到当前所在的一个子节点上, 随时可以结束游戏

移动到叶子后结束

分数=结束游戏时棋子所在位置的值

甲要让分尽量大, 乙要让分尽量小

求分

范围

n 2e5

ai 1e9

6s

1024mb

我的思路

一眼感觉树上dp, 因为乙要让分尽量小, 所以每次乙一定操作的是当前所在的剩余树上的点

但感觉不一定操作最近的

比如

1
2
3
         0
1 1
100 100 100

那么,最大答案是1, 乙第一次移动的是左边某个叶子的100, 因为如果不是这样, 那么甲向左走,可以得到>=100 > 1


没啥想法对于局部性, dp[i][j] = 点i为根的树已经删了j个点后剩余能得到的最大值, 但转移和范围 感觉都没想法

閱讀全文 »

https://atcoder.jp/contests/abc245/tasks

G - Foreign Friends

N个点, 第i个人颜色是Ki

其中一些点是好的点

初始没有边

有m个可选边, 第i个可以花费 Ci 让ui和vi连一条边(无重边自环)

对于每个点, 独立的求最小代价 让它和一个异色好点连通, 或报告不可能

范围

N 1e5

M 1e5

我的思路

既然是每个到异色好点最短距离, 那么路径上一定都是同色或非好点

目前思路是 按一个颜色的个数能不能根号分治

另一个是记录到每个点最小代价不同色的两个最近点

考虑用Floyd+提前退出? 问题是 时间复杂度怎么估计和保证

閱讀全文 »
0%