本文主要是介绍@UPC 5725 @中石油 5725 @NOI考前欢乐赛 : 小奇画画(BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
5725: 小奇画画
时间限制: 1 Sec 内存限制: 128 MB
提交: 387 解决: 65
[提交] [状态] [讨论版] [命题人:admin]
题目描述
红莲清泪两行欲吐半点却无
如初是你杳然若绯雾还在水榭畔画楼处
是谁衣白衫如初谁红裳如故
——《忆红莲》
小奇想画几朵红莲，可惜它刚开始学画画，只能从画圆开始。小奇画了n个圆，它们的圆心都在x轴上，且两两不相交（可以相切）。现在小奇想知道，它画的圆把画纸分割成了多少块？（假设画纸无限大）
输入
第一行包括1个整数n。
接下来n行，每行两个整数x，r，表示小奇画了圆心在（x，0），半径为r的一个圆。
输出
输出一个整数表示答案。
样例输入
4 7 5 -9 11 11 9 0 20
样例输出
6
提示
对于 100%数据，1<=n<=300000,-10^9<=x<=10^9,1<=r<=10^9。
[题意]
求圆把纸分成的个数, 注意 不会相交, 所以只有 相邻 内含 外切, 内切 的几种形式.
[思路]
n 个圆 一定 会 切割 成 n+1 个面.
然后我们 考虑 一个大圆 内 由 几个小圆 相切 然后 把大圆 分成两个部分, 这样 对答案 贡献 +1
我们把 大圆 做 一个节点, 内部的小圆 作为他的子节点, 建这样一棵树,
然后bfs 扫描 每个节点, 若 当前节点 的 直径 = 子节点所有直径之和, 则 ans +1
先建树,在bfs
另外一种思路, 就是贪心+暴力, 但是应该需要 记录前缀, 不然会被 hack 掉
[代码]
#include <bits/stdc++.h>
#include <stdlib.h>
#include <utility>
#define findx(x,b,n) lower_bound(b+1,b+1+n,x)-b
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
#define SHUT ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r#pragma comment(linker, "/STACK:1024000000,1024000000") // 扩栈
//next_permutation(a+1,a+x) 全排列
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())using namespace std;typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;const double PI=acos(-1.0);
const int INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e6+5;
const int MOD=1e9+7;
const int mod=1e9+7;
int dir[5][2]={0,1,0,-1,1,0,-1,0};inline void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){ x=1; y=0; d=a; }else{ ex_gcd(b,a%b,d,y,x); y-=x*(a/b);};}
inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll ans=exgcd(b,a%b,x,y);ll temp=x;x=y;y=temp-a/b*y;return ans;}
inline ll lcm(ll a,ll b){ return b/gcd(a,b)*a;}
inline ll qpow(ll x,ll n){ll res=1;for(;n;n>>=1){if(n&1)res=(res*x)%MOD;x=(x*x)%MOD;}return res;}
inline ll inv_exgcd(ll a,ll n){ll d,x,y;ex_gcd(a,n,d,x,y);return d==1?(x+n)%n:-1;}
inline ll inv1(ll b){return b==1?1:(MOD-MOD/b)*inv1(MOD%b)%MOD;}
inline ll inv2(ll b){return qpow(b,MOD-2);}/*********************************head************************/struct node{int v,next;
}edge[maxn];int cot;
int head[maxn];struct Node{int fi,se;
}V[maxn];ll ans;
int t,top;
int q[maxn];int cmp(Node a, Node b){if( a.fi == b.fi)return a.se >b.se;return a.fi < b.fi;
}
void init()
{cot = 0;memset(head,-1,sizeof(head));
}
void add(int u,int v)
{edge[++cot].v = v;edge[cot].next = head[u];head[u] = cot;
}void build_tree()
{int now = V[t].fi;while(top&&V[q[top]].se <= now) top--;if( V[t].fi == now){// cout<<" add: "<<q[top]<<" -> "<<t<<endl;add(q[top],t);q[++top] = t++;}
}
void bfs()
{queue<int>Q;Q.push(0);while(!Q.empty()){int u = Q.front();// cout<<"Debug u : "<<u<<endl;Q.pop();ll sum = 0;for(int i = head[u]; i!=-1; i = edge[i].next){int v = edge[i].v;sum += (V[v].se - V[v].fi);Q.push(v);}if( sum == (V[u].se -V[u].fi) )ans++;// if node father [L,R] = sum of son [Li,Ri]}
}
int main()
{int n;init();scanf("%d",&n);rep(i,1,n+1){int l,r;scanf("%d %d",&l,&r);V[i].fi = l-r,V[i].se = l+r;}sort(V+1,V+n+1,cmp);ans = n+1;t = 1;while( t<=n )build_tree();// cout<<"Debug : " <<endl;bfs();printf("%d\n",ans);return 0;
}
这篇关于@UPC 5725 @中石油 5725 @NOI考前欢乐赛 : 小奇画画(BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
