POJ - 2528 Mayor's posters(dfs+分治)

POJ - 2528 Mayor's posters

思路:分治思想。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
const int INF=0x3f3f3f3f;
const int N=1e4+;
int st[N],ed[N];
bool vis[N]={false};
int ans;
void dfs(int l,int r,int x)
{
if(x==)return ;
if(l<=ed[x]&&r>=st[x])
{
if(!vis[x])
{
ans++;
vis[x]=true;
}
if(l<st[x])dfs(l,st[x]-,x-);
if(r>ed[x])dfs(ed[x]+,r,x-);
}
else dfs(l,r,x-);
}
int main()
{
int c,n;
scanf("%d",&c);
while(c--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&st[i],&ed[i]);
}
ans=;
memset(vis,false,sizeof(vis));
dfs(,,n);
printf("%d\n",ans);
}
return ;
}
上一篇:Linux主机上实现树莓派的交叉编译及文件传输,远程登陆


下一篇:056——VUE中vue-router之路由参数的验证处理保存路由安全