首页 > 代码库 > 编程之美初赛第一场--树
编程之美初赛第一场--树
题目2 : 树
- 例子输入
1 3 1 2 2 1 2 3 1 2 1 1 1
- 例子输出
Case 1: 12348
解析：開始没看这道题，以为这道题是什么树或者图的算法，尽管前一段时间写了关于表达式树，红黑树什么的，可是一看那题那么长，还有权重，这难道是什么图搜索还是。。。水货还没练过搜索的题，唉……最后看了看第三题--活动中心，题意挺简单，可是没思路哈，也怪自己平时做的题实在的太少了，扯的长处多，后来剩下了不到半小时的时间去细致的看了下这道题，大致题意思：给出了树的节点个数以及每一个节点的父亲节点，当中定义根节点的深度为1，其它节点的深度依次依据根节点来定义，然后输入了几组操作的命令，事实上就是让你找给定u的全部子节点，并推断他们的深度是否在l和r之间，假设在的话则相应节点的权重+delta，最后依照题目指定的题意输出就好了，题意大致如此，非常明显须要定义权重的数组，节点编号的数组，记录每一个节点父节点的数组。最后慌慌张张写好了，结果时间也过了没办法提交验证自己是不是对，大数据肯定是过不了，唉……居然好多大神那么短的时间内所有做完而且数据全过哈！膜拜大神哈！#include <iostream> #include <stdio.h> #include <memory.h> using std::endl; using std::cin; using std::cout; int main() { int Parent[1001]; int Depth[1001]; int Answer[1001]; int T; cin >> T; int cnt=0; while(T--) { cnt++; //初始化 memset(Parent,0,sizeof(Parent)); memset(Depth,0,sizeof(Depth)); memset(Answer,0,sizeof(Answer)); //初始化根节点编号的深度值 Depth[1]=1; int N; cin >> N; int n; //输入2..N节点的父亲节点的编号 for(int i=2;i<=N;++i) { cin >> n; //存储父亲节点 Parent[i]=n; //更新深度 Depth[i]=Depth[n]+1; } int Q; //输入操作的次数 cin >> Q; int u, l, r, delta; for(int i=0;i<Q;++i) { cin >> u >> l >> r >> delta; for(int j=1;j<=N;++j) { //u的子树包含u节点本身 if(Depth[u]>=l&&Depth[u]<=r) { Answer[u]+=delta; } //假设节点的深度小于或者等于u，则不可能是u(除了u本身外)的子树 if(Depth[j]>Depth[u]) { if(Parent[j]==u) {//u的第一代孩子 if(Depth[j]>=l&&Depth[j]<=r) { Answer[j]+=delta; } }else{ //不是u的直接孩子 int temp=j; while(Depth[temp]!=Depth[u]) { temp=Parent[temp]; } //来推断是否为u的子树节点 if(temp==u&&(Depth[j]>=l&&Depth[j]<=r)) { Answer[j]+=delta; } } } } } //对存储在Answer中的权值进行最后的输出处理 int MOD =1000000007; // 10^9 + 7 int MAGIC= 12347; int Hash =0; for(int i=1;i<=N;++i) { Hash = (Hash * MAGIC + Answer[i]) % MOD; } //输出 cout << "Case " << cnt << ": "; cout << Hash << endl; } return 0; }
描写叙述
有一个N个节点的树，当中点1是根。初始点权值都是0。
一个节点的深度定义为其父节点的深度+1,。特别的，根节点的深度定义为1。
如今须要支持一系列下面操作：给节点u的子树中，深度在l和r之间的节点的权值（这里的深度依旧从整个树的根节点開始计算），都加上一个数delta。
问完毕全部操作后，各节点的权值是多少。
为了降低巨大输出带来的开销，如果完毕全部操作后，各节点的权值是answer[1..N]，请你依照例如以下方式计算出一个Hash值（请选择合适的数据类型，注意避免溢出的情况）。终于仅仅须要输出这个Hash值就可以。
MOD =1000000007; // 10^9 + 7
MAGIC= 12347;
Hash =0;
For i= 1 to N do
Hash = (Hash * MAGIC + answer[i]) mod MOD;
EndFor
输入
第一行一个整数T (1 ≤ T ≤ 5)，表示数据组数。
接下来是T组输入数据，測试数据之间没有空行。
每组数据格式例如以下：
第一行一个整数N (1 ≤ N ≤ 105)，表示树的节点总数。
接下来N - 1行，每行1个数，a (1 ≤ a ≤ N)，依次表示2..N节点的父亲节点的编号。
接下来一个整数Q(1 ≤ Q ≤ 105)，表示操作总数。
接下来Q行，每行4个整数，u, l, r, delta (1 ≤ u ≤ N, 1 ≤ l ≤ r ≤ N, -109 ≤ delta ≤ 109)，代表一次操作。
输出
对每组数据，先输出一行“Case x: ”，x表示是第几组数据，然后接这组数据答案的Hash值。
数据范围
小数据：1 ≤ N, Q ≤ 1000
大数据：1 ≤ N, Q ≤ 105
例子解释
点1的子树中有1,2,3三个节点。当中深度在2-3之间的是点2和点3。
点2的子树中有2,3两个节点。当中没有深度为1的节点。
所以，运行全然部操作之后，仅仅有2,3两点的权值添加了1。即答案是0 1 1。再计算相应的Hash值就可以。
编程之美初赛第一场--树