自动搬运

查看原文

来自洛谷，原作者为

	huayucaiji I was once great.The glory is bound to be back one day!

搬运于2025-08-24 21:50:54，当前版本为作者最后更新于2021-04-27 22:35:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

APIO 08的好题，代码量不大，思维量有一些。

解法

这种题其实套路明显，就是先预处理一些数据，最后再扫一遍求出答案。有点像二进制从高位开始一点一点逼近的感觉。

一开始，将字符串转化为数字表示。

我们可以用 DP 来求出范式$-j$ 的个数。由题意，范式$-(j-1)$ 也是范式$-j$，为了统计方便，我们先令范式$-(j-1)$ 不是范式$-j$，最后前缀和合并即可。

我们令 $f_{i,j,x}$ 为考虑到第 $i$ 位，这一位是 $x$ 的范式$-j$ 个数。易得转移方程：

如果这一位是确定的字符，那么 $x$ 就是一个定值。

求完前缀和后，我们按照前面所说的方法求解答案即可。

代码

有点丑（毕竟循环层数有点多）。

看了其他大佬的代码发现其实可以把代码中部分循环合并，优化常数和代码行数。但是本人较菜，觉得写这种思路清晰的代码比较好。

毕竟，你完全没必要在简单问题上耍杂技。

除非在女同学面前。

//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int MAXN=5e4+10; 

int n,k,r;
int f[MAXN][11][5],a[MAXN];

char trans(int x) {
	if(x==1) return 'A';
	if(x==2) return 'C';
	if(x==3) return 'G';
	return 'T';
}

signed main() {
	cin>>n>>k>>r;
	for(int i=1;i<=n;i++) {
		char c;
		cin>>c;
		if(c=='A') a[i]=1;
		else if(c=='C') a[i]=2;
		else if(c=='G') a[i]=3;
		else if(c=='T') a[i]=4;
		else a[i]=0;
	}
	
	if(!a[n]) {
		for(int i=1;i<=4;i++) {
			f[n][1][i]=1;
		}
	}
	else {
		f[n][1][a[n]]=1;
	}
	
	for(int i=n-1;i;i--) {
		if(a[i]) {
			for(int j=1;j<=k;j++) {
				for(int y=1;y<=4;y++) {
					f[i][j][a[i]]+=f[i+1][j-(a[i]>y)][y];
				}
			}
		}
		else {
			for(int x=1;x<=4;x++) {
				for(int j=1;j<=k;j++) {
					for(int y=1;y<=4;y++) {
						f[i][j][x]+=f[i+1][j-(x>y)][y];
					}
				}
			}
		}
	}
	
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=k;j++) {
			for(int x=1;x<=4;x++) {
				f[i][j][x]+=f[i][j-1][x];
			}
		}
	}
	
	for(int i=1,last=0;i<=n;i++) {
		if(a[i]) {
			printf("%c",trans(a[i]));
			k-=(a[i]<last);
			last=a[i];
		}
		else {
			int x;
			for(x=1;x<=4&&r>f[i][k-(x<last)][x];x++) {
				r-=f[i][k-(x<last)][x];
			}
			printf("%c",trans(x));
			k-=(x<last);
			last=x;
		}
	}
	puts("");
	return 0;
}