【刷题】洛谷 P3806【模板】点分治1
2024-09-02 22:16:28
题目背景
感谢hzwer的点分治互测。
题目描述
给定一棵有n个点的树
询问树上距离为k的点对是否存在。
输入输出格式
输入格式：
n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径
接下来m行每行询问一个K
输出格式：
对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号)
输入输出样例
输入样例#1：
2 1
1 2 2
2
输出样例#1：
AYE
说明
对于30%的数据n<=100
对于60%的数据n<=1000,m<=50
对于100%的数据n<=10000,m<=100,c<=1000,K<=10000000
题解
还是有点裸的点分治模板题
有趣的一点是：其实calc里跑 \(O(n^2)\) 的暴力记录哪些值可以达到，这可以过（数据水还是复杂度玄学？）
如果一定要理论复杂度正确，那就不 \(n^2\) ，每次遍历每一个询问，两次twopoints求小于等于 \(q[i]\) 的有多少对，小于等于 \(q[i]-1\) 的有多少对，相减就是等于 \(q[i]\) 的对数了
两个程序我都写了， calc里 \(n^2\) 最慢的要200多ms，\(mlogn\)的最慢只要30ms，毕竟复杂度摆在那里
两份代码都贴上来
这是暴力一点的
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=10000+10,MAXK=10000000+10,inf=0x3f3f3f3f;
int ans[MAXK],n,m,e,to[MAXN<<1],nex[MAXN<<1],beg[MAXN],w[MAXN<<1],root,f[MAXN],d[MAXN],deep[MAXN],cnt,size[MAXN],Msonsize[MAXN],finish[MAXN];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y,int z)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
w[e]=z;
}
inline void getroot(int x,int f,int ntotal)
{
Msonsize[x]=0;size[x]=1;
for(register int i=beg[x];i;i=nex[i])
if(to[i]==f||finish[to[i]])continue;
else
{
getroot(to[i],x,ntotal);
size[x]+=size[to[i]];
chkmax(Msonsize[x],size[to[i]]);
}
chkmax(Msonsize[x],ntotal-size[x]);
if(Msonsize[x]<Msonsize[root])root=x;
}
inline void getdeep(int x,int f)
{
deep[++cnt]=d[x];
for(register int i=beg[x];i;i=nex[i])
if(to[i]==f||finish[to[i]])continue;
else d[to[i]]=d[x]+w[i],getdeep(to[i],x);
}
inline void calc(int x,int st,int v)
{
d[x]=st;cnt=0;
getdeep(x,0);
for(register int i=1;i<=cnt;++i)
for(register int j=i+1;j<=cnt;++j)
if(deep[i]+deep[j]<=1e7)ans[deep[i]+deep[j]]+=v;
}
inline void solve(int x)
{
calc(x,0,1);
finish[x]=1;
for(register int i=beg[x];i;i=nex[i])
if(!finish[to[i]])
{
calc(to[i],w[i],-1);
root=0;
getroot(to[i],x,size[to[i]]);
solve(root);
}
}
int main()
{
read(n);read(m);
for(register int i=1;i<n;++i)
{
int u,v,w;
read(u);read(v);read(w);
insert(u,v,w);insert(v,u,w);
}
Msonsize[0]=inf;root=0;
getroot(1,0,n);
solve(root);
for(register int i=1;i<=m;++i)
{
int x;
read(x);
if(ans[x])puts("AYE");
else puts("NAY");
}
return 0;
}
这是优秀的（ShichengXiao OrzOrzOrzOrz）
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=10000+10,MAXM=100+10,MAXK=10000000+10,inf=0x3f3f3f3f;
int n,m,e,to[MAXN<<1],nex[MAXN<<1],beg[MAXN],w[MAXN<<1],root,f[MAXN],d[MAXN],deep[MAXN],cnt,size[MAXN],Msonsize[MAXN],finish[MAXN],q[MAXM],ans[MAXM];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y,int z)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
w[e]=z;
}
inline void getroot(int x,int f,int ntotal)
{
Msonsize[x]=0;size[x]=1;
for(register int i=beg[x];i;i=nex[i])
if(to[i]==f||finish[to[i]])continue;
else
{
getroot(to[i],x,ntotal);
size[x]+=size[to[i]];
chkmax(Msonsize[x],size[to[i]]);
}
chkmax(Msonsize[x],ntotal-size[x]);
if(Msonsize[x]<Msonsize[root])root=x;
}
inline void getdeep(int x,int f)
{
deep[++cnt]=d[x];
for(register int i=beg[x];i;i=nex[i])
if(to[i]==f||finish[to[i]])continue;
else d[to[i]]=d[x]+w[i],getdeep(to[i],x);
}
inline void calc(int x,int st,int v)
{
d[x]=st;cnt=0;
getdeep(x,0);
std::sort(deep+1,deep+cnt+1);
for(register int i=1;i<=m;++i)
{
int res1=0,res2=0,l,r;
l=1,r=cnt;
while(l<r)
{
if(deep[l]+deep[r]<=q[i])res1+=r-l,l++;
else r--;
}
l=1,r=cnt;
while(l<r)
{
if(deep[l]+deep[r]<=q[i]-1)res2+=r-l,l++;
else r--;
}
ans[i]+=(res1-res2)*v;
}
}
inline void solve(int x)
{
calc(x,0,1);
finish[x]=1;
for(register int i=beg[x];i;i=nex[i])
if(!finish[to[i]])
{
calc(to[i],w[i],-1);
root=0;
getroot(to[i],x,size[to[i]]);
solve(root);
}
}
int main()
{
read(n);read(m);
for(register int i=1;i<n;++i)
{
int u,v,w;
read(u);read(v);read(w);
insert(u,v,w);insert(v,u,w);
}
for(register int i=1;i<=m;++i)read(q[i]);
Msonsize[0]=inf;root=0;
getroot(1,0,n);
solve(root);
for(register int i=1;i<=m;++i)
if(ans[i])puts("AYE");
else puts("NAY");
return 0;
}
最新文章
- 代码的坏味道（22）——不完美的库类(Incomplete Library Class)
- hibernate在使用getCurrentSession时提示no session found for current thread
- Python Day10
- jquery 抽奖示例
- springMVC中实现servlet依赖注入
- UE4 VR 模式画面扭曲 解决方法
- JSON 数据使用方法
- ACM: 继续畅通工程-并查集-最小生成树-解题报告
- FCKeditor 2.6.4.1 初始化值不能显示中文问题
- 无插件纯Web HTML5 3D机房 终结篇（新增资产管理、动环监控等内容）
- Linux kernel的 Makefile和Kconfig以及Make menuconfig的关系【转】
- Uva 10003，切木棍
- Eclipse 下如何引用另一个项目的Java文件
- 关于FastDFS Java客户端源码中的一个不太明白的地方
- List<HashMap>和HashMap
- MongoDB笔记（三）启动命令mongod的参数
- java SWT嵌入IE,SafeArray .
- .net的retrofit--WebApiClient库深入篇
- HDU 1166 敌兵布阵(线段树单点更新，板子题)
- docker学习------docker login Harbor失败，需添加http允许权限