跳转至

260122 模拟赛

T1

给定一个 \(n\times m\) 格子的网格图，每个格子有恰好一条对角线被额外连接，你需要让网格图节点构成的图存在三染色。有一些格子被确定，你需要给出字典序最小的解，或者报告无解。

考虑一种三染色方案，对它的每行进行差分，发现往下走一个格子不会改变它的差分数组，进一步观察可以发现经过 N 和 Z 会偏移 +1 或者 -1，取决于上面一条边的差分值。因此不难得到两行要么相同要么相反，于是用带权并查集简单维护即可。

nm 写反挂成 0pts。

T2

给定 \(n\) 个模式串 \(s_{1\sim n}\) 和一个文本串 \(t\)，有 \(m\) 次询问，每次询问 \(t\) 的一个区间 \([l,r]\) 总共匹配 \(s_{1\sim n}\) 多少次。

\(n,m\le 5\times 10^5,~\sum|s_i|\le 10^6,~|t|\le 5\times 10^6\)

对 \(s\) 建出 AC 自动机，然后把 \(t\) 放上去跑一遍，就可以知道以每个位置为右端点的匹配总数。此时如果直接求 \([l,r]\) 的区间和，可能会把一些 \(L<l\) 的匹配也算上。我们找到这些不合法的匹配中，右端点最靠右的一个记为 \([L,R]\)，那么右端点在 \((R,r]\) 的匹配显然可以直接差分得到。剩下的部分是 \([L,R]\) 的一个后缀，我们可以直接对每个 \(s_i\) 的后缀预处理答案。

代码 
  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
#include<iostream>
#include<algorithm>
#include<vector>
typedef long long ll;
using namespace std;
const int N = 5e5 + 10;
const int S = 1e6 + 10;
const int T = 5e6 + 10;

struct Qr {
    int l, r, id;
    inline bool operator<(const Qr &b) const {
        return r < b.r;
    }
} q[N];

int n, m;
string t, s[N];

int que[S], hd, tl;
struct ACAM {
    struct Node {
        int chd[26], fa, cnt, mx;
        inline void clear() { for(int i = 0; i < 26; i++) chd[i] = 0; fa = cnt = mx = 0; }
    } tr[S]; int nn;
    inline ACAM() { tr[0].clear(); nn = 0; }
    inline int addNode() { return tr[++nn].clear(), nn; }
    inline void insert(string &s, int id) {
        int cur = 0;
        for(int i = 0; i < s.size(); i++) {
            int d = s[i] - 'a';
            if(!tr[cur].chd[d]) tr[cur].chd[d] = addNode();
            cur = tr[cur].chd[d];
        }
        tr[cur].cnt++;
        tr[cur].mx = id;
    }
    inline void build() {
        hd = 1, tl = 0;
        for(int i = 0; i < 26; i++) if(tr[0].chd[i]) que[++tl] = tr[0].chd[i];
        while(hd <= tl) {
            int u = que[hd++];
            for(int i = 0; i < 26; i++) {
                int tmp = tr[tr[u].fa].chd[i];
                if(tr[u].chd[i]) {
                    tr[tr[u].chd[i]].fa = tmp;
                    tr[tr[u].chd[i]].cnt += tr[tmp].cnt;
                    if(!tr[tr[u].chd[i]].mx) tr[tr[u].chd[i]].mx = tr[tmp].mx;
                    que[++tl] = tr[u].chd[i];
                } else {
                    tr[u].chd[i] = tmp;
                }
            }
        }
    }
} m1, m2;

int mat[T], ml[T];
int sta[T], val[T], top;
ll f[T], ans[N];
vector<ll> cnt[N];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> t;
    for(int i = 1; i <= n; i++) cin >> s[i];

    for(int i = 1; i <= n; i++) {
        m1.insert(s[i], i); reverse(s[i].begin(), s[i].end());
        m2.insert(s[i], i);
    }
    m1.build(), m2.build();

    for(int i = 0, cur = 0; i < t.size(); i++) {
        int d = t[i] - 'a';
        cur = m1.tr[cur].chd[d];
        mat[i] = m1.tr[cur].mx;
        ml[i] = mat[i] ? i - s[mat[i]].size() + 1 : T;
        f[i] = m1.tr[cur].cnt;
        if(i) f[i] += f[i - 1];
    }

    for(int i = 1; i <= n; i++) {
        cnt[i].resize(s[i].size() + 1);
        for(int j = 0, cur = 0; j < s[i].size(); j++) {
            int d = s[i][j] - 'a';
            cur = m2.tr[cur].chd[d];
            cnt[i][j + 1] = m2.tr[cur].cnt;
            cnt[i][j + 1] += cnt[i][j];
        }
    }

    for(int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r, q[i].l--, q[i].r--, q[i].id = i;
    sort(q + 1, q + 1 + m);
    for(int i = 0, j = 1; i < t.size(); i++) {
        while(top && ml[sta[top]] >= ml[i]) --top;
        sta[++top] = i; val[top] = ml[i];
        while(j <= m && q[j].r == i) {
            int p = sta[lower_bound(val + 1, val + 1 + top, q[j].l) - val - 1];
            if(p && p >= q[j].l) {
                ans[q[j].id] = f[i] - f[p] + cnt[mat[p]][p - q[j].l + 1];
            } else ans[q[j].id] = f[i] - (q[j].l ? f[q[j].l - 1] : 0);
            j++;
        }
    }

    for(int i = 1; i <= m; i++) cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}

T3

给定一棵点仙人掌，即保证不存在一个点同时位于两个简单环中。给定两个正整数 \(a,b\)，你需要构造两个不同的点 \(s,t\)，使得图上严格到 \(s\) 更近的点恰有 \(a\) 个，严格到 \(t\) 更近的点恰有 \(b\) 个，保证有解。

分讨两侧领域的交界处是什么样的，要么是中间一个点和它的子树不被双方控制，要么是中间一条边，双方控制两棵子树，要么是双方切断了一个环（此处有 \(3\) 种情况，分界点是两条边，一边一点，两点），要么是双方切断了一个环（分界点是一段区间，要求一个点在环上一个区间端点的对面，另一个点在另一个区间端点的子树中，深度与第一个点到该端点的距离相等）。

考虑怎么维护，第一/二种情况是简单的；后面两种情况需要做一遍仙人掌上 dp 求出每条边往下的深度（这里还需要两个可删堆）；第三种情况直接双指针，第四种情况也直接双指针，需要套个可删堆维护最深深度。