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的切点

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

---

所以还是暴力吧

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

G - Balance Update Query

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

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

1. 修改一个的上限bi

2. 修改一个的单价ai

3. 问 恰好取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

如果Latex在解密后没有渲染，刷新网页即可, 相关Issue

题目

统计 整数对$(a,b,c)$个数 满足

$1\le a \le b \le c$

$a+b+c \le 25,000,000$

$a^2+b^2=c^2+1$

我的思路

$(a-1)(a+1) = (c-b)(c+b)$

$a \le \frac{25,000,000}{3}$

提前线性筛的方式处理 可能的$a$的一个质因子

然后暴力 枚举a, 这样可以log 级别得到 a-1和a+1的分解

然后 dfs(分解) 去凑 $c+b$和$c-b$, 注意奇偶性可以剪枝，然后$c+b>c-b$也可以剪枝， $(c+b)-(c-b) = 2b \ge 2a$也可以剪枝

这样大概是 O(n * 分解的幂次之积) 的时间复杂度

i7-7700HQ 单核python3 跑了 810.686072 s, 十多分钟有点慢

https://codeforces.com/contest/1787

E. The Harmonization of XOR

问 [1,2,3,…,n] 能否拆成k个非空序列(不一定连续), 且每个序列内的数字xor为x

如果可以给具体方案

范围

n 2e5

x [1,1e9]

1s

256mb

我的思路

想了很久线性基, 没啥办法, 感觉都是O(n^2)以上

然后 显然 如果 k为奇数那么 x = xor[1..n], 如果k为偶数, 0 = xor[1…n]

然后n%4==3 的时候 xor[1..n] = 0

然后n%4==0 的时候 xor[1..n] = n

然后n%4==1 的时候 xor[1..n] = 1

然后n%4==2 的时候 xor[1..n] = n+1

其中 n%4==1 很好做, 相邻取偶数和偶数+1 就能构成

n%4==0和n%4==2没有什么办法, 但是这个如果暴力出来,是可以打表的

但是n%4==3 就连打表都不行