Asusetic
0%

2021.06.06模拟赛

发表于 分类于 Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

怎么看都很毒瘤

瑕光天下第一

2021.06.06 模拟赛

T1 背包

Link

同余最短路

先贪心拿最大的先尽可能地装，因为背包容量太大了所以最优解肯定绝大部分都是这么拿的

记他为 pp，在  mod p\bmod p 意义下转移，就是同于最短路

如果拿一个新的物品 xx ，如果 now+x<pnow+x < p 直接更新消耗 11 代价，否则可以考虑拿去一个 pp 换上 now+x mod pnow+x \bmod p 消耗 00 代价

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 5;
int T, dis[N];
bool vis[N];
queue<int> q;
typedef long long ll;
vector<int> a;
int n;
ll m;
void spfa() {
    memset(dis, 0x7f, sizeof(dis));
    dis[0] = 0;
    q.push(dis[0]);
    vis[0] = 1;
    while (!q.empty()) {
        int x  = q.front();
        vis[x] = 0;
        q.pop();
        for (auto p : a) {
            int v = x + p;
            int w = (v >= a[n - 1]) ? 0 : 1;
            if (v >= a[n - 1]) {
                v %= a[n - 1];
            }
            if (dis[v] > dis[x] + w) {
                dis[v] = dis[x] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        cin >> m >> n;
        a.resize(n);
        for (auto &v : a) {
            cin >> v;
        }
        sort(a.begin(), a.end());
        spfa();
        if (dis[m % a[n - 1]] >= (1ll << 30)) {
            cout << "IMPOSSIBLE" << endl;
            continue;
        }
        cout << (m / a[n - 1]) + dis[m % a[n - 1]] << endl;
    }
}
//Asusetic eru quionours.

T2 推箱子

Link

毒瘤之一

先连好图的模型，然后考虑从终点往回倒着推，人只能在箱子的某一侧并且是确定的

人的行为只能是

  • 推箱子
  • 从某一侧走到某一侧以便于推箱子

第一个行为没有问题，第二个行为就是找到一条不过箱子的路径到达箱子的另一侧，思考一下就能发现要求这两个位置在一个点双里

现在我们找出来了所有可行状态，然后就是考虑初始状态人可以从某一个点走到箱子旁边

现在需要统计这个点有多少个，也就是删掉一个点后有几个点与之联通，也就是删点后人所在连通块的大小

先把圆方树建出来（人比较菜不会建圆方树，不在点双里的点直接挂到了相邻点上，但是最终效果是一样的，正确的圆方树可以看 Renamoe\color{black}\text{R}\color{red}\text{enamoe} 的代码）

如果人在箱子的子树里，就只能走到自己的点双里的点

如果在箱子的点的外面，就可以走除去终点和箱子子树的所有点

码成一坨的代码：

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 <queue>
using namespace std;
const int N = 1055;
int a[N][N];
char mp[N];
int n, m;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
bool check_bound(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
int id(int x, int y) {
    return (x - 1) * m + y;
}
struct Graph {
    vector<int> edge[N * N * 2];
    void add(int u, int v) {
        edge[u].emplace_back(v);
    }
} G, Tr;
int dep[N * N * 2], vis[N * N], low[N * N], dfn[N * N], dfnid, fa[N * N * 2];
int st[N * N], top, dcc[N * N];
bool reach[N][N][4][4];
void tarjan(int x) {
    vis[x] = 1;
    low[x] = dfn[x] = ++dfnid;
    st[++top]       = x;
    dcc[x]          = x;
    for (auto v : G.edge[x]) {
        if (v == fa[x]) {
            continue;
        }
        if (!dfn[v]) {
            fa[v] = x;
            tarjan(v);
            low[x] = min(low[x], low[v]);
            if (low[v] == dfn[x]) {
                while (st[top] != v) {
                    dcc[st[top]] = x;
                    top--;
                }
                top--;
                dcc[v] = x;
            } else if (low[v] > dfn[x]) {
                while (st[top] != v) {
                    --top;
                }
                --top;
            }
        } else {
            low[x] = min(low[x], dfn[v]);
        }
    }
}
int siz[N * N * 2];
void dfs2(int x) {
    dep[x] = dep[fa[x]] + 1;
    // cout << x << " " << fa[x] << endl;
    if (x <= n * m)
        siz[x] = 1;
    for (auto v : G.edge[x]) {
        fa[v] = x;
        dfs2(v);
        siz[x] += siz[v];
    }
}
int sx, sy;
bool qvis[N][N][4];
void bfs() {
    struct Node {
        int x, y, p;
    };
    queue<Node> q;
    for (int i = 0; i < 4; ++i) {
        if (check_bound(sx + dx[i], sy + dy[i]) && !a[sx + dx[i]][sy + dy[i]]) {
            q.push(Node{sx, sy, i});
        }
    }
    while (!q.empty()) {
        Node now = q.front();
        q.pop();
        int p  = now.p;
        int nx = now.x + dx[p], ny = now.y + dy[p];
        if (check_bound(nx + dx[p], ny + dy[p]) && !a[nx + dx[p]][ny + dy[p]] &&
            !qvis[nx][ny][p]) {
            qvis[nx][ny][p] = 1;
            q.push(Node{nx, ny, p});
        }
        for (int i = 0; i < 4; i++) {
            if (reach[now.x][now.y][p][i] && !qvis[now.x][now.y][i]) {
                qvis[now.x][now.y][i] = 1;
                q.push(Node{now.x, now.y, i});
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> mp + 1;
        for (int j = 1; j <= m; j++) {
            if (mp[j] == '#') {
                a[i][j] = 1;
            }
            if (mp[j] == 'X') {
                sx = i;
                sy = j;
            }
        }
    }
    int s = id(sx, sy);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!a[i][j]) {
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k], ny = j + dy[k];
                    if (check_bound(nx, ny) && !a[nx][ny]) {
                        G.add(id(i, j), id(nx, ny));
                    }
                }
            }
        }
    }
    tarjan(s);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (vis[id(i, j)]) {
                for (int k = 0; k < 4; k++) {
                    for (int l = k + 1; l < 4; l++) {
                        if (!check_bound(i + dx[k], j + dy[k]) ||
                            !check_bound(i + dx[l], j + dy[l]))
                            continue;
                        int a = id(i + dx[k], j + dy[k]);
                        int b = id(i + dx[l], j + dy[l]);
                        if (dcc[a] == dcc[b] || dcc[a] == b || dcc[b] == a) {
                            reach[i][j][k][l] = reach[i][j][l][k] = 1;
                        }
                    }
                }
            }
        }
    }
    bfs();
    int tot = 0;
    for (int i = 1; i <= n * m; i++) {
        G.edge[i].clear();
    }
    for (int i = 1; i <= n * m; ++i) {
        if (vis[i]) {
            ++tot;
            G.add(i, i + n * m);
            if (dcc[i] != i) {
                G.add(dcc[i] + n * m, i);
            } else {
                G.add(fa[i], i);
                // cout << fa[i] << " " << i << endl;
            }
        }
    }
    dfs2(s);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (vis[id(i, j)] && (i != sx || j != sy)) {
                int p   = id(i, j);
                bool f1 = 0, f2 = 0;
                for (int k = 0; k < 4; ++k) {
                    if (qvis[i][j][k]) {
                        int x = id(i + dx[k], j + dy[k]);
                        if (fa[x] == p) {
                            ans += 1ll * siz[x];
                        } else if (dep[x] > dep[p]) {
                            if (!f1) {
                                ans += 1ll * siz[p + n * m];
                                f1 = 1;
                            }
                        } else {
                            if (fa[p] == x) {
                                ans += 1ll * tot - 1 - siz[p];
                            } else {
                                if (!f2) {
                                    ans += 1ll * tot - 1 - siz[p];
                                    f2 = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
}
// Asusetic eru quionours.

T3 家训是『不畏苦暗』

瑕光天下第一！

看std这个题大概是叫Blemishine

毒瘤之二

暴力做法是直接大力拓扑然后确定每个点能够达到的异或值，复杂度 O(210n)O(2^{10}n)

虽然是常数但是肯定过不去…

用从来没见过的压位来优化一下这个复杂度

设我们把点权低 ll 位压起来，一共有 22l2^{2^l} 种可能，预处理 trans[i,j]trans[i,j] 表示低 ll 位权值为状态位 ii 时，异或 jj 的结果

转移的时候设 dpi,jdp_{i,j} 表示点 ii 高 10−l10-l 位为 jj 时，低 ll 位的可能状态，通过 transtrans 转移

transtrans 还可以高低位拆开处理 复杂度 O(22l−122l+n210−l)O(2^{2^{l-1}}2^{2l}+n2^{10-l})

代码取得 l=4l=4 ，不过看起来 55 更优

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e6 + 5;
int n, m;
int a[N];
struct Graph {
    vector<int> edge[N];
    void add(int u, int v) {
        edge[u].emplace_back(v);
    }
} G;
int in[N];
int low(int x, int bit) {
    return x & ((1 << bit) - 1);
}
int high(int x, int bit) {
    return x >> bit;
}
int dp[N][(1 << 8) + 5];
int tmp[(1 << 8) + 5];
int hight[(1 << 8) + 5][(1 << 4) + 5], lowt[(1 << 8) + 5][(1 << 4) + 5];
int lowbit(int x) {
    return x & (-x);
}
int lg[(1 << 8) + 5];
int main() {
    cin >> n >> m;
    lg[1] = 0;
    for (int i = 2; i < (1 << 8); i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 0; i < (1 << 8); ++i) {
        for (int j = 0; j < (1 << 4); ++j) {
            for (int k = 0; k <= 7; k++) {
                if (i & (1 << k)) {
                    lowt[i][j] |= 1 << (k ^ j);
                }
            }
        }
    }
    for (int i = 0; i < (1 << 8); ++i) {
        for (int j = 0; j < (1 << 4); ++j) {
            for (int k = 8; k <= 15; k++) {
                if (i & (1 << (k - 8))) {
                    hight[i][j] |= 1 << (k ^ j);
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        in[v]++;
        G.add(u, v);
    }
    vector<int> topo;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        topo.emplace_back(x);
        for (auto v : G.edge[x]) {
            --in[v];
            if (!in[v]) {
                q.push(v);
            }
        }
    }
    dp[1][a[1] >> 4] = 1 << (a[1] & 15);
    for (auto x : topo) {
        for (int i = 0; i < (1 << 8); i++) {
            tmp[i ^ (a[x] >> 4)] = hight[high(dp[x][i], 8)][low(a[x], 4)] |
                                   lowt[low(dp[x][i], 8)][low(a[x], 4)];
        }
        for (int i = 0; i < (1 << 8); i++) {
            dp[x][i] = tmp[i];
        }
        for (auto v : G.edge[x]) {
            for (int i = 0; i < (1 << 8); i++) {
                dp[v][i] |= dp[x][i];
            }
        }
    }
    for (int i = 0; i < (1 << 10); i++) {
        if (dp[n][high(i, 4)] & (1 << (low(i, 4)))) {
            cout << i << endl;
            break;
        }
    }
}

T4 边

也许是唯一可做题

求最小生成树的过程里把相同边权的在不连通块的边全都加进去跑 tarjan，割边必然选，其他边随意

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 5;
enum Type { VOID, ANY, ALO, NONE };
const char *turn(Type typ) {
    switch (typ) {
    case ANY:
        return "any";
    case ALO:
        return "at least one";
    case NONE:
        return "none";
    default:
        return "none";
    }
}
Type ans[N];
struct Graph {
    struct Node {
        int u, v, w, id;
    };
    vector<Node> edge;
    void add(int u, int v, int w, int id) {
        edge.emplace_back(Node{u, v, w, id});
    }
} G;
namespace Tarjan {
struct Node {
    int v, id;
};
vector<Node> edge[N];
int dfn[N], low[N], dfn_id;
void add_two(int u, int v, int id) {
    edge[u].emplace_back(Node{v, id});
    edge[v].emplace_back(Node{u, id});
}
void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++dfn_id;
    for (auto e : edge[x]) {
        if (e.id == fa) {
            continue;
        }
        if (!dfn[e.v]) {
            tarjan(e.v, e.id);
            low[x] = min(low[x], low[e.v]);
            if (low[e.v] > dfn[x]) {
                ans[e.id] = ANY;
            }
        } else {
            low[x] = min(low[x], dfn[e.v]);
        }
    }
}
} // namespace Tarjan

int n, m;
namespace MST {
int fa[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void mst(Graph &G) {
    using Tarjan::add_two;
    using Tarjan::dfn;
    using Tarjan::dfn_id;
    using Tarjan::low;
    using Tarjan::tarjan;
    auto &edge = G.edge;
    sort(edge.begin(), edge.end(),
         [&](const Graph::Node &A, const Graph::Node &B) -> bool {
             return A.w < B.w;
         });
    typedef vector<Graph::Node>::iterator iter;
    iter r;
    for (iter l = edge.begin(); l != edge.end(); l = r) {
        r = l + 1;
        while (r != edge.end() && r->w == l->w) {
            r++;
        }
        for_each(l, r, [&](Graph::Node x) {
            int u = find(x.u), v = find(x.v);
            if (u == v) {
                return;
            }
            add_two(u, v, x.id);
            dfn[u] = dfn[v] = 0;
            ans[x.id]       = ALO;
        });
        for_each(l, r, [&](Graph::Node x) {
            int u = find(x.u), v = find(x.v);
            if (u == v) {
                return;
            }
            if (!dfn[u]) {
                dfn_id = 0;
                tarjan(u, -1);
            }
        });
        for_each(l, r, [&](Graph::Node x) {
            int u = find(x.u), v = find(x.v);
            if (u == v) {
                return;
            }
            Tarjan::edge[u].clear();
            Tarjan::edge[v].clear();
            fa[u] = v;
        });
    }
}
} // namespace MST
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        ans[i]     = NONE;
        MST::fa[i] = i;
        scanf("%d%d%d", &u, &v, &w);
        G.add(u, v, w, i);
    }
    MST::mst(G);
    for (int i = 1; i <= m; i++) {
        puts(turn(ans[i]));
    }
}
// Asusetic eru quionours.