决定在 codeforces 练题啦，决定每个比赛刷前四道。。。太难就算了
题意：给出x轴上的n 个点，每个点有个权值，问离m 点最近的权值小于等于k 的点离m的距离。单位是10。
思路：大水题。用l、r分别向左向右找即可。
代码：
#include<stdio.h>
int main(){
int n, m, k;
int w[];
while(~scanf("%d%d%d", &n, &m, &k)){
for(int i=; i<=n; i++){
scanf("%d", &w[i]);
}
int l=m-, r=m+;
while(l>= || r<=n){
if(l>= && w[l]<=k && w[l]!=) break;
if(r<=n && w[r]<=k && w[r]!=) break;
l--;
r++;
}
printf("%d0\n", r-m);
}
return ;
}
796A AC代码
题意：x轴上有n 个点，其中m 个有洞，初始一个球放在坐标1 ，有k 次操作，每次操作给出两个坐标，交换两个坐标的内容，如果球落入洞中，则不能再移动，问k 次操作后，球的位置。
思路：简单模拟。用pos表示球的当前位置，用pause表示球还能否移动，用u 数组标记每个位置是否有洞。有一个坑就是要判断一下初始位置有没有洞。
代码：
#include<stdio.h>
#include<string.h>
bool u[];
int main(){
int n, m, k, x, y;
while(~scanf("%d%d%d", &n, &m, &k)){
memset(u, , sizeof(u));
for(int i=; i<m; i++){
scanf("%d", &x);
u[x]=;
}
int pos=;
bool pause=u[]?true:false;
while(k--){
scanf("%d%d", &x, &y);
if(!pause){
if(x==pos) pos=y;
else if(pos==y) pos=x;
if(u[pos]==) pause=true;
}
}
printf("%d\n", pos);
}
return ;
}
796B AC代码
题意：给出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继续判断，如果是其余的结点，则答案就出来了，接着将取出的点再放入优先队列。
代码：
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
#define N 300005
#define INF 1e9 struct Node{
int x, w;
bool operator < (Node b) const{
return w<b.w;
}
};
priority_queue<Node> q; map<pair<int, int>, bool> mp; void add(int a, int b){
mp[make_pair(a, b)]=;
mp[make_pair(b, a)]=;
} queue<Node> tq;
int get(int a){
int maxt=-INF;
while(q.size()){
Node tmp = q.top();
tq.push(tmp);
q.pop();
bool flag=;
if(mp.find(make_pair(a, tmp.x))!=mp.end()){ //邻边-1
tmp.w-=;
flag=;
}
else if(tmp.x==a) tmp.w-=, flag=; //根-2
if(flag && maxt>=tmp.w) break;
if(maxt->tmp.w) break;
maxt=max(maxt, tmp.w);
}
while(tq.size()){
q.push(tq.front());
tq.pop();
}
return maxt;
} int main(){
int n, a, b;
while(~scanf("%d", &n)){
while(q.size()) q.pop();
for(int i=; i<=n; i++){
scanf("%d", &a);
a+=;
Node tmp;
tmp.x=i;
tmp.w=a;
q.push(tmp);
}
mp.clear();
for(int i=; i<n; i++){
scanf("%d%d", &a, &b);
add(a, b);
}
int mint=get();
for(int i=; i<=n; i++){
mint=min(mint, get(i));
}
printf("%d\n", mint);
}
return ;
}
796C AC代码
题意：有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 也是对每一个警察局开始广搜，结果超时，其实可以把所有警察局加入队列，然后进行一次广搜即可。
代码：
#include<stdio.h>
#include<string.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std; #define N 300005
bool u[N]; struct Point{
Point(int cx, int cd){
x=cx;
d=cd;
}
int x, d;
}; vector<Point> v[N];
int num[N]; void add(int x, int y, int i){
Point p(y, i);
v[x].push_back(p);
p.x=x;
v[y].push_back(p);
}
bool vis[N];
int ans[N], ao; queue<Point> q;
void bfs(){
while(q.size()){
Point a = q.front();
q.pop();
for(int i=; i<v[a.x].size(); i++){
int ad=v[a.x][i].x;
Point b(ad, a.d-);
if(b.d>num[b.x]){
num[b.x]=b.d;
if(b.d>) q.push(b);
}
}
}
} void bfs2(int s, int k){
Point p(s, k);
q.push(p);
while(q.size()){
Point a = q.front();
q.pop();
for(int i=; i<v[a.x].size(); i++){
int ad=v[a.x][i].x, bno=v[a.x][i].d;
Point b(ad, a.d-); if(b.d==num[b.x] && u[b.x]==){
u[b.x]=;
vis[bno]=;
q.push(b);
}
else if(vis[bno]==){
vis[bno]=;
ans[ao++]=bno;
}
}
}
} int main(){
int n, m, k, x, y;
while(~scanf("%d%d%d", &n, &m, &k)){
memset(u, , sizeof(u));
memset(num, -, sizeof(num));
for(int i=; i<m; i++){
scanf("%d", &x);
u[x]=;
num[x]=k;
Point tmp(x, k);
q.push(tmp);
}
for(int i=; i<=n; i++) v[i].clear();
for(int i=; i<n; i++){
scanf("%d%d", &x, &y);
add(x, y, i);
} bfs(); memset(vis, , sizeof(vis));
ao=;
for(int i=; i<=n; i++){
if(u[i]==){
bfs2(i, num[i]);
}
} printf("%d\n", ao);
for(int i=; i<ao; i++){
printf("%d", ans[i]);
if(i==ao-) printf("\n");
else printf(" ");
}
}
return ;
}
796D AC代码