【LGR-125】洛谷 11 月月赛 I & JROI-7 & JRKSJ-5

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}+f_{i-1,j+1}\ \ \ \ \ f_{0,0}=1\ \ \ \ \ f_{i,0}=f_{i-1,1}
\]

推导过程 \(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;

}

巴特西

【LGR-125】洛谷 11 月月赛 I & JROI-7 & JRKSJ-5

P8846 『JROI-7』PMK 配匹串符字

简要题意

思路

代码

P8847 [JRKSJ R5] 1-1 A

简要题意

思路

代码

P8848 [JRKSJ R5] 1-1 B

简要题意

思路

代码

最新文章

热门文章