如有帮助请移步voids5.cn，增加一些访问量，里面也有我未在csdn发布的博客
#A. Bad Ugly Numbers
题目大意：给你一个数字n你需要找到一个满足以下条件的数字s：
1.s大于0
2.s有n位数字
3.s任一位上不包括0
4.s不能被任意位上的数整除
解题思路：可以发现s用两个质数组成可以满足上述条件
Code:
#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
cin>>t;
while(t--){
cin>>n;
if(n==1) cout<<-1<<endl;
else {
if((2*(n-1)+3)%3==0){
for(int i=1;i<=n-2;i++) cout<<2;
cout<<33<<endl;
}
else {
for(int i=1;i<n;i++) cout<<2;
cout<<3<<endl;
}
}
}
return 0;
}
B. Maximums
题目大意：三个数组，a，x，b，x[i]是a[1 ~ i-1]的最大值，b[i]=a[i]-x[i],给你b数组，求a数组
解题思路：因为x[1]=0,所以a[1]=b[1],故可由b数组推出x数组然后推出a数组
Code：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int t,n,b[N],a[N],x[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>b[i];
x[1]=0;a[1]=b[1];
int maxx=a[1],pos=1;
for(int i=2;i<=n;i++){
a[i]=b[i]+maxx;
if(a[i]>maxx){
maxx=a[i];
pos=i;
}
}
for(int i=1;i<=n;i++){
cout<<a[i]<<' ';
}
cout<<endl;
return 0;
}
C. Permutation Partitions
题目链接：https://codeforces.com/contest/1326/problem/C
题目大意：给你一个由1~n组成的数组a[n],将数组分成k块，使每块的最大值最大，问最大值是多少和分法种数
解题思路：分成k块其实就是将n~n-k+1这几个数字放入k个区间，类似于高中排列组合的插板问题,将板子插到所要找的数字间就好了
Code：
#include<iostream>
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,k,x;
ll ans=1,sum,p=-1;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>x;
if(x>=(n-k+1)){
sum+=x;
if(p!=-1){
ans=ans*(i-p)%mod;
}
p=i;
}
}
cout<<sum<<" "<<ans;
return 0;
}
D1. Prefix-Suffix Palindrome (Easy version)
题目链接：https://codeforces.com/contest/1326/problem/D1
题目大意：给你一个字符串s，找到前后缀使a+b是回文串且最长
解题思路：简单的我们可以模拟一下
Code:
#include <bits/stdc++.h>
using namespace std;
bool ok(const string &s,int l,int r){
while(l<=r&&s[l]==s[r]) ++l,--r;
return l>r;
}
void solve(){
string s;cin>>s;
int l=0,r=s.size()-1;
while(l<r&&s[l]==s[r]) ++l,--r;
int r2,l2;
for(r2=r;r2>=l;r2--) if(ok(s,l,r2)) break;
for(l2=l;l2<=r;l2++) if(ok(s,l2,r)) break;
cout<<s.substr(0,l)
<<((r2-l>r-l2)?s.substr(l,r2-l+1):s.substr(l2,r-l2+1))
<<s.substr(r+1)
<<"
";
}
int main()
{
int t;cin>>t;
while(t--)
solve();
return 0;
}
D2. Prefix-Suffix Palindrome (Hard version)
题目链接：https://codeforces.com/contest/1326/problem/D2
题目大意：和D1一样只是范围大了
解题思路：先首尾找到最长匹配的l，r；然后再取剩下字符串的较长的回文前缀或回文后缀
KMP：
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
vector<int>cal_nxt(string s){
int n=s.length();
vector<int>nxt(n);
for(int i=1;i<n;i++){
int j=nxt[i-1];
while(j&&s[i]!=s[j]){
j=nxt[j-1];
}
if(s[i]==s[j]) nxt[i]=++j;
}
return nxt;
}
int main(){
cin>>n;
while(n--){
cin>>s;
int len = s.length();
int i=0,j=len-1;
while(i<j&&s[i]==s[j]) i++,j--;
string s1=s.substr(i,j-i+1);
string s2=s1;
reverse(s2.begin(),s2.end());
vector<int>nxt1=cal_nxt(s1+"#"+s2);
vector<int>nxt2=cal_nxt(s2+"#"+s1);
int len2=s1.size()+1+s2.size();
// cout<<j+1<<endl;
// cout<<nxt1[len2-1]<<' '<<nxt2[len2-1]<<endl;
if(nxt1[len2-1]>=nxt2[len2-1]){
cout<<s.substr(0,i)<<s1.substr(0,nxt1[len2-1])<<s.substr(j+1,len-j+1)<<endl;
}
else {
cout<<s.substr(0,i)<<s2.substr(0,nxt2[len2-1])<<s.substr(j+1,len-j+1)<<endl;
}
}
return 0;
}
字符串哈希：这个还是蛮坎坷的，按yxc大佬的模除2^64wa4，base=131 wa110,按我的写法ss=="",时也会输出一个空格。我太难了
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
typedef long long ll;
typedef unsigned long long ull;
const ll N = 1e6+5,base=113,mod=1e9+7;
ull p[N];
void init(){
p[0]=1;
for(int i=1;i<N;i++){
p[i]=p[i-1]*base%mod;
}
}
int main(){
init();
cin>>n;
while(n--){
cin>>s;
int len = s.length();
int l=0,r=len-1;
while(l<r&&s[l]==s[r]) l++,r--;
string ss=s.substr(l,r-l+1);
string tt=ss;
reverse(tt.begin(),tt.end());
int len1=ss.size();
ll res1=0,res2=0;
int ans1=0,ans2=0;
for(int i=0;i<len1;i++){
res1=(res1+p[i]*(ss[i]-'a')%mod)%mod;
res2=(res2*base+(ss[i]-'a'))%mod;
if(res1==res2) ans1=i;
}
res1=0,res2=0;
for(int i=0;i<len1;i++){
res1=(res1+p[i]*(tt[i]-'a')%mod)%mod;
res2=(res2*base+(tt[i]-'a'))%mod;
if(res1==res2) ans2=i;
}
// if(ans1==0) ss="";
// if(ans2==0) tt="";
for(int i=0;i<l;i++) cout<<s[i];
if(ans1>=ans2){
if(ss!="")for(int i=0;i<=ans1;i++) cout<<ss[i];
}
else {
if(tt!="")for(int i=0;i<=ans2;i++) cout<<tt[i];
}
for(int i=r+1;i<len;i++) cout<<s[i];
cout<<endl;
}
return 0;
}