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

G - Strongest Takahashi

n x n 格子

# 不可通行,. 可通行

选一个[1,N]中的数字D, 选择DxD的区域,花费代价D移除所有#

问移除所有#的最小代价

范围

N 50

2s

1024mb

我的思路

显然选一个最大的就是n

什么时候不是n?

(n-1)x(n-1) 覆盖不完

那有没有可能 (n-1)x(n-1) 不能覆盖完,但是可以拆成更小的

1
2
3

#..
...
..#

另一个想法是从小向大合并

1
2

#.
.#

有相邻,则合并成更大的

1
2

XX
XX

但是方向选择上?, 不一定能确定

1
2
3
4
5
6

.....#
......
###...
......
...#..
...#..

考虑dp

dp[i][j][d] 表示,覆盖掉i,j 开始d x d的范围的最小代价

但感觉不会转移

看上去,不会出现多个小块 让不能同时行分割和列分割, 但不会证明?

1
2
3
4
5
6
7
8
9

 x
 x  xxxxxxx
 x
 x      x
 x      x
        x
xxxxxx  x
        x
        x

如果是这种, 那么直接用大块覆盖更好

因此 区域覆盖= min(纵切割和,横切割和,一个正方形全覆盖的和)

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

G - Modulo Shortest Path

N 点 有向图

任意两点$i,j$, 有边$weight_{i\to j} = A_i+B_i \bmod M$

输出$i$到$N$的最短路

范围

n 2e5

m 1e9

3s

1024 mb

我的思路

说是有向, 实际上是两两联通,区别只是权重 $i \to j$ 是$A_i+B_j$, 而 $j\to i$是$A_j+ B_i$

n很大 不能可能枚举边,

但似乎, 1->a->b->c

如果忽略到mod, 边代价为= A1+Ba+Aa+Bb+Ab+Bc

也就是 A1+Bc+ (A+B)(a+b)

也就是(1->N) = 首项 + 末项 + 中间的AB

ans - (A1+Bn + (A+B)(…)) = 0 (mod M)

而注意到直接走, 就是$(A1+Bn)%M$, 所以已经存在一个[0,M)的答案, 所以最优的一定也是[0,M)内

如果 Bi 和前面的不超过M, Ai和后面的和不超过M

那么显然i只会让总代价增加(Ai+Bi), 因为可以去掉它,把前后拼起来

这里可以看出需要

(A0 + Bi)mod m + (Ai + B1) mod m < (A0 + B1) mod m < m

所以前面一定也是 [0,m)

(A0 + B1 + Ai + Bi) % m < (A0 + B1) % m < m

因此 (A0+B1+Ai+Bi) >=m, 而且这个减m 要在 上面求和的两个mod 中实现

((A0 + B1)%m + Ai + Bi) % m < (A0 + B1) % m < m

对于A0+B1 < m,

如果 Ai > A0 则Ai+B1 >= m, 如果Ai < A0, 则Bi > B1

如果 Bi > B1 则A0+Bi >= m, 如果Bi > B1, 则Ai > A0

对于2m > A0+B1 >= m

则 m - B1 <= Ai < A0, m - A0 <= Bi < B0

可以看成, 每次路径上插入一个点, 都是让总代价单调下降 (m - (ai+bi)%m)

初始$1 \to N$, 然后每次找一个去插入

但是点插入的顺序, 如何做?

按下降排序? , 前i个最大下降结果, 可是还会收到可插入的影响? 如何维护状态

另外就是这性质 有没有办法优化dij

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

G - Balls in Boxes

n个盒子, 初始第i个盒子有ai个球

k次操作

每次 等概率选一个盒子, 增加1个球

分数 = 最终每个盒子的球的个数之乘积

求分数期望 mod 998244353

范围

n 1000

k 1e9

ai [0, 1e9]

2s

1024 mb

我的思路

感觉上可以 做n和n-1的关系, 然后直接算频次, 最后除总次数 转成概率

F(n,k) = 前n个所有方案的乘积和, Ans = F(n,k) / n^k

对于最后一个盒子, 选择了j次, 对应的方案乘积和为 C(k,j) * F(n-1,k-j) * (a[n]+j)

F(n,k) = sum (a[n]+j) * F(n-1,k-j) * C(k,j), j=0..k

这里n虽然小, 但是k很大, 上面这个显然TLE, 如果能搞到n^2 左右的就好了

C(k,j) 的部分拆出来 分配给F的分母可以简化,但是依然没有去掉k的维度

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

G - GCD Permutation

给一个1~N的排列p

问有多少个有序对 (i,j), (i<=j), 满足 gcd(i,j) != 1, gcd(p[i],p[j]) != 1

范围

n 2e5

5s

1024mb

我的思路

有点想暴力 然后证明复杂度?

对于 (i,Pi), 取两个中较小的一个, 找所有包含它下标的, 用较大的去验证gcd

最多有6个不同质数因子, 最坏情况 1/2+1/3+1/5+1/7+1/11+1/13 = 1.3左右

所以最坏情况是 找n个坐标

先写个代码再说

https://atcoder.jp/contests/abc230/submissions/34500571

显然 有很多是2 的倍数的,它们如果每个都会去访问n/2, 那么已经就是n^2了, 肯定会超时

想法就是 如果 (2的倍数,3的倍数) 之类做容斥? 但是我容斥完全不会

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

G - Longest Y

一个包含字符’Y’和’.’的长n字符串S,

可以操作[0,k] 次,交换S中的两个相邻字符

问可以得到的最终S的内部最长的连续Y的长度

范围

n 2e5

k 1e12

2s

1024mb

我的思路

考虑移动

最终假设是[l..r]

那么对于初始这些y的位置的大范围是[l0..r0]

那么一定可以分成两部分

[l0..m0][m0+1..r0]

一部分向右,一部分向左

显然有个点不需要动

如果选定了第i个点p[i]和期望个数c那么,移动代价为min( 左侧k0, 右侧k1个), k0+k1+1=c

= min(sum(p[i]-k0..p[i]-1) - sum(p[i-k0]..p[i-1]) + sum(p[i+1]..p[i+k1]) - sum(p[i]+1..p[i]+k1))

换个角度

所有值变成p[i]-cnt1[i]

那么就是找一个值, 尽量多的数变成它, 且代价和 <= K

显然每多一个,代价的增量是非严格递增的

是个凸函数(下凹)

但感觉, 这样看起来, 其实左侧右侧影响不大,而是距离影响更大,

所以直接枚举中点,二分距离(选定的点的最大距离) => 去计算距离和范围,以及点数范围

这里 < 距离的必选, >距离必定不选, =距离可选可不选

似乎就没了?