跳转至

250811 模拟赛

T2 lane

给定一个排列 \(a_{1\sim n}\) 和常数 \(m\)，询问满足以下条件的数对 \((i,j)\) 个数：

  • \(i<j\le n-m+1\)；
  • \(\forall k\in[0,m),\ a_{i+k}<a_{j+k}\)

\(m\le n\le 5\times 10^4\)

发现题目限制形如一个偏序，并且数据量不大，时限还长一截，因此考虑 bitset 高维偏序。设 \(f_{i,j}=[a_i<a_{i+j}]\)，发现一个合法的解对应一列长度为 \(m\) 的全 \(1\) 区间。这里可以直接使用 st 表维护区间按位与，时间复杂度 \(O(\frac{n^2\log n}{\omega})\)。

代码 
 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
#include<iostream>
#include<bitset>
using namespace std;
const int N = 5e4 + 10;

#define bs bitset<N>

int n, m, k;
int a[N], b[N];

bs c[N];

long long ans;

int main() {

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

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

    bs tmp;
    for(int i = n; i >= 1; i--) {
        c[b[i]] = tmp >> b[i];
        tmp.set(b[i]);
    }

    for(k = 1; (1 << k) <= m; k++) {
        for(int i = 1; i + (1 << k) - 1 <= n; i++) {
            c[i] &= c[i + (1 << (k - 1))];
        }
    }

    --k;

    for(int i = 1; i + m - 1 <= n; i++) {
        ans += (c[i] & c[i + m - (1 << k)]).count();
    }

    cout << ans << '\n';

    return 0;
}

实际上，我们可以在 \(O(n)\) 内预处理出滑窗半群信息。设 \(n\) 个窗口分别为 \([l_1,r_1],[l_2,r_2],\cdots [l_n,r_n]\)，初始时，我们维护 \([l_1,r_1]\) 的后缀和；随着左端点不断右移，再记录 \((r_1,r_i]\) 的和，然后和左侧合并即可；当左端点移过 \(r_1\)，就以当前的 \(r\) 重新计算后缀和。显然均摊线性。

这样时间复杂度就可以做到 \(O(\frac{n^2}\omega)\)。

T3 metallurgy

有 \(n\) 个有标号格子，\(m\) 种物品，第 \(i\) 种物品权值为 \(a_i\)，每种物品都有无数多个。现在要求你用 \(n\) 个物品填满格子，并使得物品权值和恰为给定常数 \(S\)。问方案数对 \(2\) 取模的结果。两种方案视为不同当且仅当存在一个格子在两种方案中放了两个不同种类的物品。

\(n,S\le 10^{18},\ m\le 200,\ a_i\le 10^5\)

设第 \(i\) 个物品选了 \(b_i\) 个，那么题目限制转换为 \(\sum b_i=n,\ \sum a_ib_i=S\)。发现钦定一组 \(b_i\) 之后，方案数形如一个多重集排列：

\[ \binom{n}{b_1}\binom{n-b_1}{b_2}\binom{n-b_1-b_2}{b_3}\cdots \]

根据 Lucas 定理，组合数可以按位拆开，第一项 \(\binom{n}{b_1}\bmod 2\) 不为 \(0\) 当且仅当 \([b_i\subseteq n]\)（此处用数字表示二进制中 \(1\) 的数位集合）；继续对后面的项进行拆位，得到排列数不为 \(0\) 当且仅当 \(b_1,b_2\cdots b_m\) 是 \(n\) 集合的一个划分。

现在，我们只需把 \(n\) 的每一位分配给一种物品即可。为了解决 \(S\) 的限制，考虑从低位往高位处理（因为高位一定不会影响低位）。对于每一位，枚举填哪个物品，在 dp 中记一下向高位的贡献，然后钦定贡献的最后一位匹配 \(S\) 的当前位，并去掉该位，向高位移动一位。

代码 
 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
#include<iostream>
#include<bitset>
#define int long long
using namespace std;
const int M = 210;
const int V = 1.2e5;

int T;
int n, s, m;
int a[M];

bitset<2 * V> f[2];

signed main() {

    cin >> T;
    while(T--) {
        cin >> n >> s >> m;
        for(int i = 1; i <= m; i++) cin >> a[i];
        f[0] = 1;
        int cur = 0;
        for(int i = 0; i < 63; i++) {
            if((n >> i) & 1) {
                f[cur ^= 1] = 0;
                for(int j = 1; j <= m; j++) {
                    f[cur] ^= f[!cur] << a[j];
                }
            }
            for(int j = 0; j < V; j++) {
                f[cur].set(j, f[cur][(j << 1) | ((s >> i) & 1)]);
            }
            f[cur] = (f[cur] << V) >> V;
        }
        cout << f[cur][0] << '\n';
    }

    return 0;
}

T4 clairobscur

给定一个无向图，节点有黑白两种颜色。你初始位于 \(1\) 号节点。你每新到达一个节点，都会立即反转该节点的颜色，然后你需要选择一个相邻且颜色相同的节点前往。

问能否无限在图中走下去。

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

首先我们最后肯定是走进了一个环内。注意到一个环一定存在于一个点双内，因此可以考虑跑 Tarjan 将图化为树。

考虑最终的环，不难注意到它一定是一个奇环，并且两种颜色交替出现，而入口处相邻两个点颜色相同。为了防止前面的路径反转了环上的部分边，我们可以钦定走到环上之前的路径和环无交，并且不难证明：如果存在有交且合法的情况，一定可以调整为无交的情况。

我们可以将所有边按照两端点颜色是否相同分成两类，颜色不同的边组成了起点到环的路径以及环的大部分；颜色相同的边只能存在于环的入口处。因为后者在路径中只有一条，因此将它们从图上去掉并单独考虑。现在剩下的颜色不同的边都是可以自由行走的边。

现在一种合法方案对应一条从根出发的简单路径和一条从路径末端连接到路径中间的同色边。考虑枚举同色边，问题转化为能否走到这个环上。这时候前面的点双就派上用场了，我们考虑连接同色边的两端的两条路径，我们总会先走到一条路径上，此时我们只需要沿着路径走到端点，然后再沿着第二条路径走即可。

然而，建立点双时去掉了所有同色边，因此同色边的两端点可能存在于不同的点双内。发现这种情况还要求同色边跨越的两个点双具有祖孙关系。为了找到一条从根出发，不经过环上的边而直接走到端点的方案，仍然可以使用上面的思路，只不过考虑的是同色边的一个端点和一个割点之间的两条路径。

因此，若一条同色边的两端点位于同一个点双内，则存在解；若一条同色边两段位于两个不同的点双内，且两个点双存在祖先关系，那么存在解。祖先关系可以用圆方树和 dfn 序判。

代码 
  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
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 4e5 + 10;

struct Edge2 {
    int u, v;
} edg[N];
int ne2;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int T;
int n, m;
int col[N];

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

namespace G2 {
    Edge pool[2 * N];
    int ne, head[N];
    void addEdge(int u, int v) {
        pool[++ne] = {v, head[u]};
        head[u] = ne;
    }
    int dfn[N], sz[N], dt;
    void clear() {
        ne = dt = 0;
        for(int i = 0; i < N; i++) head[i] = 0;
    }
    void dfs(int u, int fa) {
        dfn[u] = ++dt;
        sz[u] = 1;
        for(int e = head[u]; e; e = pool[e].next) {
            int v = pool[e].v;
            if(v == fa) continue;
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
    void getdfn() {
        int rt = 1;
        if(cut[rt]) rt += n;
        else rt = bcc[rt][0];
        dfs(rt, 0);
    }
    bool check(int x, int y) {
        return (dfn[x] <= dfn[y] && dfn[y] < dfn[x] + sz[x]) || (dfn[y] <= dfn[x] && dfn[x] < dfn[y] + sz[y]);
    }
}

bool check(int x, int y) {
    if(cut[x]) x += n;
    else x = bcc[x][0];
    if(cut[y]) y += n;
    else y = bcc[y][0];
    return G2::check(x, y);
}

void clear() {
    ne2 = dt = bcnt = 0;
    ne = 1;
    for(int i = 0; i < N; i++) head[i] = cut[i] = dfn[i] = low[i] = 0;
    for(int i = 0; i < N; i++) bcc[i].clear();
    G2::clear();
}

int main() {

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

    cin >> T;
    while(T--) {
        cin >> n >> m;
        clear(); // edg, edg2, ne = 1
        for(int i = 1; i <= n; i++) {
            char ch;
            cin >> ch;
            col[i] = ch == 'W';
        }
        for(int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            ++u, ++v;
            if(col[u] == col[v]) edg[++ne2] = {u, v};
            else {
                addEdge(u, v);
                addEdge(v, u);
            }
        }
        tarjan(1, 0);
        if(top) {
            ++bcnt;
            while(top) bcc[sta[top--]].push_back(bcnt);
        }
        for(int i = 1; i <= n; i++) {
            if(!cut[i]) continue;
            for(int j : bcc[i]) {
                G2::addEdge(i + n, j);
                G2::addEdge(j, i + n);
            }
        }
        G2::getdfn();
        bool flag = false;
        for(int i = 1; i <= ne2; i++) {
            int u = edg[i].u, v = edg[i].v;
            if(bcc[u].empty() || bcc[v].empty()) continue;
            if(check(u, v)) { flag = true; break; }
        }
        cout << (flag ? "yes\n" : "no\n");
    }

    return 0;
}