总之就是 CF 1536 A & B

前言

这是第二次打 CF ,体验还不错,争取早日不做 Newbie (笑)。

这里的题解大约都和洛谷上面对应题目我提交的题解基本一样,就是多加了一些赛场描述。

添加了对应题目的 CF 和 洛谷链接,大家要是想做可以去切一切。

A Omkar and Bad Story

洛谷 | CF1536A CF | 1536A

这个题最一开始毫无思路,后来发现这题其实这道题挺水的。

题意简述

问能否找到一个序列,这个序列中任意两个数的差的绝对值都在这个序列中。

思路简述

首先先来考虑哪些情况是不行的。

当这个序列中出现负数,这肯定是不行的,因为任意一个数减去负数都会得到一个更大的数。

因此当原序列中有负数的时候,我们得到的符合题意的序列是一个无限扩展的序列,而这显然与题意不符。

然后,我们来考虑如何能够构造出符合题意的序列。

实际上手模一下就能发现,当一个序列中的数是从 0 开始的连续正整数时,这个序列里的任意两个数字的差的绝对值都在这个序列中。

于是我们就先找到原序列的最大值,判断完没有负数之后,直接输出 0 到这个最大值即可

Code

#include <bits/stdc++.h>
#define Heriko return
#define Deltana 0
#define Romano 1
#define S signed
#define U unsigned
#define LL long long
#define R register
#define I inline
#define D double
#define LD long double
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false)
using namespace std;
I void fr(LL & x)
{
    LL f = 1;
    char c = getchar();
    x = 0;
    while (c < '0' || c > '9') 
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') 
    {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    x *= f;
}
I void fw(LL x)
{
    if(x<0) putchar('-'),x=-x;
    static LL stak[35];
    LL top=0;
    do
    {
        stak[top++]=x%10;
        x/=10;
    }
    while(x);
    while(top) putchar(stak[--top]+'0');
    putchar(' ');
}
S main()
{
    LL t;fr(t);
    while(t--)
    {
        LL n,a[105],amx=-1;
        bool d=false;
        fr(n);
        for(R LL i=1;i<=n;++i)
        {
            fr(a[i]);
            if(a[i]<0) d=true;
            if(a[i]>amx) amx=a[i];
        }
        if(d)
        {
            puts("NO");
            continue;
        }
        puts("YES");
        printf("%lld\n",amx+1);
        for(R LL i=0;i<=amx;++i) fw(i);
        putchar('\n');
    }
    Heriko Deltana;
}

后记

实际上这个题还告诉我们不要被样例输出迷惑了双眼(笑),

还有就是 HYL 何老师上来直接秒了这题,这个思路基本就是何老师的。

看洛谷还有人直接输出 0 到 100 ,确实离谱,但是正确性显然。

B Prinzessin der Verurteilung

洛谷 | CF1536B CF | 1536B

这道题的题面......原神玩家直接狂喜。

大幻梦森罗万象狂气断罪眼

切回正题,先来看题目是让我们求什么。

题意简述

实际上这个题在洛谷的翻译非常的简洁明了了,不过我在 CodeForces 做的时候就理解不能

题目中定义了 MEX 是“在输入中不作为连续子字符串出现的最短字符串”。

然后每组数据给你一个字符串问你这个字符串的 MEX 是什么。

思路简述

首先先来理解一下什么是 MEX ,

当时我再看到这道题的时候是一脸懵的,因为这个翻译出来确实很拗口。

于是我就在下面举一个例子,里面展现出来的东西,就是我个人的理解。希望不要假了QaQ

比如给你一个字符串 abcax ,那么这里面所有连续子字符串其实大家都会找:

"a" , "ab" , "abc" , "abca" , "abcax" , "b" , "bc" , "bca" , "bcax" , "c" , "ca" ......

由于全列出来就太多了,于是就列出这一些吧。

那么 MEX 就是不在这里面的定义上最小的字串,也就是字典序最小的。

可能看到这里觉得这道题还有点难度?下面的一步直接让这个题的难度消失。

我们来看数据范围中说道:对于一个数据点中的所有数据 \(\sum n \ \le 1000\) ,

再由题目的定义可得 MEX 一定是原字符串的字串,又因为 \(26^3 \ge 1000\) 所以 MEX 的长度不会大于 3 。

由此我就想到了一个比较暴力的类似桶的方法,

用一个 bool 数组记录这个字符串有没有出现过,最后按照顺序输出即可。

Code

这里面有关初始化和最后循环的次序还是应当仔细想一下的

#include <bits/stdc++.h>
#define Heriko return
#define Deltana 0
#define Romano 1
#define S signed
#define U unsigned
#define LL long long
#define R register
#define I inline
#define D double
#define LD long double
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false)
using namespace std;
I void fr(LL & x)
{
    LL f = 1;
    char c = getchar();
    x = 0;
    while (c < '0' || c > '9') 
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') 
    {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    x *= f;
}
I void fw(LL x)
{
    if(x<0) putchar('-'),x=-x;
    static LL stak[35];
    LL top=0;
    do
    {
        stak[top++]=x%10;
        x/=10;
    }
    while(x);
    while(top) putchar(stak[--top]+'0');
    putchar('\n');
}
char s[1005];
bool k[30][30][30];
S main()
{
    // freopen("my.in","r",stdin);
    LL t;fr(t);
    while(t--)
    {
        LL n;
        mst(k,0);
        fr(n);gets(s+1);
        for( LL i=1;i<=n;++i)
        {
            k[s[i]-'a'+1][0][0]=1;
            if(i>1) k[s[i]-'a'+1][s[i-1]-'a'+1][0]=k[s[i-1]-'a'+1][0][0]=1;
            if(i>2) k[s[i]-'a'+1][s[i-1]-'a'+1][s[i-2]-'a'+1]=k[s[i-1]-'a'+1][s[i-2]-'a'+1][0]=k[s[i-2]-'a'+1][0][0]=1;      
        }
        bool g=0;
        for( LL p=0;p<=26 and g==0;++p)
            for( LL j=min(p,1ll);j<=26 and g==0;++j)
                for( LL i=1;i<=26 and g==0;++i)
                    if(!k[i][j][p])
                    {
                        if(p) putchar(p+'a'-1);
                        if(j) putchar(j+'a'-1);
                        if(i) putchar(i+'a'-1);
                        putchar('\n');
                        g=1;
                    }
    }
    Heriko Deltana;
}

后记

这里大约说明一下为什么原神玩家狂喜(旅行者狂喜),帮你 Bing 好了

上一篇:GYM102119A Tritwise Mex


下一篇:HDU-4747 Mex 线段树应用 Mex性质