重走长征路---OI每周刷题记录---5月17日 2014
总目录详见
做题原则，找不到测评地址的题不做。2018-11-28
重走长征路---OI每周刷题记录---5月17日 2014
本周共计24题+题
测评地址：
AC自动机+dp
1.「JoyOI1519」博彩游戏
构造：
2.「cf430A」Points and Segments (easy)
模拟：
3.「cf430B」Balls Game
4.「bzoj1755」[Usaco2005 qua]Bank Interest
5.「cf432A」Choosing Teams
单调队列：
6.「bzoj1293」[SCOI2009]生日礼物
树的直径+树形dp：
7.「JoyOI1520」树的直径
spfa：
8.「JoyOI1733」[APIO2011]寻路
dfs+kruskal：
9.「bzoj1016」[JSOI2008]最小生成树计数
离线+树状数组：
10.「bzoj1878」[SDOI2009]HH的项链
11.「bzoj2743」[HEOI2012]采花
离线+线段树：
12.「bzoj3339」Rmq Problem
并查集：
13.「bzoj1116」[POI2008]CLO
博弈论：
14.「bzoj1115」[POI2009]石子游戏Kam
线段树套平衡树：
15.「poj2104」K-th Number
tarjan：
16.「bzoj2208」[Jsoi2010]连通数
排列组合：
17.「bzoj3505」[Cqoi2014]数三角形
高精度gcd：
18.「bzoj1876」[SDOI2009]SuperGCD
bfs：
19.「JoyOI1234」bench与奔驰
并查集/tarjan：
20.「bzoj1529」[POI2005]ska Piggy banks
dp+矩阵乘法：
21.「bzoj1898」Swamp 沼泽鳄鱼
异或：
22.「bzoj1603」[Usaco2008 Oct]打谷机
背包dp：
23.「JoyOI1608」小熊分糖
概率与期望：
24.「bzoj2318」Spoj4060 game with probability Problem
题解：
AC自动机+dp
1.「JoyOI1519」博彩游戏
构造：
2.「cf430A」Points and Segments (easy)
模拟：
3.「cf430B」Balls Game
4.「bzoj1755」[Usaco2005 qua]Bank Interest
5.「cf432A」Choosing Teams
单调队列：
6.「bzoj1293」[SCOI2009]生日礼物
//P2564 [SCOI2009]生日礼物 //在线测评地址https://www.luogu.org/problemnew/show/P2564 //看了数据范围，需采用O(n)或O(nlogn)的算法。 //很难想象该题会与单调队列挂钩。 //https://blog..net/quan_tum/article/details/82764384此文代码写得易懂，且代码量小。 //样例通过，提交AC。20190424 #include <cstdio> #include <algorithm> #include <cstring> #define maxn 1000100 using namespace std; int n,k,cnt=0,pos[65]; struct node{ int c,p; }a[maxn]; int cmp(node a,node b){ return a.p<b.p; } int main(){ int i,j,t,h=1,ans; scanf("%d%d",&n,&k); for(i=1;i<=k;i++){ scanf("%d",&t); for(j=1;j<=t;j++)cnt++,a[cnt].c=i,scanf("%d",&a[cnt].p); } ans=a[n].p-a[1].p; sort(a+1,a+1+n,cmp); memset(pos,-1,sizeof(pos)); cnt=0; for(i=1;i<=n;i++){ if(pos[a[i].c]==-1)cnt++; pos[a[i].c]=a[i].p; while(h<i&&a[h].p!=pos[a[h].c])h++; if(cnt==k&&ans>pos[a[i].c]-pos[a[h].c])ans=pos[a[i].c]-pos[a[h].c]; } printf("%d ",ans); return 0; }
树的直径+树形dp：
7.「JoyOI1520」树的直径
spfa：
8.「JoyOI1733」[APIO2011]寻路
dfs+kruskal：
9.「bzoj1016」[JSOI2008]最小生成树计数
离线+树状数组：
10.「bzoj1878」[SDOI2009]HH的项链
11.「bzoj2743」[HEOI2012]采花
离线+线段树：
12.「bzoj3339」Rmq Problem
并查集：
13.「bzoj1116」[POI2008]CLO
博弈论：
14.「bzoj1115」[POI2009]石子游戏Kam
线段树套平衡树：
15.「poj2104」K-th Number
tarjan：
16.「bzoj2208」[Jsoi2010]连通数
排列组合：
17.「bzoj3505」[Cqoi2014]数三角形
高精度gcd：
18.「bzoj1876」[SDOI2009]SuperGCD
bfs：
19.「JoyOI1234」bench与奔驰
并查集/tarjan：
20.「bzoj1529」[POI2005]ska Piggy banks
dp+矩阵乘法：
21.「bzoj1898」Swamp 沼泽鳄鱼
异或：
22.「bzoj1603」[Usaco2008 Oct]打谷机
背包dp：
23.「JoyOI1608」小熊分糖
概率与期望：
24.「bzoj2318」Spoj4060 game with probability Problem