重走长征路---OI每周刷题记录---5月10日 2014
总目录详见
做题原则，找不到测评地址的题不做。2018-11-28
重走长征路---OI每周刷题记录---5月10日 2014
本周共计19题+题
测评地址：
网络流：
1.「JoyOI1517」飘飘乎居士的乌龟
2.「bzoj1458」士兵占领
后缀数组：
3.「bzoj1031」[JSOI2007]字符加密Cipher
线段树
4.「bzoj1593」[Usaco2008 Feb]Hotel 旅馆
dp：
5.「bzoj1037」 [ZJOI2008]生日聚会Party
heap+贪心+链表：
6.「bzoj2288」「POJ Challenge」生日礼物
7.「bzoj1150」[CTSC2007]数据备份Backup
抽屉原理：
8.「poj2356」Find a multiple
lca：
9.「bzoj1787」[Ahoi2008]Meet 紧急集合
贪心：
10.「bzoj2697」特技飞行
中位数：
11.「bzoj3293」 [Cqoi2011]分金币
费用流：
12.「bzoj3280」小R的烦恼
暴力：
13.「bzoj1800」[Ahoi2009]fly 飞行棋
并查集：
14. //在线测评地址
二分+后缀数组：
15.「poj1743」Musical Theme
kmp+dp+矩阵乘法：
16.「bzoj1009」[HNOI2008]GT考试
模拟：
17.「NOIP模拟赛」机器人
spfa：
18.「NOIP模拟赛」虫洞
dp+矩阵乘法：
19.「NOIP模拟赛」数列
题解：
网络流：
1.「JoyOI1517」飘飘乎居士的乌龟
2.「bzoj1458」士兵占领
后缀数组：
3.「bzoj1031」[JSOI2007]字符加密Cipher
线段树
4.「bzoj1593」[Usaco2008 Feb]Hotel 旅馆
dp：
5.「bzoj1037」 [ZJOI2008]生日聚会Party
heap+贪心+链表：
6.「bzoj2288」「POJ Challenge」生日礼物
7.「bzoj1150」[CTSC2007]数据备份Backup
抽屉原理：
8.「poj2356」Find a multiple
lca：
9.「bzoj1787」[Ahoi2008]Meet 紧急集合
贪心：
10.「bzoj2697」特技飞行
中位数：
11.「bzoj3293」 [Cqoi2011]分金币
费用流：
12.「bzoj3280」小R的烦恼
暴力：
13.「bzoj1800」[Ahoi2009]fly 飞行棋
并查集：
14.「bzoj1854」[Scoi2010]游戏
//P1640 [SCOI2010]连续攻击游戏 //在线测评地址https://www.luogu.org/problemnew/show/P1640 //感觉很难与并差集联系在一起 //https://blog..net/QTY2001/article/details/78042179此文思路写得不错，代码也够短，思路摘抄如下 //我们来考虑把属性做边，武器做便。 //如果一个联通块n是树，则能满足n-1个， //如果有环，则能满足n个。 //我们要把小值并到大值下面，因为优先满足小值，才能满足大值。 //如果能构成一个环，整个联通快就一定满足。 //看了代码，跟踪了数据，弄懂了。 //样例通过，提交AC。2019-4-3 #include <stdio.h> #include <string.h> #define maxn 10100 int n,m,f[maxn],vis[maxn]; int min(int a,int b){ return a<b?a:b; } int getf(int u){ return f[u]==u?u:f[u]=getf(f[u]); } int main(){ int x,y,i,f1,f2; memset(vis,0,sizeof(vis)); scanf("%d",&n),m=min(n,10000),m++;//m++是为了处理环的情况。 for(i=1;i<=m;i++)f[i]=i; for(i=1;i<=n;i++){ scanf("%d%d",&x,&y); f1=getf(x),f2=getf(y); if(f1==f2)vis[f1]=1; else if(f1<f2)f[f1]=f2,vis[f1]=1;//大的放上面，小的挂下面 else f[f2]=f1,vis[f2]=1; } for(i=1;i<=m;i++) if(!vis[i]){ printf("%d ",i-1); break; } return 0; }
二分+后缀数组：
15.「poj1743」Musical Theme
kmp+dp+矩阵乘法：
16.「bzoj1009」[HNOI2008]GT考试
模拟：
17.「NOIP模拟赛」机器人
spfa：
18.「NOIP模拟赛」虫洞
dp+矩阵乘法：
19.「NOIP模拟赛」数列
