"蔚来杯"2022牛客暑期多校训练营7 赛后总结

比赛成绩

AC：3

RANK：502

试题订正

C.Constructive Problems Never Die

难度：check-in

当且仅当全部 $a_{i}a\_i$ 相同时才无解。

其余情况：

没有出现过的数随便填，剩下的数一定每个数恰好只剩下一个，错排（每个数填下一个数的位置）就行。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
int a[MAXN],b[MAXN],cnt[MAXN],ans[MAXN];
bool vis[MAXN];
int main()
{
    int T;
    cin>>T;
    int n;
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i) cnt[i]=vis[i]=0;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]),++cnt[a[i]],b[i]=a[i];
        if(cnt[a[1]]==n)
        {
            printf("NO\n");
            continue;
        }
        sort(b+1,b+n+1);
        int len=unique(b+1,b+n+1)-b-1;
        for(int i=1;i<len;++i) ans[b[i]]=b[i+1];
        ans[b[len]]=b[1];
        printf("YES\n");
        int tmp=1;
        for(int i=1;i<=n;++i)
        {
            while(tmp<=n && cnt[tmp]) ++tmp;
            if(!vis[a[i]]) printf("%d ",ans[a[i]]),vis[a[i]]=1;
            else printf("%d ",tmp++);
        }
        putchar('\n');
    }
    return 0;
}

F.Candies

难度：easy

不难证明不论删的顺序如何，对答案没有影响，因此只要暴力删除即可。

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
struct node{
    int data, nxt, pre;
};
node a[MAXN];
int n, x, ans;
bool vis[MAXN];
int main(){
    scanf("%d%d",&n,&x);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i].data), a[i].nxt = i + 1, a[i].pre = i - 1;
    a[1].pre = n; a[n].nxt = 1;
    for(int i = 1; !vis[i] && n; i = a[i].nxt){
        bool flag = false;
        if(a[i].nxt == i) break;
        while(i && a[i].nxt && (a[i].data == a[a[i].nxt].data || a[i].data + a[a[i].nxt].data == x)){
            if(a[i].nxt == i) break;
            a[a[i].pre].nxt = a[a[i].nxt].nxt;
            a[a[a[i].nxt].nxt].pre = a[i].pre;
            i = a[i].pre;
            ans++; n -= 2;
            if(n <= 0) break;
            flag = true;
        }
        if(flag == false) vis[i] = true;
    }
    printf("%d\n",ans);
    return 0;
}

G.Regular Expression

难度：easy

题目给的 https://regex101.com/ 确实是个好东西。

分情况讨论：

$11$ .当长度为 $11$ 时（以 $\mathrm{"}a\mathrm{"}"a"$ 为例）：匹配的长度最小的字符串为： $\mathrm{"}a\mathrm{"}"a"$ , $\mathrm{"}\mathrm{.}\mathrm{"}"."$ 。

$22$ .当长度为 $22$ 且相同时（以 $\mathrm{"}aa\mathrm{"}"aa"$ 为例）：匹配的长度最小的字符串为： $\mathrm{"}aa\mathrm{"}"aa"$ , $\mathrm{"}a\mathrm{.}\mathrm{"}"a."$ , $\mathrm{"}\mathrm{.}a\mathrm{"}".a"$ , $\mathrm{"}\mathrm{.}\mathrm{.}\mathrm{"}".."$ , $\mathrm{"}\mathrm{.}+\mathrm{"}".+"$ , $\mathrm{"}\mathrm{.}\ast \mathrm{"}".*"$ , $\mathrm{"}a+\mathrm{"}"a+"$ , $\mathrm{"}a\ast \mathrm{"}"a*"$ 。

$33$ .当长度为 $22$ 且不同时（以 $\mathrm{"}ab\mathrm{"}"ab"$ 为例）：匹配的长度最小的字符串为： $\mathrm{"}ab\mathrm{"}"ab"$ , $\mathrm{"}a\mathrm{.}\mathrm{"}"a."$ , $\mathrm{"}\mathrm{.}b\mathrm{"}".b"$ , $\mathrm{"}\mathrm{.}\mathrm{.}\mathrm{"}".."$ , $\mathrm{"}\mathrm{.}+\mathrm{"}".+"$ , $\mathrm{"}\mathrm{.}\ast \mathrm{"}".*"$ 。

$44$ .当长度大于 $22$ 且全部相同时（以 $\mathrm{"}aaaaaaaa\mathrm{"}"aaaaaaaa"$ 为例）：匹配的长度最小的字符串为： $\mathrm{"}a+\mathrm{"}"a+"$ , $\mathrm{"}a\ast \mathrm{"}"a*"$ , $\mathrm{"}\mathrm{.}+\mathrm{"}".+"$ , $\mathrm{"}\mathrm{.}\ast \mathrm{"}".*"$ 。

$55$ .当长度大于 $22$ 且不是全部相同时（以 $\mathrm{"}aaaaabba\mathrm{"}"aaaaabba"$ 为例）：匹配的长度最小的字符串为： $\mathrm{"}\mathrm{.}+\mathrm{"}".+"$ , $\mathrm{"}\mathrm{.}\ast \mathrm{"}".*"$ 。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=2e5+5;
char a[MAXN];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s",a+1);
        int len=strlen(a+1);
        if(len==1) printf("1 2\n");
        else if(len==2)
        {
            if(a[1]!=a[2]) printf("2 6\n");
            else printf("2 8\n");
        }
        else
        {
            bool flag=0;
            for(int i=2;i<=len;++i)
            {
                if(a[i]!=a[1])
                {
                    flag=1;
                    break;
                }
            }
            if(flag) printf("2 2\n");
            else printf("2 4\n");
        }
    }
    return 0;
}