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

Codeforces Round 968 (Div. 2)

时间：2024-08-26 12:36:49浏览次数：8  
标签：int 968 Codeforces long read while Div define getchar

良心出题人给了中文题解！！！

A. Turtle and Good Strings

长度为 \(n\) 的字符串至少分成两段，使 \(\forall i < j\) ，第 \(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;
}

string s;

int main()
{
    int T = read();
    while(T--)
    {
        int len = read();
        cin >> s;
        if(s[0] == s[len - 1]) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

B. Turtle and Piggy Are Playing a Game 2

假设最终答案为 \(val\) ， \(\text{Turtle}\) 只需要把小于 \(val\) 的值删除，\(\text{Piggy}\) 只需要把大于 \(val\) 的值删除

等价于对于一个序列，第一步删除最小值，第二步删除最大值，重复操作直至只剩一个数，答案即为第 \(\lfloor \frac{n}{2} \rfloor + 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 = 1e5 + 5;
int a[N];

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

C. Turtle and Good Pairs

考场上手动模拟 \((i, j)\) 不做贡献的条件，胡乱推导后得出结论：尽可能使相邻字符不相同

于是用 \(set\) 维护出现次数最多的字符以及它的个数，每次取出次数最多的字符填在第 \(i\) 个位置，并将次数-1

为了使相邻字符不同，先不将第 \(i\) 个字符放回集合（除非下一步没得取了，被迫相邻字符相同），先取出现次数次大的字符

有种摩尔投票统计绝对众数的感觉，当不存在绝对众数时不会出现相邻字符相同的情况

然而猜结论是不行的，需要严谨的数学证明：

image

题解中最小化 $\sum_{i=1}^{m-1} a_i \times a_{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 = 2e5 + 5;
int cnt[N];
multiset< pair<int, int> > S;
multiset< pair<int, int> > SS;
string s;
int main()
{
    int T = read();
    while(T--)
    {
        int len = read();
        cin >> s;
        for(int i = 0; i <= 25; ++i) cnt[i] = 0;
        for(int i = 0; i < len; ++i) cnt[s[i] - 'a']++;
        S.clear(), SS.clear();
        for(int i = 0; i <= 25; ++i)
            if(cnt[i]) S.emplace(pair<int, int>(cnt[i], i));
        for(int i = 1; i <= len; ++i)
        {
            pair<int, int> now = *prev(S.end());
            S.erase(now);
            now.first --;
            printf("%c", (char)(now.second + 'a'));
            if(!SS.empty())
            {
                S.emplace(*SS.begin());
                SS.clear();
            }
            if(S.empty()) S.emplace(now);
            else if(now.first ) SS.emplace(now);
        }
        printf("\n");
    }
    return 0;
}

D1. Turtle and a MEX Problem (Easy Version)

观察到可以使用 \(2\) 次操作同一个序列得到这个序列的第二 \(\text{mex}\) 值

记第 \(i\) 个序列的 \(\text{mex}\) 为 \(u_i\) ，第二 \(\text{mex}\) 为 \(v_i\)

则 \(\forall x\)

\[f(x) = \max\{\max_{1\le i \le n} v_i, x\} \]

点击查看代码 
#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 = 2e5 + 5;
vector<int> a[N];
int mex[N], mmex[N];
int cnt[N];

void solve(int id)
{
    int len = a[id].size();
    for(int i = 0; i <= len + 1; ++i) cnt[i] = 0;
    for(int i = 0; i < len; ++i)
    {
        int x = a[id][i];
        if(x <= len) cnt[x]++;
    }
    mex[id] = 0;
    for(int i = 0; i <= len + 1; ++i)
    {
        if(cnt[i] == 0)
        {
            mex[id] = i;
            break;
        }
    }
    mmex[id] = 0;
    for(int i = mex[id] + 1; i <= len + 1; ++i)
    {
        if(cnt[i] == 0)
        {
            mmex[id] = i;
            break;
        }
    }
}

ll add(int l, int r)
{
    if(l > r) return 0;
    return 1ll * (l + r) * (r - l + 1) / 2;
}

int main()
{
    int T = read();
    while(T--)
    {
        int n = read(), m = read();
        for(int i = 1; i <= n; ++i)
        {
            a[i].clear();
            int len = read();
            while(len--)
            {
                int x = read();
                a[i].emplace_back(x);
            }
            solve(i);
        }
        sort(mmex + 1, mmex + n + 1);
        ll ans = 0, mx = mmex[n];
        ans = mx * min((mx + 1), 1ll * (m + 1)) + add(mx + 1, m);
        printf("%lld\n", ans);
    }   
    return 0;
}

D2. Turtle and a MEX Problem (Hard Version)

增加了限制：同一个序列 \(i\) 至多操作 \(1\)次

考虑有向图：由 \(u_i\) 向 \(v_i\) 连边

一次操作相当于将 \(x\) 变为 \(u_i\) ，并断开 \(u_i\) 的一条出边

当 \(u_i\) 有超过 \(1\) 条出边时，断开哪条边都可以，也就是哪条边都可以走

设 \(dp[x]\) 表示当前位于点 \(i\) ，每次选择一条出边能够到达的点编号的最大值

在有向图上倒序 \(dp\)

如何统计答案？

\(\forall x\) 都可以取到 \(\max u_i\)

\(\forall x\) 都可以取到 \(dp[x]\)

当 \(i\) 的出边个数大于 \(1\) 时，\(\forall x\) 都可以取到 \(dp[i]\)

记 \(k = \max v_i\) ，小于等于 \(k\) 的枚举，大于 \(k\) 的 \(x\) ，\(f(x) = x\) 最优

总结

  • 情况复杂时先将所有想到的情况列举下来
点击查看代码 
#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 = 2e5 + 5;
vector<int> a[N];
int mex[N], mmex[N]; // mmex最大不超过len + 1
int cnt[N];

int dp[N], in[N], out[N];
vector<int> e[N];
queue<int> q;

void solve(int id)
{
    int len = a[id].size();
    for(int i = 0; i <= len + 1; ++i) cnt[i] = 0;
    for(int i = 0; i < len; ++i)
    {
        int x = a[id][i];
        if(x <= len) cnt[x]++;
    }
    mex[id] = 0;
    for(int i = 0; i <= len + 1; ++i)
    {
        if(cnt[i] == 0)
        {
            mex[id] = i;
            break;
        }
    }
    mmex[id] = 0;
    for(int i = mex[id] + 1; i <= len + 1; ++i)
    {
        if(cnt[i] == 0)
        {
            mmex[id] = i;
            break;
        }
    }
}

ll add(ll l, ll r)
{
    if(l > r) return 0;
    return (l + r) * (r - l + 1) / 2;
}

int main()
{
    int T = read();
    while(T--)
    {
        int n = read(), m = read(), mxlen = 0;
        for(int i = 1; i <= n; ++i)
        {
            a[i].clear();
            int len = read();
            mxlen = max(mxlen, len);
            while(len--)
            {
                int x = read();
                a[i].emplace_back(x);
            }
            solve(i);
        }

        mxlen++;
        for(int i = 0; i <= mxlen; ++i)
        {
            dp[i] = 0, in[i] = 0, out[i] = 0;
            e[i].clear();
        }
        while(!q.empty()) q.pop();
        
        for(int i = 1; i <= n; ++i) e[mmex[i]].push_back(mex[i]), ++in[mex[i]], ++out[mex[i]];

        for(int i = 0; i <= mxlen; ++i)
            if(in[i] == 0) q.emplace(i);
        
        while(!q.empty())
        {
            int id = q.front();
            q.pop();
            dp[id] = max(dp[id], id);
            for(int v : e[id])
            {
                dp[v] = max(dp[v], dp[id]);
                --in[v];
                if(in[v] == 0) q.emplace(v);
            }
        }
        int mx = 0;
        ll ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            mx = max(mx, mex[i]);
            if(out[mex[i]] >= 2) mx = max(mx, dp[mex[i]]);
        }

        ans = add(mx + 1, m);
        for(int i = 0; i <= min(mx, m); ++i) ans += max(mx, dp[i]);
        printf("%lld\n", ans);
    }
    return 0;
}

E1. Turtle and Inversions (Easy Version)

使所有区间的前缀 \(\max\) 的 \(\max\) 小于所有区间的后缀 \(\min\) 的 \(\min\)

将序列的数分为两种，小数和大数，小数为 \(0\) ，大数为 \(1\) ，将排列转化为 \(01\) 序列

一个排列是有趣排列的充要条件为，它的某个 \(01\) 序列为有趣序列，即对于任意一个区间 \([l, r]\) 所有的 \(0\) 在 \(1\) 前面，且 \(0\) 和 \(1\) 至少都有一个

对于一个有趣序列（ \(0\) 和 \(1\) 的位置已经固定），为了使逆序对数最多，可以贪心地将大数 \(1\) 从大到小排列，小数 \(0\) 从大到小排列

一种做法呼之欲出：枚举 \(1\) 的个数，然后将大数小数都从大到小排列，统计逆序对，\(O(n^2)\)

题解给了一种 \(O(n^2)\) 的 \(DP\) ：

image

考虑 \(O(n)\) 做法：

我们将必须填 \(0\) 的位置称为固定 \(0\) ，必须填 \(1\) 的位置成为固定 \(1\) ，其他位置称为自由点

设 \(c_i\) 表示位置 \(i\) 之前有几个固定 \(1\) ，设 \(C_i\) 表示位置 \(i\) 之前有几个自由点

假设目前枚举大数 \(1\) 的个数为 \(k\) 个，其中 \(k - m\) 个为自由 \(1\) ，将它们全部放在最靠前的自由点上最优

当 \(i\) 为固定 \(0\) 时，能和它产生逆序对的 \(1\) 的个数为 \(c_i + \min\{C_i, k - m\}\)

当 \(i\) 为固定 \(1\) 时，能和它产生逆序对的 \(1\) 的个数为 \(c_i + \min\{C_i, k - m\}\)

当 \(i\) 为自由点时，不论值为 \(0\) 或者 \(1\) ，能和它产生逆序对的 \(1\) 的个数为 \(c_i + \min\{C_i, k - m\}\)

此时还缺少所有的 \(0\) 相互之间的贡献，即为 \(\frac{(n-k)(n-k-1)}{2}\)

观察 \(c_i + \min\{C_i, k - m\}\) ，\(c_i\) 不随 \(k\) 变化为定值，单独记录 \(tmp = \sum c_i\)

\(\min\{C_i, k - m\}\) 随 \(k\) 单调不降，将 \(C_i\) 排序后，考虑位置 \(pos\) ，对于 \(i \le pos\) ， \(C_i < k - m\) ，取 \(\sum C_i\) ，对于 \(i > pos\) ， \(C_i \ge k - m\) 取 \((k - m) \times (n - pos)\)

对于任意 \(k\) 可以 \(O(1)\) 解决

总结

  • 将排列大小关系转化为 \(01\) 序列
点击查看代码 
#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 = 5e3 + 5;
int l[N], r[N], c[N], C[N];
int a[N], b[N];

void solve()
{
    int n = read(), m = read();
    for(int i = 1; i <= n; ++i) c[i] = -1, C[i] = 0;
    for(int i = 1; i <= m; ++i)
    {
        l[i] = read(), r[i] = read();
        c[l[i]] = 0, c[r[i]] = 1;
    }
    int L = m, R = n - m;
    ll tmp = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(c[i] == -1) C[i] = 1, c[i] = 0;
        a[i] = C[i - 1], tmp += c[i - 1];
        C[i] += C[i - 1], c[i] += c[i - 1]; // 第i个数前面有多少空位，有多少个必选的1
    }

    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) b[i] = b[i - 1] + a[i];
    ll ans = 0, now = 0;
    int pos = 0;
    for(int t = L; t <= R; ++t) // t个1
    {
        now = 1ll * (n - t) * (n - t - 1) / 2;
        while(pos < n && a[pos + 1] <= t - m) ++pos;
        ans = max(ans, now + b[pos] + 1ll * (n - pos) * (t - m));
    }
    printf("%lld\n", ans + tmp);
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

E2. Turtle and Inversions (Hard Version)

增加了限制：区间可以相交

考虑两个区间 \([l_i, r_i] , [l_{i + 1}, r_{i + 1}], l_i < l_{i + 1} < r_i\)

对于 \([l_i, l_{i+1}]\) 一定都为 \(0\) ，对于 \([r_i, r_{i+1}]\) 或 \([r_{i+1}, r_i]\) 一定都为 \(1\)

剩余区间为 \([l_{i+1}, min(r_i, r_{i+1})]\) ，即完成了一次区间合并

若干次区间合并后改为区间不交，解法同 \(E1\)

点击查看代码 
#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 = 5e3 + 5;
int c[N], C[N];
int a[N], b[N];
pair<int, int> jian[N];

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if(a.first == b.first ) return a.second > b.second ;
    return a.first < b.first ;
}

void solve()
{
    int n = read(), m = read(), flag = 0;
    for(int i = 1; i <= n; ++i) c[i] = -1, C[i] = 0;
    for(int i = 1; i <= m; ++i)
    {
        jian[i].first = read(), jian[i].second = read();
        if(!flag && c[jian[i].first ] == 1) flag = 1;
        if(!flag && c[jian[i].second ] == 0) flag = 1;
        c[jian[i].first ] = 0, c[jian[i].second ] = 1;
    }
    sort(jian + 1, jian + m + 1, cmp);
    m = unique(jian + 1, jian + m + 1) - (jian + 1);
    for(int i = 2; i <= m; ++i)
    {
        if(jian[i].first > jian[i - 1].second ) continue;
        for(int j = jian[i - 1].first + 1; j < jian[i].first ; ++j)
        {
            if(c[j] == 1) flag = 1;
            else c[j] = 0;
        }
        for(int j = min(jian[i - 1].second , jian[i].second ) + 1; j < max(jian[i - 1].second , jian[i].second ); ++j)
        {
            if(c[j] == 0) flag = 1;
            else c[j] = 1;
        }
        jian[i].second = jian[i - 1].second ;
    }
    if(flag){ printf("-1\n"); return ; }
    int L = 0, R = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(c[i] == 1) ++L;
        if(c[i] == 0) ++R; 
    }
    R = n - R;
    ll tmp = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(c[i] == -1) C[i] = 1, c[i] = 0;
        a[i] = C[i - 1], tmp += c[i - 1];
        C[i] += C[i - 1], c[i] += c[i - 1]; // 第i个数前面有多少空位，有多少个必选的1
    }

    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) b[i] = b[i - 1] + a[i];
    ll ans = 0, now = 0;
    int pos = 0;
    for(int t = L; t <= R; ++t) // t个1
    {
        now = 1ll * (n - t) * (n - t - 1) / 2;
        while(pos < n && a[pos + 1] <= t - L) ++pos;
        ans = max(ans, now + b[pos] + 1ll * (n - pos) * (t - L));
    }
    printf("%lld\n", ans + tmp);
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

F 先咕着，涉及知识盲区了

标签：int,968,Codeforces,long,read,while,Div,define,getchar
From： https://www.cnblogs.com/wenqizhi/p/18380806

相关文章

  • EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)
    Preface两个礼拜前打的比赛拖到现在才写博客，我只能说也是个神人了这场其实D2很快就想到做法了，但自己把自己给否了，后面不管了实现了一发交上去发现过了然后这天由于12点左右室友就关灯睡觉了，我写完D2后看了眼E没仔细想就睡觉去了，后面发现E其实很trivialA.Distance......
  • Codeforces Round #900 (Div. 3)
    三年之后第一次打比赛，用小号打了场\(Div.3\)，居然没有AK，感觉实力退步到小学了。A.HowMuchDoesDaytonaCost?若只判断题，只要判断\(\{a_n\}\)中是否存在\(k\)即可。B.AleksaandStack构造方法不唯一，我直接输出奇数列，显然正确。C.VasilijeinCacak若只判断题......
  • Codeforces Round 967 (Div. 2) - C
    题意概述这是一个交互题。有一棵有\(n\)个节点的树，节点编号从\(1\)到\(n\)，并要求你使用以下类型的查询来猜测它："?ab"会告诉你哪个节点\(x\)在点\(a\)和\(b\)之间（\(|d(a,x)-d(b,x)|\)的值最小），其中\(d(x,y)\)是节点\(x\)和\(y\)之间的距离。如果存在不......
  • CodeForces - 1353D Constructing the Array
    CodeForces-1353D这道题也可能比较简单，主要是要想到优先队列要怎么使用，这一点如果用递归会写不了但是因为对优先队列不太熟悉，只有被提示可以用优先队列才想到要怎么用，还是很重要的STL注意运算符的重构应该反着来写其他的思维很朴素，运算符的重构就是，先比较长度，优先用长度长......
  • CodeForces-431C k-Tree
    感觉这个题的dp还是有点思维的，可能就是我现在能做到的题目的天花板级别的了，dp还是要点灵感感觉，以下是代码，可能要写题解要过好久，先水着include<bits/stdc++.h>defineintlonglongdefineendl'\n'usingnamespacestd;constintmod=1000000007;intn,k,d;intdp[200][2]=......
  • CodeForces - 1336A Linova and Kingdom
    CodeForces-1336A就差一点点，很可惜，少发现个很显而易见的结论就是一个点的价值，实际上就是（这个点的深度-之后的点的数目）就是\(depth_i-size_i\)然后只要用dfs维护就好了然后把一个点的价值用STL优先队列放在一起，贪心完成。但是可能也算不上什么贪心，因为是很朴素的东西......
  • Codeforces Round 967 (Div. 2)
    A.MakeAllEqual签到题，先确定最终答案，然后把其他数删去，转化为统计众数点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglongintread(){intx=0;boolf=false;charc=getchar();while(c<......
  • 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})\)的爆标做法。首先无解当且仅当图联通且无割边。首先考虑加边的贡献。一个比较直观的感受就是只会尽可能少的加边，即加边到整个图连通。证明考虑删掉的边。如果加多了边导致删......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99