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

E - Average and Median

给你一个数列

从中选一些数,保证任意相邻的两个至少一个被选

求 平均数的最大值

求 中位数的最大值, 这里偶数个的时候, 取第 n/2 个 而不是中间两个的平均数

范围

n 1e5

ai [1,1e9]

我的思路

想dp吧, 但是如果是dp[i][0/1] 表示第i个是否选的最大平均值

那么问题是, 前面更小的平均值可能让结果更大

因为 (v0c0+a[i])/(c0+1) < (v1c1+a[i])/(c1+1), 并不意味着 v0和v1的大小关系

但如果把数量带上, 啊不就n^2空间

然后思路二, 先任意选一些合法, 然后剩下的没选的中, 从大到小,只要比当前平均值大, 则选择, 否则不选

这样最优 = 最优

问题是 如何枚举所有初步合法, 就算枚举了, 这样搞 至少还有个n倍

再就是,直接从大到小选,选到合法为止, 但是看起来样例就是反例

再就是 考虑二分答案, 答案是否小于 val, 如果小于, 则所有大于它的都必选, 因为如果不选,而答案小于val,则选了可以更大

这样对于剩下的来说, 依然和数量和和有关比如 200 100 1 100 200,

不会了

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

G - Gardens

A个种子1

B个种子2

C个种子3

N个花园

要满足条件, 任何花园都有种种子

每个花园每种的个数[0,1]

不需要把所有都种植

求方案数mod 998244353

范围

n 5e6

3s

1024mb

我的思路

R(i,j) 表示,i个花园,种完其中j个花园的方案数

T(n) 表示,n个花园,恰好种满这n个花园的方案数, T(n) = R(n,n)

ans = T(n)

S(n) = R(n,n) + R(n,n-1) + R(n,n-2) + … + R(n,0);

S(n) = R(n,n) * binom(n,n) + R(n-1,n-1) * binom(n,n-1) + .. + R(0,0) * binom(n,0)

S(n) = T(n) * binom(n,n) + T(n-1) * binom(n,n-1) + .. + T(0) * binom(n,0)

S(n) 很容易算, 相当于A,B,C互不影响, = prod (sum binom(n,0..X)), X=A,B,C, 问题是这个依赖于n需要O(n),

如果能反过来得到T(n) 就好了

T(n) = S(n) - (T(n-1) * binom(n,n-1) + … + T(0) * binom(n,0))

T(n)/n! = S(n)/n! - sum T(i)/i!/(n-i)!

考虑花园状态只有2^3-1=7 种,那么就是 七种中,总个数小于a,b,c的

生成方程?

$\sum \lbrack pwr_x\le a,pwr_y\le b,pwr_z\le c \rbrack ((1+x)(1+y)(1+z)-1)^n$

$= \sum_{i\in[0, n],i_x\le a,,i_y\le b,i_z\le c} (-1)^{n-i} \binom{n}{i} \binom{i}{i_x}\binom{i}{i_y}\binom{i}{i_z} $

$= \sum_{i\in[0, n],i_x\le a,,i_y\le b,i_z\le c} (-1)^{n-i} \binom{n}{i} \binom{i}{min(i,i_x)}\binom{i}{min(i,i_y)}\binom{i}{min(i,i_z)} $

并没法算

再就是, 假设 a<=b<=c

ans(a,b,c) 通过 ans(b,b,b) 让每次头-1,或者尾+1,多次得到

去考虑之间的变化

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

G - Divide a Sequence

长n数组A

2^{n-1}种方式切割成非空顺序数字

f(切割) = $\prod$每个子数组的 (max-min)

求 $\sum$ f(所有切割)

mod 998244353

范围

2s 1024mb

我的思路

dp搞一搞

考虑最后一个数组长度
dp[i] = dp[i-len] * ((max-min)([i-len+1..i]))

但这样就O(n) 状态, n^2转移了

然后,算的时候,max和min可以拆开, 但是如果 两两不等的话, 即使用了 区间sum dp * max, 也可能max需要一个一个枚举,也是n^2

问题变成说

dp[i] = sum max(a[i-len+1..i]) * dp[i-len] - min(a[i-len+1..i]) * dp[i-len]

考虑相邻转移

i-1: sum max(a[j+1..i-1]) * dp[j]

1. a[i]是[j+1..i]的最大值, 那么找最小的j, 这之家你的贡献 = a[i] * sum dp[j..i-1]
2. a[i]不是[j+1..i]的最大值, 那么这贡献 = sum max(a[j+1..i])*dp[j] = sum max(a[j+1..i-1])*dp[j]

因此相邻的dp虽然没有直接关系, 但是可以利用上次的计算

dp[i] = a[i] * sum(dp[j..i-1]) + sum f(0..j)

min同理

似乎就没了

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