比赛链接

A

题解

知识点：KMP，构造。

考虑构造全 $0,1$ 串，至少有一个可行。

我们只需要考虑到 $t$ 的border $t'$ ，即 $t'+s+t'$ ：

1. 当 $t'+s+t'$ 总长小于等于 $t$ ，显然成立。
2. 否则， 若 $t'+s+t'$ 中有子串等于 $t$ ，那么这个子串不会完整包含前后两端的 $t'$ ，这时border就会相交，产生连锁反应，可以证得 $t$ 是全 $0,1$ 串，此时显然成立。
3. 若没有子串等于 $t$ ，则直接可行。

因此，我们只需要构造两次检查一下即可，检查方式有KMP、Z函数、哈希等等。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; class KMP {    int m;    string p;    vector<int> nxt; public:    KMP() {}    KMP(const string &_p) { init(_p); }     void init(const string &_p) {        m = _p.size() - 1;        p = _p;        nxt.assign(m + 1, 0);        for (int i = 2;i <= m;i++) {            nxt[i] = nxt[i - 1];            while (nxt[i] && p[i] != p[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];            nxt[i] += p[i] == p[nxt[i] + 1];        }    }     vector<int> find(const string &s) {        int n = s.size() - 1;        vector<int> pos;        for (int i = 1, j = 0;i <= n;i++) {            while (j && s[i] != p[j + 1]) j = nxt[j];            j += s[i] == p[j + 1];            if (j == m) {                pos.push_back(i - j + 1);                j = nxt[j];            }        }        return pos;    }     vector<int> get_cycle_time() {        vector<int> res;        int pos = m;        while (pos) {            pos = nxt[pos];            res.push_back(m - pos);        }        return res;    }     vector<int> get_cycle_loop() {        vector<int> res;        for (auto val : get_cycle_time())            if (!(m % val)) res.push_back(val);        return res;    }    int min_cycle_loop() { return get_cycle_loop()[0]; }     void debug() {        for (int i = 1;i <= m;i++)            cout << nxt[i] << " \n"[i == m];    }};/// KMP，前缀函数O(|P|)、查找O(|S|+|P|)、循环相关O(|P|)，维护字符串前缀函数 bool solve() {    int n;    cin >> n;    string t;    cin >> t;    KMP kmp("?" + t);    if (kmp.find("?" + t + string(n, '0') + t).size() <= 2) cout << string(n, '0') << '\n';    else cout << string(n, '1') << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; class KMP {    int m;    string p;    vector<int> nxt; public:    KMP() {}    KMP(const string &_p) { init(_p); }     void init(const string &_p) {        m = _p.size() - 1;        p = _p;        nxt.assign(m + 1, 0);        for (int i = 2;i <= m;i++) {            nxt[i] = nxt[i - 1];            while (nxt[i] && p[i] != p[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];            nxt[i] += p[i] == p[nxt[i] + 1];        }    }     vector<int> find(const string &s) {        int n = s.size() - 1;        vector<int> pos;        for (int i = 1, j = 0;i <= n;i++) {            while (j && s[i] != p[j + 1]) j = nxt[j];            j += s[i] == p[j + 1];            if (j == m) {                pos.push_back(i - j + 1);                j = nxt[j];            }        }        return pos;    }     vector<int> get_cycle_time() {        vector<int> res;        int pos = m;        while (pos) {            pos = nxt[pos];            res.push_back(m - pos);        }        return res;    }     vector<int> get_cycle_loop() {        vector<int> res;        for (auto val : get_cycle_time())            if (!(m % val)) res.push_back(val);        return res;    }    int min_cycle_loop() { return get_cycle_loop()[0]; }     void debug() {        for (int i = 1;i <= m;i++)            cout << nxt[i] << " \n"[i == m];    }};/// KMP，前缀函数O(|P|)、查找O(|S|+|P|)、循环相关O(|P|)，维护字符串前缀函数 bool solve() {    int n;    cin >> n;    string t;    cin >> t;    KMP kmp("?" + t);    if (kmp.find("?" + t + string(n, '0') + t).size() <= 2) cout << string(n, '0') << '\n';    else cout << string(n, '1') << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; class KMP {    int m;    string p;    vector<int> nxt; public:    KMP() {}    KMP(const string &_p) { init(_p); }     void init(const string &_p) {        m = _p.size() - 1;        p = _p;        nxt.assign(m + 1, 0);        for (int i = 2;i <= m;i++) {            nxt[i] = nxt[i - 1];            while (nxt[i] && p[i] != p[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];            nxt[i] += p[i] == p[nxt[i] + 1];        }    }     vector<int> find(const string &s) {        int n = s.size() - 1;        vector<int> pos;        for (int i = 1, j = 0;i <= n;i++) {            while (j && s[i] != p[j + 1]) j = nxt[j];            j += s[i] == p[j + 1];            if (j == m) {                pos.push_back(i - j + 1);                j = nxt[j];            }        }        return pos;    }     vector<int> get_cycle_time() {        vector<int> res;        int pos = m;        while (pos) {            pos = nxt[pos];            res.push_back(m - pos);        }        return res;    }     vector<int> get_cycle_loop() {        vector<int> res;        for (auto val : get_cycle_time())            if (!(m % val)) res.push_back(val);        return res;    }    int min_cycle_loop() { return get_cycle_loop()[0]; }     void debug() {        for (int i = 1;i <= m;i++)            cout << nxt[i] << " \n"[i == m];    }};/// KMP，前缀函数O(|P|)、查找O(|S|+|P|)、循环相关O(|P|)，维护字符串前缀函数 bool solve() {    int n;    cin >> n;    string t;    cin >> t;    KMP kmp("?" + t);    if (kmp.find("?" + t + string(n, '0') + t).size() <= 2) cout << string(n, '0') << '\n';    else cout << string(n, '1') << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

F

题解

知识点：二分，贪心。

显然每次只有最小值和最大值会被票出。

具体来说，我们统计最大值和最小值中点左右两侧的人数，左侧一定给最大值票，右侧一定给最小值票。当左大于等于右时，最大值会被票出，否则最小值会被票出。

因此，我们排序后，用二分找到中点的位置，用双指针表示当前剩余区间。

时间复杂度 $O(n\log n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    vector<pair<int, int>> a(n + 1);    for (int i = 1;i <= n;i++) {        int x;        cin >> x;        a[i] = { x,i };    }    sort(a.begin() + 1, a.end());     int l = 1, r = n;    for (int i = 1;i <= n - 1;i++) {        int mid = a[l].first + a[r].first >> 1;        int it = upper_bound(a.begin() + l, a.begin() + r + 1, pair<int, int>{ mid, 2e9 }) - a.begin();        int lval = it - l;        int rval = r - it + 1;        if (lval >= rval) r--;        else l++;    }    cout << a[l].second << '\n';    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    vector<pair<int, int>> a(n + 1);    for (int i = 1;i <= n;i++) {        int x;        cin >> x;        a[i] = { x,i };    }    sort(a.begin() + 1, a.end());     int l = 1, r = n;    for (int i = 1;i <= n - 1;i++) {        int mid = a[l].first + a[r].first >> 1;        int it = upper_bound(a.begin() + l, a.begin() + r + 1, pair<int, int>{ mid, 2e9 }) - a.begin();        int lval = it - l;        int rval = r - it + 1;        if (lval >= rval) r--;        else l++;    }    cout << a[l].second << '\n';    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    vector<pair<int, int>> a(n + 1);    for (int i = 1;i <= n;i++) {        int x;        cin >> x;        a[i] = { x,i };    }    sort(a.begin() + 1, a.end());     int l = 1, r = n;    for (int i = 1;i <= n - 1;i++) {        int mid = a[l].first + a[r].first >> 1;        int it = upper_bound(a.begin() + l, a.begin() + r + 1, pair<int, int>{ mid, 2e9 }) - a.begin();        int lval = it - l;        int rval = r - it + 1;        if (lval >= rval) r--;        else l++;    }    cout << a[l].second << '\n';    return 0;}

H

题解

知识点：构造。

尝试在正方形对角线上选择一点，将正方形分为左上正方形，右下正方形和两个对称的长方形。

然后，按照类似gcd的方式，对长方形进行划分正方形。

可以统计得到一定存在一点，使得长方形划分后的正方形数量不超过 $24$ ，即总和不超过 $50$ 。

因此，我们递归执行两种操作即可。

时间复杂度 $O(n^2)$

空间复杂度 $O(n^2)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int gcd(int a, int b, int &cnt) {    if (b) {        cnt += a / b;        return gcd(b, a % b, cnt);    }    else return a;} vector<tuple<int, int, int>> ans; void dfs_rec(int x, int y, int a, int b);void dfs_sqr(int x, int y, int a); void dfs_rec(int x, int y, int a, int b) {    bool sw = a < b;    if (sw) swap(x, y), swap(a, b);    if (!b) return;    for (int i = b;i <= a;i += b) {        if (sw) dfs_sqr(y, x + i - b, b);        else dfs_sqr(x + i - b, y, b);    }    if (sw) dfs_rec(y, x + a / b * b, b, a % b);    else dfs_rec(x + a / b * b, y, a % b, b);} void dfs_sqr(int x, int y, int a) {    if (a == 1) return;    if (a <= 7) {        ans.push_back({ x,y,a });        return;    }    bool ok = 0;    for (int i = 1;i <= a - 1;i++) {        int cnt = 0;        gcd(i, a - i, cnt);        if (cnt >= 25) continue;        ok = 1;        dfs_sqr(x, y, i);        dfs_rec(x + i, y, a - i, i);        dfs_rec(x, y + i, i, a - i);        dfs_sqr(x + i, y + i, a - i);        break;    }    assert(ok);    ans.push_back({ x,y,a });} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    dfs_sqr(1, 1, n);    cout << ans.size() << '\n';    for (auto [x, y, a] : ans) cout << x << ' ' << y << ' ' << a << '\n';    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; int gcd(int a, int b, int &cnt) {    if (b) {        cnt += a / b;        return gcd(b, a % b, cnt);    }    else return a;} vector<tuple<int, int, int>> ans; void dfs_rec(int x, int y, int a, int b);void dfs_sqr(int x, int y, int a); void dfs_rec(int x, int y, int a, int b) {    bool sw = a < b;    if (sw) swap(x, y), swap(a, b);    if (!b) return;    for (int i = b;i <= a;i += b) {        if (sw) dfs_sqr(y, x + i - b, b);        else dfs_sqr(x + i - b, y, b);    }    if (sw) dfs_rec(y, x + a / b * b, b, a % b);    else dfs_rec(x + a / b * b, y, a % b, b);} void dfs_sqr(int x, int y, int a) {    if (a == 1) return;    if (a <= 7) {        ans.push_back({ x,y,a });        return;    }    bool ok = 0;    for (int i = 1;i <= a - 1;i++) {        int cnt = 0;        gcd(i, a - i, cnt);        if (cnt >= 25) continue;        ok = 1;        dfs_sqr(x, y, i);        dfs_rec(x + i, y, a - i, i);        dfs_rec(x, y + i, i, a - i);        dfs_sqr(x + i, y + i, a - i);        break;    }    assert(ok);    ans.push_back({ x,y,a });} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    dfs_sqr(1, 1, n);    cout << ans.size() << '\n';    for (auto [x, y, a] : ans) cout << x << ' ' << y << ' ' << a << '\n';    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; int gcd(int a, int b, int &cnt) {    if (b) {        cnt += a / b;        return gcd(b, a % b, cnt);    }    else return a;} vector<tuple<int, int, int>> ans; void dfs_rec(int x, int y, int a, int b);void dfs_sqr(int x, int y, int a); void dfs_rec(int x, int y, int a, int b) {    bool sw = a < b;    if (sw) swap(x, y), swap(a, b);    if (!b) return;    for (int i = b;i <= a;i += b) {        if (sw) dfs_sqr(y, x + i - b, b);        else dfs_sqr(x + i - b, y, b);    }    if (sw) dfs_rec(y, x + a / b * b, b, a % b);    else dfs_rec(x + a / b * b, y, a % b, b);} void dfs_sqr(int x, int y, int a) {    if (a == 1) return;    if (a <= 7) {        ans.push_back({ x,y,a });        return;    }    bool ok = 0;    for (int i = 1;i <= a - 1;i++) {        int cnt = 0;        gcd(i, a - i, cnt);        if (cnt >= 25) continue;        ok = 1;        dfs_sqr(x, y, i);        dfs_rec(x + i, y, a - i, i);        dfs_rec(x, y + i, i, a - i);        dfs_sqr(x + i, y + i, a - i);        break;    }    assert(ok);    ans.push_back({ x,y,a });} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    dfs_sqr(1, 1, n);    cout << ans.size() << '\n';    for (auto [x, y, a] : ans) cout << x << ' ' << y << ' ' << a << '\n';    return 0;}

J

题解

知识点：线性dp，前缀和。

考虑设 $f_{i,j}$ 为考虑了前 $i$ 个数的后缀（不可为空）最小值为 $j$ 时的方案数。显然， $j \in [-m,m]$ 中。

在 $f_{i-1,j}$ 时，$[-j,m]$ 的数字可以被使用，进一步分类讨论转移方程：

1. 当 $j\geq 0$ 时，后缀最小值更新为 $a_i$ 本身：

   fi−1,j→fi,[−j,m]$$f_{i-1,j}\to f_{i,[-j,m]}$$

   $$f_{i-1,j} \to f_{i,[-j,m]}$$

2. 当 $j < 0$ 时，后缀最小值更新为 $a_i + j$ ：

   fi−1,j→fi,[0,m+j]$$f_{i-1,j}\to f_{i,[0,m+j]}$$

   $$f_{i-1,j} \to f_{i,[0,m+j]}$$

用前缀和优化转移即可。

时间复杂度 $O(nm)$

空间复杂度 $O(m)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; const int P = 998244353;int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m;    cin >> n >> m;    vector<int> f(2 * m + 1);    f[2 * m] = 1;    for (int i = 0;i < n;i++) {        vector<int> g(2 * m + 1);        for (int j = -m;j <= m;j++) {            if (j >= 0) (g[-j + m] += f[j + m]) %= P;            else {                (g[0 + m] += f[j + m]) %= P;                (g[j + m + m + 1] -= f[j + m] - P) %= P;            }        }        for (int j = -m + 1;j <= m;j++) (g[j + m] += g[j - 1 + m]) %= P;        swap(f, g);    }    int ans = 0;    for (int i = -m;i <= m;i++) (ans += f[i + m]) %= P;    cout << ans << '\n';    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; const int P = 998244353;int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m;    cin >> n >> m;    vector<int> f(2 * m + 1);    f[2 * m] = 1;    for (int i = 0;i < n;i++) {        vector<int> g(2 * m + 1);        for (int j = -m;j <= m;j++) {            if (j >= 0) (g[-j + m] += f[j + m]) %= P;            else {                (g[0 + m] += f[j + m]) %= P;                (g[j + m + m + 1] -= f[j + m] - P) %= P;            }        }        for (int j = -m + 1;j <= m;j++) (g[j + m] += g[j - 1 + m]) %= P;        swap(f, g);    }    int ans = 0;    for (int i = -m;i <= m;i++) (ans += f[i + m]) %= P;    cout << ans << '\n';    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; const int P = 998244353;int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m;    cin >> n >> m;    vector<int> f(2 * m + 1);    f[2 * m] = 1;    for (int i = 0;i < n;i++) {        vector<int> g(2 * m + 1);        for (int j = -m;j <= m;j++) {            if (j >= 0) (g[-j + m] += f[j + m]) %= P;            else {                (g[0 + m] += f[j + m]) %= P;                (g[j + m + m + 1] -= f[j + m] - P) %= P;            }        }        for (int j = -m + 1;j <= m;j++) (g[j + m] += g[j - 1 + m]) %= P;        swap(f, g);    }    int ans = 0;    for (int i = -m;i <= m;i++) (ans += f[i + m]) %= P;    cout << ans << '\n';    return 0;}

L

题解

知识点：离线，枚举。

考虑离线后倒着操作，并统计行的个数。

显然每行每列只关心最后一次操作的类型，之后的操作不需要考虑。

记录列开、列关的列数分别为 $cnt_{on},cnt_{off}$ 。若行操作为打开，答案增加 $m - cnt_{off}$ ，否则增加 $cnt_{on}$ 。

最后统计没被操作的行，对于每行答案增加 $cnt_{on}$ 。

时间复杂度 $O(n+q)$

空间复杂度 $O(n+m+q)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; struct Query {    bool row;    int id;    bool on;}Q[1000007]; bool row_vis[1000007];bool col_vis[1000007];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m, q;    cin >> n >> m >> q;    for (int i = 1;i <= q;i++) {        string row;        int id;        string on;        cin >> row >> id >> on;        Q[i] = { row == "row",id,on == "on" };    }     ll ans = 0;    int cnt_on = 0, cnt_off = 0;    for (int i = q;i >= 1;i--) {        if (Q[i].row) {            if (row_vis[Q[i].id]) continue;            ans += Q[i].on ? m - cnt_off : cnt_on;            row_vis[Q[i].id] = 1;        }        else {            if (col_vis[Q[i].id]) continue;            if (Q[i].on) cnt_on++;            else cnt_off++;            col_vis[Q[i].id] = 1;        }    }    for (int i = 1;i <= n;i++) if (!row_vis[i]) ans += cnt_on;    cout << ans << '\n';    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; struct Query {    bool row;    int id;    bool on;}Q[1000007]; bool row_vis[1000007];bool col_vis[1000007];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m, q;    cin >> n >> m >> q;    for (int i = 1;i <= q;i++) {        string row;        int id;        string on;        cin >> row >> id >> on;        Q[i] = { row == "row",id,on == "on" };    }     ll ans = 0;    int cnt_on = 0, cnt_off = 0;    for (int i = q;i >= 1;i--) {        if (Q[i].row) {            if (row_vis[Q[i].id]) continue;            ans += Q[i].on ? m - cnt_off : cnt_on;            row_vis[Q[i].id] = 1;        }        else {            if (col_vis[Q[i].id]) continue;            if (Q[i].on) cnt_on++;            else cnt_off++;            col_vis[Q[i].id] = 1;        }    }    for (int i = 1;i <= n;i++) if (!row_vis[i]) ans += cnt_on;    cout << ans << '\n';    return 0;}
#include <bits/stdc++.h>using namespace std;using ll = long long; struct Query {    bool row;    int id;    bool on;}Q[1000007]; bool row_vis[1000007];bool col_vis[1000007];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m, q;    cin >> n >> m >> q;    for (int i = 1;i <= q;i++) {        string row;        int id;        string on;        cin >> row >> id >> on;        Q[i] = { row == "row",id,on == "on" };    }     ll ans = 0;    int cnt_on = 0, cnt_off = 0;    for (int i = q;i >= 1;i--) {        if (Q[i].row) {            if (row_vis[Q[i].id]) continue;            ans += Q[i].on ? m - cnt_off : cnt_on;            row_vis[Q[i].id] = 1;        }        else {            if (col_vis[Q[i].id]) continue;            if (Q[i].on) cnt_on++;            else cnt_off++;            col_vis[Q[i].id] = 1;        }    }    for (int i = 1;i <= n;i++) if (!row_vis[i]) ans += cnt_on;    cout << ans << '\n';    return 0;}