博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 4358 Boring counting(莫队+DFS序+离散化)
阅读量:5339 次
发布时间:2019-06-15

本文共 3649 字,大约阅读时间需要 12 分钟。

Boring counting

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 98304/98304 K (Java/Others)

Total Submission(s): 2811    Accepted Submission(s): 827

Problem Description
In this problem we consider a rooted tree with N vertices. The vertices are numbered from 1 to N, and vertex 1 represents the root. There are integer weights on each vectice. Your task is to answer a list of queries, for each query, please tell us among all the vertices in the subtree rooted at vertice u, how many different kinds of weights appear exactly K times?
 

 

Input
The first line of the input contains an integer T( T<= 5 ), indicating the number of test cases.
For each test case, the first line contains two integers N and K, as described above. ( 1<= N <= 10
5, 1 <= K <= N )
Then come N integers in the second line, they are the weights of vertice 1 to N. ( 0 <= weight <= 10
9 )
For next N-1 lines, each line contains two vertices u and v, which is connected in the tree.
Next line is a integer Q, representing the number of queries. (1 <= Q <= 10
5)
For next Q lines, each with an integer u, as the root of the subtree described above.
 

 

Output
For each test case, output "Case #X:" first, X is the test number. Then output Q lines, each with a number -- the answer to each query.
Seperate each test case with an empty line.
 

 

Sample Input
1
3 1
1 2 2
1 2
1 3
3
2
1
3
 

 

Sample Output
Case #1:
1
1
1

 

题目链接:

把DFS序和莫队算法结合了起来,前两发杯具PE,如果用过DFS序配合线段树的话就大概能知道怎么做了,对于一颗子树的询问显然DFS序是很适合的,然后这样就得到了每一个点所管理的区间[L,R],那莫队移动的时候怎么判断是否遇到了某一个原树上的节点呢?显然用先序遍历的方式来得到某一个点管理的区间,那么L这个点必定是子树树根的位置,若这个点管理的位置是[L,R]那么实际上这个子树根点的值就是arr[L],不过由于每一个区间都是满点的,就映射成val[timeorder]=arr[u],其中u是某次dfs时的起点。

除此之外还要判断当前减掉的数字是从k减到k-1还是k+1减到k,加上的同理,最后每一个case之间换一行,结尾不换行Orz……另外最近在玩C++11的匿名函数,在sort里随便用下玩

代码:

#include 
#include
using namespace std;#define INF 0x3f3f3f3f#define CLR(arr,val) memset(arr,val,sizeof(arr))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair
pii;typedef long long LL;const double PI=acos(-1.0);const int N=1e5+7;struct edge{ int to; int pre;};struct info{ int l,r; int id,b;};info Q[N];edge E[N];int head[N],tot;int L[N],R[N],order,val[N];int arr[N],cnt[N],ans[N];vector
vec;void init(){ CLR(head,-1); tot=0; CLR(L,0); CLR(R,0); order=0; CLR(val,0); CLR(cnt,0); vec.clear();}inline void add(int s,int t){ E[tot].to=t; E[tot].pre=head[s]; head[s]=tot++;}void dfs(const int &now,const int &pre){ L[now]=++order; val[order]=arr[now]; for (int i=head[now]; ~i; i=E[i].pre) { int v=E[i].to; //if(v!=pre) dfs(v,now); } R[now]=order;}int main(void){ int tcase,n,k,i,a,b,m,rt; scanf("%d",&tcase); for (int q=1; q<=tcase; ++q) { init(); scanf("%d%d",&n,&k); for (i=1; i<=n; ++i) { scanf("%d",&arr[i]); vec.push_back(arr[i]); } sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end()); for (i=1; i<=n; ++i) arr[i]=lower_bound(vec.begin(),vec.end(),arr[i])-vec.begin(); for (i=0; i
Q[i].l) { --l; ++cnt[val[l]]; if(cnt[val[l]]==k) ++temp; else if(cnt[val[l]]==k+1) --temp; } while (r
Q[i].r) { --cnt[val[r]]; if(cnt[val[r]]==k-1) --temp; else if(cnt[val[r]]==k) ++temp; --r; } ans[Q[i].id]=temp; } printf("Case #%d:\n",q); for (i=0; i

转载于:https://www.cnblogs.com/Blackops/p/6040686.html

你可能感兴趣的文章
Linux 的 date 日期的使用
查看>>
PHP zip压缩文件及解压
查看>>
SOAP web service用AFNetWorking实现请求
查看>>
Java变量类型,实例变量 与局部变量 静态变量
查看>>
mysql操作命令梳理(4)-中文乱码问题
查看>>
Python环境搭建(安装、验证与卸载)
查看>>
一个.NET通用JSON解析/构建类的实现(c#)
查看>>
Windows Phone开发(5):室内装修 转:http://blog.csdn.net/tcjiaan/article/details/7269014
查看>>
详谈js面向对象 javascript oop,持续更新
查看>>
关于这次软件以及pda终端的培训
查看>>
jQuery上传插件Uploadify 3.2在.NET下的详细例子
查看>>
如何辨别一个程序员的水平高低?是靠发量吗?
查看>>
新手村之循环!循环!循环!
查看>>
正则表达式的用法
查看>>
线程安全问题
查看>>
SSM集成activiti6.0错误集锦(一)
查看>>
下拉刷新
查看>>
linux的子进程调用exec( )系列函数
查看>>
MSChart的研究
查看>>
C# 索引器
查看>>