4
27
2015
5

人傻就该多做题#3

[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)\)

Category: OI | Tags: | Read Count: 939
lmxyy 说:
2015年4月29日 11:34

可不可以求一下 BZOJ 3935 Rbtree 的做法。。。

lmxyy 说:
2015年4月29日 22:12

在哪里啊。我怎么没有看到。

lmxyy 说:
2015年4月29日 22:16

看到了,但是怎么看不懂啊???还是谢谢了!!!

Avatar_small
kzoacn 说:
2015年4月29日 22:45

@lmxyy: 其实还有一种O(n^3)的题解但是我没有看懂 = =,原文如下:
f(i,j,k) 表示以 i 为根的子树中,有 j 个黑点,且子树内的黑点外加 k 可以覆盖整个子树的最小代价。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com