重走长征路---OI每周刷题记录---3月1日 2014
总目录详见
做题原则，找不到测评地址的题不做。2018-11-28
重走长征路---OI每周刷题记录---2月22日 2014
本周共计 题+题
测评地址：
线段树
1.「poj2828」Buy Tickets
二分
2.「JoyOI1359」收入计划
spfa+二分
3.「usaco2007.1」架设电话线
素数筛法
4. //在线测评地址
网络流
5.「codevs1034」家园
6.「网络流24题」最小路径覆盖问题
7.「poj1740」A New Stone Game Nim
博弈论
8.「poj2234」Matches Game
9.「bzoj1054」移动玩具 bfs+hash
bfs
10.最少转弯
11.「poj3275」Ranking the Cows
spfa
12.「poj3255」Roadblocks
13.「poj1062」昂贵的聘礼
dfs+dp
14.「bzoj1040」骑士
treap
15.「bzoj1862/1056」GameZ游戏排名系统
16.「bzoj3224」普通平衡树
费用流
17.「JoyOI1982」武器分配
18.「bzoj1877」晨跑
计算几何+凸壳
19.「bzoj1007」水平可见直线
并查集
20.「bzoj1015」星球大战starwar
zkw线段树
21.「codevs1080」线段树练习1
题解：
线段树
1.「poj2828」Buy Tickets
二分
2.「JoyOI1359」收入计划
spfa+二分
3.「usaco2007.1」架设电话线
素数筛法
4.「poj2262」Goldbach’s Conjecture
//Goldbachs Conjecture POJ - 2262 //在线测评地址https://vjudge.net/problem/POJ-2262 //先用 线性筛 筛出 1000000 以内的素数 //发现有78498个 //没把握的是，每次找到和的关系，极限是78498/2,如果是100个数据,稳过 //样例通过，提交AC。2019-2-16 13:12 #include <stdio.h> #include <string.h> #define maxn 1000100 int prime[maxn],not_prime[maxn],tot=0; void linear_shaker(int x){ int i,j; memset(not_prime,0,sizeof(not_prime)); for(i=2;i<=x;i++){ if(!not_prime[i])prime[++tot]=i; for(j=1;prime[j]*i<=x;j++){ not_prime[prime[j]*i]=1; if(i%prime[j]==0)break; } } } int main(){ int i,z,x,y; linear_shaker(maxn-100); while(scanf("%d",&z)&&z){//此处不能写成 while(scanf("%d",&z)&z) for(i=1;i<=tot;i++) if(not_prime[z-prime[i]]==0){ printf("%d = %d + %d ",z,prime[i],z-prime[i]); break; } } return 0; }
网络流
5.「codevs1034」家园
6.「网络流24题」最小路径覆盖问题
7.「poj1740」A New Stone Game Nim
博弈论
8.「poj2234」Matches Game
9.「bzoj1054」移动玩具 bfs+hash
bfs
10.最少转弯
11.「poj3275」Ranking the Cows
spfa
12.「poj3255」Roadblocks
13.「poj1062」昂贵的聘礼
dfs+dp
14.「bzoj1040」骑士
treap
15.「bzoj1862/1056」GameZ游戏排名系统
16.「bzoj3224」普通平衡树
费用流
17.「JoyOI1982」武器分配
18.「bzoj1877」晨跑
计算几何+凸壳
19.「bzoj1007」水平可见直线
并查集
20.「bzoj1015」星球大战starwar
zkw线段树
21.「codevs1080」线段树练习1
