Codeforces Round #936 (Div. 2) Разбор
Разница между ru11 и ru12, 10,731 символ(ов) изменены
автор: [user:exhausted,2024-03-22], разработчик: [user:exhausted,2024-03-22]↵

[
tutorial:1946A]↵

автор: [user:max0000561,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵

[tutorial:1946B]↵

автор: [user:exhausted,2024-03-22], разработчик: [user:exhausted,2024-03-22]↵

[tutorial:1946C]↵

автор: [user:azureglow,2024-03-22], разработчик: [user:azureglow,2024-03-22]↵

[tutorial:1946D]↵

автор: [user:yunetive29,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵

[tutorial:1946E]↵

автор: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22], разработчик: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22]↵

[tutorial:1946F]
problem:1946A]↵

<spoiler summary="Разбор">↵
[tutorial:1946A]↵
</spoiler>↵


<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵

using i64 = long long;↵

void solve() {↵
    int n;↵
    std::cin >> n;↵
    std::vector<int> a(n);↵
    for (int i = 0; i < n; i++) {↵
        std::cin >> a[i];↵
    }↵
    std::sort(a.begin(), a.end());↵
    int p = (n + 1) / 2 - 1;↵
    int res = std::count(a.begin() + p, a.end(), a[p]);↵
    std::cout << res << "\n";↵
}↵

signed main() {↵
    std::ios::sync_with_stdio(false);↵
    std::cin.tie(nullptr);↵

    int t = 1;↵
    std::cin >> t;↵

    while (t--) {↵
        solve();↵
    }↵
}↵
~~~~~↵
</spoiler>↵

автор: [user:max0000561,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵

[problem:1946B]↵

<spoiler summary="Разбор">↵
[tutorial:1946B]↵
</spoiler>↵


<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
const int P = 1e9 + 7;↵

void solve() {↵
    int n, k;↵
    cin >> n >> k;↵
    vector<int> a(n);↵
    for (int i = 0; i < n; i++)↵
        cin >> a[i];↵
    int S = 0, sum = 0;↵
    int cur = 0;↵
    for (int i = 0; i < n; i++) {↵
        sum += a[i];↵
        cur += a[i];↵
        cur = max(cur, 0LL);↵
        S = max(S, cur);↵
    }↵
    sum = (sum % P + P) % P;↵
    S = S % P;↵
    int t = 1;↵
    for (int i = 0; i < k; i++) {↵
        t = t * 2 % P;↵
    }↵
    int ans = (sum + S * t - S + P) % P;↵
    cout << ans << '\n';↵
}↵


signed main() {↵
    //cout << fixed << setprecision(20);↵
    ios::sync_with_stdio(false);↵
    cin.tie(nullptr);↵
    int T = 1, G = 1;↵
    //cin >> G;↵
    cin >> T;↵
    while (T--)↵
        solve();↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

автор: [user:exhausted,2024-03-22], разработчик: [user:exhausted,2024-03-22]↵

[problem:1946C]↵

<spoiler summary="Разбор">↵
[tutorial:1946C]↵
</spoiler>↵


<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
 ↵
using i64 = long long;↵
 ↵
void solve() {↵
    int n, k;↵
    std::cin >> n >> k;↵
    std::vector<std::vector<int>> adj(n);↵
    for (int i = 0; i < n - 1; i++) {↵
        int v, u;↵
        std::cin >> v >> u;↵
        --v, --u;↵
        adj[v].emplace_back(u);↵
        adj[u].emplace_back(v);↵
    }↵
    auto check = [&](int x) {↵
        int res = 0;↵
        auto dfs = [&](auto self, int v, int f) -> int {↵
            int sz = 1;↵
            for (int u : adj[v]) {↵
                if (u == f) {↵
                    continue;↵
                }↵
                sz += self(self, u, v);↵
            }↵
            if (sz >= x && f != v) {↵
                ++res, sz = 0;↵
            }↵
            return sz;↵
        };↵
        int t = dfs(dfs, 0, 0);↵
        return (res > k || (t >= x && res == k) ? true : false);↵
    };↵
    int low = 1, high = n / (k + 1) + 1;↵
    while (high - low > 1) {↵
        int mid = (low + high) / 2;↵
        if (check(mid)) {↵
            low = mid;↵
        } else {↵
            high = mid;↵
        }↵
    }↵
    std::cout << low << "\n";↵
}↵
 ↵
signed main() {↵
    std::ios::sync_with_stdio(false);↵
    std::cin.tie(nullptr);↵
 ↵
    int t = 1;↵
    std::cin >> t;↵
 ↵
    while (t--) {↵
        solve();↵
    }↵
}↵
~~~~~↵
</spoiler>↵

автор: [user:azureglow,2024-03-22], разработчик: [user:azureglow,2024-03-22]↵

[problem:1946D]↵

<spoiler summary="Разбор">↵
[tutorial:1946D]↵
</spoiler>↵


<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
using ll = long long;↵
 ↵
#define int ll↵
#define all(a) a.begin(), a.end()↵
 ↵
void solve() {↵
    int n, x;↵
    cin >> n >> x;↵
    ++x;↵
    vector<int> a(n);↵
    for (int &i: a)↵
        cin >> i;↵
    int res = -1;↵
    for (int i = 30; i >= 0; --i) {↵
        vector<int> b;↵
        bool open = false;↵
        for (int j = 0; j < a.size(); ++j) {↵
            if (!open)↵
                b.push_back(a[j]);↵
            else↵
                b.back() ^= a[j];↵
            if (a[j] & (1 << i))↵
                open = !open;↵
        }↵
        if (!(x & (1 << i))) {↵
            if (open) {↵
                cout << res << '\n';↵
                return;↵
            }↵
            a = b;↵
        } else {↵
            if (!open)↵
                res = max(res, (int) b.size());↵
        }↵
    }↵
    cout << res << '\n';↵
}↵
 ↵
signed main() {↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(nullptr);↵
    int t = 1;↵
    cin >> t;↵
    while (t--)↵
        solve();↵
}↵
~~~~~↵
</spoiler>↵


<spoiler summary="Решение (74TrAkToR)">↵
~~~~~↵
#include<bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
int const maxn = 1e5 + 5;↵
int a[maxn];↵
 ↵
int solve(int n, int x) {↵
    int res = 0, curr = 0;↵
    for (int i = 1; i <= n; i++) {↵
        curr ^= a[i];↵
        if ((curr|x) == x) curr = 0, res++;↵
        else {↵
            if (i == n) return -1;↵
        }↵
    }↵
    return res;↵
}↵
 ↵
main() {↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    int t;↵
    cin >> t;↵
    while (t--) {↵
        int n, x;↵
        cin >> n >> x;↵
        for (int i = 1; i <= n; i++) cin >> a[i];↵
        int ans = -1;↵
        ans = max(ans, solve(n, x));↵
        for (int b = 29; b >= 0; b--) {↵
            if ((x>>b)&1) {↵
                int y = (x^(1 << b));↵
                for (int c = b - 1; c >= 0; c--) {↵
                    if (((y>>c)&1) == 0) y ^= (1 << c);↵
                }↵
                ans = max(ans, solve(n, y));↵
            }↵
        }↵
        cout << ans << '\n';↵
    }↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

автор: [user:yunetive29,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵

[problem:1946E]↵

<spoiler summary="Разбор">↵
[tutorial:1946E]↵
</spoiler>↵


<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define eb emplace_back↵
#define int long long↵
const int N = 200200, P = 1e9 + 7;↵
int fact[N], reverse_fact[N];↵

int binpow(int x, int n) {↵
    if (n == 0)↵
        return 1;↵
    if (n == 1)↵
        return x;↵
    int t = binpow(x, n / 2);↵
    t = t * t % P;↵
    if (n % 2 == 1)↵
        t = t * x % P;↵
    return t;↵
}↵

int inv(int x) {↵
    return binpow(x, P - 2);↵
}↵

void precalc() {↵
    fact[0] = 1;↵
    for (int i = 1; i < N; i++)↵
        fact[i] = fact[i - 1] * i % P;↵
    for (int i = 0; i < N; i++)↵
        reverse_fact[i] = inv(fact[i]);↵
}↵

int C(int n, int k) {↵
    return fact[n] * reverse_fact[k] % P * reverse_fact[n - k] % P;↵
}↵

int f(int a, int b) {↵
    return C(a + b, b);↵
}↵

vector<vector<int>> g;↵
vector<int> dp, siz;↵

void dfs(int v) {↵
    int cnt = 0, x = -1, y = -1;↵
    for (auto to : g[v]) {↵
        dfs(to);↵
        siz[v] += siz[to];↵
        if (siz[to] == 1)↵
            cnt++;↵
        else if (x == -1)↵
            x = to;↵
        else↵
            y = to;↵
    }↵
    if (x == -1)↵
        dp[v] = fact[cnt];↵
    else if (y == -1)↵
        dp[v] = dp[x] * fact[cnt] % P * f(siz[x], cnt) % P;↵
    else↵
        dp[v] = dp[x] * dp[y] % P * f(siz[x], siz[y]) % P;↵
}↵


void solve() {↵
    int n, m1, m2;↵
    cin >> n >> m1 >> m2;↵
    vector<int> pref(m1), suf(m2);↵
    for (auto &it : pref)↵
        cin >> it;↵
    for (auto &it : suf)↵
        cin >> it;↵
    for (auto &it : pref)↵
        it--;↵
    for (auto &it : suf)↵
        it--;↵
    g.assign(n, {});↵
    dp.assign(n, 1);↵
    siz.assign(n, 1);↵
    if (pref.back() != suf.front() || pref.front() != 0 || suf.back() != n - 1) {↵
        cout << 0 << '\n';↵
        return;↵
    }↵
    for (int i = m1 - 1; i > 0; i--) {↵
        g[pref[i]].eb(pref[i - 1]);↵
        for (int j = pref[i] - 1; j > pref[i - 1]; j--)↵
            g[pref[i - 1]].eb(j);↵
    }↵
    for (int i = 0; i < m2 - 1; i++) {↵
        g[suf[i]].eb(suf[i + 1]);↵
        for (int j = suf[i] + 1; j < suf[i + 1]; j++)↵
            g[suf[i + 1]].eb(j);↵
    }↵
    dfs(pref.back());↵
    cout << dp[pref.back()] << '\n';↵
}↵


signed main() {↵
    //cout << fixed << setprecision(20);↵
    ios::sync_with_stdio(false);↵
    cin.tie(nullptr);↵
    int T = 1, G;↵
    //cin >> G;↵
    precalc();↵
    cin >> T;↵
    while (T--)↵
        solve();↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵


автор: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22], разработчик: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22]↵

[problem:1946F]↵

<spoiler summary="Разбор">↵
[tutorial:1946F]↵
</spoiler>↵


<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵

using i64 = long long;↵

template<class Info>↵
struct Fenwick {↵
    std::vector<Info> t;↵
    int n;↵
    ↵
    Fenwick(int n = 0) : n(n) {↵
        t.resize(n);↵
    }↵
    ↵
    void add(int x, const Info &v) {↵
        for (int i = x + 1; i <= n; i += i & -i) {↵
            t[i - 1] = t[i - 1] + v;↵
        }↵
    }↵
    ↵
    Info sum(int x) {↵
        x++;↵
        Info res = Info();↵
        for (int i = x; i > 0; i -= i & -i) {↵
            res = res + t[i - 1];↵
        }↵
        return res;↵
    }↵
    ↵
    Info rangeSum(int l, int r) {↵
        Info res = sum(r) - sum(l - 1);↵
        return res;↵
    }↵
};↵

void solve() {↵
    int n, q;↵
    std::cin >> n >> q;↵
    std::vector<int> a(n), pos(n + 1);↵
    for (int i = 0; i < n; i++) {↵
        std::cin >> a[i];↵
    }↵
    std::reverse(a.begin(), a.end());↵
    for (int i = 0; i < n; i++) {↵
        pos[a[i]] = i;↵
    }↵
    constexpr int K = 19;↵
    std::vector<i64> res(q);↵
    std::vector<std::vector<std::pair<int, int>>> qry(n);↵
    for (int i = 0; i < q; i++) {↵
        int l, r;↵
        std::cin >> l >> r;↵
        l--, r--;↵
        std::swap(l, r);↵
        l = n - l - 1;↵
        r = n - r - 1;↵
        qry[r].emplace_back(l, i);↵
    }↵
    std::vector<i64> dp(n + 1);↵
    Fenwick<i64> f(n);↵
    for (int r = 0; r < n; r++) {↵
        int x = a[r];↵
        dp[x] = 1;↵
        // n * log(n) * log(n)↵
        for (int y = x; y <= n; y += x) {↵
            if (pos[y] > pos[x]) {↵
                continue;↵
            }↵
            for (int z = 2 * y; z <= n; z += y) {↵
                if (pos[z] > pos[y]) {↵
                    continue;↵
                }↵
                dp[z] += dp[y];↵
            }↵
        }↵
        // n * log(n) * log(n)↵
        for (int y = x; y <= n; y += x) {↵
            f.add(pos[y], dp[y]);↵
            dp[y] = 0;↵
        }↵
        // q * log(n)↵
        for (auto [l, i] : qry[r]) {↵
            res[i] += f.rangeSum(l, r);↵
        }↵
    }↵
    for (int i = 0; i < q; i++) {↵
        std::cout << res[i] << " \n"[i == q - 1];↵
    }↵
}↵

signed main() {↵
    std::ios::sync_with_stdio(false);↵
    std::cin.tie(nullptr);↵

    int t = 1;↵
    std::cin >> t;↵

    while (t--) {↵
        solve();↵
    }↵
}↵
~~~~~↵
</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский exhausted 2024-03-22 22:55:06 12652
ru13 Русский exhausted 2024-03-22 22:52:10 6834
ru12 Русский azureglow 2024-03-22 21:58:39 10731 Мелкая правка: '03-22]\n\n[tutorial:' -> '03-22]\n\n/spoiler [tutorial:'
en2 Английский exhausted 2024-03-22 21:10:45 0 (published)
ru11 Русский exhausted 2024-03-22 21:10:24 0 (опубликовано)
en1 Английский exhausted 2024-03-22 21:08:43 696 Initial revision for English translation (saved to drafts)
ru10 Русский exhausted 2024-03-22 20:52:28 462
ru9 Русский exhausted 2024-03-22 20:50:40 44
ru8 Русский exhausted 2024-03-22 20:49:00 38
ru7 Русский exhausted 2024-03-22 20:48:18 127
ru6 Русский exhausted 2024-03-22 20:47:31 4 Мелкая правка: '4-03-22]\nРазработ' -> '4-03-22]\n\nРазработ'
ru5 Русский exhausted 2024-03-22 20:47:23 2
ru4 Русский exhausted 2024-03-22 20:47:11 2 Мелкая правка: '4-03-22]\nРазработ' -> '4-03-22]\n\nРазработ'
ru3 Русский exhausted 2024-03-22 20:46:57 2 Мелкая правка: '4-03-22]\n\nРазработ' -> '4-03-22]\nРазработ'
ru2 Русский exhausted 2024-03-22 20:46:48 2 Мелкая правка: '4-03-22]\nРазработ' -> '4-03-22]\n\nРазработ'
ru1 Русский exhausted 2024-03-22 20:46:36 150 Первая редакция (сохранено в черновиках)