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?）但证明不了??

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

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

Ex - Trio

整点A,B,C 每个时刻 +1/-1 等概率

求 T时刻, A,B,C首次三个同时共点的概率 mod 998244353

范围

A,B,C,T [0,1e5]

2s

1025mb

我的思路

p(t) = t时刻首次共点

q(t) = t时刻共点

h(t) = 初始共点, t时候后依然共点

p(t) = q(t) - sum(i < t) p(i)h(t-i)

首先如果能快速/预处理求q和h，就是个分治的卷积

那么问题是如何求q和h

先sort A,B,C

考虑间距(d0,d1)=(AB,AC)， 这样的话，h不过是初始(d0,d1)=(0,0)的q的特例而已，所以如何算q?

那么是1/8等概率

1
2
3
4
5
6
7
8

(+0,+0)
(+0,-2)
(-2,+0)
(-2,-2)
(+2,+2)
(+2,+0)
(+0,+2)
(+0,+0)

似乎比较难弄其 个数关系?

容斥似乎也不好容斥

换成距离考虑A增加dA,B增加dA+AB,C增加dA+AC

P(t,d)=t时间，增加d的概率:

1
2
3
4

d = inccnt - deccnt
t = inccnt + deccnt
inccnt = (d+t)/2
P(t,d) = binom(t,(d+t)/2) / 2^t

q(t) = for dA: sum p(t,dA) * p(t,dA+AB) * p(t,dA+AC)

这样 对于给定t 需要(幂次和binom可以预处理) O(t) 来算

https://codeforces.com/contest/1824

B2 LuoTianyi and the Floating Islands (Hard Version)

n点边权1的树, 问对于任意k个不同指定点，到这k个指定点距离和最小的点的个数的期望值 mod 1e9+7

k <= n <= 2e5

2s

256mb

我的思路

k = 奇数，显然有唯一重心, 期望为1

k = 偶数，对于点u, 则其所有链接的子树 不能有 > k/2个指定点

合法的方案数 cnt = for u, for v is child of u, (binom(n,k) - sum binom(sz[v],j)binom(n-sz[v],k-j),j <= k/2)

但直接暴力显然TLE