https://ac.nowcoder.com/acm/contest/81599
g min(x,y) 没写 min WA 了一发。居然能过样例，应该会报 warning 但我从来不看。ctrl backspace 还是得看着
j 读完就会了但做的并不快，当时 k 还没读
k 一开始在一棵线段树上分别维护数字和符号，共用一个 mdf，比较混乱，还有顺序问题。重构了一遍
改进一下前期跟榜策略：读题，没秒掉就扔出去，读到 ds 大胆做
D \(\star\)
观察：
- 如果要买，尽量早买
- 如果某回合产量 \(\ge p_1+p_2\)，之后的决策平凡，且容易 \(O(1)\) 计算答案
- 最坏情况下大约调和级数回合后就能满足上一条。即只需要考虑前 \(m\approx p\log p\) 回合
DP。设 \(f[i,j]\) 表示第 \(i\) 回合后产量为 \(j\) 的最大存量。其中 \(i\le m,j<p_1+p_2\)
刷表转移。枚举下一次要种的向日葵
J
设以当前位置为右端点，长 \(a[i]\) 的区间全 \(1\) 的概率为 \(b[i]\)。对答案的贡献为 \(f[k]=\sum b[i]\times a[i]^k\)
考虑转移到下一个位置：
0：清空1：令 \(a\) 集体 \(+1\)，再增加一个 \(a=1,b=1\)?：同1，再令 \(b\) 集体 \(\div2\)
利用二项式定理，只需要维护 \(f[0\sim k]\)。时间复杂度 \(O(nk^2)\)
std 的叙述非常神秘。
K
线段树分别维护数字和符号。容易查询一个数字区间的数值。在符号位置维护该符号和后面数值构成的运算，想办法合并运算
查询时第一个到倒数第二个运算区间查询，第一个数值和最后一个运算单独处理
牺牲常数可以写得比较清新
// * mul + sum + lst
struct Info {
bool flg; // 是否含有 +
mint mul,sum,lst;
Info(){}
Info(bool flg,mint mul,mint sum,mint lst):flg(flg),mul(mul),sum(sum),lst(lst){}
friend Info operator + (const Info &x,const Info &y) {
if( !x.flg ) return {y.flg, x.mul*y.mul, y.sum, y.lst};
if( y.flg ) return {1, x.mul, x.sum+x.lst*y.mul+y.sum, y.lst};
else return {1, x.mul, x.sum, x.lst*y.mul};
}
} t[N*4];
std 没有分开维护数字和符号，把表达式分成一个数字、只有乘、有加三类，值得一看
L
除法是讨厌的，先改写成乘法：定义“等效距离”，初始为 \(x\)，每秒 \(-1\)，速度 \(\div2\) 等价于剩余等效距离 \(\times2\)
标签：Info,sum,多校,2024,牛客,lst,mul,mint,flg From： https://www.cnblogs.com/ft61/p/18325059