#include<bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n, vector<int>(m));
        for (auto &i: a) {
            for (auto &j: i) cin >> j;
        }
        if (n * m == 1) cout << "-1\n";
        else {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    cout << a[(i + 1) % n][(j + 1) % m] << ' ';
                }
                cout << '\n';
            }
        }
    }
}

#include<bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < s.size() && s[i] == '0'; ++i) {
        if (t[i] != '0') {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        ll x;
        cin >> n >> x;
        vector<ll> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
        vector<int> dp(n + 2);
        for (int i = n - 1; i >= 0; --i) {
            int q = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();
            dp[i] = dp[q] + q - i - 1;
        }
        cout << accumulate(dp.begin(), dp.end(), 0ll) << '\n';
    }
}

Принцип Дирихле

#include<bits/stdc++.h>
using namespace std;

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto& i : a) cin >> i;
        vector<int> pos(n);
        iota(pos.begin(), pos.end(), 0);
        vector<pair<int, int>> ans;
        for (int i = n - 1; i; --i) {
            vector<int> occ(i, -1);
            for (auto j : pos) {
                if (occ[a[j] % i] != -1) {
                    ans.emplace_back(j, occ[a[j] % i]);
                    pos.erase(find(pos.begin(), pos.end(), j));
                    break;
                }
                occ[a[j] % i] = j;
            }
        }
        reverse(ans.begin(), ans.end());
        cout << "YES\n";
        for (auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n';
    }
}

Решите для одного дерева

Ответ — размер дерева

Пусть размеры удаленных поддеревьев — $$$a_1, a_2, \ldots a_m$$$. Мы знаем, что $$$a_1 + a_2 + \ldots + a_m = n$$$, тогда $$$a_1 | a_2 \ldots a_m \leq n$$$. Чтобы доказать это рассмотрим каждый бит отдельно. Он добавит $$$1$$$ к результату, если хотя бы один из них $$$1$$$, $$$0$$$ иначе, в любом случае это меньше суммы.

#include<bits/stdc++.h>
using namespace std;

void solve() {
    int k;
    cin >> k;
    vector<int> a(k);
    for (int i = 0; i < k; ++i) {
        cin >> a[i];
        for (int j = 0; j < a[i] - 1; ++j) {
            int trash;
            cin >> trash;
        }
    }
    sort(a.begin(), a.end(), greater<>());
    int ans = 0;
    for (auto x : a) {
        for (int h = 23; h >= 0; --h) {
            int ca = ans >> h & 1, cx = x >> h & 1;
            if (cx == 0) continue;
            if (ca == 0) ans |= 1 << h;
            else {
                ans |= (1 << h) - 1;
                break;
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

#include<bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> black(n);
        vector<int> edg(m);
        vector<vector<int>> g(n);
        for (int i = 0; i < m; ++i) {
            int x, y, c;
            cin >> x >> y >> c;
            --x, --y;
            edg[i] = x ^ y;
            g[x].push_back(i);
            g[y].push_back(i);
            if (c == 0) {
                black[x].push_back(i);
                black[y].push_back(i);
            }
        }
        vector<int> deg(n);
        for (int i = 0; i < n; ++i) deg[i] = g[i].size() & 1;
        vector<bool> del(m, false), used(n, false);
        auto dfs = [&](auto dfs, int u) -> void {
            used[u] = true;
            for (auto id : black[u]) {
                int to = edg[id] ^ u;
                if (used[to]) continue;
                dfs(dfs, to);
                if (deg[to]) {
                    del[id] = true;
                    deg[to] ^= 1;
                    deg[u] ^= 1;
                }
            }
        };
        bool ok = true;
        for (int i = 0; i < n; ++i) {
            if (used[i]) continue;
            dfs(dfs, i);
            ok &= !deg[i];
        }
        if (!ok) {
            cout << "NO\n";
            continue;
        }
        auto euler = [&](auto euler, int u) -> void {
            while (!g[u].empty()) {
                int id = g[u].back();
                g[u].pop_back();
                int to = edg[id] ^ u;
                if (del[id]) continue;
                del[id] = true;
                euler(euler, to);
            }
            cout << u + 1 << ' ';
        };
        cout << "YES\n";
        cout << m - accumulate(del.begin(), del.end(), 0) << '\n';
        euler(euler, 0);
        cout << '\n';
    }
}

Подумайте над самым глупым решением

Сделайте меморизацию и отсечения

Готово!

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<vector<bool>> memo;
string res;
vector<int> cnt;
string s;

bool rec(int i, int cur) {
    if (i == k) {
        if (cur == 0) {
            return true;
        }
        return false;
    }
    if (memo[i][cur]) return false;
    memo[i][cur] = true;
    for (int c = 0; c < 2; ++c) {
        int q = cur;
        if (c == 0) q += cnt[i];
        else q += n - cnt[i];
        if ((q & 1) == s[i] - '0') {
            if (rec(i + 1, q / 2)) {
                res += char(c + '0');
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        cin >> n >> k;
        cin >> s;
        reverse(s.begin(), s.end());
        cnt = vector<int>(k);
        for (int i = 0; i < n; ++i) {
            string t;
            cin >> t;
            reverse(t.begin(), t.end());
            for (int j = 0; j < k; ++j) cnt[j] += t[j] - '0';
        }
        memo = vector<vector<bool>>(k, vector<bool>(n, false));
        res = "";
        rec(0, 0);
        if (res.empty()) cout << "-1\n";
        else cout << res << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    cout << "? aa" << endl;
    int p, v[10];
    cin >> p; p--;
    cout << "? zzzzzzzzzz" << endl;
    int hsh, hsho;
    ll nom = 0, cnt = 1;
    cin >> hsh;
    hsho = hsh;
    hsh++;
    for (int i = 0; i < 10; i++) {
        nom += 26 * cnt;
        cnt *= p;
        v[i] = 26 - (hsh % p);
        hsh /= p;
    }
    string s;
    cnt = 1;
    ll ch = 0;
    for (int i = 0; i < 10; i++) {
        if (v[i] < 1) {
            v[i] = 26;
            v[i + 1]--;
        }
        ch += cnt * v[i];
        cnt *= p;
        s += 'a' + (v[i] - 1);
    }
    cout << "? " << s << endl;
    int ans;
    cin >> ans;
    cout << "! " << p << ' ' << ans + nom - ch - hsho << endl;
}

int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}