HDU - 5156 Harry and Christmas tree

题目链接 : http://acm.hdu.edu.cn/showproblem.php?pid=5156

题意 :

给一颗编号为1-n的以1为根的树, 已知有m个颜色的礼物分布在某些节点上(同一节点可以有多个),

问 : 对于编号从1-n的节点, 每一个节点对应子树上有多少颜色不同的礼物.

思路 :

一开始的想法是DFS记录节点序列, 再开vector记录每个节点上挂的礼物(同一节点上对颜色去重), 用树状数组统计一个区间内不同颜色的种类

但是由于记录位置的数组同样要开到二维, 超过了限制, 于是也开成vector, 果断超时

后来还是看discuss里边sxbk同学的代码才知道更好的解法

DFS记录序列不是节点序列, 而是将所有节点的全部颜色(已去重)都记录在序列内, 这样位置记录的数组可以只用一维

这道题收获挺大的, 对DFS序的思想理解深入了, 同时学习了统计一个区间内有多少不同的数这个问题的解法

题目代码 :

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int MAXN = 5e4+;

 const int MAXM = 5e5+;

 vector<int> edge[MAXN];

 vector<int> gift[MAXN];

 int seq[*MAXM];

 int st[MAXN];

 int ed[MAXN];

 int s[*MAXM];

 int mp[*MAXM];

 int ans[MAXN];

 int pos[MAXN];

 int cnt, n, m;

 void Dfs(int u, int fa)

 {

     st[u] = cnt + ;

     int num = gift[u].size();

     for(int i = ; i < num; i++) {

         seq[++cnt] = gift[u][i];

     }

     int len = edge[u].size();

     for(int i = ; i < len; i++) {

         int v = edge[u][i];

         if(v != fa) Dfs(v, u);

     }

     ed[u] = cnt;

 }

 int Lowbit(int x)

 {

     return x & (-x);

 }

 void Add(int x, int val)

 {

     for(int i = x; i <= cnt; i += Lowbit(i)) {

         s[i] += val;

     }

 }

 int Sum(int x)

 {

     int res = ;

     for(int i = x; i > ; i -= Lowbit(i)) {

         res += s[i];

     }

     return res;

 }

 bool cmp(int a, int b)

 {

     return ed[a] < ed[b];

 }

 void Init()

 {

     for(int i = ; i <= n; i++) {

         edge[i].clear();

         gift[i].clear();

     }

     for(int i = ; i <= n; i++) {

         pos[i] = i;

     }

     memset(s, , sizeof(s));

     memset(mp, , sizeof(mp));

 }

 int main()

 {

     int u, v;

     while(scanf("%d %d", &n, &m) != EOF) {

         Init();

         for(int i = ; i < n-; i++) {

             scanf("%d %d", &u, &v);

             edge[u].push_back(v);

             edge[v].push_back(u);

         }

         while(m--) {

             scanf("%d %d", &u, &v);

             if(find(gift[u].begin(), gift[u].end(), v) == gift[u].end()) {

                 gift[u].push_back(v);

             }

         }

         cnt = ;

         Dfs(, -);

         sort(pos+, pos++n, cmp);

         for(int i = ; i <= cnt; i++) {

             if(mp[seq[i]] == ) {

                 Add(i, );

                 mp[seq[i]] = i; //如果是第一次出现, mp[seq[i]]记录为当前位置

             }

         }

         int right = ;

         for(int i = ; i <= n; i++) {

             int now = pos[i];

             while(right <= ed[now]) {

                 if(mp[seq[right]] != right) { //如果不是第一次出现

                     Add(mp[seq[right]], -);  //减去前一次出现的

                     Add(right, );

                     mp[seq[right]] = right;   //重新定义这个数最近一次出现位置

                 }

                 right++;

             }

             ans[now] = Sum(ed[now]) - Sum(st[now] - );

         }

         printf("%d", ans[]);

         for(int i = ; i <= n; i++) {

             printf(" %d", ans[i]);

         }

         printf("\n");

     }

     return ;

 }

另外第一次学习到统计一个区间内有多少不同的数这个问题的解法

基本思路是树状数组, 但是有重复的数, 要保证在一个区间内只更新过一次

所做的处理是用先遍历记录数字的数组a, 用数-位置数组 mp[a[i]] 来记录每个数第一次出现的位置并该点更新

这个操作对应的代码

 for(int i = ; i <= n; i++) {

     if(mp[a[i]] == ) { //如果是第一次出现, 记录第一次出现位置并更新

         Add(i, );

         mp[a[i]] = i;

     }

 }

记录左右查询, 每个查询按区间右端点R[i]从小到大排序

设一个扫描线k, 它的目的保证R[i]之前所有不同的点只更新过一次, 并且是在离R[i]最近的那个点更新

如此便可以写出这样一段代码

 for(int i = ; i <= query_num; i++) {

     while(k <= R[i]) {

         if(mp[a[i]] != k) {     //如果不是最新次出现

             Add(mp[a[k]], -);  //将上一次出现的更新-1

             Add(k, );　　       //将这个位置新出现的更新1

             mp[a[k]] = k;       //更新这个数最近一次的位置

         }

         k++;

     }

     ans[i] = Sum(ed[i]) - Sum(st[i] - );

 }

恩, 就是这样...

巴特西

HDU - 5156 Harry and Christmas tree

最新文章

热门文章