https://codeforces.com/contest/1750
给定长n的括号字符串, 求它的所有子串(连续)的代价和
代价: 一个字符串的代价为 循环右移一次, 任意位置插入左括号一次, 任意位置插入右括号一次, 的最小次数使括号合法
读错题了, 字符串的循环右移是可以选子串循环右移的
n 2e5
2s
256mb
显然 枚举不可能, 那么显然就是推数学公式,转换成贡献和, 而我推不出
众所周知, 一个括号串合法等价于 左括号1,右括号-1, 任意前缀非负, 所有和为0
那么当计算出 前后括号差值后知道至少需要增加的括号数
然后对于最小值的处理, 有两个办法, 左右通过括号包裹相当于 坐标轴向上平移,
做循环右移
而这两个有时可能还可以组合
而问题是如何取max
https://atcoder.jp/contests/abc276/tasks
范围 [0,m] 单调递增 n个数, 且相邻 mod 3 不同
问 方案数 mod 998244353
n 1e7
m 1e7
4s
1024mb
f(n,m) = 范围 [0,m] 放n个数, 第一个放0 的方案数
ans = sum f(n,0..m)
f(n,m) = sum f(n-1,m-非3倍数)
考虑 生成函数 f(n,m) 为 生成函数$F_n$的系数
$F_1 = 1+x+x^2+x^3+\cdots = \frac{1}{1-x}$
$ans = \lbrack x^m \rbrack (F_n \cdot \frac{1}{1-x}) $
$F_i = F_{i-1} \cdot (x+x^2+x^4+x^5+x^7+x^8+\cdots)$
$= F_{i-1} \cdot \frac{x+x^2}{1-x^3}$
$F_n = F_1 \cdot (\frac{x+x^2}{1-x^3})^{n-1} $
$ans = \lbrack x^m \rbrack \frac{(x+x^2)^{n-1}}{(1-x)^2(1-x^3)^{n-1}}$
然后 我暴力算 样例就TLE了
https://atcoder.jp/contests/abc275/tasks
n种物品, 每种无限多个
第i种, 重ai,体积bi,价值ci
f(X) = 总重量<=X,总体积<=X的最大价值
可证明 lim_{x->infty}f(X)/X 的极限存在, 求极限
n 2e5
ai,bi,ci [1e8,1e9]
2s
1024mb
感觉就一个很数学的题
考虑3元组, (a,b,c) 若 a >= b, 等价于a个(a/a,b/a,c/a)
若 a < b, 等价于a个(a/b,b/b,c/b)
于是分成两种
$(1,p\le1,c_0),p=b_0/a_0$
$(q\le1,1,c_1),q=a_0/b_0$
而实际上未来增长只会是 这两种按一个比例的和
$(t_0,pt_0,c_0t_0) + (qt_1,t_1,c_1t_1)$
$t_0 + qt_1 = pt_0+t_1 $
$t_0 = t_1 (1-q)/(1-p)$
$c_{0,1} = (c_0t_0 + c_1t_1)/(t_0 + qt_1)$
$= (c_0(1-q)/(1-p) + c_1)/((1-q)/(1-p)+ q)$
$= (c_0/(1-p)+c_1/(1-q))/(1/(1-p)+q/(1-q))$
$ans=\max(c_0,c_1,(c_0(1-q)+ (1-p)c_1)/((1-q)+ (1-p)q))$
问题是两两计算的话 为n^2
稍微改一下
$1,p < 1,c_0$
$1,q > 1,c_1$
$pt_0+qt_0=t_0+t_1$其中$t_0,t_1 > 0$ 即$t_0 = t_1 \frac{q-1}{1-p}$
$c_{0,1}=\frac{c_0t_0+c_1t_1}{t_0+t_1}$
$= \frac{c_0\frac{q-1}{1-p}+c_1}{\frac{q-1}{1-p}+1}$
$= \frac{\frac{c_0}{1-p}-\frac{c_1}{1-q}}{\frac{1}{1-p}-\frac{1}{1-q}}$
也就是 $(\frac{1}{1-\frac{b_i}{a_i}},\frac{\frac{c_i}{a_i}}{1-\frac{b_i}{a_i}})$ 这些点之间的最大斜率
n个点之间 找最大斜率
但注意到的是 是由第4向限和第1向限的点, 并不是两两之间, (因为两两之间的话 相当于$t <0)
直接考虑 分别两坨点的凸包
双指针???? 不会了
https://atcoder.jp/contests/abc274/tasks
给定 h行W列, 一些地方是障碍
问最少安装多少摄像头, 能监控所有非障碍区域,
一次安装 在一个非障碍区域并监控它自身和朝向(4向)的一段连续的非障碍区域
同一个地方可以安装多个不同向的
h,w 300
2s
1024mb
把连续一段横着 或者竖着 看作一个单位
那么 对于(i,j) 所在的横的r_x, 和竖的c_y
有关系r_x+c_y >= 1
所有 r和c的取值只能1/0
要 所有r+c 的和最小
似乎是个线性规划?
https://atcoder.jp/contests/abc260/tasks
n球, 颜色ci
f(球的一个排列) = 相邻不同色的个数
对于k=1..m分别求 $\sum(f(排列)^k)$ mod 998244353
n 2.5e5
m 2.5e5
ci [1,n]
8s
1024mb
k==1 时
那颜色可以分开考虑
一个颜色 去计算它能构成x个间隔, 那么它每个贡献 (x+1(两端))/2, 再乘上方案数
注意每个排列的最左和最右还要-1, 所以还要减 n!
k==2时
明显就不一样了, 因为贡献变成了 (相邻不同色)^2
颜色c 有 x间隔 ( (x+1) + 其它颜色间隔贡献 -1)^2
问题 其它颜色贡献会受到颜色c的间隔数x 影响
如果直接按照题目来, 按f(P)归类
如果能算出 不同为y个的 出现次数t(y)
那么 就是 f(1) = sum t(y) * y
f(2) = sum t(y) * y^2
这样做也是 需要O(n m) 的
而且怎么算不同出现次数也没啥想法