比赛链接：http://codeforces.com/contest/902
比赛时间：12/19
rating：1500->1478
A. Visiting a Friend
【题意】有n个起点和终点已知的传送带，Pig可以从起点移动到传送带上任意一点，已知Pig和他朋友的位置，问pig能否去看望他的朋友。【题解】遍历每个[左端点,右端点-1]，访问过的标记一下，再for(pig->朋友位置)一遍，如果全部访问过则为yes，否则为no。
【代码】
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int vis[105]={0}; int n,m; scanf("%d%d",&n,&m); while(n--) { int s,e; scanf("%d%d",&s,&e); for(int i=s+1;i<=e;i++) vis[i-1]=1; } for(int i=0;i<=m-1;i++) if(!vis[i]) { cout<<"NO"<<endl; return 0; } cout<<"YES"<<endl; return 0; }
B. Coloring a Tree
【题意】给定一颗二叉树，求将所有节点染成指定颜色需要的操作次数，每次操作是将该节点的所有子树染色。
【题解】从根节点搜到底，只要当前颜色与父节点颜色不同，则ans++。
【代码】
#include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<algorithm> #include<vector> #include<queue> using namespace std; vector<int>e[10005]; int cr[10005],ans; void dfs(int u,int co) { for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(cr[v]!=co) { ans++; } dfs(v,cr[v]); } } int main() { int n,fa; scanf("%d",&n); for(int i=2;i<=n;i++) { scanf("%d",&fa); e[fa].push_back(i); } for(int i=1;i<=n;i++) { scanf("%d",&cr[i]); } ans=1; dfs(1,cr[1]); printf("%d\n",ans); }
