BZOJ4651兼UOJ#220 【NOI2016】网格

Posted by EtaoinWu on 周四 04 五月 2017

... 代码码了 7k+,250+ sloc。。。 前后重构 2 次才卡常卡过 ... 这题特判多

显然 ans<=2

特判

  • n * m - c <= 1, ans=-1
  • n * m - c == 2, 考虑这两个点的连通性
  • min(n,m)==1, 直接把区间拿出来 , 把前缀后缀的连续死节点搞死 , 中间如果还剩任意 then 0 else 1

其他平凡情况

只要判出 ans=0 or ans=1 就好了 。 蛐蛐跳蚤打字太难打 , 下文称为死节点和活节点 。

  1. 考虑 n*m 很小
  2. 建图 ,dfs 一遍 , 不联通 then 0
  3. 建图 , 把活着的节点跑个 tarjan, 有割点 then 1, 此时方案是任意割点
  4. else 2
  5. 考虑 n*m 很大

  6. 思路 : 只考虑被搞死的点周边的点

  7. 考虑八联通相邻节点 , 这些点如果不联通 then 0( 对应于上文第一条
  8. 对于每个联通块 ( 指的是选出这些点之后 , 其他点都活着 , 却被无视 、 删除了 , 剩下的相连节点形成了各个联通块 ) 跑个 tarjan, 发现会被卡 。 如图 , 活表示活节点 , 死表示死节点 , 联 & 蛤表示与死节点相连的活节点 :
 活活活活活活活活 
 活联联联活活活活 
 活联死联活活活活 
 活联联蛤联联活活 
 活活活联死联活活 
 活活活联联联活活 
 活活活活活活活活 
  • “ 蛤 ” 这个地方形成了假的割点 。
  • 怎么处理 ?
  • 答 : 把与 “ 联 ” 节点相邻的节点也扔进来 。 记作 “ 连 ”。
  • 那么这张图变成了 :
 连连连连连活活活 
 连联联联连活活活 
 连联死联连连连活 
 连联联蛤联联连活 
 连连连联死联连活 
 活活连联联联连活 
 活活连连连连连活 
( 瞎眼 ...
  • 跑个 tarjan, 判断 “ 联 ” 节点里面有没有割点即可 。 这样蛤节点就不是割点了 。

注意 , 本题在判断什么节点是联节点的时候不能使用 map、unordered_map。。。 都会 t

使用 vector+lower_bound 可过

我的 UOJ 提交记录

#pragma GCC optimize(3)
#include "bits/stdc++.h"
using namespace std;
#ifdef __attribute__
#define fast __attribute__((optimize("O3"), target("no-ieee-fp,arch=amdfam10")))
#define inline fast inline
#else
#define fast
#define inline inline
#endif
#define USE_FREAD_IO
#ifdef USE_FREAD_IO
#define BUF_SIZE 5000010
char buf[BUF_SIZE];
int cur = BUF_SIZE;
FILE *in = stdin;
inline char gnc()
{
    if (cur == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); cur = 0; }
    return buf[cur++];
}
#else
#define gnc getchar
#endif
template<typename T>
inline void gi(T &dx)
{
    dx = 0;
    int yc = gnc();
    //bool nega = false;
    while (yc < '0' || yc > '9') { /*nega = (yc == '-' ? true : nega);*/ yc = gnc(); }
    while (yc >= '0' && yc <= '9') { dx = (T)(dx * 10 + yc - '0'); yc = gnc(); }
    //if (nega) { dx = -dx; }
}
inline void gc(char &x)
{
    do x = gnc(); while (!isgraph(x));
}
#if __cplusplus >= 201103l || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103l)
template<typename T, typename ...Args> inline void gi(T &a, Args &...args)
{ gi(a); gi(args...); }
#else
template<typename t1, typename t2> inline void gi(t1 &a, t2 &b) { gi(a); gi(b); }
template<typename t1, typename t2, typename t3> inline void gi(t1 &a, t2 &b, t3 &c) { gi(a); gi(b); gi(c); }
template<typename t1, typename t2, typename t3, typename t4> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d) { gi(a); gi(b); gi(c); gi(d); }
template<typename t1, typename t2, typename t3, typename t4, typename t5> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d, t5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); }
#endif

typedef long long ll;
const int maxn = 6666666;
ll n, m, c;
int T;
struct flea
{
    int x, y;
    flea() : x(0), y(0) {}
    flea(int x, int y) : x(x), y(y) {}
    flea &operator+=(const flea &a)
    {
        x += a.x; y += a.y;
        return *this;
    }
    flea &operator-=(const flea &a)
    {
        x -= a.x; y -= a.y;
        return *this;
    }
    bool operator<(const flea &a) const
    {
        return x < a.x || (x == a.x && y < a.y);
    }
    bool operator==(const flea &a) const
    {
        return x == a.x && y == a.y;
    }
    bool operator!=(const flea &a) const
    {
        return x != a.x || y != a.y;
    }
} fs[maxn];
int gw[maxn];
bool ok(const flea &a)
{
    return a.x >= 1 && a.x <= n && a.y >= 1 && a.y <= m;
}
flea delta1[] = { //  长度为 1 四联通 
    flea(+0,+1), flea(+1,+0), flea(+0,-1), flea(-1,+0)
};
flea delta2[] = { //  长度为 1 八联通 
    flea(+0,+1), flea(+1,+1), flea(+1,+0), flea(+1,-1), flea(+0,-1), flea(-1,-1), flea(-1,+0), flea(-1,+1)
};
flea delta3[] = { //  长度为 2 八联通 
 //flea(+0,+1), flea(+1,+1), flea(+1,+0), flea(+1,-1), flea(+0,-1), flea(-1,-1), flea(-1,+0), flea(-1,+1),
    flea(+0,+2), flea(+1,+2), flea(+2,+2), flea(+2,+1), flea(+2,+0), flea(+2,-1), flea(+2,-2), flea(+1,-2),
    flea(+0,-2), flea(-1,-2), flea(-2,-2), flea(-2,-1), flea(-2,+0), flea(-2,+1), flea(-2,+2), flea(-1,+2)
};
int pdist(const flea &a, const flea &b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}
struct graph
{
    int beg[maxn], nxt[maxn], to[maxn];
    int e;
    void ae(int x, int y)
    {
        ++e;
        to[e] = y;
        nxt[e] = beg[x];
        beg[x] = e;
    }
    void ae2(int x, int y)
    {
        ae(x, y);
        ae(y, x);
    }
} g;
int tme = 0;
int dfn[maxn], low[maxn];
bool vis[maxn];
int gds[maxn], gdc;
int id[maxn];
void havis(int x)
{
    if (vis[x]) return;
    vis[x] = true;
    for (int i = g.beg[x]; i; i = g.nxt[i]) {
        int y = g.to[i];
        havis(y);
    }
}
void dfs(int x, int fa = -1)
{
    if (id[x] == 0) return;
    dfn[x] = low[x] = ++tme;
    int cct = 0; // child cnt
    bool good = false;
    for (int i = g.beg[x]; i; i = g.nxt[i]) {
        int y = g.to[i];
        if (y == fa) continue;
        if (id[y] == 0) continue;
        if (dfn[y]) {
            low[x] = min(low[x], dfn[y]);
        } else {
            ++cct;
            dfs(y, x);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) good = true;
        }
    }
    if ((fa == -1 && cct > 1) || (fa != -1 && good)) gds[++gdc] = x;
}
int calc()
{
    if (n * m - c <= 1) { return -1; }
    if (n * m - c == 2) {
        vector<vector<char> > gg;
        gg.resize(n + 1);
        for (int i = 1; i <= n; ++i) gg[i].resize(m + 1);
        for (int i = 1; i <= c; ++i) gg[fs[i].x][fs[i].y] = 1;
        vector<flea> zz;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (!gg[i][j]) zz.push_back(flea(i, j));
            }
        }
        if (pdist(zz[0], zz[1]) > 1) return 0;
        return -1;
    }
    if (min(n, m) == 1) {
        if (c == 0) return 1;
        ll z = n * m;
        for (int i = 1; i <= c; ++i) {
            gw[i] = fs[i].x * fs[i].y;
        }
        sort(gw + 1, gw + c + 1);
        ll lb = 0, rb = c + 1;
        gw[0] = 0, gw[c + 1] = z + 1;
        while (lb < rb && gw[lb + 1] == gw[lb] + 1) ++lb;
        while (lb < rb && gw[rb - 1] == gw[rb] - 1) --rb;
        if (lb + 1 >= rb) return 1;
        return 0;
    }
    //  建立 O(c) 个重要节点 
    vector<pair<flea,int> > pol;
    for (int i = 1; i <= c; ++i) {
        flea t = fs[i];
        pol.push_back(make_pair(t, 0));
        for (int j = 0; j < sizeof(delta2) / sizeof(flea); ++j) {
            t += delta2[j];
            if(ok(t)) pol.push_back(make_pair(t, 1));
            t -= delta2[j];
        }
        for (int j = 0; j < sizeof(delta3) / sizeof(flea); ++j) {
            t += delta3[j];
            if (ok(t)) pol.push_back(make_pair(t, 2));
            t -= delta3[j];
        }
    }
    sort(pol.begin(), pol.end());
    vector<flea> m;
    flea t(-233, -233);
    int cc = 0;
    for (vector<pair<flea, int> >::iterator i = pol.begin(); i != pol.end(); ++i) {
        if (i->first != t) {
            t = i->first;
            m.push_back(t);
            id[++cc] = i->second;
        }
    }
    //  建图 
    tme = 0;
    g.e = 0;
    for (int i = 1; i <= cc; ++i) g.beg[i] = 0;
    for (vector<flea>::iterator i = m.begin(); i != m.end(); ++i) {
        flea t = *i;
        for (int j = 0; j < sizeof(delta1) / sizeof(flea); ++j) {
            t += delta1[j];
            vector<flea>::iterator k = lower_bound(m.begin(), m.end(), t);
            if (k != m.end() && *k == t) {
                g.ae(i - m.begin() + 1, k - m.begin() + 1);
            }
            t -= delta1[j];
        }
    }
    for (int i = 1; i <= cc; ++i) {
        dfn[i] = low[i] = 0;
        vis[i] = false;
    }
    gdc = 0;
    for (int i = 1; i <= cc; ++i) {
        if (id[i] && !dfn[i]) {
            if (vis[i]) return 0;
            havis(i);
            dfs(i);
        }
    }
    //if (tme < cc) return 0;
    for (int i = 1; i <= gdc; ++i) {
        if (id[gds[i]] == 1) return 1;
    }
    return 2;
}
int main()
{
    gi(T);
    for (int T_ = 1; T_ <= T; ++T_) {
        gi(n, m, c);
        for (int i = 1; i <= c; ++i) {
            gi(fs[i].x, fs[i].y);
        }
        printf("%d\n", calc());
    }
    return 0;
}

tags: NOI, UOJ, BZOJ