5
15
2015
0

【屯】五月半才开始的五月病

……总算开始打算屯一发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


屯完了。。交的时候有道低飞的代码没能跑过。。蛋碎了= =||

Category: 日常 | Tags: | Read Count: 1497

登录 *


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