https://codeforces.com/contest/520/problem/D
题目大意
给出 $n$ 个立方体（其实可能叫正方形更好，因为其实只需要考虑 $2$ 维），考虑 $OX$ 是地面，$OY$ 是向上的方向。每个立方体用 $(x, y)$ 表示其位置。定义某个立方体是稳定的当且仅当：
- 立方体在地面上（$x = 0$）
- 其下方有某个稳定的立方体且它们有共用的边或角（$(x - 1, y - 1), (x, y - 1), (x + 1, y)$ 中至少一个位置有立方体且其稳定）。
A 和 B 两个人轮流从中取出某个立方体，使得抽出后图形还是稳定的。将取出的立方体的下标按照取出的顺序排列，A 先取，并且希望这个 $n$ 进制数尽量大。B 希望数尽量小，问最后数字是多少，结果对 $10^9 + 9$ 取模。
$2 \le n \le 10^5$。$-10^9 \le x_i \le 10^9$。$0 \le y \le 10^9$。最初给出的图形是稳定的。
简要题解
容易想到我们可以一直维护当前可以取的集合，每次取完更新这个集合。A 肯定取当前能取最大的，B 反之，因为是个 $n$ 进制数，且最后序列是个排列，因此对于 A 不存在前面取的小，能更好的情况，对 B 同理。
静态的检查一个块是不是能移出也是容易的，因为只需检查它上面三个位置是否有块，如果有其是否有其他支撑块即可。当我们抽出一个块后，那么其下面的有些块可能因为不需要支撑了，也变得可以抽出了。特别的，其上面的某些块，可能因为这个支撑没了使得其他支撑块变得不可选，比较简单的写法就是直接检查两边上下周围的所有可能有影响的块。（我们注意到其实稍微远一点的块其检查的范围内完全没有变化，因此我们并不需要重新检查）。
注意这个检查范围要比抽出的 $(x, y)$ 紧邻的一圈大一些，因为有下面这样的情况。
--
|1 |
-- -- --
|2 | |0 |
-- --
最初 $1$ 或 $2$ 都可以被抽出，但 A 抽走 $2$ 后会使得 $0$ 不能在 $1$ 之前抽出。
Tag 加了 BFS 但其实这不是什么正经的 BFS，只是写法有点像罢了。
注意模数。
复杂度
$T$：$O(n \log n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<long long Mo=998244353> struct ModInt {
static long long MO;
static void setMo(long long mo) { MO = mo; }
long long x;
ModInt(long long x=0) : x(x){ norm(); }
friend istream &operator>>(istream& in, ModInt &B) { in>>B.x; return in; }
friend ostream &operator<<(ostream& out, const ModInt &B) {
out<<B.x; return out; }
// ModInt operator=(int x_) { x=x_; norm(); return *this; }
void norm() { x = (x%MO + MO) % MO; }
long long get() { return x; }
ModInt operator-() const { return ModInt(MO - x); }
ModInt operator+=(const ModInt &B) { x+=B.x; if(x>=MO) x-=MO; return *this; }
ModInt operator-=(const ModInt &B) { x-=B.x; if(x<0) x+=MO; return *this; }
ModInt operator*=(const ModInt &B) { x=x*B.x%MO; return *this; }
ModInt operator+(const ModInt &B) const { ModInt ans=*this; return ans+=B; }
ModInt operator-(const ModInt &B) const { ModInt ans=*this; return ans-=B; }
ModInt operator*(const ModInt &B) const { ModInt ans=*this; return ans*=B; }
ModInt operator^(long long n) const {
ModInt a=*this; ModInt ans(1);
while(n) { if(n&1) ans*=a; a*=a; n>>=1; }
return ans;
}
ModInt inv() const { return (*this)^(MO-2); } // if MO is prime
ModInt operator/=(const ModInt &B) { (*this)*=B.inv(); return *this; }
ModInt operator/(const ModInt &B) const { ModInt ans=*this; return ans/=B; }
bool operator<(const ModInt &B) const { return x<B.x; }
bool operator==(const ModInt &B) const { return x==B.x; }
bool operator!=(const ModInt &B) const { return x!=B.x; }
};
template<long long Mo> long long ModInt<Mo>::MO = Mo;
// typedef ModInt<998244353> Mint;
// typedef ModInt<1'000'000'007> Mint;
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
typedef ModInt<1'000'000'009> Mint;
void solve() {
int n; cin >> n;
map<PII, int> pos2id;
vector<PII> id2pos;
int x, y;
for (int i = 0; i < n; i++) {
cin >> x >> y;
pos2id[{x, y}] = i;
id2pos.push_back({x, y});
}
auto check = [&](int x, int y) -> bool {
for (int i = -1; i <= 1; i++) {
if (!pos2id.count({x + i, y + 1})) continue;
int f = 0;
for (int j = -1; j <= 1; j++) {
if (x + i + j == x) continue;
if (pos2id.count({x + i + j, y})) {
f = 1;
break;
}
}
if (!f) return false;
}
return true;
};
set<int> se;
for (int i = 0; i < n; i++) {
auto [x, y] = id2pos[i];
if (check(x, y)) {
se.insert(i);
}
}
Mint ans = 0;
for (int i = 0; i < n; i++) {
// cerr << "se : ";
// for (int i : se) cerr << i << ' ';
// cerr << endl;
int id;
if (i & 1) {
id = *se.begin();
} else {
id = *se.rbegin();
}
se.erase(id);
auto [x, y] = id2pos[id];
pos2id.erase({x, y});
for (int i = -2; i <= 2; i++) {
for (int j = -1; j <= 1; j++) {
int nx = x + i, ny = y + j;
if (auto it = pos2id.find({nx, ny}); it != pos2id.end()) {
int id2 = it->second;
if (check(nx, ny)) {
se.insert(id2);
} else {
if (auto it2 = se.find(id2); it2 != se.end()) {
se.erase(it2);
}
}
}
}
}
ans *= n;
ans += id;
// cerr << i << ' ' << id << ' ' << ans << endl;
}
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Minimization - Codeforces Round 317 [AimFund Thanks-Round] (Div. 1)