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

Ex - K-Coloring

n点无向图

m 边

点赋值 [1,k] 相邻点值不同的方案数 mod 998244353

n 30

m [0,30]

k 1e9

8s

1024mb

我的思路

m 30, n 30, 想到的30相关的就是2^{30/2} 的meet-in-the-middle, 但没什么具体的想法

方案统计

对于一个具体方案，考虑按照 点的index顺序从小到大交换

例如 1染色x , u染色1, 那么把所有x和1染色的交换成1和x, 那么得到的依然合法

这样 index顺序虫小到大 染色c个的方案数 f(c)

ans = sum f(c) A(Permutation)(k,c)

1
2
3
4

dfs(u, cntcolor){
  color[u] = [1..cntcolor+1] and !=color[v in connect[u]]
  dfs(u+1, max(cntcolor,color[u]);
}

感觉复杂度会爆炸?吧?

不同难搞，要不然就是反过来容斥 相同

属性i = 边i连的两点颜色相同

ans = sum (-1)^count(属性…) g(属性…)

这个问题就是 $2^{30}$太大, 需要拆分

右侧的g()=k^{未连通块个数}

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

Ex - Optimal Path Decomposition

n 点树

找最小整数k，使得有方案满足染色

• 每个相同具体颜色，连通且简单路径
• 树里所有简单路径 最多K种颜色

n 2e5

2s

1024mb

我的思路

这第一眼上去像是重轻儿子

第二眼上去像是树上DP

虽然具体的染色的情况 不和 K直接相关

但是 当两个不同颜色链的端点相邻，那么把它们染成同样的颜色，得到的K不会比之前的更差

dp[u][u是否可以向上连] = {u的子树中最多颜色的路径，从u向下最多颜色的路径}

显然 子树cnt >= u向下

看起来是一个 O(n^2) 的状态

而从u 向下最多颜色的路径 <= u到最深叶子的

如果有办法 把这个缩减这个向下颜色的路径的维度

然而根据轻重儿子的链式方法，根到任何叶子最多经过O(log(n)) 条不同的重链

所以如果直接 轻重链方案，那么方案 <= 2log n

所以 dp[u][u是否可以向上连][u向下最多的颜色的路径 <= 2log n] = u子树中最多颜色的路径

似乎就能做了?

https://codeforces.com/contest/1830

B - The BOSS Can Count Pairs

长度n数组 a,b

计算多少对 i < j 满足 ai * aj = bi + bj

t 1e4

sum n 2e5

ai,bi [1,n]

4s

512mb

我的思路

加的范围保证了 <= 2n

所以 对于同样的a 直接整合

然后 2n (1+1/2+1/3+…), 所以真的枚举的 乘法对是满足范围的

然后对于具体的 v0=ai,v1=aj

那么对应 bi/bj 是两个集合, 或者map[b]=count

每次选小的 去大的里面搜, 这复杂度不知道多少, 过了pretest,被hack tle了

https://codeforces.com/contest/1830/submission/207625447

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

Ex - Balanced Tree

给定n点树T

构建n点新的有根树R满足

• lca(u,v) 在 T中的path(u,v)上

• 所有非根点u, 2sz[u] <= sz[fa[u]]

(题目保证有解)

输出R

n 1e5

2s

1024mb

我的思路

显然 性质2说明所有向下分叉至少是2叉

性质一怎么用?

如果在R中u是v的祖先节点

lca(u,v) = u

u一定在路径T(u,v)上

…

v1,v2 在 u 两个分支, lca(v1,v2) = u

u要在(v1,v2) 路径上

…

如果u选作 R的根, 那么在T 中u的一个分支中的所有点一定在R中也是同一个分支中

所以要在T中找一个点，使得它的所有分支的点数 * 2 都 <= n

注意到 任意点最多一个分支 点数 * 2 > n, 所以沿着这个方向走，这个方向的点数单调递减

而 …-u-(v > n/2), 则从选择u移动到选择v: (…-u < n/2)-v-(…)

所以总可以找到一个点

那么选作为根以后，直接按它切开，剩余的连通块就是子问题了

但是如何 优化每次寻找?

还是直接暴力复杂度就够了

注意到第一次是O(n)

那么第二次每个块 <= n/2, 而总复杂度依然是O(n)

所以 O(n log n) 暴力就没了

写完以后发现，不一定是 所有二叉，因为 两点的话 ，叶子是1, 带叶子的一个是2也是合法的，所以二不二叉不重要，重要的是所有分叉 <= n/2

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

G - Edge Elimination

perfect k(>=2)叉树,深度D(根深度=0)

问最少剪掉多少边，存在一个点数为X的连通分量

数据足数 t <= 100

原树点树 <= 1e18

2s

1024mb

我的思路

如果 选定连通分量 再剪断边

那么 显然连通分量的所有点有唯一lca，那么如果这个lca不是根的化，只需要在lca的父向边剪断

而对于指定了根以后，剩余的全是从指定根向叶子向的连通路径

因此每次剪断边相当于减去 1+k+k2+… = (k^?-1)/(k-1)

注意到 点<=1e18

log2(1e18) = 59.794705707972525, 即 D <= 60

所以对于指定根来说 可以枚举根在哪一层

x = (k^{d+1}-1)/(k-1) - a1(k1-1)/(k-1) - a2(k2-1)/(k-1) - a3(k3-1)/(k-1) -…

min(a1+a2+a3+..)

然后注意到 不同层的点的剪断次数之间还有限制关系，所以 这像是一线性规划?

一个方向是考虑 k = 2时，就是二叉树

每次都是减去 2^d-1

1
2
3
4
5
6
7
8
9
10
11

1110101011011110
1111111111111111
    111111111111
    111111111111
      1111111111
      1111111111
        11111111
        11111111
           11111
           11111
               1

想要从高到低 贪心（数位dp?）但证明不了??

但这样至少是可行解不一定是最优解