luogu-P1061题解

第一篇高难度题解

主要题意

用从第 $s$ 位到第 $t$ 位的字母分别表示的数字是第 $s$ 位字母减去字母 $a$ 再加 $1$ ，即s-'a'+1。需要保证这串字母一直是从左到右递增。现在要求求出比这串字母大的后 $5$ 串字母，严格要求中间无其他排列方式。

解题思路

首先把字母转为数字，存放如一个二维数组中。然后，如果最后一位 $+1$ 不会大于 $t$ ，那么直接 $+1$ ；否则在找到最高的 $+1$ 小于等于 $t$ 且最后一位加上比这位大的数字数量小于等于 $t$ 的一位数。（抽象，具体见代码）

然后将得到的一串数字存入数组，再经过处理（见代码）后输出。

上代码！

#include <bits/stdc++.h>
using namespace std;
int s,t,w;
string str;
int a[1001][1001];
int main()
{
	cin>>s>>t>>w;
	cin>>str;
	for(int i=0;i<w;i++)
		a[0][i]=str[i]-'a'+1;
	for(int i=1;i<=5;i++)
	{
		if(a[i-1][w-1]+1>t)
		{
			for(int j=0;j<w;j++)
				a[i][j]=a[i-1][j];
			int x=w-1;
			while(a[i-1][x]+1>t||a[i-1][x]+w-x>t)
				x--;
			a[i][x]++;
			for(int j=x+1;j<w;j++)
				a[i][j]=a[i][x]+j-x;
		}
		else
		{
			for(int j=0;j<w-1;j++)
				a[i][j]=a[i-1][j];
			a[i][w-1]=a[i-1][w-1]+1;
		}
		for(int j=0;j<w;j++)
			cout<<(char)(a[i][j]+'a'-1);
		puts("");
	}
}