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

Ex - Marquee

给定长度L的字符串S, 包含大小写字母, 在宽W的滚动显示器上，每次移动一个字母

因此有L+W-1种状态,例如S=ABC,W=5,点表示空

1
2
3
4
5
6
7

ABC..
BC...
C....
....A
...AB
..ABC
.ABC.

现在问题是 给定长度L字符串 T，问有多少个 状态和T匹配

T中有字符_可以匹配任意字符

l,w 3e5

5s

1024mb

我的思路

实际上滚动可以看成，S左侧W-1个点，右侧W-1个点

1

.....S.....

然后 用T去匹配

这匹配有点KMP的感觉，

但这里任意字符_ 似乎不是很好转移

一个想法是 KMP的树状版：AC自动机能有用吗？

但实际还是,KMP中 aba 的后缀最长匹配前缀的是a

而___的后缀最长匹配前缀是__

需要一个可以支持 通配符号的类似的 匹配算法

自匹配还算好，就是kmp的原理

dp[i]=i结尾后缀 相等的 最长前缀长度

dp[i] = dp[j] + 1, match(a[i],a[j+1]) and dp[i-1]最先递归向下到j

然而并不对

例如 样例1

1
2

ABC
..___

对于T来说 ..___ 的后缀(.___)match的最长前缀长度为4 (..__)

但是对于..ABC => .ABC. 转换 并不是只鉴定最后一位就可以的

也就是

1
2
3
4
5

 .ABC.
..ABC
..___
 ..__
 ..___

这个match关系没有传递性

但是是必要条件，因为S的子串如果match,则可以看成T的一个特例化，而如果 特例化对应match,则非特例化一定match

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

G - Return to 1

n点,m有向边

从1开始，每次 从当前点选一条边移动，问$10^{10^{100}}$次时能否回到1

n,m 2e5

2s

1024mb

我的思路

次数巨大，如果走k1次回到1，k2次回到1

那么可以 gcd(k1,k2)次的足够大的倍数回到1， 因为 问题中的次数巨大，所以 ak1+bk2=c gcd(k1,k2) = 10^{10^{100}}能找到正解

所以 问题是能否找到 两个不同的次数的 gcd 只有2和5的因子

一个不会证明的想法是，计算从1出发到达每个点的不超过2种 距离，和逆向从1倒退不超过2种距离

这样每个点 可以得到2x2种从1到1的距离

对所有距离做gcd看看是否只有 2和5的因子

但是这个做法，正确性 感觉不会证明

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

Ex - Shojin

N个问题, 难度(Ai,Bi)

选择$D \in [1,N]$天 完成所有N个问题，即把N个问题分成D个连续非空子区间

疲劳x 每天初始 = 0，每天完成当前的区间中的问题

区间内问题顺序可以任意调整，每次完成一个问题后 x_new = A x_old+B

给定X, 问 min D, 使得 sum x_每天结束<= X

输出 (min D, 对于 min D时最小的sum x_每天结束)

n 2e5

X 1e8

ai [1,1e5]

1<= bi

sum bi <= X

3s

1024mb

我的思路

先说一天内，如果指定了区间

先i后j: $a_j(a_i x + b_i) + b_j$

先j后i: $a_i(a_j x + b_j) + b_i$

如果要 $a_j(a_i x + b_i) + b_j < a_i(a_j x + b_j) + b_i$

即 $a_j b_i + b_j < a_i b_j + b_i$

即 $(a_j-1) b_i < (a_i-1) b_j$

即 $\frac {a_j-1}{b_j} < \frac{a_i-1}{b_i}$

即每个元素 可以按照key = $-\frac{a-1}{b}$ 排序

反过来排序则是最大

问题其实变成对于给定D, 求min

对于min显然 随着D增加，min 单调递减，因为至少有一天两个问题，而后一个问题的额外代价 是 (Ax+B)-x = (A-1)x+B, 而单独放一天则是B, 而A>=1

有一个巨大的dp

dp[i][d] 以i结束，i前面划分了d天的 最小消耗

就是求 dp[n][min d] <= x

dp[i][d] = min(dp[j][d-1] + cost[j+1..i]), j<i

首先 状态就n^2,空间就n^2 ,转移看上去要n^2,时间就是n^4

先说能否降低到n^3, 也就是cost[i...j] 有没有什么快速的计算方法或者预处理

显然x=Ax+B可以用矩阵乘法表示

那么就可以用线段树按 上面 -(a-1)/b 的顺序 维护

一个区间就是区间内的变成 对应的矩阵，而区间外的 变成 单位矩阵

那么计算一个区间cost[i...j] 无非就是cost[i...j-1] 基础上让 j在线段树中对应的 变为对应矩阵再计算完整线段树的 矩阵乘法结果，

这样显然 循环 遍历i,j 能 n^2 log n 算出所有cost[i..j]

至少时间复杂度变成 n^3 + n^2 log n

感觉 还缺了什么数学性质

但对于相邻的两个区间，并不知道 相邻位置放在哪个区间好

因为并不知道 它 排序后的位置，

虽然可以 预估它放最前 和 最后的贡献变化，一个是预估，另一个是需要他前后的区间的信息

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

G - Max of Medians

给长2n的数组A,让元素配成n对，每对做xor得到长n的序列B

求 max(sorted(B)[n/2+1])

n 1e5

ai [0,2^30]

5s

1024mb

我的思路

xor + max 常见思路从高位向低位贪心,

对于第b位

min(count 0, count 1) 就是能构成1 的方案数

如果 min >= n/2 +1, 那么 就是 从 b位是0和是1的分成两组，其中各选出一个，还需要对低位进行处理啊

如果 min < n/2+1, 那么就是b位无法成为1,那么0和1分成两组，这两组内部选两个排序

这两个都并不好处理，因为第n/2+1大在这过程中不光没有消掉，而且还会增加维度

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

G - Bags Game

n包, i个x[i]钱

每次3选1

• 获得 最左/最右 一个
• 获得 最左/最右 (一共B个,可以分别取一部分) - A元
• 获得 最左/最右 (一共D个,可以分别取一部分) - C元

两人交替, 分别是X,Y, 求X-Y 的双方最优操作后的值，一个要最大，一个要最小

n 3000

xi,a,b,c,d, 1e9

2.5s

1024mb

我的思路

如果没有后两种

那就是经典的dp[l][r] = 从当前开始最优差值

dp[l][r] = max(x[l] - dp[l+1][r], x[r] - dp[l][r-1])

现在多了两种批量的情况

例如其中第二个方案就是 x[l...i] + x[j...r] - A - dp[i+1][j-1], len(l..i)+len(j..r) == B

但是注意到可以变换一下

x[l...r] - x[i+1..j-1] - A - dp[i+1][j-1], len(l..i)+len(j..r) == B

令 ndp[i..j] = x[i..j] + dp[i..j]

dp[l..r] = max(x[l] - dp[l+1][r],x[r]-dp[l][r-1],x[l..r] - A/C - ndp[i+1..j-1])

不妨设 第一种是 支付E=0元，取得F=1个

dp[l..r] = x[l..r] - min(A/C/E + ndp[i+1..j-1,A/C/E])

因此 需要一个 能够快速查询

[l...r]区间内 A/C/E + min(ndp[len(l..r)-B/D/F]) 即可

minndp[l..r] 可以通过minndp[l-1..r-1] 维护小根堆转移得到