YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， 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等概率

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

閱讀全文 »

發表於 更新於 分類於 ， 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

閱讀全文 »

發表於 更新於 分類於 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%

閱讀全文 »

發表於 更新於 分類於 ， 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 中炸弹的个数

换成表就是

1
2
3
4
   0  1  2
0  x  x
1  x  x  x
2     x  x

考虑两位

1
2
3
4
5
6
7
8
9
10
    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 很大

而上面形状可以知道

1
2
3
4
5
6
7
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])

还是不是特别能知道

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(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其它位一致,

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

閱讀全文 »

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
G(数学,KMP,string hash)

CF tracker

Edu List

https://codeforces.com/contest/1598

G. The Sum of Good Numbers

十进制下没有0的是好数字

a = 好数字 数组

且其中 a[i]+a[i+1] == x 也是好数字

s = a的字符串拼接

问，输入s和x, 求a[i] 和 a[i+1] 在s中的位置

范围

|s| 5e5

|x| 2e5

2s

256mb

我的思路

两个数字加起来 = x

那么至少一个 >= x/2

所以有一个的长度 = |x| 或 |x-1|(这还需要x的首位是1)

那么可以枚举这个长度

问题变成s[j...j+len]是一个数， 那么它的后临 或 前临 是否是 x-它

这样直接暴力肯定不行, 如何快速计算和比对?

直接数字化 然后 mod 不同的值来算hash?

长度 怎么参与考虑

有个严重的问题就是，做加法或者减法会有进位和借位，所以这似乎就跟字符串算法不太能联系起来了

没有特别想懂 这里没有0的意义, 没有0有什么特殊性质吗? , 27+67 = 94, 依然有进位

然后如果 x 是由两个len = |x|的加起来, 那么可以考虑hash一下所有长度|x|的, 再枚举连接处

x首位>1 则有一个和它首位 差不超过1,

始终感觉没有 把 相邻和求和之间建立任何联系

閱讀全文 »
0%