Global Round 7

A

输出n个数字不含0，且这个数不能整除他所包含的物质，考虑3的性质，输入33334这类的数字即可

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		if(n==1)printf("-1\n");
		else {
		for(int i=0;i<n-1;i++)printf("3");
		printf("4\n");
		}
	}
}

B

就是给一个数组b[i]=a[i]-x,然后求a[i]，维护一下x就可以了

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int b[200010]; 
int a[200010];
ll maxx = -1e18;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&b[i]);
	for(int i=0;i<n;i++){
		if(i==0)printf("%d ",b[i]),maxx=max(1ll*b[i],maxx);
		else printf("%d ",b[i]+maxx),maxx=max(1ll*b[i]+maxx,maxx);
	}
}

C

首先最大的和肯定是前k个最大的数，然后能切的地方就是任意两个被选数两个之间的间隔数即可

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 2e5+10;
const int mod = 998244353;
int a[N]; 
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	ll ans = 0;
	for(int i=n;i>n-k;i--)ans+=i;
	int s=n-k+1;
	int pos = 0;
	while(a[pos]<s)pos++;
	ll ans1=1;
	int pre=pos;
	for(int i=pos+1;i<n;i++){
		if(a[i]>=s){
			ans1=(ans1*(i-pre))%mod;
			pre=i;
		}
	}
	printf("%lld %lld\n",ans,ans1);
}

D

从一个字符串截取从头开始一段，从尾开始一串，连接起来后最长的回文串。
考虑先从头找回文，然后再剩下的字符串中，找从头开始或者从尾开始的最长回文，这个怎么找呢？
使用KMP，把原字符串s加上’#(-s)’例如(cbabcdf)=(cbabccdf#fdccbabc)这样，最长回文就是next数组的最后一个值，然后把s反过来再求一次即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e6+10;
int nex[N];
void getnex(string s){
	for(int i=0;i<s.size();i++)nex[i]=0;
	nex[0]=-1;
	int i=0,k=-1;
	while(i<s.size()){
		if(k==-1||s[i]==s[k])nex[++i]=++k;
		else k=nex[k];
	}
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		string s;
		cin>>s;
		string s1;
		int pos=-1;
		for(int i=0;i<(s.size()-1)/2;i++){
			if(s[i]==s[s.size()-i-1]){
				pos=i;
			}
			else break;
		}
		s1=s.substr((pos+1),s.size()-2*(pos+1));
		string s2=s1;
		reverse(s2.begin(),s2.end());
		s1+="#";
		s1+=s2;
		getnex(s1);
		int len = nex[s1.size()-1]+1;
		s2+="#";
		string s3 = s2;
		reverse(s3.begin(),s3.end());
		s2+=s3;
		getnex(s2);
		int len2 = nex[s2.size()-1]+1;
		for(int i=0;i<=pos;i++)printf("%c",s[i]);
		if(len>=len2)
		for(int i=0;i<len;i++)printf("%c",s1[i]);
		else for(int i=0;i<len2;i++)printf("%c",s2[i]);
		for(int i=s.size()-pos-1;i<s.size();i++)printf("%c",s[i]);
		printf("\n");
	}
}