Atcoder abc355

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
E(二进制,最短路)F()G()

https://atcoder.jp/contests/abc355

E - Guess the Sum

交互题

有隐藏数组 a[0,2^n-1]

每次只能询问 sum a[2^i * j,2^i *(j+1)] mod 100

求 sum a[l..r] % 100

要求 询问次数最小

我的思路

首先 进行 二进制拆解有一个方案是

1
2
3
4
5
6
7
8
9
query(l,r,ql,qr,i,j):
  assert(l <= ql and qr <= r)
  if(l == ql and qr == r) return ask(i,j);
  m = (l+r)/2
  if(ql < m) ret += query(l,m,ql,min(m,qr),i-1,j*2) 
  if(qr > m) ret += query(m,r,max(m,ql),qr,i-1,j*2+1) 
  return ret

ans = query(0,1 << n,l,r,n,0)

这个问题是 不能保证最小次数

例如 求a[0..14],那么 只需要 a[0..15] - a[15..15] 两次 而不是3次

这个从二进制上看单侧

14 = 1110, 也就是连续的最多需要两次可以计算出

所以想的是 l 的二进制 变为 r的二进制过程中， 只能 加 或 减 2的幂次，且幂次不能超过当前值的最高位的1

所以 l,r的高位相同的地方忽略掉，处理低不同的位 例如1100 -> 1110，高位1100相同，只用考虑00->10

所以贪心吗，感觉”实现题”写着都好难受

题解

这个和 abc349d 很像, 但这里可以使用减法

对于整数 $x,y(0\leq x,y\leq 2^N)$, 定义$S(x,y)$ :

$$
S(x,y)\equiv \begin{cases} 0\ (x=y) \ \displaystyle\left( \sum_{i=x}^{y-1} A_i\right)\ (x<y)\ -S(y,x)\ (x>y) \end{cases}
$$

那么答案 $=S(L,R+1)$

询问是$S(2^ij,2^i(j+1))$

也有了$S(2^i(j+1),2^ij)=S(2^ij,2^i(j+1))$

$S(x,z) = S(x,y)+S(y,z)$

所以这里是暴力建图 然后求最短路，并没有塞入额外的智力

F - MST Query

初始图G是树, n点边有权重

每次对图增加一条边 u-v,权重w，求增加以后得图的 最小生成树

n 2e5

q 2e5

权重 \in [1,10]

我的思路

只是增没有删，想法是每次 增加以后，删除环上的一条边，但这样似乎是有问题的

可能最大的两个相等，而新的和 其中一个删的构成环另一个不构成环？吗？

即使这样逻辑是对的，如何快速找环最大似乎也没有啥办法，因为如果树的机构不被破坏，是可以 快速倍增lca一类的

这里的 边权 非常小, 所以感觉要特殊的利用这个非常小的性质

最小生成树好像是两种算法，

  • 每次选全局最小的边u-v且u和v不属于同一个连通块链接
  • 第一次选最小的边，后面由该连通块延伸出的最小边

感觉想 第一种，然后做一个阶段记忆化，完成所有1边的连接，完成所有2边的连接，完成所有3边的连接。。。当连成树以后截断

这样新增一个 边x， 只需要 在 对应的位置往后 做计算

这样的好处是 前面小的不用再操作，但复杂度感觉最坏每次还是能O(n),全部是10，然后全部一个一个变9

这样引出的就是，10的内部先做 内部并查集？这样每次需要重算的是 新增的 w对应啥？

一个想法是 如果确定了一个并查集的点内部所有边都是x，那么总的内部代价 = (点数-1)*x 并不用关心具体的边数

题解

$W=10$

$G_k$ 表示G的子图 其中边权$\le k$

$c(H)=$表示图$H$中连通块的个数

那么 $MST(G)=\sum_{k=0}^{W-1} (c(G_k)-1)$

证明:

(方法1), 在MST(G)的边中, 有$N-c(G_k)$条边 的边权不大于 k,

从而, $(N-c(G_k))-(N-c(G_{k-1}))=c(G_{k-1})-c(G_k)$ 的边权恰好是 k( 这里说的不是原图的 中=k的条数，而是在MST中=k的条数)

因此$\sum_{k=1}^W k(c(G_{k-1})-c(G_k))=(\sum_{k=0}^{W-1}c(G_k)) - Wc(G_W) = (\sum_{k=0}^{W-1}c(G_k)) - W = \sum_{k=0}^{W-1}(c(G_k)-1)$

这样的话 维护W个 并查集，每次只需要更新O(W)个并查集即可

官方题解交CPython还会TLE

G - Baseball

给定N,K,Pi

P[n], T/A交替游戏

T 从 1..N选 k个不同的数，令选出的为x[k]

A 从 1..n, 以概率 pi/(sum pi) 来选i, 令选出的为y

A的分数 = min |xi - y|, 也就是 和y最近的T选的数

T希望让得分的期望尽量小,

输出最小的期望 * (sum pi)

n 5e4

pi 1e5

5s

1024mb

我的思路

也就是选了x以后

$\sum_{i=1}^n p_i * \min |x_j - i|$

dp[i][j] = 前i个，第i个选中，一共选了j个 的价值和

dp[i][1] = $\sum_{k=1}^i (i-k) p_k$

dp[i][j > 1] = min(dp[k][j-1] + cost(k,i))

cost(i,j) =$\sum_{k=i}^j p[i]*\min(|k-i|,|j-k|)$

一个是状态是$O(NK)$的过大

cost如何快速计算

转移的代价还要多一个N

对于给定i,j. cost(i,j)还比较好计算

1
2
3
4
5
i...mid...j
只需要计算

- (i...mid)系数单调递增
- (mid+1...j)系数从右侧向左侧单调递增

可以用st表

1
2
3
4
p[i]*0+p[i+1]*1+p[i+2]*2+p[i+3]*3+p[i+4]*4+p[i+5]*5
= (p[i]*0+p[i+1]*1+p[i+2]*2+p[i+3]*3)+(p[i+4]*4+p[i+5]*5)
= (st_p[i][power=2])+4*sum[i+4..i+5] + (p[i+4]*0+p[i+5]*1)
= (st_p[i][power=2])+4*sum[i+4..i+5] + st_p[i+4][power=1]

问题同样是，就算计算这个快，要枚举所有i,j依然是$n^2$的

另一个想法类似于退火

1
2
3
4
5
6
7
8
9
10
三个相邻的x, 如果两端不懂，考虑中间移动带来的变化

x . . .|. . . x . . .[.]. . . x
右移
x . . .[.]. . . x . . .|. . . x
        + + + + - - - -
        对应的这两段 的1倍增减的变化
        这样看上去似乎没有单调性， 因为例如
x 1 1 1 1 1 1 x 1 1 1 1 1 999 999 x
        这在中间移动始终不影响边的999，而只有移动到边的999会显然更小

也想过 放的x逐渐增多，但是显然对于 111…111同样没有局部性

总结

https://atcoder.jp/contests/abc355/editorial

卡E,卡F了好难受