锐客网

  1. 首页 > it技术 > >

善用stl。。。。。。。。Codeforces|善用stl。。。。。。。。Codeforces Round #316 (Div. 2) D - Tree Requests

http://codeforces.com/contest/570/problem/D
题意：
给一颗树， 每一个节点上有一个字符， 有m次询问，每一个询问：rot,dep。 表示问：在节点rot的所有子树中，（离根节点）深度为dep 的点能不能组成回文的字符串。
一开始年轻的想法：
就是觉得太麻烦了，好难做。
然后看了看别人的算法，觉得自己好菜啊，好菜啊，好菜啊。
：
运用stl 很好解决这个问题：
vecotrans[][] 开一个二维的vector，实际就是三维 =。= ，我们 把dfs序跑出来， 把深度为dep，字符为ch 的节点放进ans[dep][ch-‘a’] ,里面，对于 rot 的子树不就是在 L[rot]…………R[rot]之间么，可得解
【善用stl。。。。。。。。Codeforces|善用stl。。。。。。。。Codeforces Round #316 (Div. 2) D - Tree Requests】哦！！！ 还有一个问题就是： 这道题q神的代码看起来差不多啊，但是只跑了500ms，一定要去学习一波！！！！！
7-18 回顾 ： 只有一串666了

/* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\=/O ____/`---'\____ .'\\||//`. /\\|||:|||//\ /_||||| -:- |||||-\ || \\\-/// || | \_|''\---/''|| \.-\__`-`___/-. / ___`. .'/--.--\`. . __ ."" '<`.___\_<|>_/___.'>'"". | | :`- \`.; `\ _ /`; .`/ - ` : | | \\ `-.\_ __\ /__ _/.-` // ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 佛祖保佑永无BUG */ #include #include #include #include #include #include #include #include #include #include #define mem(a) memset(a,0,sizeof(a)) #define INF 0x7fffffff//INT_MAX #define inf 0x3f3f3f3f// const double PI = acos(-1.0); const double e = exp(1.0); template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template T lcm(T a, T b) { return a / gcd(a, b) * b; } bool cmpbig(int a,int b){return a>b; } bool cmpsmall(int a,int b){return a v[maxn]; vector ans[maxn][26]; int n, m; char s[maxn]; int in[maxn], out[maxn], tot; void dfs(int h, int x){in[x] = ++tot; ans[h][s[x-1]-'a'].push_back(tot); for(int i = 0; i < v[x].size(); i++) dfs(h+1, v[x][i]); out[x] = tot; } int main(){//freopen("in.txt", "r", stdin); int a; scanf("%d%d", &n, &m); for(int i = 2; i <= n; i++){ scanf("%d", &a); v[a].push_back(i); } scanf("%s",s); tot = 0; dfs(1, 1); int v, h; for(int i = 0; i < m; i++){ scanf("%d%d", &v, &h); int p = 0; for(int j = 0; j < 26; j++){ int d = upper_bound(ans[h][j].begin(), ans[h][j].end(), out[v]) - lower_bound(ans[h][j].begin(), ans[h][j].end(), in[v]); if(d&1) p++; if(p > 1) break; } if(p > 1) puts("No"); else puts("Yes"); }return 0; }

    推荐阅读


    上一篇：武汉智能楼宇管理师培训考试、应聘、工作、薪资的介绍

    下一篇：奶奶的手