锐客网

  1. 首页 > it技术 > >

其他|Codeforces Round #316 (Div. 2)-D. Tree Requests-DFS+二分+hash

其他二分

dfs求出每个点的深度，并用in、out数组记录该点 管辖的节点范围（in[x]和out[x]之间的数都是x节点所管辖的内容）
从而实现 以深度 为主要因素，以 字母类型为次要因素 把所有节点的内容分类记录在cal[depth][27]数组里 (hash思想)
对于每次查询 ，x,h 先判断 depth[x]是否大于等于h 若大于，则yes
若小于，则 在cal[h]的【1-27】里遍历，寻找是否有 in[x]--out[x]之间的点，有则二分得到个数，判断奇偶，因为要形成回文串，只要奇数个数不超过一就可以了


【其他|Codeforces Round #316 (Div. 2)-D. Tree Requests-DFS+二分+hash】

#include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn = 500005; int tm[maxn]; char vv[maxn]; vector q[maxn]; int depth[maxn]; intin[maxn]; int out[maxn]; int knum=0; vector cal[maxn][27]; int dfs1(int x,int cur) { int i; cal[cur][vv[x]-'a'+1].push_back(++knum); in[x]=knum; for (i=0; i=t2) printf("Yes\n"); else {int line=0,flag=0; for (i=1; i<=26; i++) {int tf1=lower_bound(cal[t2][i].begin(),cal[t2][i].end(),in[t1])- cal[t2][i].begin()+1; int tf2=upper_bound(cal[t2][i].begin(),cal[t2][i].end(),out[t1])- cal[t2][i].begin()+1; if ((tf2-tf1)%2) { if (line==0) {line=1; continue; } if (line==1) {flag=1; break; } }} if (flag==0) printf("Yes\n"); else {printf("No\n"); } } } return 0; }



    推荐阅读


    上一篇：教程|Spring Boot 集成 AmazonS3 存储服务教程

    下一篇：eventbus|eventbus 配置