ACM-ICPC 2015 Changchun Preliminary Contest_综合

这次比赛的题目偏简单，但是对一些知识点确实是生疏了，平时还需注重复习。

A. Alisha's Party 题库链接

B. Ponds 题库链接

C. Aggregated Counting 题库链接

D. Clock Adjusting 题库链接

E. Travel 题库链接

F. Favorite Donut 题库链接

G. The Water Problem 题库链接

H. Elven Postman 题库链接

I. Food Problem 题库链接

J. Unknown Treasure 题库链接

K. Good Numbers 题库链接

L. Marisa's Cake 题库链接

M. Robot Dog 题库链接

A. Alisha's Party 题库链接
- 通过率: 69.67 %
- 通过人数: 85

B. Ponds 题库链接（拓扑排序+dfs）

通过率: 72.09 %
通过人数: 62
不断去掉度为0或1的水池，算出最终联通块为奇数个水池的价值之和。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxp=1e4+10;
int dgr[maxp]; //每个点的度
int v[maxp]; //每个ponds的价值
int p,m;
ll sum,num;
int vis[maxp];
vector<int> mp[maxp];void init(){memset(dgr,0,sizeof(dgr));memset(vis,0,sizeof(vis));for(int i=0;i<=p;i++)mp[i].clear();scanf("%d%d",&p,&m);for(int i=1;i<=p;i++)scanf("%d",&v[i]);int u,v;for(int i=0;i<m;i++){scanf("%d%d",&u,&v);dgr[u]++;dgr[v]++;mp[u].push_back(v);mp[v].push_back(u);}
}void toposort(){queue<int> q;for(int i=1;i<=p;i++){if(dgr[i]==0) vis[i]=1;if(dgr[i]==1){vis[i]=1;q.push(i);}}int tmp;while(!q.empty()){tmp=q.front();q.pop();int d;for(int i=0;i<mp[tmp].size();i++){d=mp[tmp][i];if(!vis[d]){if(--dgr[d]==1){q.push(d);vis[d]=1;}}}}
}void dfs(int x){num++;sum+=v[x];vis[x]=1;int tmp;for(int i=0;i<mp[x].size();i++){tmp=mp[x][i];if(!vis[tmp]){dfs(tmp);}}
}int main(){int T;scanf("%d",&T);while(T--){init();toposort();ll ans=0;for(int i=1;i<=p;i++){num=0;sum=0;if(!vis[i]){dfs(i);if(num&1){ans+=sum;}}}printf("%lld\n",ans);}return 0;
}

C. Aggregated Counting 题库链接
- 通过率: 14.29 %
- 通过人数: 1
D. Clock Adjusting 题库链接
- 通过率: 0 %
- 通过人数: 0
E. Travel 题库链接
- 通过率: 88.89 %
- 通过人数: 48
F. Favorite Donut 题库链接
- 通过率: 27.27 %
- 通过人数: 3

G. The Water Problem 题库链接（RMQ，简单模拟也可）

通过率: 99.38 %
通过人数: 161

RMQ（区间最值查询），这道题数据量比较小，直接模拟也可。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1e3+10;
int n,q,a[maxn];
int main(){int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&q);int l,r,mx;while(q--){mx=-1;scanf("%d%d",&l,&r);for(int i=l;i<=r;i++)mx=max(mx,a[i]);printf("%d\n",mx);}}return 0;
}

H. Elven Postman 题库链接（二叉搜索树）

通过率: 95.08 %
通过人数: 58
简单题。不讲了，直接上代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;typedef struct BiNode{int data;struct BiNode *lchild,*rchild;
}BiNode,*BiTree;void Insert(BiTree &T,int x){if(T==NULL){T=(BiTree)malloc(sizeof(BiNode));T->data=x;T->lchild=T->rchild=NULL;return ;}if(x<T->data) Insert(T->lchild,x);else Insert(T->rchild,x);
}void query(BiTree T,int x){if(!T) return ;if(T->data==x) return ;if(x<T->data){printf("E");query(T->lchild,x);}else{printf("W");query(T->rchild,x);}
}int main(){int T,n,a;scanf("%d",&T);while(T--){BiTree T=NULL;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a);Insert(T,a);}int q;scanf("%d",&q);while(q--){scanf("%d",&a);query(T,a);printf("\n");}}return 0;
}

I. Food Problem 题库链接
- 通过率: 50 %
- 通过人数: 5
J. Unknown Treasure 题库链接
- 通过率: 73.53 %
- 通过人数: 25
K. Good Numbers 题库链接
- 通过率: 0 %
- 通过人数: 0
L. Marisa's Cake 题库链接
- 通过率: 100 %
- 通过人数: 4
M. Robot Dog 题库链接
- 通过率: 0 %
- 通过人数: 0

ACM-ICPC 2015 Changchun Preliminary Contest