Eous的小站
日记

日记

Mon Dec 16 2024
7 分钟
life 日记
1323 字

聪明的人已经发现了（不聪明的人也该发现了），上一篇日记是12月12日的，但是这一篇是12月16日的。一不小心鸽了 33 天。

至于前三天，你只需要知道我在打 usaco 和 bf-v 。其他没甚讲的。那个 usaco 也是，第一道就来一道贪心（一生之敌）。然后第二道又是一道差分约束。也是打的来。其实是有原题的，但是我忘了。有讲头的也只有 usaco 的银组T3。

Silver_C 2D Conveyer Belt#

看不着题面的点这里

说句闲话：其实我的大号是没打过银组的，但是我有小号。
我们发现，每一个建了传送带的格子，就相当于向传送带指向的点建了一条边。而没有建的，就相当于向四个方向都建了边。而指向外面或者最外层的没有建边的点就统一连到一个点：00 上面。还有最重要的结论：当且仅当形成环的时候，环上的点和最终要走到环上的点是走不出去的。于是乎我们考虑从每一个点开始搜。搜到环了就标成出不去。但是这么做的时间复杂度是 O(qn4)\mathcal{O}(qn^4) ，就算是剪枝以后也有 O(qn2)\mathcal{O}(qn^2) 这么做明显不现实。
我们先考虑简单版：只查询一次。现在的做法是枚举每一个点，从它开始搜。但是，我们想，能不能把它变成从一个点搜呢？我们发现，能出去的点一定形成一颗以 00 为根的内向树（就是子节点指向父亲节点的树）。我们都知道，内向树很麻烦，几乎不可处理。所以我们考虑建反图，那样子，环还是环，但是内向树却变成了外向树，我们便可以直接从 00 开始搜，搜到的点就是能出去的点。
然后我们就得到了一个 O(n2)\mathcal{O}(n^2) 的做法。但是总共不是只有一次询问，于是我们考虑如何处理询问。我们发现：每次多加一个新的传送带就是将 44 条边删成 11 条边。但是，我们知道，删边十分的麻烦，即使是链表也一样。于是我们考虑离线，倒序枚举。那样子每次就是加边，这就十分的简单了。我们考虑加边后，每次从 00 开始搜，搜出来有多少个点就是上一个请求的答案（这个自己想想）。于是，我们发现，还是 O(qn2)\mathcal{O}(qn^2) 。还是不可以。我们考虑剪枝：每次搜过的，计数并打上标记，以后不再搜。但是我们发现，第一次搜就把 00 和所有能出去的点都标记了。这些点现在就想墙一样挡着。于是我们只能考虑寻找新的起点。还是那句话：第一次搜就把 00 和所有能出去的点都标记了。于是我们压根就不用再从 00 开始搜，能影响答案的也就只有加边的那个点。于是我们直接考虑从这个点开始搜，搜到的点计数，那样总点数减累计的能出去的点数就是上一个请求的答案。但是，如果能这个点能影响答案，当且仅当之前不能到但现在能到，也就是说，它当前不能到但是它周围四个点有一个能到，它才能作为新的起点。这样，我们就真正的把他优化到了 O(n2+q)\mathcal{O}(n^2 + q) 。
因为有些恶心的细节所以还是放下代码：

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxq = 2e5 + 5;
const int maxn = 1e6 + 5;
const int dir[4][2] = {-1,0,1,0,0,-1,0,1};
int n,q;
int x[maxq],y[maxq],d[maxq];
int ans[maxn],cnt = -1;
bool vis[maxn],mp[maxn];
struct edge {
    int v;
    edge *nxt;
}*head[maxn];
int toint(int x,int y) {
    if (x < 1 || x > n || y < 1 || y > n)//这里的意思是出去了就是0点
        return 0;
    return (x - 1) * n + y;
}
void adde(int u,int v) {
    auto tmp = new edge;
    tmp->v = v;
    tmp->nxt = head[u];
    head[u] = tmp;
}
void dfs(int u) {//搜索并计数
    if (vis[u])
        return;
    vis[u] = 1;
    cnt ++;
    for (auto i = head[u]; i; i = i->nxt)
        dfs(i->v);
}
signed main() {
    scanf("%lld%lld",&n,&q);
    for (int i = 1; i <= q; i++) {
        scanf("%lld%lld",x + i,y + i);
        char ch;
        cin >> ch;
        mp[toint(x[i],y[i])] = 1;
        switch (ch) {
        case 'U':
            d[i] = 0;
            break;
        case 'D':
            d[i] = 1;
            break;
        case 'L':
            d[i] = 2;
            break;
        default:
            d[i] = 3;
            break;
        }
        adde(toint(x[i] + dir[d[i]][0],y[i] + dir[d[i]][1]),toint(x[i],y[i]));//建反图
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!mp[toint(i,j)])
                for (int k = 0; k < 4; k++)
                    adde(toint(i + dir[k][0],j + dir[k][1]),toint(i,j));//没有标记的点就四个方向都建边
    for (int i = q; i >= 1; i--) {
        static int st = 0;//如果是第一次就从0开始搜
        static bool fl = 1;//标记它能不能成为新的起点
        if (fl)
            dfs(st);
        ans[i] = n * n - cnt;//记录答案
        st = toint(x[i],y[i]);
        fl = 0;
        for (int j = 0; j < 4; j++)
        {
            if (j == d[i])
                continue;
            int tx = x[i] + dir[j][0];
            int ty = y[i] + dir[j][1];
            fl |= vis[toint(tx,ty)];//旁边四个点能到
            adde(toint(tx,ty),st);//加边
        }
        fl &= (!vis[st]);//当前不能到，就作为新的起点
    }
    for (int i = 1; i <= q; i++)
        printf("%lld\n",ans[i]);
    return 0;
}