首页 > 其他分享 >Codeforces Round 967 (Div. 2)

Codeforces Round 967 (Div. 2)

时间：2024-08-23 22:37:49浏览次数：11  
标签：begin 967 int Codeforces long read while Div mx

A. Make All Equal

签到题，先确定最终答案，然后把其他数删去，转化为统计众数

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 105;
int a[N], cnt[N];

int main()
{
    int T = read();
    while(T--)
    {   
        int n = read(), ans = 0x3f3f3f3f;
        for(int i = 1; i <= n; ++i)
        {
            a[i] = read();
            ++cnt[a[i]];
        }
        for(int i = 1; i <= n; ++i) ans = min(ans, n - cnt[i]);
        for(int i = 1; i <= n; ++i) --cnt[a[i]];
        printf("%d\n", ans);
    }
    return 0;
}

B. Generate Permutation

神奇构造题，通过手动枚举 \(n = 1,2,3,4\) 大胆猜测奇数有解偶数无解，并按照如下构造

\[1,3,5,\cdots n - 2,n,n-1,\cdots,4,2 \]

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 105;
int a[N], cnt[N];

int main()
{
    int T = read();
    while(T--)
    {   
        int n = read();
        if(n % 2 == 1)
        {
            int pos = (n + 1) / 2, now = n - 1;
            for(int i = 1; i <= pos; ++i) printf("%d ", 2 * i - 1);
            for(int i = pos + 1; i <= n; ++i, now -= 2) printf("%d ", now);
            printf("\n");
        }else printf("-1\n");
    }
    return 0;
}

C. Guess The Tree

第一次场切交互题！

观察到最多 \(15n\) 次询问，考虑一个 \(\log\) 的做法，二分！

依照 \(\text{prim}\) 算法，最初令 \(1\) 为树根，并逐步将其他点连接到树上

定义函数 \(get(l, r)\) 表示将 \(l, r\) 相连，并记录其中的边

考虑询问 \((l, r)\) 的结果 \(x\)：

若 \(x = l\) ，说明 \(l, r\) 直接相连，将 \(r\) 加入树并向答案中加入边 \((l, r)\)

若 \(x \neq l\) ，说明 \(l\) 到 \(r\) 的路径上还有其他点 \(x\) ，若 \(x\) 未加入树，递归相连 \(l, x\) ；若 \(r\) 未加入树，递归相连 \(x, r\)

连接一条边的均摊复杂度为 \(\log n\)

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 1005;
int vis[N], cnt = 0;
vector< pair<int, int> > ans;

void get(int l, int r)
{
    printf("? %d %d\n", l, r);
    fflush(stdout);
    int mid = read();
    if(mid == l)
    {
        vis[l] = vis[r] = 1;
        ans.push_back(pair<int, int>(l, r));
        return ;
    }
    if(!(vis[l] && vis[mid])) get(l, mid);
    if(!(vis[r] && vis[mid])) get(mid, r);
}

int main()
{
    int T = read();
    while(T--)
    {   
        int n = read();
        cnt = 0;
        for(int i = 0; i <= n; ++i) vis[i] = 0;
        ans.clear();
        get(1, n);
        for(int i = 2; i < n; ++i) if(!vis[i]) get(1, i);
        printf("! ");
        for(auto it = ans.begin(); it != ans.end(); ++it)
            printf("%d %d ", (*it).first , (*it).second );
        printf("\n");
        fflush(stdout);
    }
    return 0;
}

D. Longest Max Min Subsequence

首先想到最多的个数就是数字的种类数，再考虑如何最小化字典序

大胆猜测这是一个贪心，一个位置 \(i\) （值为 \(val\)）能够被选择要满足两个要求：

  1. 在此之前没有选择过值为 \(val\) 的位置

  2. 选择位置 \(i\) 不会减少答案

记 \(last[i]\) 表示数值 \(i\) 在序列中最后出现的位置

每次在当前能选择的位置中选择能最小化字典序的位置，若值相同优先选位置小的

思路简单，实现却是另一回事

赛时用 \(set\) 维护 \(last\) 数组，然后就是求一个区间内的 \(\min/\max\) ，直接莽线段树

以及，因为一些值只出现了一次，我给它单独处理了！实际上按照 \(last\) 维护它不影响正确性

赛后改出来的依托答辩 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int inf = 0x3f3f3f3f;
const int N = 3e5 + 5;
int n, a[N], cnt[N], last[N];
vector<int> pos[N];
set<int> S;
set<int> Q;

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

struct node1
{
    int mx, pos;
    node1(){ mx = pos = 0; }
    node1 friend operator + (node1 a, node1 b)
    {
        node1 c;
        if(a.mx >= b.mx )
        {
            c.mx = a.mx ;
            c.pos = a.pos;
        }else
        {
            c.mx = b.mx ;
            c.pos = b.pos;
        }
        return c;
    }
}mx[N << 2];

struct node2
{
    int mn, pos;
    node2(){ mn = pos = 0; }
    node2 friend operator + (node2 a, node2 b)
    {
        node2 c;
        if(a.mn <= b.mn )
        {
            c.mn = a.mn ;
            c.pos = a.pos;
        }else
        {
            c.mn = b.mn ;
            c.pos = b.pos;
        }
        return c;
    }
}mn[N << 2];

void pushup(int k)
{
    mx[k] = mx[ls(k)] + mx[rs(k)];
    mn[k] = mn[ls(k)] + mn[rs(k)];
}

void build(int k, int l, int r)
{
    if(l == r){ mx[k].mx = mn[k].mn = a[l], mx[k].pos = mn[k].pos = l; return ; }
    int mid = (l + r) >> 1;
    build(ls(k), l, mid), build(rs(k), mid + 1, r);
    pushup(k);
}

void update(int k, int l, int r, int pos)
{
    mx[k].mx = -inf, mn[k].mn = inf, mx[k].pos = mn[k].pos = 0;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(pos <= mid) update(ls(k), l, mid, pos);
    else update(rs(k), mid + 1, r, pos);
    pushup(k);
}

node1 querymax(int k, int l, int r, int L, int R)
{
    if(L <= l && r <= R) return mx[k];
    int mid = (l + r) >> 1;
    if(R <= mid) return querymax(ls(k), l, mid, L, R);
    if(L > mid) return querymax(rs(k), mid + 1, r, L, R);
    return querymax(ls(k), l, mid, L, R) + querymax(rs(k), mid + 1, r, L, R);
}

node2 querymin(int k, int l, int r, int L, int R)
{
    if(L <= l && r <= R) return mn[k];
    int mid = (l + r) >> 1;
    if(R <= mid) return querymin(ls(k), l, mid, L, R);
    if(L > mid) return querymin(rs(k), mid + 1, r, L, R);
    return querymin(ls(k), l, mid, L, R) + querymin(rs(k), mid + 1, r, L, R);
}

int ans[N];
int vis[N];

int P = 1, op = 1;


int main()
{
    int T = read();
    while(T--)
    {   
        n = read();

        for(int i = 0; i <= n; ++i)
        {
            cnt[i] = last[i] = 0, pos[i].clear();
            vis[i] = 0;
        }
        S.clear(), Q.clear();
        P = 1, op = 1;

        for(int i = 1; i <= n; ++i)
        {
            a[i] = read();
            ++cnt[a[i]];
            pos[a[i]].push_back(i);
            if(cnt[a[i]] >= 2) last[a[i]] = i;
        }

        build(1, 1, n);

        int m = 0, tot = 0;

        for(int i = 1; i <= n; ++i) 
            if(last[i]) S.insert(last[i]);

        for(int i = 1; i <= n; ++i)
        {
            if(cnt[i] > 0) ++m; // 值域
            if(cnt[a[i]] == 1)
            {
                Q.insert(i); // 下标
                update(1, 1, n, i);
            }
        }
        Q.insert(n + 1);
        while(P <= n && tot < m)
        {
            if(cnt[a[P]] == 1)
            {
                ans[++tot] = a[P];
                Q.erase(P);
                ++P;
                op ^= 1;
                continue;
            }
            if(vis[P]){ ++P; continue; }
            int nx = min(*Q.begin() - 1, *S.begin());
            // printf("P = %d, nx = %d, S.begin = %d\n", P, nx, *S.begin());
            if(op == 1)
            {
                node1 now = querymax(1, 1, n, P, nx);
                if(*Q.begin() <= n && *Q.begin() < *S.begin() && a[*Q.begin()] > now.mx )
                {
                    ans[++tot] = a[*Q.begin()];
                    P = (*Q.begin()) + 1;
                    Q.erase(Q.begin());
                }else
                {
                    ans[++tot] = now.mx ;
                    P = now.pos + 1;
                    S.erase(last[now.mx ]);
                    for(auto it = pos[now.mx ].begin(); it != pos[now.mx ].end(); ++it)
                    {
                        vis[*it] = 1;
                        update(1, 1, n, *it);
                    }
                }
                op ^= 1;
            }else
            {
                node2 now = querymin(1, 1, n, P, nx);
                if(*Q.begin() < *S.begin() && a[*Q.begin()] < now.mn )
                {
                    ans[++tot] = a[*Q.begin()];
                    P = (*Q.begin()) + 1;
                    Q.erase(Q.begin());
                }else
                {
                    ans[++tot] = now.mn ;
                    P = now.pos + 1;
                    S.erase(last[now.mn ]);
                    for(auto it = pos[now.mn ].begin(); it != pos[now.mn ].end(); ++it)
                    {
                        vis[*it] = 1;
                        update(1, 1, n, *it);
                    }
                }
                op ^= 1;
            }
        }
        printf("%d\n", m);
        for(int i = 1; i <= tot; ++i) printf("%d ", ans[i]);
        printf("\n");
    }
    return 0;
}

研读题解，发现要维护的区间 \(\min/\max\) 的取点是一段区间，如果用 \(set\) 维护这个区间的 \(\min/\max\) ，并在全局用 \(vis\) 数组记录延迟删除，由于区间的左右端点都是递增的，每个数只会进出 \(set\) 一次，复杂度是 \(O(n \log n)\) ，完美薄纱我的线段树

仿照题解的2.0版本 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int inf = 0x3f3f3f3f;
const int N = 3e5 + 5;
int n, a[N];
int last[N], vis[N];
set<int> la;
set< pair<int, int> > mx, mn;
vector<int> ans;
int main()
{
    int T = read();
    while(T--)
    {
        n = read();
        for(int i = 1; i <= n; ++i) last[i] = inf, vis[i] = 0;
        la.clear(), mx.clear(), mn.clear(), ans.clear();

        for(int i = 1; i <= n; ++i) a[i] = read(), last[a[i]] = i;
        for(int i = 1; i <= n; ++i) la.insert(last[i]);
        for(int i = 1; i <= *la.begin(); ++i)
        {
            mx.emplace(pair<int, int>(-a[i], i));
            mn.emplace(pair<int, int>(a[i], i));
        }
        int pos = 0;
        while(!mx.empty() || !mn.empty())
        {
            pair<int, int> now;
            if(ans.size() & 1)
            {
                now = *mn.begin();
                ans.emplace_back(now.first );
                vis[now.first ] = 1;
            }else
            {
                now = *mx.begin();
                ans.emplace_back(-now.first );
                vis[-now.first ] = 1;
            }
            pos = now.second + 1;
            // 剔除不合法的方案，包括已经选过的数，在pos之前的数
            while(*la.begin() != inf && vis[a[*la.begin()]])
            {
                int p = *la.begin();
                la.erase(la.begin());
                for(int i = p + 1; i <= min(*la.begin(), n); ++i)
                {
                    mx.emplace(pair<int, int>(-a[i], i));
                    mn.emplace(pair<int, int>(a[i], i));
                }
            }
            while(!mx.empty() && (vis[-(*mx.begin()).first ] || (*mx.begin()).second < pos)) mx.erase(mx.begin());
            while(!mn.empty() && (vis[(*mn.begin()).first ] || (*mn.begin()).second < pos)) mn.erase(mn.begin());
        }
        printf("%d\n", ans.size());
        for(int it : ans) printf("%d ", it);
        printf("\n");
    }
    return 0;
}

总结

  • 延迟删除操作搭配 \(set\)

  • \(emplace\) 是 \(insert\) ，\(emplace\_back\) 是 \(push\_back\)

  • 优先观察要维护的信息的单调性以及优先使用 \(STL\)

E1. Deterministic Heap (Easy Version)

没看懂题，画个图理解一下，注意题中要求为满二叉树

image

一个确定性二叉树就是每次取较大值的儿子时选择是唯一的，即不存在某次操作中两个儿子的值相等的情况

如果手动模拟的话，发现这是一种递归操作，记录子树的一些必要信息来转化为从低向上的递推操作

设 \(dp[i][j]\) 表示层数为 \(i\) 的二叉树，根节点值为 \(j\) 的确定性二叉树的个数（根节点的值即为这颗子树进行的加操作）

发现可以只在根节点操作，即两儿子的值的和 \(\le j\)

先求两儿子的值的和恰好为 \(j\) 的个数，再通过前缀和处理得到两儿子的值的和 \(\le j\) 的个数

记 \(C[x][i]\) 表示在层数为 \(i\) 的二叉树中，根节点值为 \(x\) 的个数。这是任意的二叉树，不必满足确定性

即在 \(2^i - 1\) 个节点中加操作 \(x\) 次，隔板法得

\[C[x][i] = \binom{x + 2^i - 2}{2^i - 2} = \binom{x + 2^i - 2}{x} \]

\(x\) 次乘法预处理 \(C[x][i]\)

转移时枚举左子树根的值 \(k\) ，右子树值为 \(j - k\) ，易得转移：

\[dp[i][j] = \sum_{k = 0 \& k \neq j - k}^{j} dp[i - 1][\max\{k, j - k\}] \times C[\min\{k, j - k\}][i - 1] \]

发现枚举 \(\max\{k, j - k\}\) 可以得到更优雅的公式：

\[dp[i][j] = \sum_{k = \lfloor \frac{j}{2}\rfloor + 1 }^{j} 2 \times dp[i - 1][k] \times C[j - k][i - 1] \]

不要忘记前缀和处理 \(dp[i][j]\) ！

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 505;
int n, K;
ll mod;
ll jc[N], inv[N];
ll C[N][N];
ll qpow(ll a, ll b, ll mod)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

void init()
{
    jc[1] = jc[0] = inv[1] = inv[0] = 1;
    for(int i = 2; i <= 500; ++i) jc[i] = jc[i - 1] * i % mod;
    inv[500] = qpow(jc[500], mod - 2, mod);
    for(int i = 499; i >= 2; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}

void getC(int x, int i)
{
    ll ans = inv[x], tmp = (qpow(2, i - 1, mod) - 2 + mod) % mod;
    for(int i = 1; i <= x; ++i) ans = ans * (tmp + i) % mod;
    C[x][i] = ans;
}

ll dp[N][N], pd[N][N];

void add(ll &a, ll b){ a = (a + b >= mod) ? (a + b - mod) : (a + b); }

int main()
{
    int T = read();
    while(T--)
    {
        n = read(), K = read(), mod = read();
        init();
        for(int x = 0; x <= K; ++x)
            for(int i = 2; i <= n; ++i)
                getC(x, i);

        for(int j = 0; j <= K; ++j) dp[1][j] = 1;
        for(int i = 2; i <= n; ++i)
        {
            for(int j = 1; j <= K; ++j)
            {
                dp[i][j] = pd[i][j] = 0;
                for(int k = 0; k <= j; ++k)
                {
                    if(k == j - k) continue;
                    add(pd[i][j], dp[i - 1][max(k, j - k)] * C[min(k, j - k)][i] % mod);
                }
                add(pd[i][j], pd[i][j - 1]);
                add(dp[i][j], pd[i][j]);
            }
        }
        printf("%lld\n", dp[n][K]);
    }

    return 0;
}

E2. Deterministic Heap (Hard Version)

本题不保证正确性！

目前该题解只存在于理论（代码还没通过）

本题的限制在于，不止第一个要求确定性，第二步也要求确定性，而第一步会改变树的结构！

考虑如下情况：\(j > p, k > q\)

image

第二步则需要比较 \(k\) 与 \(p\) 的大小，用到了 \(i\) 的孙子信息，考虑给 \(dp\) 加一维记录儿子信息

设 \(dp1[i][j][k]\) 表示层数为 \(i\) ，根节点值为 \(j\) ，较大儿子的值为 \(k\) 的双步确定二叉树个数

仍然是先求两儿子值恰好为 \(j\) 时的个数，再前缀和处理

转移时枚举大儿子的大儿子的值 \(l\)

若 \(l > j - k\) 则相当于第二步仍选大儿子，另一棵树随意

\[dp1[i][j][k] = \sum_{l = j - k + 1}^{k} 2 \times dp1[i - 1][k][l] \times C[j - k][i - 1] \]

若 \(\lfloor \frac{k}{2} \rfloor + 1 \le l < j - k\) ，需要限制大孙子的值

设 \(dp0[i][j][k]\) 表示层数为 \(i\) ，根节点值为 \(k\) ，大儿子的值为 \(k\) 的单步确定二叉树个数

\[dp1[i][j][k] = \sum_{l = \lfloor \frac{k}{2} \rfloor + 1}^{j - k - 1} 2\times dp0[i - 1][k][l] \times dp[i - 1][j - k] \]

对于 \(dp0\) ，仍然先求两儿子值恰好为 \(j\) 的个数

\[dp0[i][j][k] = dp[i - 1][k] \times C[j - k][i - 1] \]

尚未通过的代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 505;
ll n, K, mod;
ll jc[N], inv[N];

ll qpow(ll a, ll b, ll mod)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

void init()
{
    jc[0] = jc[1] = inv[0] = inv[1] = 1;
    for(int i = 2; i <= 500; ++i) jc[i] = jc[i - 1] * i % mod;
    inv[500] = qpow(jc[500], mod - 2, mod);
    for(int i = 499; i >= 2; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}

ll C[N][N]; // C(x, i)
void getC(int x, int i)
{
    ll ans = inv[x], tmp = (qpow(2, i, mod) - 2 + mod) % mod;
    for(int j = 1; j <= x; ++j) ans = ans * (tmp + j) % mod;
    C[x][i] = ans;
}

ll dp[105][N];
ll dp0[105][N][N], dp1[105][N][N];

ll add(ll a, ll b){ return (a + b >= mod) ? (a + b - mod) : (a + b); }

int main()
{
    int T = read();
    while(T--)
    {
        n = read(), K = read(), mod = read();

        init();
        for(int x = 0; x <= K; ++x)
            for(int i = 1; i <= n; ++i)
                getC(x, i);

        for(int i = 0; i <= n; ++i)
            for(int j = 0; j <= K; ++j)
                for(int k = 0; k <= K; ++k)
                {
                    dp[i][j] = 0;
                    dp0[i][j][k] = dp1[i][j][k] = 0;
                }

        for(int i = 0; i <= K; ++i) dp[1][i] = 1;

        for(int j = 1; j <= K; ++j)
            for(int k = 1; k <= j; ++k)
                dp0[2][j][k] = dp1[2][j][k] = 2 * min(k, j - k + 1);

        for(int j = 1; j <= K; ++j)
            for(int k = 1; k <= j; ++k)
            {
                dp0[2][j][k] = add(dp0[2][j][k], dp0[2][j][k - 1]);
                dp1[2][j][k] = add(dp1[2][j][k], dp1[2][j][k - 1]);
            }
        
        for(int i = 2; i <= n; ++i)
            for(int j = 1; j <= K; ++j)
            {

                // 更新 dp, pd
                for(int k = (j >> 1) + 1; k <= j; ++k)
                    dp[i][j] = add(dp[i][j], 2ll * dp[i - 1][k] * C[j - k][i - 1] % mod);
                
                dp[i][j] = add(dp[i][j], dp[i][j - 1]);
            }
        
        for(int i = 3; i <= n; ++i)
        {
            for(int j = 1; j <= K; ++j)
            {
                // 更新 dp0
                for(int k = (j >> 1) + 1; k <= j; ++k)
                    dp0[i][j][k] = add(dp0[i][j][k], 2ll * dp[i - 1][k] * C[j - k][i - 1] % mod);
 
                for(int k = 0; k <= j; ++k)
                    dp0[i][j][k] = add(dp0[i][j][k], dp0[i][j - 1][k]);

                for(int k = (j >> 1) + 1; k <= j; ++k)
                {
                    int l = (k >> 1) + 1, r = k;
                    r = min(r, j - k - 1);
                    if(l <= r) dp1[i][j][k] = add(dp1[i][j][k], 2ll * (dp0[i - 1][k][r] - dp0[i - 1][k][l - 1] + mod) % mod * dp[i - 1][j - k] % mod);
                    l = j - k + 1, r = k;
                    if(l <= r) dp1[i][j][k] = add(dp1[i][j][k], 2ll * (dp1[i - 1][k][r] - dp1[i - 1][k][l - 1] + mod) % mod * C[j - k][i - 1] % mod);
                }
                for(int k = 0; k <= j; ++k) dp1[i][j][k] = add(dp1[i][j][k], dp1[i][j - 1][k]);
            }
            for(int j = 1; j <= K; ++j)
                for(int k = 1; k <= j; ++k)
                {
                    dp0[i][j][k] = add(dp0[i][j][k], dp0[i][j][k - 1]);
                    dp1[i][j][k] = add(dp1[i][j][k], dp1[i][j][k - 1]);
                }
        }
        // printf("%lld ", dp[n][K]);
        ll ans = dp1[n][K][K];
        printf("%lld\n", ans);
    }
    return 0;
}

/*

6
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037

2
12
40
100
32
224

1
100 500 100000037

66681128

2
87 63 100000037
13 437 100000039

83566569
54517140

*/

标签：begin,967,int,Codeforces,long,read,while,Div,mx
From： https://www.cnblogs.com/wenqizhi/p/18377196

相关文章

  • Codeforces Round 967(Div.2)之赛后总结
    CodeforcesRound967(Div.2)传送锚点A.MakeAllEqual1.题面分析废话这么多，说白了就是求总数减去最多出现数的个数的值。2.解法直接用桶装一下，然后扫一遍维护最大值。3.code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e6+520;......
  • Codeforces Round 967 (Div. 2) ABCD
    来源：CodeforcesRound967(Div.2)做题时间：2024_08_21A.MakeAllEqual使所有元素相等的最小操作次数，就是保留最大的数字所以操作次数就是总数减去数量最多得数B.GeneratePermutation题意构造一个序列\(p\)，内部元素是\([1,2,\cdots,n]\)打乱使长度为\(n\)的初始......
  • Solution - Codeforces 1970G3 Min-Fund Prison (Hard)
    时间\(\mathcal{O}(\frac{n\sqrt{n}\logn}{\omega})\)空间\(\mathcal{O}(\frac{n\logn}{w})\)的爆标做法。首先无解当且仅当图联通且无割边。首先考虑加边的贡献。一个比较直观的感受就是只会尽可能少的加边，即加边到整个图连通。证明考虑删掉的边。如果加多了边导致删......
  • Codeforces Round 967 (Div. 2)-D
    CodeforcesRound967(Div.2)-D这些天在留校集训……我之前空余时间在看模电，最近在玩黑猴……九月开学了估计也不能闲下来……但这个博客我还是会抽空更新的╰(°▽°)╯Problem-D-Codeforces虽然代码写得特别丑陋，但好歹是我完全想的思路——自己还de了一天bug（゜ー゜）......
  • Codeforces Round 967 (Div. 2)
    题不难。A.MakeAllEqual题意：一个圆，上面有\(n\)个数，每次可以删去相邻的两个不同数中任意一个，求至少几次使得剩下的数都一样。显然下界是出现次数最多的数且一定能取到，时间复杂度\(O(n)\)。提交记录B.GeneratePermutation题意：要求构造一个排列，使得\(x\)所在位置大......
  • CF 2001 E2 solution (967 Div.2)
    CF2001E2由于对称，所以设\(heap[u]\)为两次确定堆，且第一次弹出的是\(u\)，\(heap[u,v]\)是第一次\(u\)，第二次\(v\)则答案就是\(\sumheap[u]=2^{n-1}·heap[x]\)其中\(x\)任意。不妨我们考虑第一次都是从第一个叶子弹出，那么对于其他不同的第二个弹出的点，根据对称性......
  • 题解：Codeforces Round 967 (Div. 2) B [思维/构造]
    B.GeneratePermutationtimelimitpertest:1.5secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputThereisanintegersequence\(a\)oflength\(n\),whereeachelementisinitially\(-1\).Misukihastwoty......
  • Divisiblity of Difference
    题目传送门思路首先得知道个性质，即若$a\bmodb=c\bmodb$，那么$(a-c)\bmodb=0$，因为余数在$(a-c)$中被减掉了。于是我们可以把所有余数相同的$a_i$丢进一个vector里，之后再看余数相同的$a_i$的数量有没有$\gek$，有的话就输出前$k$个数，没有就输出No。代码#i......
  • Codeforces Round 966 (Div. 3)
    A.PrimaryTask#include<bits/stdc++.h>usingnamespacestd;usingvi=vector<int>;voidsolve(){strings;cin>>s;if(s.size()<=2){cout<<"NO\n";return;}if(s[0]!......
  • 题解：Codeforces Round 967 (Div. 2) [暴力/贪心]
    A.MakeAllEqualtimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenacyclicarray\(a_1,a_2,\ldots,a_n\).Youcanperformthefollowingoperationon\(a\)atmost\(n-......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99