最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • Codeforces Round #295 Div1 B(Cubes)

    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);
    }
    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » Codeforces Round #295 Div1 B(Cubes)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级