P8846 『JROI-7』PMK 配匹串符字
简要题意
给出一正整数 \(n(1 \leq n \leq 10^5)\)，求出一个由小写英文字母组成的字符串 \(S\)，使得 \(|S|=n\) 且 \(\sum_{i=1}^{n}{\operatorname{Next}_i}\) 最小。（如果有多组解，输出任意一组解即可）
注：\(\operatorname{Next}\) 为 \(S\) 的失配数组。
思路
首先失配数组和最小的话当然是 \(0\)，那怎么是 \(0\) 呢？考虑失配数组的定义。\(\operatorname{Next}_i\) 为 \(S[1:i]\) 中最长的前缀使其等于后缀的长度。如果 \(\operatorname{Next}_i=0\) 那么不存在前缀=后缀。怎样不存在？直接构造一个 \(\texttt{abbbbbb...}\) 即可。
时间复杂度 \(O(n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
if(i==1)putchar('a');else putchar('b');
}
return 0;
}
P8847 [JRKSJ R5] 1-1 A
简要题意
给你一个由 \(1,-1\) 组成的长度为 \(n(1 \leq n \leq 10^6)\) 的序列 \(a\)，你需要将其重排，使得最大子段和最小。输出重排后的序列。（如果有多组解，输出任意一组解即可）
思路
首先，直觉告诉我们，一定要 \(\texttt{1 -1 1 -1 ...}\) 这样交错输出。
如果 \(1\) 的数量不等于 \(2\) 的数量呢？我一开始的思路是从中间二分插入，但是这样子是错误的。
事实上，如果 \(-1\) 的数量大于 \(1\) 的数量，我们直接将 \(-1\) 拼到后面去，这样子可以做到最大子段和为 \(1\)。
如果 \(1\) 的数量大于 \(-1\) 的数量呢？我们同样拼到后面去，这样子可以做到最大子段和为 \(\textbf{1 的数量}-\textbf{-1 的数量}\)。
可证明这已经是最优的。
时间复杂度 \(O(n)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int pos,neg;
signed main(){
ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n;
for(int i=1,v;i<=n;i++){
cin>>v;
if(v==1)pos++;
else neg++;
}
int init=1;
for(int i=1;i<=n&&pos&&neg;i++){
cout<<init<<' ';
if(init==1)pos--;
else neg--;
init=(-init);
}
if(pos>0){
while(pos--)cout<<1<<' ';
}
if(neg>0){
while(neg--)cout<<-1<<' ';
}
return 0;
}
P8848 [JRKSJ R5] 1-1 B
简要题意
给你一个由 \(1,-1\) 组成的长度为 \(n(1 \leq n \leq 10^4)\) 的序列 \(a\)，询问有多少个将 \(a\) 重排后的序列使得该序列的最大子段和最小化。答案对 \(998244353\) 取模。
思路
首先由上题得在 \(1\) 的个数（下设为 \(p\)）大于 \(-1\) 的个数）（下设为 \(e\)）时，最大子段和的最小值 \(L=\sum a\)，在 \(p<e\) 时 \(L=1\)，在 \(p=e\) 时 \(L=0\)。
- 当 \(p\leq e\) 时，与 \(-1\) 和 \(1\) 的位置无关，我们可以直接将 \(-1\) 固定，到里面插入 \(1\)。因此此时答案为 \(\binom{p}{e+1}\)。
- 当 \(p>e\) 时，与位置有关，我们考虑 DP，设 \(f_{i,j}\) 为前 \(i\) 个数凑出和为 \(j\) 的方案数，则动态转移方程：
推导过程 \(f_{i,j}\) 可以从从 \(f_{i-1,j-1}\) 中加上 \(1\) 得来，也可以从 \(f_{i-1,j+1}\) 中减去 \(1\) 得来。\(f_{i,0}\) 只能从 \(f_{i-1,1}\) 中减去 \(1\) 得来。
但是对于 \(1 \leq n \leq 10^4\) 时 \(f\) 空间开不下，需要进行滚动数组优化。
时间复杂度 \(O(n^2)\)（\(p>e\)）或 \(O(n\log n)\)（\(p\leq e\)）。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[10005],fold[100005];
int fact[10005];
const int mod = 998244353;
int n,pos,neg,sum;
int pow(int a,int b,int mod) {
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod) {
if(b&1) {
ans=1ll*ans*a%mod;
}
}
return ans;
}
int inv(int x){
return pow(x,mod-2,mod);
}
int c(int m,int n){
return (fact[n]*inv(fact[m])%mod)*inv(fact[n-m])%mod;
}
signed main(){
cin>>n;
for(int i=1,v;i<=n;i++){
cin>>v;
if(v==1)pos++;
else neg++;
sum+=v;
}
if(neg>=pos){
fact[0]=fact[1]=1;
for(int i=2;i<=(n+1);i++){
fact[i]=fact[i-1]*i%mod;
}
cout<<c(pos,neg+1)<<'\n';
return 0;
}
f[0]=fold[0]=1;
for(int i=1;i<=n;i++){
f[0]=fold[1];
for(int j=1;j<=sum;j++){
f[j]=(fold[j-1]+fold[j+1])%mod;
}
memcpy(fold,f,sizeof(f));
}
cout<<f[sum]<<'\n';
return 0;
}