Codeforces Round 968 (Div. 2)

admin2024-08-29  7

前言

        掉大分的一场比赛aaa

        原因是 D1 看错条件了一直在想 D2 最后还没想出来。

        Standings:6922

        题目链接:Dashboard - Codeforces Round 968 (Div. 2) - Codeforces

A. Turtle and Good Strings

        题意:

        给一个字符串,判断是否能把它分成 k(k >= 2) 个连续的段,使得每一段的起点和其他任意一段的终点不相等。

        思路:

        首先注意到首字母一定是第一段的开头,尾字母一定是最后一段的结尾,那么只要这两个字母不相等我们就有办法分割(直接 1 ~ n-1 作一段,n 单独作一段即可),反之无解。

#include<cstdio>
#include<cstring>
using namespace std;

int T,n;
char s[105];

int main()
{
    scanf("%d",&T);
    while (T --)
    {
        scanf("%d",&n);
        scanf("%s",s + 1);
        if(s[1] == s[n]) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

B. Turtle and Piggy Are Playing a Game 2

        题意:

        给一个序列,A 每次可以移除相邻两个数中较小的那个数,B 每次可以移除相邻两个数中较大的那个数,A 想要使最后剩下的那个数最大,B 想要使最后剩下的那个数最小,两个人都以最优方案操作,A 先开始,求最后剩下的那个数。

        思路:

        显然每次 A 会移除一个最小的数,B 会移除一个最大的数,于是把序列从小到大排序,最后剩下的数就是排名第 Codeforces Round 968 (Div. 2),\lfloor \frac{n}{2} \rfloor + 1,第1张 的数。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define N 100005

int T,n,a[N],ans;

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

C. Turtle and Good Pairs

        题意:

        给一个字符串。

        定义 “ pleasant pair ” (i,j) 为当前仅当存在一个 k (i <= k < j) 满足以下条件的数对:

        1. Codeforces Round 968 (Div. 2),s_k \neq s_{k + 1},第2张

        2. Codeforces Round 968 (Div. 2),s_k \neq s_i,第3张 or Codeforces Round 968 (Div. 2),s_{k + 1} \neq s_j,第4张

        定义 “ good pair ” (i,j) 为当且仅当 Codeforces Round 968 (Div. 2),s_i = s_j,第5张 或者 (i,j) 是 “ pleasant pair ” 的数对。

        你需要重排这个字符串,使得 “ good pair ” 的数目尽量多。

        思路:

        正难则反,我们可以发现 “not good pair” 会满足 “A...AB...B” 这种形式,其中 A 和 B 出现一次以上,且这个子串中只有 A,B 两种字母。

        手玩一下可以发现我们想要这些 “not good pair” 尽量少,就得把相同字母尽量都隔开,于是有一个贪心的构造方法:按相同字母出现次数从大到小排序,以黑白相间的方式轮流插入。

        注意输出的时候用 cout 貌似会比 printf 快很多。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 200005

int T,n;
char s[N];

struct Node
{
    int id,val;
}a[30];

int cmp(Node x,Node y) { return x.val > y.val ; }

int main()
{
    scanf("%d",&T);
    while (T --)
    {
        scanf("%d",&n);
        scanf("%s",s + 1);
        for (int i = 0;i < 26;++ i) a[i].id = i,a[i].val = 0;
        for (int i = 1;i <= n;++ i) ++ a[s[i] - 'a'].val;
        sort(a,a + 26,cmp);
        int now = a[0].id;
        int tmp = a[0].val;
        for (int i = 1;i < 26;++ i)
        {
            if(!a[i].val) break;
            if(now == a[i].id) continue;
            if(a[i].val < tmp)
            {
                for (int j = 1;j <= a[i].val;++ j)
                    cout << char('a' + now) << char('a' + a[i].id);
                tmp -= a[i].val;
            }
            else if(a[i].val == tmp)
            {
                for (int j = 1;j <= a[i].val;++ j)
                    cout << char('a' + now) << char('a' + a[i].id);
                if(i <= 24) tmp = a[i + 1].val,now = a[i + 1].id;
                else tmp = 0;
            }
            else
            {
                for (int j = 1;j <= tmp;++ j)
                    cout << char('a' + a[i].id) << char('a' + now);
                now = a[i].id,tmp = a[i].val - tmp;
            }
        }
        if(tmp)
        {
            for (int j = 1;j <= tmp;++ j) cout << char('a' + now);
        }
        cout << endl;
    }
    return 0;
}

D1. Turtle and a MEX Problem (Easy Version)

        题意:

        给若干个序列和一个数 m ,你可以通过这些数列对 m 做任意次操作,每次操作选择一个数列,将 m 插入这个数列得到一个新的数列 a ,然后让 m = MEX(a) 。设 f(i) 表示 m = i 的时候能通过操作得到的最大值(每个序列可以用无数次),求 Codeforces Round 968 (Div. 2),\sum_{i = 0} ^ m f(i),第6张 。

        思路:

        由于每个序列可以用无数次,那么显然某个数 x 要么不操作,要么就选定一个数列操作两次。我们统计每个数列的 mex1 和 mex2 ,分别记作 v1 和 v2 ,那么操作一次可能得到 v1 或者 v2,操作两次一定会得到 v2 ,操作三次以上都再也不能使得到的值更大了。

        记所有 v2 的 max 为 mx,那么对于比 mx 大的 x ,显然不需要进行操作;对于小于等于 mx 的 x ,显然能通过操作得到的最大值就是 mx 了。

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
using namespace std;

#define N 200005

int T,n,m,l[N],mx,p[N];
long long ans;

struct Node
{
    int v1,v2;
}a[N];

int max(int x,int y) { return x > y ? x : y ; }

int min(int x,int y) { return x < y ? x : y ; }

int main()
{
    scanf("%d",&T);
    while (T --)
    {
        scanf("%d%d",&n,&m),mx = 0;
        for (int i = 1;i <= n;++ i)
        {
            map<int, int> vis;
            scanf("%d",&l[i]);
            for (int j = 1,x;j <= l[i];++ j)
                scanf("%d",&x),vis[x] = 1;
            int now = 0;
            for (int j = 0;j <= l[i] + 2;++ j)
            {
                if(now >= 2) break;
                if(!vis[j])
                {
                    if(!now) a[i].v1 = j;
                    else a[i].v2 = j;
                    ++ now;
                }
            }
            mx = max(mx,a[i].v2);
        }
        if(m > mx) ans = 1ll * (mx + 1 + m) * (m - mx) / 2ll;
        else ans = 0ll;
        ans += 1ll * min(m + 1,mx + 1) * mx;
        printf("%lld\n",ans);
    }
    return 0;
}

D2. Turtle and a MEX Problem (Hard Version)

        题意:

        和 Easy Version 唯一的区别就是每个数列只能用至多一次。

        思路:

        限定了每个序列的操作次数为 1 ,这里有个很妙的 trick ,就是把抽象的操作具化到图上:这里我们可以建一条边由 v1 指向 v2 ,走过这条边就表示把值从 v1 变成 v2 ,每条边只可以走一次。注意到 v1 < v2 是恒成立的,于是我们建出来的图就是一个 DAG ,我们接下来在 DAG 上 dp 即可。设 fi 表示从点 i 出发可以到达的最大的点,可以通过倒序DP解决。

        那么对于大于 mx 的 x ,我们同样无需操作;对于小于等于 mx 的 x ,我们要么直接从 x 的出边走到最大的那个点,要么选择一个 “有两条以上出边” 的点,删掉这个点的一条出边再走,走到最大的那个点。

        后者的操作实际上是将 x 先变成某一个 v1 再进行操作,在把 x 变成 v1 的时候相当于选择了 v1 所在的某个序列先得到了 v1,于是这个序列不能再用了 ,这等价于在图上先删掉了 v1 的一条出边再走,而删掉的这条边可以是任意一条出边,因为任何一个 v1 所在的序列都可以得到 v1 。

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
using namespace std;

#define N 200005

int T,n,m,l[N],mx,mxn,p[N],f[N];
long long ans;

struct Node
{
    int v1,v2;
}a[N];

int max(int x,int y) { return x > y ? x : y ; }

int min(int x,int y) { return x < y ? x : y ; }

void solve()
{
    vector<int> v[mx + 1];
    int tmp = 0;
    for (int i = 0;i <= mx;++ i) f[i] = i;
    for (int i = 1;i <= n;++ i) v[a[i].v1].push_back(a[i].v2);
    for (int i = mx;i >= 0;-- i)
    {
        for (auto j : v[i]) f[i] = max(f[i],f[j]);
        if(int(v[i].size()) > 1) tmp = max(tmp,f[i]);
    }
    for (int i = 0;i <= min(mx,m);++ i) ans += 1ll * max(mxn,max(i,max(f[i],tmp)));
    return;
}

int main()
{
    scanf("%d",&T);
    while (T --)
    {
        scanf("%d%d",&n,&m),mx = mxn = 0;
        for (int i = 1;i <= n;++ i)
        {
            map<int, int> vis;
            scanf("%d",&l[i]);
            for (int j = 1,x;j <= l[i];++ j)
                scanf("%d",&x),vis[x] = 1;
            int now = 0;
            for (int j = 0;j <= l[i] + 2;++ j)
            {
                if(now >= 2) break;
                if(!vis[j])
                {
                    if(!now) a[i].v1 = j;
                    else a[i].v2 = j;
                    ++ now;
                }
            }
            mxn = max(mxn,a[i].v1);
            mx = max(mx,a[i].v2);
        }
        if(m > mx) ans = 1ll * (mx + 1 + m) * (m - mx) / 2ll;
        else ans = 0ll;
        solve();
        printf("%lld\n",ans);
    }
    return 0;
}

Codeforces Round 968 (Div. 2),第7张

总结

        看错题目条件导致了一场掉大分,但是收获了 D2 这么好的 trick 也算是没白打这场比赛。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!