codeforces 796A-D

决定在 codeforces 练题啦，决定每个比赛刷前四道。。。太难就算了

796A Buying A House

题意：给出x轴上的n 个点，每个点有个权值，问离m 点最近的权值小于等于k 的点离m的距离。单位是10。

思路：大水题。用l、r分别向左向右找即可。

代码：

 1 #include
 2 int main(){
 3   int n, m, k;
 4   int w[105];
 5   while(~scanf("%d%d%d", &n, &m, &k)){
 6     for(int i=1; i<=n; i++){
 7       scanf("%d", &w[i]);
 8     }
 9     int l=m-1, r=m+1;
10     while(l>=1 || r<=n){
11       if(l>=1 && w[l]<=k && w[l]!=0) break;
12       if(r<=n && w[r]<=k && w[r]!=0) break;
13       l--;
14       r++;
15     }
16     printf("%d0\n", r-m);
17   }
18   return 0;
19 }

796B Find The Bone

题意：x轴上有n 个点，其中m 个有洞，初始一个球放在坐标1 ，有k 次操作，每次操作给出两个坐标，交换两个坐标的内容，如果球落入洞中，则不能再移动，问k 次操作后，球的位置。

思路：简单模拟。用pos表示球的当前位置，用pause表示球还能否移动，用u 数组标记每个位置是否有洞。有一个坑就是要判断一下初始位置有没有洞。

代码：

 1 #include
 2 #include<string.h>
 3 bool u[1000005];
 4 int main(){
 5   int n, m, k, x, y;
 6   while(~scanf("%d%d%d", &n, &m, &k)){
 7     memset(u, 0, sizeof(u));
 8     for(int i=0; i){
 9       scanf("%d", &x);
10       u[x]=1;
11     }
12     int pos=1;
13     bool pause=u[1]?true:false;
14     while(k--){
15       scanf("%d%d", &x, &y);
16       if(!pause){
17         if(x==pos) pos=y;
18         else if(pos==y) pos=x;
19         if(u[pos]==1) pause=true;
20       }
21     }
22     printf("%d\n", pos);
23   }
24   return 0;
25 }

796C Bank Hacking

题意：给出n 个结点的树，每个结点有各自的权值，你有w 的力量，可以取走权值小于w 的结点，要求一一取走这n 个结点，取走x 结点后所有和x 相邻的还有次相邻（就是距离是2）的结点权值加1（必须处于连通状态），问w 的最小值。注意，第一个取走结点的位置可以自己挑，后面的必须是已取走结点的邻点。

思路：

　　被题意坑了好久，假设图为1-2-3-4，先取走3，然后1、2、4的权值加1，现在取走2，1的权值加1（4的权值不会改变，因为2-4已经不连通）。除掉题意的坑以外，这题还是很简单的，假设你先取走x 点，所有x 的邻接点权值加1，其余点权值都加2。所以，w 的值只取决于第一个取走的点。

　　n 的值高达30万，所以肯定不能用n^2解决，我呢，先把所有结点权值加2，接着存入优先队列。然后枚举第一个取走的点，用get(i)表示他的最大值，get(i)里面不断取出队头，如果是i，则权值-2继续判断，如果是i 的邻点，则权值-1继续判断，如果是其余的结点，则答案就出来了，接着将取出的点再放入优先队列。

代码：

 1 #include
 2 #include
 3 #include
 4 #include

796D Police Stations

题意：有n 个城市，其中m 个城市有警察局，要求每个城市离警察局距离不能大于d，接下来给出n 个城市之间的路（是一根树，所以n-1条路），问最多可以删掉多少条路。

思路：

　　广搜。挺难的，我先是思路错了wa，后来思路对了，又tle了好几次。每个城市离警察局不能超过d，那么我从每一个警察局出发，对于每一个城市，用num表示最多还可以走几步（警察局的num等于d），第一次bfs 就用于求出num数组。接着第二次bfs，从每一个警察局出发，如果从该警察局到城市x 后还可以走d 步，这个d

　　刚开始我第一个bfs 也是对每一个警察局开始广搜，结果超时，其实可以把所有警察局加入队列，然后进行一次广搜即可。

代码：

  1 #include
  2 #include<string.h>
  3 #include<set>
  4 #include