Atcoder abc290

發表於 2023-05-27 更新於 2025-07-05 分類於 Atcoder ， ABC Disqus：文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘

G(贪心)Ex(数学)

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

1110101011011110
1111111111111111
    111111111111
    111111111111
      1111111111
      1111111111
        11111111
        11111111
           11111
           11111
               1

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

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

閱讀全文 »

Atcoder abc289

發表於 2023-05-23 更新於 2025-07-05 分類於 Atcoder ， ABC Disqus：文章字數： 1.4k 所需閱讀時間 ≈ 5 分鐘

Ex(inverse of polynomial,生成函数,NTT)

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等概率

(+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的概率:

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) 来算

閱讀全文 »

Codeforces Round 872

發表於 2023-05-08 更新於 2025-07-05 分類於 Codeforces ， Div1 Disqus：文章字數： 3.2k 所需閱讀時間 ≈ 11 分鐘

B2(树,数学)C(树上启发式合并)D(离线,线段树,二维前缀和,跳点,线段树维护一次方程)

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

閱讀全文 »

nowcoder 牛客练习赛109

發表於 2023-03-03 更新於 2025-07-05 分類於 NowCoder Disqus：文章字數： 1.4k 所需閱讀時間 ≈ 5 分鐘

E(点分治)F(不看题解不懂题意)

https://ac.nowcoder.com/acm/contest/51721

E - 有向树

n点树,点上有值a[i]

所有边可正向可反向(2种状态)

一个具体的图的价值 = 图中 u可达v ,则贡献 |a[u]-a[v]|

求边所有2^{n-1}个图的价值和

范围

n 2e5

ai [1,1e9]

1s

256MB

我的思路

显然 u..->..v的贡献了2^{n-1-length(u,v)}次

提出来前面就相当于边权1/2了

想的是树上启发式合并

这样每次节点的合并都是小点向大点合并，重儿子就是全部成靠移动和全部乘上1/2, 上个线段树

这样似乎是 O(n (log n)^2) 吗?

只过了21~28%

閱讀全文 »

Atcoder abc288

發表於 2023-02-09 更新於 2025-07-05 分類於 Atcoder ， ABC Disqus：文章字數： 2.6k 所需閱讀時間 ≈ 9 分鐘

G(找规律)Ex(递归,容斥,DP,排列组合)

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

G - 3^N Minesweeper

[0…3^n-1]的位置上有0个或1个炸弹

如果两个数在三进制表示下，所有对应位的差<=1,那么两个数相邻

对于p=0..3^n-1 位置p相邻的位置上有 $a[p]$个炸弹(包括自己)

请构造一个满足的方案

范围

n 12

2s

1024mb

我的思路

3^12 = 531441

注意到 111111111111111111(3进制下) 和所有相邻

而 111111111111111110(3进制下) 和除了 ???????????????????2(3进制下)以外的相邻

因此可以计算 ???????????????????2 中炸弹的个数

同理可以计算 ???????????????????0 中炸弹的个数

因此也就有算 ???????????????????1 中炸弹的个数

换成表就是

考虑两位

    00 01 02 10 11 12 20 21 22
00   x  x     x  x
01   x  x  x  x  x  x
02      x  x     x  x
10   x  x     x  x     x  x
11   x  x  x  x  x  x  x  x  x
12      x  x     x  x     x  x
20            x  x     x  x
21            x  x  x  x  x  x
22               x  x     x  x

看起来就是解一个超大的线性方程组

并且在2位的时候, 它依然是线性无关的, 也就是有唯一解

如果要记录个数关系可能需要7 ^ 12=13841287201 很大

而上面形状可以知道

f(00,10,20) = (00+01   , 10+11   , 20+21   )
f(01,11,21) = (00+01+02, 10+11+12, 20+21+22)
f(02,12,22) = (   01+02,    11+12,    21+22)

(00,01,02) = f(f(00,10,20)[0],f(01,11,21)[0],f(02,12,22)[0])
(10,11,12) = f(f(00,10,20)[1],f(01,11,21)[1],f(02,12,22)[1])
(20,21,22) = f(f(00,10,20)[2],f(01,11,21)[2],f(02,12,22)[2])

还是不是特别能知道

    000 001 002 010 011 012 020 021 022 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222
000   x   x       x   x                   x   x       x   x
001   x   x   x   x   x   x               x   x   x   x   x   x
002       x   x       x   x                   x   x       x   x
010   x   x       x   x       x   x       x   x       x   x       x   x
011   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x
012       x   x       x   x       x   x       x   x       x   x       x   x
020               x   x       x   x                   x   x       x   x
021               x   x   x   x   x   x               x   x   x   x   x   x
022                   x   x       x   x                   x   x       x   x
100   x   x       x   x                   x   x       x   x                   x   x       x   x
101   x   x   x   x   x   x               x   x   x   x   x   x               x   x   x   x   x   x
102       x   x       x   x                   x   x       x   x                   x   x       x   x
110   x   x       x   x       x   x       x   x       x   x       x   x       x   x       x   x       x   x
111   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x
112       x   x       x   x       x   x       x   x       x   x       x   x       x   x       x   x       x   x
120               x   x       x   x                   x   x       x   x                   x   x       x   x
121               x   x   x   x   x   x               x   x   x   x   x   x               x   x   x   x   x   x
122                   x   x       x   x                   x   x       x   x                   x   x       x   x
200                                       x   x       x   x                   x   x       x   x
201                                       x   x   x   x   x   x               x   x   x   x   x   x
202                                           x   x       x   x                   x   x       x   x
210                                       x   x       x   x       x   x       x   x       x   x       x   x
211                                       x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x   x
212                                           x   x       x   x       x   x       x   x       x   x       x   x
220                                                   x   x       x   x                   x   x       x   x
221                                                   x   x   x   x   x   x               x   x   x   x   x   x
222                                                       x   x       x   x                   x   x       x   x

(100,101,102) = f(
                  100+101,
                  100+101+102,
                      101+102
                )
(100+101) = f(
              100+101+110+111,
              100+101+110+111+120+121,
                      110+111+120+121,
            ) [0]

(100+101+110+111) = f(
                      a[000],
                      a[100]
                      a[200]
                     ) [1]

这样能看出一点规律

最叶子的是高位0~2其它位一致,

然后按照从高到低在组内交换

閱讀全文 »