线上OJ:
一本通:1936:【06NOIP普及组】Jam的计数法 (opens in a new tab)
AcWing:427. Jam的计数法 (opens in a new tab)
洛谷:P1061 [NOIP2006 普及组] Jam 的计数法 (opens in a new tab)
关键语句:
1、每个字母互不相同
,(即字母不能重复出现) 规则①
2、而且从左到右是严格递增的
(举例,只能是 bdfij,不能是 bdfji) 规则②
3、隐藏条件:'a' 对应的数字是1,'b'对应的数字是2
核心思想:
1、如果用字母思考有点绕,我们可以先转换成数字来推理
举例样例输入的(s=2, t=10, w=5):
因为s=2,所以起始字母是b;t=10,所以末尾字母是A
a | b | c | d | e | f | g | h | i | j |
---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A |
根据 规则① 和 规则②,可得知当位数w为5时: 最小的数是23456;最大的数6789A。
如果要求 2789A 的下一个数,由于
第 w 位的A是(s=2, t=10中的)最大值,不存在再+1的字母,所以A不能+1
第 w-1 位的9可以+1, 但9+1=A;由规则②可知,第 w 位必须比第 w-1 位大,但已经没有比A更大的,所以第 w-1 位的9也不能+1
第 w-2 位的8可以+1, 但8+1=9;由规则②可知,第 w-1 位必须比第 w-2 位大,所以第 w-1 位最少是A;此时第 w 位已经没有比A更大的,所以第 w-2 位的8也不能+1
第 w-3 位的7可以+1, 但7+1=8;由规则②可知,第 w-2 位必须比第 w-3 位大,所以第 w-2 位最少是9,第 w-1 位最少是A;此时第 w 位已经没有比A更大的,所以第 w-3 位的7也不能+1
第 w-4 位的2可以+1, 且2+1=3;由规则②可知,第 w-3 位必须比第 w-4 位大,所以第 w-3 位最少是4,第 w-2 位最少是5,第 w-1 位最少是6;第 w 位最少是 7
所以,2789A的下一个数是34567
我们会发现,规律如下
1、如果 已知 了 第 j 位 数字,则 最小 的 w 位宽的数是后续的每位数字只+1
2、第 j 位的数字加上1以后,后面的每一位至少都要+1,则 传递 到最后一位数字时 多 加 (w-1)- j(w-1是最后一位的索引,j是第j位的索引)。换句话说,最后一位(第 w-1 位)是 s[t] 时,第 j 位的 s[j] +1 不能超过 s[t] - (w-1)- j;否则第 j 位的就不能+1。还得继续向前检查第 j-1 位.
第 w-4 位 第 w-3 位 第 w-2 位 第 w-1 位 第 w 位
≤ 6 ≤ 7 ≤ 8 ≤ 9 ≤ A
第 w-4 位 | 第 w-3 位 | 第 w-2 位 | 第 w-1 位 | 第 w 位 |
---|---|---|---|---|
≤ 6 | ≤ 7 | ≤ 8 | ≤ 9 | ≤ A |
所以,本题的核心是:
1、如果 ③式 ,s[j] 可以直接+1,且后面每一位都+1即可。
2、反之,如果第 j 位不能 +1,继续向前搜索第 j-1 位
因为 , 所以③式可变为
题解代码:
#include <bits/stdc++.h>
using namespace std;
int s, t, w;
string str;
/*
核心: s[j]+1 <= s[t]-[(w-1)-j] s[t]='a'+t-1
所以 s[j]+1<='a'+t-1-[(w-1)-j]
*/
int main()
{
cin >> s >> t >> w >> str;
for(int i = 1; i <= 5; i++)
{
bool flag = false;
for(int j = w-1; j > 0; j--) // 当w=5时,j为0-4,对应s[0]-s[4]
{
if( str[j] + 1 <= 'a' + t - 1 - ((w - 1) - j) ) // 如果第j位能+1(向后传递后最后一位不会出界)
{
flag = true; // 标记本轮找到了下一个最小数字
str[j] += 1; // 因为第j位能+1,所以先+1
for(int k = j + 1; k < w; k++) str[k] = str[k-1] + 1; // 此时的最小值是后面每一位在前一位基础上+1
cout << str << endl; // 都更新完后输出
break;
}
}
if(flag == false) break; // 如果某一轮没有找到下一个数,继续循环也找不到,跳出循环即可
}
return 0;
}