kzoacn's Blog

[5.20]开了这么久还没有填完就弃了吧

感觉一轮回来之后就没有好好做过题……

计数菌:

22

【BZOJ4008】正向设计状态死活不行……设\(f[i][j]\)为剩余j轮，前i张未打出的概率,讨论下一张牌能否出牌，得到

\(f[i+1][j]+=f[i][j] \times (1-p_{i+1})^j\) \(f[i+1][j-1]+=f[i][j] \times(1-(1-p_{i+1})^j)\)

【BZOJ4029】大水题，每次贪心往最后一个非零位+1，统计答案

【BZOJ1055】\(f[l][r][x]\)表示\([l,r]\)能否形成\(x\)，记忆化搜索

【BZOJ3996】最小割，模型很常见

【BZOJ4002】我数学不好:Xs酱的题解，不懂得为什么是这个递推式的可以去看看Fib数列的推导

【BZOJ3209】裸数位dp

【BZOJ3935】虽然是以前做的既然要写题解就算进去吧= =

这题是省队集训时drcrow学长的题

设\(y_i,x_i\)分别是调整前后\(i\)的颜色，问题即如下的整数规划

\[min.~\sum_{y_i=0}x_i\]

\[ s.t.~ \sum x_i= \sum y_i \]

\[\sum_j[dis(i,j)\leq X]x_j>0 \]

可(dui)以(pai)证明约束矩阵是一个全幺模矩阵，线性规划的最优解即为整数规划的最优解，所以直接上单纯形就好了

【BZOJ1857】三分套三分……

【BZOJ4034】做过3083的都会……链剖dfs序线段树

【BZOJ2084】hash+二分水题，5e5的数据居然200ms+就过了，数据有点水

【BZOJ2275】校内互测出过这题的强化版= =，打表可得答案为将n对于斐波那契数列进行二进制拆分后的lowbit

【BZOJ4028】分块不多说、

【BZOJ4052】水……

【BZOJ4063】水……

【BZOJ3611】虚树dp

【BZOJ2816】LCT……虽说Splay就可以了……

【BZOJ1511】求前缀i的最长循环子串就是i=next[i]一直蹦到最后一个不为0的值然后被i减,用一种类似于路径压缩的东西处理一下就可以了

for(int i=1;i<=n;i++)if(next[next[i]])next[i]=next[next[i]];
for(int i=1;i<=n;i++)if(next[i])ans+=i-next[i];

【BZOJ2823】最小圆覆盖，随机增量

【BZOJ3564】旋转点+把椭圆沿x缩成圆，然后最小圆覆盖

【BZOJ1891&&BZOJ2050】被数据范围吓到了，写dinicT了，于是学习了HK算法……，先求一遍匹配，然后在残余网络求scc，没了

【BZOJ4059】预处理每个数的前驱后继位置,对于一段区间,找出其中的单个元素,递归判断左右两侧,从两端同是枚举可以证明为\(O(nlogn)\)