国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > Codeforces Round #295 Div1 B(Cubes)

Codeforces Round #295 Div1 B(Cubes)

来源:程序员人生   发布时间:2015-03-30 08:49:45 阅读次数:3188次

Problem

这里写图片描述

Limits

TimeLimit(ms):3000

MemoryLimit(MB):256

M[1,105]

Xi[?109,109]

Yi[0,109]

Look up Original Problem From here

Solution

1个点可取,当且仅当,把它取了以后,上面的点不会失去平衡而掉下来。

开两个优先队列q1,q2q1的顶元素最大,q2的顶元素最小,起初把所有可取的点都放入q1,q2,然后,轮番从q1,q2取点,如果访问过了就取下1个,取出点后,判断这个点是不是可取,如果不可取则取下1个…每次取出的点,判断(Xi?1,Yi?1),(Xi,Yi?1),(Xi+1,Yi?1)这3个点是不是可取,如果可取,则加入q1,q2。这样就能够得到M进制数。

Complexity

TimeComplexity:O(M×log2M)

MemoryComplexity:O(M)

My Code

//Hello. I'm Peter. #include<cstdio> #include<iostream> #include<sstream> #include<cstring> #include<string> #include<cmath> #include<cstdlib> #include<algorithm> #include<functional> #include<cctype> #include<ctime> #include<stack> #include<queue> #include<vector> #include<set> #include<map> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef unsigned int uin; #define peter cout<<"i am peter"<<endl #define input freopen("data.txt","r",stdin) #define randin srand((unsigned int)time(NULL)) #define INT (0x3f3f3f3f)*2 #define LL (0x3f3f3f3f3f3f3f3f)*2 #define gsize(a) (int)a.size() #define len(a) (int)strlen(a) #define slen(s) (int)s.length() #define pb(a) push_back(a) #define clr(a) memset(a,0,sizeof(a)) #define clr_minus1(a) memset(a,⑴,sizeof(a)) #define clr_INT(a) memset(a,INT,sizeof(a)) #define clr_true(a) memset(a,true,sizeof(a)) #define clr_false(a) memset(a,false,sizeof(a)) #define clr_queue(q) while(!q.empty()) q.pop() #define clr_stack(s) while(!s.empty()) s.pop() #define rep(i, a, b) for (int i = a; i < b; i++) #define dep(i, a, b) for (int i = a; i > b; i--) #define repin(i, a, b) for (int i = a; i <= b; i++) #define depin(i, a, b) for (int i = a; i >= b; i--) #define pi 3.1415926535898 #define eps 1e⑼ #define MOD 1000000007 #define MAXN #define N 100100 #define M priority_queue<int>qbig; priority_queue<int, vector<int>, greater<int> >qsmall; int m; bool vis[N]; map<pair<int,int>,int>mapit; struct Point{ int x,y; }poi[N]; int dx[6]={-1,0,1,-1,0,1}; int dy[6]={-1,-1,-1,1,1,1}; const ll mod=1e9 + 9; bool can_move(Point p0){ rep(i,3,6){ Point p1; p1.x=p0.x+dx[i]; p1.y=p0.y+dy[i]; pair<int,int>p=make_pair(p1.x,p1.y); if(mapit.find(p)!=mapit.end()){ int t1=mapit[p]; if(vis[t1]) continue; bool ok=false; rep(j,0,3){ Point p2; p2.x=p1.x+dx[j]; p2.y=p1.y+dy[j]; if(p2.x==p0.x && p2.y==p0.y) continue; pair<int,int>p=make_pair(p2.x,p2.y); if(mapit.find(p)!=mapit.end()){ int t1=mapit[p]; if(vis[t1]) continue; ok=true; break; } } if(!ok) return false; } } return true; } int main(){ scanf("%d",&m); rep(i,0,m){ int x,y; scanf("%d %d",&x,&y); pair<int,int>p=make_pair(x,y); mapit[p]=i; poi[i].x=x,poi[i].y=y; vis[i]=false; } rep(i,0,m){ if(can_move(poi[i])){ qbig.push(i); qsmall.push(i); } } int turn=-1; vector<ll>res; res.clear(); while(1){ int now=0; turn=(turn+1)%2; if(turn==0){//Vasya big while(!qbig.empty()){ now=qbig.top(); if(vis[now]){ qbig.pop(); continue; } else if(!can_move(poi[now])){ qbig.pop(); continue; } else break; } if(qbig.empty()) break; qbig.pop(); vis[now]=true; res.pb(now); pair<int,int>p=make_pair(poi[now].x,poi[now].y); mapit.erase(p); rep(i,0,3){ int x=poi[now].x+dx[i]; int y=poi[now].y+dy[i]; pair<int,int>p=make_pair(x,y); if(mapit.find(p)!=mapit.end()){ int t1=mapit[p]; if(vis[t1]) continue; if(can_move(poi[t1])){ qbig.push(t1); qsmall.push(t1); } } } } else if(turn==1){//.. small while(!qsmall.empty()){ now=qsmall.top(); if(vis[now]){ qsmall.pop(); continue; } else if(!can_move(poi[now])){ qsmall.pop(); continue; } else break; } if(qsmall.empty()) break; qsmall.pop(); vis[now]=true; res.pb(now); pair<int,int>p=make_pair(poi[now].x,poi[now].y); mapit.erase(p); rep(i,0,3){ int x=poi[now].x+dx[i]; int y=poi[now].y+dy[i]; pair<int,int>p=make_pair(x,y); if(mapit.find(p)!=mapit.end()){ int t1=mapit[p]; if(vis[t1]) continue; if(can_move(poi[t1])){ qbig.push(t1); qsmall.push(t1); } } } } } int len=gsize(res); ll m1=1,ans=0; depin(i,len-1,0){ ans=(ans+((res[i]*m1)%mod))%mod; m1=(m1*m)%mod; } printf("%lld ",ans); }
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生