跳转至

260301 模拟赛

T1

你有一个 \(n\times m\) 的网格图，有 \(n\) 行格子和 \(m\) 列格子。你需要在每个格子中填入以下四种图案之一，使得：

  • 每条曲线都是单一颜色；
  • 不存在闭合曲线；

示意图

有 \(q\) 次操作，每次操作形如限制某个格子必须填某个图案，或者删除之前的某个限制。请你在最开始以及每次操作之后回答，填满其它格子的方案数。

\(n,m\le 10^9,~q\le 2\times 10^5\)

首先注意到确定第一行以后，下面的每一行要么和第一行相同，要么和第一行相反。注意到所有行不完全相同，并且所以列也不完全相同只有一种情况：

\ \ \ / / /
\ \ \ / / /
\ \ \ / / /
/ / / \ \ \
/ / / \ \ \

没办法画很好所以凑合理解一下，可以自己手玩。所以我们容易得出没有限制的方案数：\(2(2^n+2^m-2+(n-1)(m-1))\)。

考虑只有加入限制的操作怎么做，然后可以直接线段树分治。首先我们引入了颜色的限制，我们先给 \([1,4]\) 减一变成 0-index 的 \([0,3]\)，然后给 \(i\oplus j\) 为奇数的位置的颜色异或上 \(2\)。这样就可以用 \(4\) 个哈希表维护所有行相等和所有列相等分别 \(2\) 种总共 \(4\) 种情况。然后全相等也可以简单维护。然后对于上面示意图的那种情况只需维护中心点的取值矩阵即可，中间的四个点在进行完变换之后还有两种情况，应该是

30  12
21  03

随便维护即可。

代码 
  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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 10;
const int MOD = 1e4 + 7;

inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

inline void gmax(int &a, int b) { a = max(a, b); }
inline void gmin(int &a, int b) { a = min(a, b); }
inline void add(int &a, int b) { a += b, (a >= MOD) && (a -= MOD); }

struct Node {
    int x, y, t;
};
struct Rec {
    int x1, y1, x2, y2;
};
struct modf {
    Node v;
    Rec r1, r2;
    bool t1, t2;
    int f1, f2, f3, f4;
};

int n, m, q;
Node val[N]; int nn;
unordered_map<ull, ull> mp;

Rec r1, r2;
unordered_map<int, int> row, col;
int f1, f2, f3, f4;
modf sta[N]; int top;

int cnt[4], cur;

void insert(int x, int y, int t) {
    int tmp1 = row[x], tmp2 = col[y];
    int t0 = t; t ^= ((x ^ y) & 1) << 1; cnt[t]++; cur++;
    sta[++top] = {{x, y, t}, r1, r2, !(bool)(tmp1 >> t & 1), !(bool)(tmp2 >> t & 1), f1, f2, f3, f4};
    tmp1 |= (1 << t); tmp2 |= (1 << t);
    if(tmp1 != 1 && tmp1 != 2) f1 = -1;
    else if(~f1 && row[x] == 0) f1--;
    if(tmp1 != 4 && tmp1 != 8) f2 = -1;
    else if(~f2 && row[x] == 0) f2--;
    if(tmp2 != 1 && tmp2 != 8) f3 = -1;
    else if(~f3 && col[y] == 0) f3--;
    if(tmp2 != 2 && tmp2 != 4) f4 = -1;
    else if(~f4 && col[y] == 0) f4--;
    row[x] = tmp1, col[y] = tmp2;
    if(t == 0 || t == 3) gmax(r1.x1, x), gmin(r2.x2, x);
    else gmin(r1.x2, x), gmax(r2.x1, x);
    if(t == 2 || t == 3) gmax(r1.y1, y), gmin(r2.y2, y);
    else gmin(r1.y2, y), gmax(r2.y1, y);
}
int calc() {
    int res = 0;
    if(~f1) add(res, qpow(2, f1));
    if(~f2) add(res, qpow(2, f2));
    if(~f3) add(res, qpow(2, f3));
    if(~f4) add(res, qpow(2, f4));
    if(cnt[0] == cur) add(res, MOD - 1);
    if(cnt[1] == cur) add(res, MOD - 1);
    if(cnt[2] == cur) add(res, MOD - 1);
    if(cnt[3] == cur) add(res, MOD - 1);
    if(r1.x1 < r1.x2 && r1.y1 < r1.y2) add(res, (ll)(r1.x2 - r1.x1) * (r1.y2 - r1.y1) % MOD);
    if(r2.x1 < r2.x2 && r2.y1 < r2.y2) add(res, (ll)(r2.x2 - r2.x1) * (r2.y2 - r2.y1) % MOD);
    return res;
}
void roll_back() {
    int x = sta[top].v.x, y = sta[top].v.y, t = sta[top].v.t;
    cur--; cnt[t]--;
    r1 = sta[top].r1, r2 = sta[top].r2;
    if(sta[top].t1) row[x] ^= (1 << t);
    if(sta[top].t2) col[y] ^= (1 << t);
    f1 = sta[top].f1, f2 = sta[top].f2, f3 = sta[top].f3, f4 = sta[top].f4;
    --top;
}

namespace SegT {
    vector<Node> tr[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void insert(int p, int l, int r, int ql, int qr, const Node &v) {
        if(ql <= l && r <= qr) return tr[p].push_back(v);
        int mid = (l + r) >> 1;
        if(ql <= mid) insert(lc(p), l, mid, ql, qr, v);
        if(mid < qr) insert(rc(p), mid + 1, r, ql, qr, v);
    }
    void solve(int p, int l, int r) {
        int pre = top;
        for(Node &o : tr[p]) ::insert(o.x, o.y, o.t);
        if(l == r) cout << calc() << '\n';
        else {
            int mid = (l + r) >> 1;
            solve(lc(p), l, mid);
            solve(rc(p), mid + 1, r);
        }
        while(pre != top) roll_back();
    }
}

int main() {

    freopen("puzzle.in", "r", stdin);
    freopen("puzzle.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> q;
    r1 = r2 = {1, 1, n, m}; f1 = f2 = n, f3 = f4 = m;
    for(int i = 1; i <= q; i++) {
        char op; int x, y, t;
        cin >> op >> x >> y;
        if(op == '+') {
            cin >> t; t--;
            val[++nn] = {x, y, t};
            mp[(ull)x << 32 | y] = (ull)nn << 32 | i;
        } else {
            ull &tmp = mp[(ull)x << 32 | y];
            int tm = (int)tmp;
            int id = (int)(tmp >> 32);
            SegT::insert(1, 0, q, tm, i - 1, val[id]);
            tmp = 0;
        }
    }
    for(auto [pos, tmp] : mp) {
        if(tmp) {
            int tm = (int)tmp;
            int id = (int)(tmp >> 32);
            SegT::insert(1, 0, q, tm, q, val[id]);
        }
    }
    SegT::solve(1, 0, q);

    return 0;
}

T3

给定一个边仙人掌（任意一条边至多只在一个简单环中）和常数 \(k\)，放置最少的关键点覆盖整个仙人掌，一个关键点可以覆盖它 \(k\) 邻域内的所有点。

\(n\le 4\times 10^6\)

如果是树那肯定就是经典贪心了。考虑搬上仙人掌，如果发现一个环上必须要放置关键点，那就把所有子树产生的需求区间（即要求这个区间内放置至少一个点）分成两类：和父亲割点有交的，没交的。对第二类跑一遍最小点覆盖，然后尝试覆盖一些第一类点，最大化本子树在父亲那里的需求区间半径（区间半径显然是越大越好）。

具体的，先扫两遍环，把子树之间的贡献处理掉。然后容易通过一遍预处理，来移动最小点覆盖最左边那个点，动态求出最右边那个点的位置。没被覆盖的第一类区间形成一个滑窗，用单调队列维护即可。时间复杂度线性。

代码 
  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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
const int N = 4e6 + 10;

inline void read(int &x) {
    static char ch;
    while(!isdigit(ch = getchar_unlocked()));
    x = ch - '0';
    while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
}
inline void write(int x) {
    static char buf[60], top = 0;
    do buf[++top] = x % 10 + '0', x /= 10; while(x);
    while(top) putchar_unlocked(buf[top--]);
    putchar_unlocked('\n');
}

struct Edge {
    int v, next;
} pool[4 * N];
int ne, head[2 * N];
inline void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct Range {
    int l, r, w;
};

int T, n, m, k, ans;
int dfn[N], low[N], dt, bcnt;
int sta[N], top;
vector<int> bcc[N];

void tarjan(int u, int fe) {
    sta[++top] = u;
    dfn[u] = low[u] = ++dt;
    for(int e = head[u]; e; e = pool[e].next) {
        if(e == fe) continue;
        int v = pool[e].v;
        if(!dfn[v]) {
            tarjan(v, e ^ 1);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                ++bcnt;
                bcc[bcnt].push_back(u);
                while(sta[top + 1] != v) bcc[bcnt].push_back(sta[top--]);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void sort(vector<Range> &a, int n) {
    static vector<Range> p[N];
    for(int i = 0; i <= n; i++) p[i].clear();
    for(Range &i : a) p[i.r].push_back(i);
    a.clear();
    for(int i = 0; i <= n; i++)
        for(Range &j : p[i]) a.push_back(j);
}
void reduce(vector<Range> &a) {
    vector<Range> res;
    for(int i = 0, mx = -N - 5; i < a.size(); i++) {
        if(a[i].l <= mx) continue;
        if(!res.empty() && a[i].r == res.back().r) res.pop_back();
        res.push_back(a[i]); mx = max(mx, a[i].l);
    }
    a.swap(res);
}

int f[2 * N]; bool tp[2 * N], g[N];
void dfs(int u, int fa) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs(v, u);
    }
    if(u <= n) {
        int mx = 0, mn = N + 5;
        for(int e = head[u]; e; e = pool[e].next) {
            int v = pool[e].v;
            if(v == fa) continue;
            if(tp[v]) mx = max(mx, f[v]);
            else mn = min(mn, f[v]);
        }
        if(mx + mn <= k) tp[u] = 0, f[u] = mn;
        else tp[u] = 1, f[u] = mx;
    } else {
        int sz = bcc[u - n].size();
        vector<int> &cur = bcc[u - n]; cur.push_back(cur[0]);
        for(int i = 1, pre = -1; i < 2 * sz; i++) {
            if(pre > -1) pre--;
            if(i == sz) continue;
            if(tp[cur[i % sz]] && f[cur[i % sz]] <= pre) tp[cur[i % sz]] = 0, f[cur[i % sz]] = N + 5;
            else if(!tp[cur[i % sz]]) pre = max(pre, k - f[cur[i % sz]]);
        }
        for(int i = 2 * sz - 1, pre = -1; i >= 1; i--) {
            if(pre > -1) pre--;
            if(i == sz) continue;
            if(tp[cur[i % sz]] && f[cur[i % sz]] <= pre) tp[cur[i % sz]] = 0, f[cur[i % sz]] = N + 5;
            else if(!tp[cur[i % sz]]) pre = max(pre, k - f[cur[i % sz]]);
        }
        int mx = -1, mn = N + 5, mxp;
        for(int i = 1; i < sz; i++)
            if(tp[cur[i]]) mx = max(mx, min(i, sz - i) + f[cur[i]]);
            else mn = min(mn, min(i, sz - i) + f[cur[i]]);
        if(mx == -1) return tp[u] = 0, f[u] = mn, void();
        if(mx <= k) return tp[u] = 1, f[u] = mx, void();
        vector<Range> r1, r2;
        for(int i = 1; i < sz; i++)
            if(tp[cur[i]] && min(i, sz - i) + f[cur[i]] > k) r1.push_back({i - (k - f[cur[i]]), i + (k - f[cur[i]])});
            else if(i == 0 || tp[cur[i]]) {
                int l = i - (k - f[cur[i]]), r = i + (k - f[cur[i]]);
                if(r >= sz) l -= sz, r -= sz;
                r2.push_back({l, r, k - f[cur[i]] - min(i, sz - i)});
            }
        sort(r1, sz), sort(r2, sz); reduce(r1), reduce(r2);
        static int nxt[N], len[N], que[N], hd, tl; hd = 1, tl = 0;
        for(int i = sz - 1, j = r1.size(); i >= 0; i--) {
            while(j > 0 && r1[j - 1].l > i) --j;
            if(j == r1.size()) nxt[i] = i, len[i] = 1;
            else assert(r1[j].r < sz), nxt[i] = nxt[r1[j].r], len[i] = len[r1[j].r] + 1;
        }
        assert(!r1.empty());
        int cnt = len[r1[0].r]; assert(r1[0].r < sz);
        mx = -1, mxp = 0;
        for(int i = 0, j = 0; i <= r1[0].r; i++) {
            if(len[i] != cnt) continue;
            while(j < r2.size() && r2[j].r < i) {
                while(hd <= tl && r2[j].w <= r2[que[tl]].w) --tl;
                que[++tl] = j++;
            }
            while(hd <= tl && r2[que[hd]].l + sz <= nxt[i]) ++hd;
            int tmp;
            if(hd > tl) tmp = N + 2;
            else tmp = r2[que[hd]].w;
            if(tmp > mx || tmp == N + 2 && min(i, sz - nxt[i]) < min(mxp, sz - nxt[mxp])) mx = tmp, mxp = i;
        }
        assert(~mx);
        for(int i = mxp, j = 0; ; i = r1[j].r) {
            g[cur[i]] = 1; mn = min(mn, min(i, sz - i)); ++ans;
            while(j < r1.size() && r1[j].l <= i) ++j;
            if(j == r1.size()) break;
        }
        if(mx == N + 2) return tp[u] = 0, f[u] = mn, void();
        return tp[u] = 1, f[u] = k - mx, void();
    }
}

inline void clear_Edge() {
    for(int i = 1; i <= 2 * n; i++) head[i] = 0; ne = 1;
}
void clear() {
    clear_Edge();
    for(int i = 0; i <= n + 1; i++) {
        dfn[i] = low[i] = sta[i] = 0;
        f[i] = N + 5, tp[i] = 1;
        g[i] = 0;
        bcc[i].clear();
    }
    dt = bcnt = top = 0; ans = 0;
}

int main() {

    freopen("tower.in", "r", stdin);
    freopen("tower.out", "w", stdout);

    read(T);
    while(T--) {
        read(n), read(m), read(k);
        clear();
        for(int i = 1; i <= m; i++) {
            int u, v; read(u), read(v);
            addEdge(u, v); addEdge(v, u);
        }
        tarjan(1, 0);
        clear_Edge();
        for(int i = 1; i <= bcnt; i++) {
            for(int j : bcc[i]) addEdge(i + n, j), addEdge(j, i + n);
        }
        dfs(1, 0);
        if(tp[1]) g[1] = 1, ++ans;
        write(ans);
        for(int i = 1; i <= n; i++) putchar_unlocked(g[i] + '0'); putchar_unlocked('\n');
    }

    return 0;
}