Codeforces 520D. Cubes 贪心模拟
来源：程序员人生 发布时间：2015-04-11 09:25:06 阅读次数：3732次
每步都取当前稳定的格子里面数字最大或最小的数.
用1个set保护当前可取的格子 *begin 最大 *(--end) 最小
每删除1个格子都要对这个格子周围的6个格子进行稳定性检查
1个格子上面的3个格子肯定了这个格子的稳定性
/* ***********************************************
Author :CKboss
Created Time :2015Äê03ÔÂ03ÈÕ ÐÇÆÚ¶þ 23ʱ46·Ö15Ãë
File Name :D.cpp
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long int LL;
const LL mod = 1e9+9;
const int maxn=100100;
struct BOX
{
int x,y,id;
}box[maxn];
typedef pair<int,int> pII;
int n;
map<pII,int> mPI;
set<pII> Pt;
set<int> St;
bool isST(int id)
{
int x=box[id].x;
int y=box[id].y;
pII tp;
/// check (x⑴,y+1)
tp = make_pair(x⑴,y+1);
if(Pt.count(tp)==1)
{
if(Pt.count( make_pair(x⑵,y) )
|| Pt.count( make_pair(x⑴,y) ))
;
else return false;
}
/// check (x,y+1)
tp = make_pair(x,y+1);
if(Pt.count(tp)==1)
{
if(Pt.count( make_pair(x⑴,y) )
|| Pt.count( make_pair(x+1,y) ))
;
else return false;
}
/// check (x+1,y+1)
tp = make_pair(x+1,y+1);
if(Pt.count(tp)==1)
{
if(Pt.count( make_pair(x+1,y) )
|| Pt.count( make_pair(x+2,y) ))
;
else return false;
}
return true;
}
void checkST(int id)
{
if(isST(id))
{
St.insert(id);
}
else
{
if(St.count(id)) St.erase(id);
}
}
void checkround(int id)
{
int x=box[id].x;
int y=box[id].y;
checkST(id);
for(int i=⑴;i<=1;i++) /// dx
{
for(int j=⑴;j<=1;j+=2) /// dy
{
int nx=x+i,ny=y+j;
pII tp = make_pair(nx,ny);
if(Pt.count(tp)==1)
{
int dd=mPI[tp];
checkST(dd);
}
}
}
}
void Remove(int id)
{
int x=box[id].x;
int y=box[id].y;
/// erase
Pt.erase(make_pair(x,y));
St.erase(id);
/// check other stable box
for(int i=⑴;i<=1;i++) // dx
{
for(int j=⑴;j<=1;j+=2) // dy
{
int nx=x+i,ny=y+j;
pII tp = make_pair(nx,ny);
if(Pt.count(tp)==1)
{
int ID=mPI[tp];
checkround(ID);
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
box[i]=(BOX){x,y,i};
mPI[make_pair(x,y)]=i;
Pt.insert(make_pair(x,y));
}
/// check stable disassemble box
int mxid=0,miid=0;
for(int i=0;i<n;i++)
{
if(isST(i))
{
St.insert(i);
mxid=max(mxid,i);
miid=min(miid,i);
}
}
vector<int> vi;
for(int loop=0;loop<n;loop++)
{
if(loop%2==0) //find max
{
vi.push_back(mxid);
Remove(mxid);
}
else // find min
{
vi.push_back(miid);
Remove(miid);
}
if(loop==n⑴) continue;
miid=*St.begin();
mxid=*(--St.end());
}
LL ans=0,base=1;
for(int sz=vi.size(),i=sz⑴;i>=0;i--)
{
ans=(ans+base*vi[i]%mod)%mod;
base=(base*n)%mod;
}
cout<<ans%mod<<endl;
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
