CodeTON Round 3

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
E(括号匹配)F(DP)

https://codeforces.com/contest/1750

E — Bracket Cost

给定长n的括号字符串, 求它的所有子串(连续)的代价和

代价: 一个字符串的代价为 循环右移一次, 任意位置插入左括号一次, 任意位置插入右括号一次, 的最小次数使括号合法

读错题了, 字符串的循环右移是可以选子串循环右移的

范围

n 2e5

2s

256mb

我的思路

显然 枚举不可能, 那么显然就是推数学公式,转换成贡献和, 而我推不出

众所周知, 一个括号串合法等价于 左括号1,右括号-1, 任意前缀非负, 所有和为0

那么当计算出 前后括号差值后知道至少需要增加的括号数

然后对于最小值的处理, 有两个办法, 左右通过括号包裹相当于 坐标轴向上平移,

做循环右移

而这两个有时可能还可以组合

而问题是如何取max

题解

结论: 序列a 代价为 max(pre[0],pre[len]) - min(pre[0..len])

proof

如果 pre[0] < pre[len] 右侧插入右括号

如果 pre[0] > pre[len] 左侧插入左括号

读错题了, 既然子串循环右侧移动, 那么每次 把最小值前缀的)的最大下标的下一个位置 ...)( 整个右移动, 这一段前缀min加1, 那么不就显然了…..

然后就是无脑的贡献计算了

F - Majority

问长n的0/1字符串, 有多少个可以通过变形变成全1的字符串

变形: 每次选 两个s中字符为1的下标i,j, 如果 s[i..j] 中1的个数>= 0的个数,那么 可以把s[i..j]全变成1

求合法的字符串数 mod m

范围

$n \in [1,5000]$

$m \in [10,10^9]$

2 s

1024 mb

我的思路

首先合法的一定首尾是1

1001 是最长的可以两个1变成多个1的

10001不行

但是 110001 是可以的

这个n给人一个$O(n^2)$的感觉

dp[i][j??] = 前i个, 且第i个填1的???? j能表示个啥

想的是直接的1的个数的话, 那么意味着前面有些可以产生更多1的并没有处理,而对于这个状态也不一定

1001001 和 1100001 都是3个1, 但是第一个可以变,后面的不能变

所以说 如果j是 前i个1 通过所有可能变化后的1的个数的话

1000011 -> 10000110001, 可以让后面110001 变成全1

1100001 -> 11000010001, 不可以让后面

而这样的话 j表示变化后的也不行..

也就是直接个数的状态作为j感觉并不行

一个可行但是感觉空间时间都会炸的方案就是

dp[vector<int>] = 不表示原始, 而表示变化后的压缩后的, 直接把连续的0和1的状态,用个数表示

但这样空间 时间, 都卜行

然后说 如果前面一段 如果不能继续压缩, 那么对于任何一段 1(a个) 0(b个) 1(c个)

有

a-b+c < 0

a >= 1

c >= 1

即 a < b-1, c < b-1

因此 原来不行的一段, 拼接上了bc 101010101(a)—0(b)1(c)

那么说明 最后3个101一定可行的, 否则有更长的可行的, 可以去掉前缀得到 最后三个是可行的

所以 对于一个压缩后的增加一个产生的变化可以均摊O(1)

那么问题就是 除非 不可压缩状态很少, 才能这样搞, 否则时间空间还是没得说

题解

一样的结论,如果可行,则每次处理一个 1(a)0(b)1(c) 的串( 证明如上

按长度DP !!!

dp[len][prefix] = 长度len, 通过所有可能操作最终变来 前缀有prefix个1 的方案数

例如 dp[i][0] = 2^{i-1}, 首位0,后面随便放

那么ans = dp[n][n]

dp[i][i] = 2^i - sum dp[i][0..i-1] 所有方案-前缀非n

对于0<j<i 显然第j个位置是1, 第j+1个位置是0, 那么其实考虑从j+1 开始向后的连续有a个0, 然后开始是1, 这样不会重复统计

[1...j][a个0][b个1....]

j+b < a, 最后一段长度为 i-j-a

还有最后一段全为0的 1种

有 dp[i][j] = dp[j][j] (1 + sum (dp[i-j-a][b]), 其中 j+b < a, a > 0, b > 0 , i-j-a-b >=0),

整理一下 令 c=i-j-a 则a= i-j-c

dp[i][j] = dp[j][j] (1 + sum dp[c][b]) , 其中 b+c < i-2j, c >= b > 0 (这个本来在dp中[c >= b 就一直有])

所以只用考虑 (1,1) 和 b+c <= i-2j-1 围成的3角形的和, 看起来二维实际就是个一维前缀, 随便搞搞

G - Doping

如果数列 为单调增1 那么 fancy

f(排列) = 排列的最小切割(划分后数组个数), 让每部分fancy,

给定长n的 排列p, 求 长n字典序列小于p 的 f为k=1..n的 个数,mod m

范围

n 2000

m [10,1e9]

3s

512 mb

我的思路

字典序小于, 有一点 数位dp的感觉

因为如果是 数位dp那么高位定了以后, 剩余的可能性 就是1-n移除高位, 所以 是n种

然后限制有两个,

  1. 首位的最大值(用于限定首位, < p[i])
  2. 首位的前一位(用于f计数)

如果这样搞, 问题变成 给定 [1...n] 中一些数, 要计算不同切割的方案数

例如 1,2,5,6,7

如何 计算2个相邻的方案数, 还要控制首个的大小

1
2
3
4
5
6
7
8
9
10
11
12
1 5-6-7 2
2 5-6-7 1
2-1 5-6-7
5-6-7 2-1
1-2 7 5-6
7 1-2 5-6
5-6 1-2 7
7 5-6 1-2
1-2 6-7 5
5 1-2 6-7
6-7 5 1-2
6-7 1-2 5

首先 (n个数,里面m个相邻, 现在求i个相邻的方案数) f

等于 选binom(m,i) 作为指定相邻, 剩下相邻全不满足,

(这个指定+其余任意 g 就可以二项式容斥+二项式反演

g(i) = sum binom(j,i) f(j) , m>=j>=i

g很好算 相当于 指定i个后, 剩下 n-i 个随便排 = binom(m,i) (n-i)!

这样对于给定n,m 可以 O(m)算出所有f(i)

问题在于 首个数字的值, 看上面的 1,2,5,6,7 首个数字 出现次数 各不相同

如何把首个数字得出, 或者说 如何 < p[i] 的方案数得出?

总结

E

太菜 推不出 结论? 哦,不是,是读错题了…………………

不过整体感觉是对的, 就是找公式变贡献计算.

不读错题的话,没啥难的

F

按 长度DP 说实话写了太多次了, 但是每次感觉都是超明显的按长度从小到大dp, 这竟然想不到了…..

感觉上这种 “前后”关系不大的, 就是应该要去想长度从小到大了, 而我上面考虑都在按照 前i个去想, 这样的话,就只能在屁股上增长, 虽然这个题 也可以那样dp:

也很接近, 就是我这里没想好的j的状态, 其实再试一下就应该能想出来的, 这里试了初始1个数, 和变化后的1的个数, 而没有尝试变化后,后缀1的个数

dp[i][j] = 前i个, 所有处理后, 后缀1的长度为j, 哎, 又是大的感觉对了, 具体的没往下尝试出, 而且这里后缀1的长度 其实还听自然, 特别是我自己推出了 一定是1(a)0(b)1(c)的处理时

这E,F真就是 知识都会, 但太菜, 感觉跟abc276ex 一样

G

TODO

参考

官方