AtCoder Grand Contest 016

时间：2024-11-04 22:33:56

在雅礼和衡水的dalao们打了一场atcoder

然而窝好菜啊……

A - Shrinking

题意：定义一次操作为将长度为n的字符串变成长度n-1的字符串，且变化后第i个字母为变化前第i 或 i+1 个字母，求使整个字符串为同一字母的最少变换次数。

题解：求同一字母的最大间距（包括首尾）的最小值即可。

#include<cstdio>

#include<algorithm>

#define MN 1111

using namespace std;

int mmh=1e9;

char s[MN];

int main(){

    scanf("%s",s);

    for (int i='a';i<='z';i++){

        int la=-,ans=,j;

        for (j=;s[j];j++)

        if (s[j]==i){

            if (ans<j-la-) ans=j-la-;

            la=j;

        }

        if (ans<j-la-) ans=j-la-;

        if (mmh>ans) mmh=ans;

    }

    printf("%d\n",mmh);

}

B - Colorful Hats

题意：给一个序列ai，问是否存在另一个序列bi满足对于任意i，bi中除 i 以外不同数字数量为ai。

题解：如果ai中有数字相差超过1，那肯定就不合法，然后分情况讨论。如果ai中所有数都相等记为x，那要么n=x+1要么n>=x*2时合法，否则ai中较小的那部分数肯定在bi中是单独存在的，然后判定不单独存在的的部分是否满足数量要求即可。

#include<cstdio>

#include<algorithm>

#define MN 111100

using namespace std;

int n,s,S,a[MN],ma=,mi=1e9;

int main(){

    scanf("%d",&n);

    for (int i=;i<=n;i++) scanf("%d",&a[i]),ma=max(ma,a[i]),mi=min(mi,a[i]);

    if (ma-mi>) return puts("No"),;

    if (ma==mi) return puts(n>=ma*||n==ma+?"Yes":"No"),;

    s=ma;S=n;

    for (int i=;i<=n;i++) if (a[i]==mi) s--,S--;

    puts(S>=s*&&s>?"Yes":"No");

}

C - +/- Rectangle

题意：要求构造一个矩阵满足所有元素的总和为正数，任意指定大小的子矩形内总和为负数。

考场上没写出来，赛后看的题解，好神啊。

#include<queue>

#include<cstdio>

#include<algorithm>

using namespace std;

int read_p,read_ca,read_f;

inline int read(){

    read_p=;read_ca=getchar();read_f=;

    while (read_ca<''||read_ca>'') read_f=read_ca=='-'?-:read_f,read_ca=getchar();

    while (read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p*read_f;

}

int H,W,h,w;

int main(){

    H=read();W=read();h=read();w=read();

    if ((H/h)*(W/w)*(*(h*w-)+)>=*(H*W-(H/h)*(W/w))) return puts("No"),;

    puts("Yes");

    for (int i=;i<=H;i++,puts(""))

    for (int j=;j<=W;j++)

    if (i%h==&&j%w==) printf("%d ",-(*(h*w-)+));else printf("%d ",);

}

D在衡水dalao的帮助下（大约是没有）理解了。

设$a_{n}=a_{0}⊕a_{1}⊕……⊕a_{n-1}$，问题先转化为每次把一个$a_{i}$与$a_{n}$交换的问题。交换当然是考虑置换环，但是相同元素怎么办？有相同的元素的可以直接强行并成一个环，代价照算。然后如果置换环里有$a_{n}$那代价要减少2。

继续留坑

怒掉rating

相关文章