Codeforces Contest 521 B Cubes —— 贪心，模拟

本文主要是介绍Codeforces Contest 521 B Cubes —— 贪心，模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

在二维平面上有n个格子，如果一个格子的y>0，那么(x,y-1),(x-1,y-1),(x+1,y-1)中必定有一个位置有格子，每个格子有一个编号。现在有两个人分别将格子取下来，放到n进制数中之前的格子的后方，第一个人想要将最终这个数的值最大，第二个人想要这个值最小，问你在不违反前提的情况下他们轮流取格子，最终这个n进制数转换为10进制的值是多少

题解：

它可能是凭麻烦程度到2400的。。
用set存可能可行的id，在使用的时候需要判断是否可行，
可能可行就意味着这个格子上面三位无格子或者有其它格子支撑着它。注意判不行之后就要把它删掉，否则会t
有两种方法可以做：map或者数组。
用map.count的话其实和数组时间复杂度差不多
map的话直接记录位置，数组的话像下面这样记录它旁边6个位置的id即可

情况太麻烦了，自己意会一下。

map：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+9;
const int N=1e5+5;
#define pa pair<int,int>
map<pa,int>mp;
int near[N][6];
struct node
{int x,y;ll id;bool operator< (const node& a)const{return id<a.id;}
}a[N];
ll p[N];
int vis[N];
set<int>s;
int judge(int id)
{if(near[id][1])if(!near[near[id][1]][5]&&!near[near[id][1]][3])return 0;if(near[id][0])if(!near[near[id][0]][4]&&!near[near[id][0]][3])return 0;if(near[id][2])if(!near[near[id][2]][4]&&!near[near[id][2]][5])return 0;return 1;
}
void add(int id)
{if(!id||vis[id])return ;if(near[id][1]&&!vis[near[id][1]]){if(near[near[id][1]][3]&&!vis[near[near[id][1]][3]]);else if(near[near[id][1]][5]&&!vis[near[near[id][1]][5]]);elsereturn ;}if(near[id][0]&&!vis[near[id][0]]){if(near[near[id][0]][4]&&!vis[near[near[id][0]][4]]);else if(near[near[id][0]][3]&&!vis[near[near[id][0]][3]]);elsereturn ;}if(near[id][2]&&!vis[near[id][2]]){if(near[near[id][2]][4]&&!vis[near[near[id][2]][4]]);else if(near[near[id][2]][5]&&!vis[near[near[id][2]][5]]);elsereturn ;}s.insert(id);
}
int check(int id)
{if(near[id][1]&&!vis[near[id][1]]){if(!near[near[id][1]][3]&&!near[near[id][1]][5])return 0;if(!near[near[id][1]][5])if(vis[near[near[id][1]][3]])return 0;if(!near[near[id][1]][3])if(vis[near[near[id][1]][5]])return 0;if(near[near[id][1]][3]&&vis[near[near[id][1]][3]]&&near[near[id][1]][5]&&vis[near[near[id][1]][5]])return 0;}if(near[id][0]&&!vis[near[id][0]]){if(!near[near[id][0]][4]&&!near[near[id][0]][3])return 0;if(!near[near[id][0]][4])if(vis[near[near[id][0]][3]])return 0;if(!near[near[id][0]][3])if(vis[near[near[id][0]][4]])return 0;if(near[near[id][0]][3]&&vis[near[near[id][0]][3]]&&near[near[id][0]][4]&&vis[near[near[id][0]][4]])return 0;}if(near[id][2]&&!vis[near[id][2]]){if(!near[near[id][2]][4]&&!near[near[id][2]][5])return 0;if(!near[near[id][2]][4])if(vis[near[near[id][2]][5]])return 0;if(!near[near[id][2]][5])if(vis[near[near[id][2]][4]])return 0;if(near[near[id][2]][5]&&vis[near[near[id][2]][5]]&&near[near[id][2]][4]&&vis[near[near[id][2]][4]])return 0;}return 1;
}
int main()
{ll n;scanf("%lld",&n);ll ret=1;p[0]=1;for(int i=1;i<=n;i++){ret=ret*n%mod,p[i]=ret;scanf("%d%d",&a[i].x,&a[i].y);a[i].id=i;mp[{a[i].x,a[i].y}]=i;}for(int i=1;i<=n;i++){near[i][0]=mp[{a[i].x-1,a[i].y+1}];near[i][1]=mp[{a[i].x,a[i].y+1}];near[i][2]=mp[{a[i].x+1,a[i].y+1}];near[i][3]=mp[{a[i].x-1,a[i].y-1}];near[i][4]=mp[{a[i].x,a[i].y-1}];near[i][5]=mp[{a[i].x+1,a[i].y-1}];}for(int i=1;i<=n;i++)if(judge(i))s.insert(i);int f=0,r=n-1;set<int>::iterator it;ll ans=0;while(!s.empty()){if(!f){it=s.end();it--;while(!check(*it))s.erase(it--);int pos=*it;//cout<<*it<<endl;ans=(ans+(a[pos].id-1ll)*p[r])%mod;vis[a[pos].id]=1;add(near[pos][4]),add(near[pos][3]),add(near[pos][5]);s.erase(it);}else{it=s.begin();while(!check(*it))s.erase(it++);int pos=*it;//cout<<*it<<endl;ans=(ans+(a[pos].id-1ll)*p[r])%mod;vis[a[pos].id]=1;add(near[pos][4]),add(near[pos][3]),add(near[pos][5]);s.erase(it);}r--,f^=1;}printf("%lld\n",ans);return 0;
}

数组：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+9;
const int N=1e5+5;
#define pa pair<int,int>
map<pa,int>mp;
int near[N][6];
struct node
{int x,y;ll id;
}a[N];
ll p[N];
int vis[N];
set<int>s;
int judge(int id)
{if(near[id][1])if(!near[near[id][1]][5]&&!near[near[id][1]][3])return 0;if(near[id][0])if(!near[near[id][0]][4]&&!near[near[id][0]][3])return 0;if(near[id][2])if(!near[near[id][2]][4]&&!near[near[id][2]][5])return 0;return 1;
}
void add(int id)
{if(!id||vis[id])return ;if(near[id][1]&&!vis[near[id][1]]){if(near[near[id][1]][3]&&!vis[near[near[id][1]][3]]);else if(near[near[id][1]][5]&&!vis[near[near[id][1]][5]]);elsereturn ;}if(near[id][0]&&!vis[near[id][0]]){if(near[near[id][0]][4]&&!vis[near[near[id][0]][4]]);else if(near[near[id][0]][3]&&!vis[near[near[id][0]][3]]);elsereturn ;}if(near[id][2]&&!vis[near[id][2]]){if(near[near[id][2]][4]&&!vis[near[near[id][2]][4]]);else if(near[near[id][2]][5]&&!vis[near[near[id][2]][5]]);elsereturn ;}s.insert(id);
}
int check(int id)
{if(near[id][1]&&!vis[near[id][1]]){if(!near[near[id][1]][3]&&!near[near[id][1]][5])return 0;if(!near[near[id][1]][5])if(vis[near[near[id][1]][3]])return 0;if(!near[near[id][1]][3])if(vis[near[near[id][1]][5]])return 0;if(near[near[id][1]][3]&&vis[near[near[id][1]][3]]&&near[near[id][1]][5]&&vis[near[near[id][1]][5]])return 0;}if(near[id][0]&&!vis[near[id][0]]){if(!near[near[id][0]][4]&&!near[near[id][0]][3])return 0;if(!near[near[id][0]][4])if(vis[near[near[id][0]][3]])return 0;if(!near[near[id][0]][3])if(vis[near[near[id][0]][4]])return 0;if(near[near[id][0]][3]&&vis[near[near[id][0]][3]]&&near[near[id][0]][4]&&vis[near[near[id][0]][4]])return 0;}if(near[id][2]&&!vis[near[id][2]]){if(!near[near[id][2]][4]&&!near[near[id][2]][5])return 0;if(!near[near[id][2]][4])if(vis[near[near[id][2]][5]])return 0;if(!near[near[id][2]][5])if(vis[near[near[id][2]][4]])return 0;if(near[near[id][2]][5]&&vis[near[near[id][2]][5]]&&near[near[id][2]][4]&&vis[near[near[id][2]][4]])return 0;}return 1;
}
int main()
{ll n;scanf("%lld",&n);ll ret=1;p[0]=1;for(int i=1;i<=n;i++){ret=ret*n%mod,p[i]=ret;scanf("%d%d",&a[i].x,&a[i].y);a[i].id=i;mp[{a[i].x,a[i].y}]=i;}for(int i=1;i<=n;i++){near[i][0]=mp[{a[i].x-1,a[i].y+1}];near[i][1]=mp[{a[i].x,a[i].y+1}];near[i][2]=mp[{a[i].x+1,a[i].y+1}];near[i][3]=mp[{a[i].x-1,a[i].y-1}];near[i][4]=mp[{a[i].x,a[i].y-1}];near[i][5]=mp[{a[i].x+1,a[i].y-1}];}for(int i=1;i<=n;i++)if(judge(i))s.insert(i);int f=0,r=n-1;set<int>::iterator it;ll ans=0;while(!s.empty()){if(!f){it=s.end();it--;while(!check(*it))s.erase(it--);int pos=*it;ans=(ans+(a[pos].id-1ll)*p[r])%mod;vis[a[pos].id]=1;add(near[pos][4]),add(near[pos][3]),add(near[pos][5]);s.erase(it);}else{it=s.begin();while(!check(*it))s.erase(it++);int pos=*it;ans=(ans+(a[pos].id-1ll)*p[r])%mod;vis[a[pos].id]=1;add(near[pos][4]);add(near[pos][3]);add(near[pos][5]);s.erase(it);}r--,f^=1;}printf("%lld\n",ans);return 0;
}

这篇关于Codeforces Contest 521 B Cubes —— 贪心，模拟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---