做着做着cf就坐下了

1344A Hilbert’s Hotel

题目里 $i+a_{i\bmod n}$ 给我整懵了，难道不应该是 $(i+a_i)\bmod n$🐎
所以按上述第二式处理结果，并转至$[0,n)$的范围内，查重即可，$O(n\log n)，也可O(n)$。

a.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            a[i] += i;
            if (a[i] < 0) a[i] = (a[i] % n) + n;
            a[i] %= n;
        }
        sort(a.begin(), a.end());
        a.resize(unique(a.begin(), a.end()) - a.begin());
        if (a.size() != n) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}

1344B Monopole Magnets

有一个网格，可以放任意数目的$N,S$，每次可以选择一对同一行/列的$N,S$，使$N$向$S$移动$1$。
要求使用最少的$N$，满足：

  • 每一行/列至少有一个$S$；
  • 每一个黑色格子都可以被访问到；
  • 每一个白色格子都不能被访问到。

首先可以想到如果合法的情况下，给每个黑格子都放入$S$，不会影响答案；那么就可以想到如果合法，最小的答案就是连通块的个数，$bfs$处理。
现在思考哪些情况不合法：

  • 如果对于某一列/行，在一个白块的两侧有黑色格子，那么这一列/行都不能含有$S$，违背条件$1$；
  • 如果某一行/列只有白色，那么至少有一列/行也是全白的，这样$S$可以放在交点处，才能满足条件$1$。

$O(nm)$

b.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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e3 + 5;

int n, m, cnt;
int to[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
char g[N][N];
bool l[N][N], r[N][N], u[N][N], d[N][N];

void bfs(int x, int y) {
    ++cnt;
    queue<pii> q;
    q.emplace(x, y);
    g[x][y] = '.';
    while (!q.empty()) {
        pii t = q.front();
        q.pop();
        for (auto i : to) {
            pii tt = t;
            tt.first += i[0];
            tt.second += i[1];
            if (tt.first < 1 || tt.first > n || tt.second < 1 || tt.second > m)
                continue;
            if (g[tt.first][tt.second] != '#')
                continue;
            g[tt.first][tt.second] = '.';
            q.emplace(tt);
        }
    }
}

bool check() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            l[i][j] = l[i][j - 1];
            if (g[i][j - 1] == '#')
                l[i][j] = true;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= 0; --j) {
            r[i][j] = r[i][j + 1];
            if (g[i][j + 1] == '#')
                r[i][j] = true;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            u[i][j] = u[i - 1][j];
            if (g[i - 1][j] == '#')
                u[i][j] = true;
        }
    }
    for (int i = n; i >= 0; --i) {
        for (int j = 1; j <= m; ++j) {
            d[i][j] = d[i + 1][j];
            if (g[i + 1][j] == '#')
                d[i][j] = true;
        }
    }
    bool row = false, col = false;
    for (int i = 1; i <= n; ++i) {
        if (!r[i][0])
            row = true;
    }
    for (int i = 1; i <= m; ++i) {
        if (!d[0][i])
            col = true;
    }
    if (row ^ col) {
//        cout << "empty difference WRONG" << endl;
        return true;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (g[i][j] == '.' && ((u[i][j] && d[i][j]) || (l[i][j] && r[i][j]))) {
//                cout << "black wight blacck WRONG" << endl;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> (g[i] + 1);
    }
    if (check()) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (g[i][j] == '#')
                bfs(i, j);
        }
    }
    cout << cnt << endl;
    return 0;
}

1344C Quantifier Question

$a[l] \& a[l+1] \& \dots \& a[r] = x$
对于 $f(x_1,x_2…x_n)=(x_{i_1} < x_{j_1}) \& (x_{i_2} < x_{j_2}) \& \dots \& (x_{i_m} < x_{j_m})$，每个$x$变量的量词出现顺序是 $Q_1Q_2…Q_n$，要求全称量词 $\forall$ 最多，使得 $Q_1x_1Q_2x_2\dots Q_nx_nf(x_1,x_2\dots x_n)$ 为真。

首先可以想到与有向图有关，如果图中有环，那么必然不成立，大小关系无法成环，通过拓扑排序判定。
然后在纸上画画又可以发现，只有从小向大放的时候，才有可能出现 $\forall$，因此选择贪心，而且对于图中的一条路，最多只能有一个点是 $\forall$ 的；
如果一个点已经被前面的点已经限制为 $\exists$，那么枚举到它时，会将通过自己的路上的其他点全限制为 $\exists$。
$O(n)$

c.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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int n, m;
bool typo(const vector<vi> &g, vi &ind) {
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!ind[i])
            q.emplace(i);
    }
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ++cnt;
        for (int v : g[u]) {
            --ind[v];
            if (!ind[v])
                q.emplace(v);
        }
    }
    return cnt == n;
}

void bfs(const vector<vi> &g, vi &vis, int s) {
    queue<int> q;
    q.emplace(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int v : g[u])
            q.emplace(v);
    }
}

int main() {
    cin >> n >> m;
    vector<vi> g(n + 1), rg(n + 1);
    vi ind(n + 1);
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        g[u].emplace_back(v);
        rg[v].emplace_back(u);
        ++ind[v];
    }
    if (!typo(g, ind)) {
        cout << -1 << endl;
        return 0;
    }
    int cnt = 0;
    string ans;
    vi vis(n + 1), rvis(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (vis[i] || rvis[i])
            ans += "E";
        else {
            ++cnt;
            ans += "A";
        }
        bfs(g, vis, i);
        bfs(rg, rvis, i);
    }
    cout << cnt << endl << ans << endl;
    return 0;
}