重走长征路---OI每周刷题记录---3月1日 2014

总目录详见https://blog.csdn.net/mrcrack/article/details/84471041

做题原则，找不到测评地址的题不做。2018-11-28

重走长征路---OI每周刷题记录---2月22日  2014

本周共计 题+题

测评地址：

线段树

1.「poj2828」Buy Tickets 

二分

2.「JoyOI1359」收入计划 

spfa+二分

3.「usaco2007.1」架设电话线 

素数筛法

4.「poj2262」Goldbach’s Conjecture   //在线测评地址https://vjudge.net/problem/POJ-2262

网络流

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 

//Goldbach's 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\n",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