2
15
2015
4

人傻就该多做题#1

计数菌:

50

 

代码菌:http://kzoacn.is-programmer.com/code

[3.14]完结撒花!

【BZOJ2565】manacher

BZOJ2729ans=n!*(A(n+1,2)*A(n+3,m)+2*(n+1)*A(n+2,m-1)*m)我的高精度已经废了

【BZOJ2730】暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力

【BZOJ1415】

bfs预处理\( next[i][j] \)表示聪聪在i可可在j,聪聪的下一个位置

\( f[i][j] \)表示聪聪在i可可在j,聪聪吃到可可的期望次数
\( G[i] \)表示i的边,\( deg[i] \)表示i的度数
\[ f[i][j]=\frac{\sum_{v \in G[j]} f[next[next[i][j]][j]][v]+f[next[next[i][j]][j]][j]}{deg[j]+1}+1 \]
边界:\( f[i][i]=0 \) 若\( next[next[i][j]]=j \)或\( next[i][j]=j \)则\( f[i][j]=1 \)
【BZOJ1833】传送门
【BZOJ2435】说好的卡爆栈呢
【BZOJ3239】BSGS裸题
【BZOJ2318】传送门
【BZOJ3165】传送门
【BZOJ1568】同上
【BZOJ3208】暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力
【BZOJ3043】差分,操作等价于+-1,正的减负的加,没了
【BZOJ1419】传送门
【BZOJ1018】分类讨论到吐
【BZOJ3786】(伪)toptree
【BZOJ3153】传送门
【BZOJ2223】整体二分
【BZOJ2048】\( \sum_{i=1}^n \frac1{2i}=\frac{ln(n+1)+r}2 \)
【BZOJ3544】前缀和,从左往右扫一遍,在set中边插入边查询
【BZOJ3550】单纯形直接上
【BZOJ2007】裸对偶图最短路
【BZOJ2306】\( f[u][v][d] \)表示从u到v经过\(2^d\)个边的最大值,则\( f[u][v][d]=max(f[u][x][d-1]+p^{2^{d-1}}f[x][v][d-1]) \) ,然后挂精度,然后……就那啥了
【BZOJ1369】对于数据来说三种颜色就可以了……
【BZOJ3036】\(f[i]\)表示从i走到n的期望,[tex]f[u]=\frac{\sum_{(u,v)\in E}f[v]+w}{out[u]}[/tex]
【BZOJ3884】欧拉定理[tex] a^x \% p =a^{x \% \varphi(p) }\% p[/tex] 以及[tex]cx \% cy =c(x \% y)[/tex]然后就可以做此题了
方便起见我们令x等于那一坨2的幂,k为p的2的因子的数量,对于奇数来说直接递归计算,偶数的话\[ans=2^k(2^{x-k}\% \frac{p}{2^k})=2^k(2^{x+k(\varphi(\frac{p}{2^k})-1)}\% \varphi(\frac{p}{2^k}))\]
由于\(x=\varphi(x)\)的递归次数远小于\(log(x)\),就可以过喽,加上记忆化复杂度更好,只不过会MLE……P.S. 算phi的话直接暴力44ms,线性筛1~2s……
upd:咦……似乎不分类讨论就行了,看这里

【BZOJ2460】按价值降序贪心,线形基判断是否加入就可以了,证明见花神的拟阵 P.S. 终于挤进第二页了……这么弱现在才到第二页,你看看人家xxx和yyy还有人家zzz,比你高到不知道哪里去了

【BZOJ2464】水题

【BZOJ2795】答案一定是长度的约数,直接\(O(\sqrt n)\)枚举约数+hash不行,如果一个循环节可行那么他的倍数也可行,于是预处理出每个数的最小质因子,每次尝试缩小规模,每次询问做到\(O(log(n))\)

【BZOJ3894】好像在哪里见过的最小割裸题……

【BZOJ3083】链剖+dfs序+分类讨论

【BZOJ1978】dp[i]表示以i为因数的答案,枚举因数dp

【BZOJ1409】指数就是fib,矩乘+欧拉定理秒

【BZOJ3173】前缀max+维护序列,fhqTreap秒之

【BZOJ3282】LCT裸题

【BZOJ2141】分块轻松愉♂悦

【BZOJ3306】3083弱化版,本来还以为会有菊花图呢……

【BZOJ1087】水状压
【BZOJ2662】分层图……

【BZOJ3774】题解

【BZOJ3034】质数从小到大选,高(Py)精(th)度(on)(python会T……

【BZOJ1149】若有解答案显然为所有节点的 \( \sum \)[左子树size<右子树size] ,无解情况是maxdep-mindep>1或一棵树的左右子树均不完全,dfs即可

【BZOJ2588】LCA+主席树

【BZOJ3123】上题的启发式合并加强版,没写垃圾回收过了,有空写一写垃圾回收版本

【BZOJ2836】链剖+dfs序+sgt裸题

【BZOJ2843】LCT裸题,也可以离线链剖

【BZOJ2947】multiset

【BZOJ1924】建图缩点最长路

【BZOJ2462&&BZOJ2351】二维hash

【BZOJ3288】phi的前缀积

Category: OI | Tags: | Read Count: 1088
Avatar_small
CreationAugust 说:
2015年2月16日 17:41

一下午又刷了两个题太神了OTZ

PoPoQQQ 说:
2015年2月24日 20:26

2223不用整体二分吧= = 出现次数大于len/2的数一定是中位数,因此只要取区间中位数验证一下就行了 用可持久化线段树就能搞

Avatar_small
kzoacn 说:
2015年2月25日 11:58

@PoPoQQQ: 能整体二分的我都不写主席树……个人感觉整体二分更好写一点……而且没有内存的问题

PoPoQQQ 说:
2015年2月27日 10:47

@kzoacn: 确实- - 之前就有整体二分的题卡主席树的内存这种事情- - 不过还是觉得主席树更无脑一些- -


登录 *


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