……总算开始打算屯一发bzoj 的题了。。。基于最近的刷题情况→_→被大神喷刷题狂魔了=_+|||
[5.19]10t撒花= -屯题速度是不是太慢了
[5.26]25t撒花，还有一半=_=|||
[6.1]45t撒花→_→最后6t
现在做了几道：
51+3
p1047：先行用单调队列搞出最大最小值，再列搞出来，然后就n²枚举
p2241：此题为暴力而生n=100，n^6的暴力加点剪枝跑的飞起
p1486：二分+dfs判负环
p2732：设y=ax²+bx→y1<=ax²+bx<=y2化一下：(b≥y1/x-ax)and(b<=y2/x-ax)然后就是求半平面交了=_+|||不知道n²过不过的了。。我打的nlogn跑的超慢orz_sone爷rank1，128ms，然后我3400+ms=_=|||
p2705：求∑gcd(i,n)(1<=i<=n),设k为n的约数,f(k)表示gcd(x,n)=k,x的个数,则ans=∑(k*f(k))(k为n的约数),因为gcd(x,n)=k,gcd(x/k,n/k)=1,所以f(k)=phi(n/k),ans=∑(k*phi(n/k))
p1876：更相减损术= =|||
p1011：这算什么。。乱搞- =|||
p1832：倍增LCA
p2429：最小生成树，大于最小生成树上最长边的a[i]个数
p1878：离线+树状数组前缀和
p1821：先按距离排序，然后并查集维护联通性
p1856：C(n,n+m)-C(n+1,n+m)→((n+m)!(n+1-m))/((n+1)!m!)，逆元搞下就行了
p1830：最终的串一定是三个串的前缀。。于是枚举前缀即可
p4080：→_→随机化生成一个序列。。。然后乱搞即可...由于是使过去的= -所以直接交了
p4008：0 0|||→f[i][j]表示前i张牌，还有j轮的概率。。对于第i+1张0 0可能打出又可能不打出转移：f[i][j]×(1-p[i+1])^j→f[i+1][j]和f[i][j]×(1-(1-p[i+1])^j)→f[i+1][j-1]
p3916：暴力匹配，允许一次失配
p2733：每个联通块一颗线段树，操作就是线段树的合并，于是可以用并查集维护联通性
p3111：初一时的坑= =，当时想起来30分可能还是会的233，后来zzk给我们讲了一下。。水Dp
p3680：传说中的模拟退火，爬山法，就是求受力平衡点，然后从(0,0)向答案逼近，逼近的距离越来越小
p1806：f[i][a1][a2][b1][b2]表示选到第i个字母，第一辆矿车末尾是a1,a2，第二辆是b1,b2，然后随便转移，滚动数组优化空间
p2789：树状数组逆序对
p1003：spfa+Dp
p1015：离线倒序加点，并查集搞搞就行了
p1050：。。怎么看这题都有印象= =原来是codevs上的舒适的路线233
p1899：我的dp好弱啊。。。f[i][j]表示前i个人，一队wait时间为j时的最优值，然后考虑进哪个队
p1930：标算是什么。。拆点费用流随便搞。。但是= =恶意卡spfa的数据真是吐血，幸好我有善良的学长~
p1867：f[i][j]表示到第ij个位置上的概率讨论有无钉子的情况即可
p1880：spfa+最长链
p1786：f[i][j]表示第i个-1填j的最小最小代价
p1831：同p1786
p2435：bfs和dfs都能水过。。那些0ms是打表的吗= =|||
p1145：ans=f[1324]-f[1243]-f[1432]=(f[1x2x]-f[1423])-(f[12xx]-f[1234])-(f[14xx]-f[1423])=f[1x2x]+f[1234]+f[13xx]-f[1xxx];然后这4个都可以用树状数组搞出来→_→前排膜黄学长跑的怎么那么快
p2242：第一问快速幂，第二问因为 ax≡b(mod n)→ax-ny=b 由于n为质数所以a与n互质，所以x≡a^(-1)b(mod n)，第三问GSBS
p2729：数学题，高精度搞下就行了
p1324：黑白染色最小割
p1491：被描述唬住系列，Floyd模拟就行了
p3223：填坑系列= =|||指针写splay真是优美。。。
p3229：GarsiaWachs算法→_→什么鬼，从序列左端开始找第一个w[k-1]<w[k+1]的k,合并w[k-1],w[k]，然后从当前点往左找第一个w[j]>w[k-1]+w[k]的j,把合并后的值插j后面..直到剩下一堆，这样裸的暴力弄怎么看都是n²的然而1s过了
p1081：找规律
p3098：多rand几次就行了= =|||好担心rp broken
p1965：x≡(n/2+1)^m*l(mod n+1)
p1789：同1830
p2186：求phi(m!)*(n!/m!) phi(m!)=m!*(p-1)/p(p为m!的质因数) 所以ans=m!*(p-1)/p*(n!/m!)→n!*(p-1)/p
p3444：考虑一张无向图，把要挨着的东西全连上，显然要合法就必须每个联通块是一条链，记链数为b，a个人没要求ans=2^b*(a+b)!
p2048：到现在才去添这个坑。。调和级数极限公式→_→Ak在说的欧拉常数原来是用这的
p2423：f[i][j]表示A前i B前j 最长公共子序列长度 g[i][j]记的是个数，然后乱搞计数即可
p2743：参照1878
p2438：scc缩点后ans=入度为0的点的个数，对于只有一个点的联通块特判
p1264：树状数组维护求LCS
p3174：排序后水dp
p2822：卡特兰数第n项。。
p1037：f[i][j][k1][k2]表示前i个人有j个男孩，其中男孩最多比女孩多k1人，女比男多k2人，f[i+1][j+1][k1+1][k2-1]=∑(f[i][j][k1][k2]),f[i+1][j][k1-1][k2+1]=∑(f[i][j][k1][k2])
p1407：贱贱3个月前做的题。。c[i]+x*p[i]≡c[j]+x*p[j](mod m)→(p[i]-p[j])*x-my=c[j]-c[i]
p2565：manacher+Dp
屯完了。。交的时候有道低飞的代码没能跑过。。蛋碎了= =||
评论 (0)
