2022牛客多校第七场

C Constructive Problems Never Die
F Candies
G Regular Expression

C Constructive Problems Never Die

题意：

给定一个长度为n的序列a，要找到一个序列p，满足p[i]!=a[i] (1<=i<=n)

思路：

先将没出现过a数组的元素存在vector里，若将a数组中没连在一起的数字每个向前移动，其他的都填上没出现的数字即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=100010;
typedef long long ll;
int read()
{
    int m=0,n=1; 
	char ch;
	ch=getchar();
    while(ch<'0'||ch>'9')
	{  
	    if(ch=='-') 
		 n=-1;
	    ch=getchar();
	}
    while(ch>='0'&&ch<='9')
	{
	    m=m*10+ch-'0';
	    ch=getchar();
	}
    return m*n;
}
int a[maxn],vis[maxn],num[maxn];
vector<int> v;
int main(){
    int t,n,f;
    t=read();
    while(t--){//1e5
        v.clear();
        memset(a,0,sizeof(a));
        memset(num,0,sizeof(num));
        memset(vis,0,sizeof(vis));
        n=read();
        f=0;
        for(int i=1;i<=n;i++){
            a[i]=read();
            if(i!=1&&a[i]!=a[i-1]) f=1;
            vis[a[i]]++;
        }
        for(int i=1;i<=n;i++){
            if(vis[i]==0){//如果这个元素在a数组没出现过，说明在p中可以放在任意位置
                v.push_back(i);
            }
        }
        if(f==0){
            puts("NO");
        }else{
            int x=0;
            puts("YES");
            a[n+1]=a[1];
            for(int i=1;i<=n;i++){
                if(num[a[i]]==0&&a[i+1]!=a[i]){
                    printf("%d ",a[i+1]);
                    num[a[i]]++;
                }else{
                    printf("%d ",v[x]);
                    x++;
                }
            }
            printf("\n");
        }
    }   
}

F Candies

题意：

有一个环形数组，可以对其进行两种操作，求最多可以进行多少次操作。

1、选择两个连续的相同的数，然后删除它们。

2、选择两个连续的位置，它们加起来的和为x,然后删除它们。

思路：

因为是环形数组，每次操作只需要考虑当前位置和后一位置的关系。但每次操作都会改变数的临近关系，用递归的方法，直接求这个位置能进行多少次操作，用这个方法遍历每个位置即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int vis[N],ne[N];//vis存这个数临近的下一个数，ne存存这个数临近的上一个数
ll n,x;
ll v[N];
int qu(int a,int b){
    int ans=0;
    if(a==b) return 0;
    if(v[b]==v[a]||v[b]+v[a]==x){
              
               vis[ne[a]]=vis[b];
               ne[vis[b]]=ne[a];
               vis[b]=b;
               vis[a]=a;
                 ans+=qu(ne[a],vis[ne[a]])+1;
           }
     return ans;
}
int main(){
    scanf("%lld%lld",&n,&x);
    for(int i=0;i<n;i++) scanf("%lld",&v[i]);
    ll ans=0;
    for(int i=0;i<n;i++){
        vis[i]=(i+1)%n;
        ne[i]=(i-1+n)%n;
    }
    
        int cnt=0;
       for(int i=0;i<n;i++){
           if(vis[i]==i) {
               cnt++;
                continue;      
            }
           ans+=qu(i,vis[i]);
    }
    printf("%lld",ans);
}

G Regular Expression

题意：

求最小长度正则表达式匹配字符串，并求出满足所述条件的正则表达式有多少种。

思路：

当时没太看懂题目给的匹配的实例，大部分是在给的网站上试出来的。 $.$ 可以代表任意的数而 $+$ 任意拓展前一个字符，所以特判string长为1，其他的最小长度匹配字符串为2，还有就是出现字符串长为二，且两个字符一样的情况。

代码：

#include<bits/stdc++.h>
using namespace std;
int t;
string s;
int main(){
    cin>>t;
    while(t--){
        cin>>s;
        int f=0;
        for(int i=0;i<s.size()-1;i++){
            if(s[i]!=s[i+1]) {
                f=1;break;
            }
        }
        if(s.size()==1) cout<<1<<" "<<2<<endl;
        else if(f==0&&s.size()==2) cout<<2<<" "<<8<<endl;
        else if(f==1&&s.size()==2) cout<<2<<" "<<6<<endl;
        else if(f==1) cout<<2<<" "<<2<<endl;
        else cout<<2<<" "<<4<<endl;
    }
}