Codeforces Round #135 (Div. 2)题解
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
A:k-String
水题一枚，判断每个字母的数量是否为K的倍数
B：Special Offer! Super Price 999 Bourles!
找到一个区间内，9的个数最多而且数字越大越好。
感觉就是细节处理题，从高位一位一位往低位判断
#include<cstdio>#include<cstring>#include<iostream>#include<vector>#define N 200005#define pb(a) push_back(a)#define mp(a,b) make_pair(a,b)using namespace std;vector<pair<int,int> >edge[N];int f[N],g[N];void dfs1(int u,int pre){ f[u]=0; for(int i=0;i<edge[u].size();i++){ int v=edge[u][i].first,w=edge[u][i].second; if(v==pre) continue; dfs1(v,u); f[u]+=f[v]+w; }}void dfs2(int u,int pre){ for(int i=0;i<edge[u].size();i++){ int v=edge[u][i].first,w=edge[u][i].second; if(v==pre) continue; g[v]=g[u]-w+(1-w); dfs2(v,u); }}int main(){ int n,u,v; while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n;i++) edge[i].clear(); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); edge[u].pb(mp(v,0)); edge[v].pb(mp(u,1)); } dfs1(1,0); g[1]=f[1]; dfs2(1,0); int ans=n; for(int i=1;i<=n;i++) if(g[i]<ans) ans=g[i]; printf("%d\n",ans); for(int i=1;i<=n;i++) if(g[i]==ans) printf("%d ",i); puts(""); } return 0;}经典的线段树题目，同POJ hotel。
详见http://blog.csdn.net/acm_cxlove/article/details/7916299