Atcoder abc288

發表於 2023-02-09 更新於 2025-04-21 分類於 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其它位一致,

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

閱讀全文 »

Educational Codeforces Round 115

發表於 2023-02-08 更新於 2025-04-21 分類於 Codeforces ， Edu 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,

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

閱讀全文 »

Educational Codeforces Round 116

發表於 2023-02-07 更新於 2025-04-21 分類於 Codeforces ， Edu Disqus：文章字數： 2.6k 所需閱讀時間 ≈ 9 分鐘

F(树,数学推演)

CF tracker

Edu List

https://codeforces.com/contest/1606

F. Tree Queries

根1 n点树

q个询问: 每次给点v, 数k

删除任意点任意顺序 (根和v不能删除)

每次删除u: 让u的子节点的父节点 = fa[u]

求max(childcount(v) - 删除点数 * k)

每个询问独立从初始树询问

范围

n 2e5

q 2e5

k [0,2e5]

6s

512mb

我的思路

k == 0 时，显然贪心就完了，要让一个后代点成为v的子节点, 就是要让它到v之间的路径上的其它点都删除

所以 v最多能有它的子树中叶子个点

最少就是不删除时它直接的节点数，为了让答案更大，所以节点一定在这个范围之间

如果知道 v 得到x个子节点的最少删除数量cnt[v][x]，那么x - cnt[v][x]*k

几个问题，

第一cnt没法计算所有因为空间和时间复杂度都是O(n^2)的？

第二即使暴力算cnt, cnt并不一定连续, 例如 1-2-3,2-4,2-5, 那么其实1的子节点要么1个要么3个，虽然可以乱删到2个，但是那种的过程不是贪心方向的

第三即使有了cnt, 那么对于给定的v和k 还要枚举x才行会达到O(nq)

一个方向，离线掉，看如何批量的处理计算

总有一点点斜率维护的感觉，如果斜率是凸的，那么只是去找斜率k的切点

閱讀全文 »

Educational Codeforces Round 117

發表於 2023-02-06 更新於 2025-04-21 分類於 Codeforces ， Edu Disqus：文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘

F(DP)G(排列组合)

CF tracker

Edu List

https://codeforces.com/contest/1612

F. Armor and Weapons

n个盾，m个武器

power = 盾idx + 武器idx

有q个 idx组合是加强的 power = qi(盾idx) + qj(武器idx) + 1(比沒有加強的多1)

初始，(盾1,武器1)

如果想得到盾k 或者武器k, 那么power 需要>= k

同时只能持有两个，所以之前得到过但是放弃的不能用于组合也就是(a,b) -> (a, <= a+b+(?1)) or ( <= (a+b+?1), b)

问(1,1) -> (n,m) 的最小次数

范围

n,m 2e5

q 2e5

2s 512mb

我的思路

dp[m][n] = min(dp[m][n-m ~ n-1],dp[m][n-m-1] if (m,n-m-1)在q中), 对于另一侧固定，类似的

从小到大的角度，在沒有q的情況，就是(1,1) -> (1,2) -> (3,2) -> (3,5) -> (8,5) 這樣是最快的

如何處理有q的？

如果没有上界 (a,b)->(a,a+b+1), 那么如果继续固定a, 那么显然 (a,a+b+1) 不会比(a,a+b) 差，因为(a,a+(a+b+1)) 都可达

问题是如果需要(a,a+b) -> (a+a+b,a+b) 呢

既然如此，又注意到不使用q都是log级别的次数

直接dp空间不够

所以变成

dp[a][step] = maxb

也就是求min step, 使得 dp[m][step] = n

有个问题是满足局部性吗

似乎不会证明

感觉需要改一改

dpa[a][step] = maxb 为最后一次是固定a 得到的maxb

dpb[b][step] = maxa 为最后一次是固定b 得到的maxa

dpa[a][step] = max(a+dpa[a][step-1]+(?1), a+wb+(?1) (dpb[wb][step-1] >= a))

dpb 同理

问题对于给定 step, dpa内有单调性吗

似乎可以归纳一下，设给定step, dpa和dpb都是非严格单调递增,

那么step+1时，如果dpa[step+1][a] > dpa[step+1][a+1]

a+dpa[step][a]+1 <= (a+1) + dpa[step][a+1], 所以上一次不是固定a,

如果是固定b:

有额外点数 b+dpb[step][b](==a-b-1)+1 (更大则都是b,更小则当前不可达), 只要(b+1)+dpb[step][b+1](>=a-b-1) 存在

无额外点数 b+dpb[step][b](==a-b) (更大则都是b,更小则当前不可达), 只要(b+1)+dpb[step][b+1](>=a-b) 存在

但注意到这种情况是 a > b 那么必定比这种情况是之前a不存在(否则之前存在一定是通过a而不是通过b)，所以只能通过b到达，所以得证

然后需要注意的是，如果其中一个很小，那么就需要固定一个反复跳另一个, 这个时候就不要暴力了

写了一下发现并没有单调性

4次，(1,1)(1,2)(3,2)(3,5)(3,8)

4次，(1,1)(1,2)(3,2)(3,5)(8,5)

但4次，4的话最大只能得到7

所以还是暴力吧

閱讀全文 »

Atcoder abc287

發表於 2023-02-05 更新於 2025-04-21 分類於 Atcoder ， ABC Disqus：文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘

G(离线,线段树)Ex(Floyd-Warshall,bitset)

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

G - Balance Update Query

n种卡，每种无限多，初始每种单价ai,最多取bi张

q个询问，每次三种可能操作

修改一个的上限bi
修改一个的单价ai
问恰好取x张的最大价值

范围

n,q 2e5

ai [0,1e9]

bi [0,1e4]

2s

1024mb

我的想法

如果固定，贪心从单价大到小的去取

对单价排序做根号分治

让每个块的个数保持在sqrt(n)个

这样每次修改操作就是最多改变 sqrt(n)个块，每个块内部就是 log(sqrt(n)) 的操作次数时间复杂度 O(q sqrt(n) log(sqrt(n)))

而查询，因为可以做块的个数和与代价和记录，所以暴力找在哪个块，再在块里暴力搜，O(q (sqrt(n)+log(sqrt(n))))

2s 还是会tle的

200000*math.sqrt(200000)*math.log(math.sqrt(200000))/math.log(2) = 91203683.14743526

它的确也tle了

https://atcoder.jp/contests/abc287/submissions/38429726

21AC + 19TLE

閱讀全文 »