https://ac.nowcoder.com/acm/contest/51721
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%
https://atcoder.jp/contests/abc288/tasks
[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 | 0 1 2 |
考虑两位
1 | 00 01 02 10 11 12 20 21 22 |
看起来就是解一个超大的线性方程组
并且 在2位的时候, 它依然是 线性无关的, 也就是有唯一解
如果要记录 个数关系可能需要7 ^ 12=13841287201 很大
而上面形状可以知道
1 | f(00,10,20) = (00+01 , 10+11 , 20+21 ) |
还是不是特别能知道
1 | 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 |
1 | (100,101,102) = f( |
这样能看出一点规律
最叶子的是高位0~2其它位一致,
然后 按照从高到低在组内交换
https://codeforces.com/contest/1598
十进制下没有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,
始终感觉没有 把 相邻和求和之间建立任何联系
https://codeforces.com/contest/1606
根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的切点
https://codeforces.com/contest/1612
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
所以还是暴力吧