決定在 codeforces?練題啦，決定每個比賽刷前四道。。。太難就算了
D796動車。796A Buying A House
題意：給出x軸上的n 個點，每個點有個權值，問離m?點最近的權值小于等于k?的點離m的距離。單位是10。
思路：大水題。用l、r分別向左向右找即可。
代碼：
1 #include<stdio.h> 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<stdio.h> 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<m; 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<stdio.h> 2 #include<vector> 3 #include<queue> 4 #include<map> 5 #include<algorithm> 6 using namespace std; 7 #define N 300005 8 #define INF 1e9 9 10 struct Node{ 11 int x, w; 12 bool operator < (Node b) const{ 13 return w<b.w; 14 } 15 }; 16 priority_queue<Node> q; 17 18 map<pair<int, int>, bool> mp; 19 20 21 void add(int a, int b){ 22 mp[make_pair(a, b)]=1; 23 mp[make_pair(b, a)]=1; 24 } 25 26 queue<Node> tq; 27 int get(int a){ 28 int maxt=-INF; 29 while(q.size()){ 30 Node tmp = q.top(); 31 tq.push(tmp); 32 q.pop(); 33 bool flag=1; 34 if(mp.find(make_pair(a, tmp.x))!=mp.end()){ //鄰邊-1 35 tmp.w-=1; 36 flag=0; 37 } 38 else if(tmp.x==a) tmp.w-=2, flag=0; //根-2 39 if(flag && maxt>=tmp.w) break; 40 if(maxt-1>tmp.w) break; 41 maxt=max(maxt, tmp.w); 42 } 43 while(tq.size()){ 44 q.push(tq.front()); 45 tq.pop(); 46 } 47 return maxt; 48 } 49 50 int main(){ 51 int n, a, b; 52 while(~scanf("%d", &n)){ 53 while(q.size()) q.pop(); 54 for(int i=1; i<=n; i++){ 55 scanf("%d", &a); 56 a+=2; 57 Node tmp; 58 tmp.x=i; 59 tmp.w=a; 60 q.push(tmp); 61 } 62 mp.clear(); 63 for(int i=1; i<n; i++){ 64 scanf("%d%d", &a, &b); 65 add(a, b); 66 } 67 int mint=get(1); 68 for(int i=2; i<=n; i++){ 69 mint=min(mint, get(i)); 70 } 71 printf("%d\n", mint); 72 } 73 return 0; 74 }
796D Police Stations
題意：有n?個城市，其中m 個城市有警察局，要求每個城市離警察局距離不能大于d，接下來給出n 個城市之間的路（是一根樹，所以n-1條路），問最多可以刪掉多少條路。
思路：
廣搜。挺難的，我先是思路錯了wa，后來思路對了，又tle了好幾次。每個城市離警察局不能超過d，那么我從每一個警察局出發，對于每一個城市，用num表示最多還可以走幾步（警察局的num等于d），第一次bfs?就用于求出num數組。接著第二次bfs，從每一個警察局出發，如果從該警察局到城市x?后還可以走d 步，這個d<num[x]時，這條路肯定可以不要，如果d==num[x]且城市x?第一次到達，則保留下來，如果不是第一次到達，也可以刪掉。處理的時候要小心。。
剛開始我第一個bfs 也是對每一個警察局開始廣搜，結果超時，其實可以把所有警察局加入隊列，然后進行一次廣搜即可。
代碼：
1 #include<stdio.h> 2 #include<string.h> 3 #include<set> 4 #include<map> 5 #include<vector> 6 #include<queue> 7 #include<algorithm> 8 using namespace std; 9 10 #define N 300005 11 bool u[N]; 12 13 struct Point{ 14 Point(int cx, int cd){ 15 x=cx; 16 d=cd; 17 } 18 int x, d; 19 }; 20 21 vector<Point> v[N]; 22 int num[N]; 23 24 void add(int x, int y, int i){ 25 Point p(y, i); 26 v[x].push_back(p); 27 p.x=x; 28 v[y].push_back(p); 29 } 30 bool vis[N]; 31 int ans[N], ao; 32 33 34 35 queue<Point> q; 36 void bfs(){ 37 while(q.size()){ 38 Point a = q.front(); 39 q.pop(); 40 for(int i=0; i<v[a.x].size(); i++){ 41 int ad=v[a.x][i].x; 42 Point b(ad, a.d-1); 43 if(b.d>num[b.x]){ 44 num[b.x]=b.d; 45 if(b.d>0) q.push(b); 46 } 47 } 48 } 49 } 50 51 void bfs2(int s, int k){ 52 Point p(s, k); 53 q.push(p); 54 while(q.size()){ 55 Point a = q.front(); 56 q.pop(); 57 for(int i=0; i<v[a.x].size(); i++){ 58 int ad=v[a.x][i].x, bno=v[a.x][i].d; 59 Point b(ad, a.d-1); 60 61 if(b.d==num[b.x] && u[b.x]==0){ 62 u[b.x]=1; 63 vis[bno]=1; 64 q.push(b); 65 } 66 else if(vis[bno]==0){ 67 vis[bno]=1; 68 ans[ao++]=bno; 69 } 70 } 71 } 72 } 73 74 75 int main(){ 76 int n, m, k, x, y; 77 while(~scanf("%d%d%d", &n, &m, &k)){ 78 memset(u, 0, sizeof(u)); 79 memset(num, -1, sizeof(num)); 80 for(int i=0; i<m; i++){ 81 scanf("%d", &x); 82 u[x]=1; 83 num[x]=k; 84 Point tmp(x, k); 85 q.push(tmp); 86 } 87 for(int i=1; i<=n; i++) v[i].clear(); 88 for(int i=1; i<n; i++){ 89 scanf("%d%d", &x, &y); 90 add(x, y, i); 91 } 92 93 94 bfs(); 95 96 memset(vis, 0, sizeof(vis)); 97 ao=0; 98 for(int i=1; i<=n; i++){ 99 if(u[i]==1){ 100 bfs2(i, num[i]); 101 } 102 } 103 104 printf("%d\n", ao); 105 for(int i=0; i<ao; i++){ 106 printf("%d", ans[i]); 107 if(i==ao-1) printf("\n"); 108 else printf(" "); 109 } 110 } 111 return 0; 112 }
?
