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+提前退出? 问题是 时间复杂度怎么估计和保证

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

G - Construct Good Path

n点m边 简单无向连通图.

边长=点数

构造一条 长度小于4N的边, 让点i出现次数%2 == s[i]

范围

n 1e5

m 1e5

2s

1024mb

我的思路

说是图, 但是树也是图, 所以树应该也可以, 所以 先从图中随便提出个树再在树上做

显然树上有个不满足个数的方案

根到点再返回根, 这样走完所有再决定 根需要奇数次还是偶数次

但这样搞次数肯定超了

考虑树上两种,一个是成链,一个是分叉

链上 a-b-c-d-e-f-g-h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

abcdefgh
xxxxxxxx
      x
     x
      x
     x
    x  
   x
    x
   x
  x
 x
  x
 x
x

然后是分叉, 考虑分叉= 多个链合并起来, 主要关注一下合并处的奇偶

1
2
3
4
5

 a
 b
 c
d f 
e g

可以看成a b c d e 和 c f g 两条链

c的奇偶性 = 原来c的奇偶性 + 1(额外链数)

似乎就没了, 因为新增的链 对 链头的重复可以看成链尾上多一次,这样每个点次数不超过4, 最后判断根要奇还是偶即可

但是感觉好难写啊