CSP历年复赛题-P1061 [NOIP2006 普及组] Jam 的计数法

原题链接：https://www.luogu.com.cn/problem/P1061

题意解读：从编号s~t的字母从挑w个，组成一种特殊的数字，数字里字母都是升序的，给定初始数字，要计算后5个。

解题思路：

1、模拟法

模拟样例：

2 10 5

有效字母范围：b,c,d,e,f,g,h,i,j 

初始值：b d f i j

要计算b d f i j的下一个，采取如下步骤：

1、从右边数，先看第一位j，有效字母中是否有一个大于j的，如果有则用第一个大于j的进行替换，显然没有

2、从右边数，再看第二位i，有效字母中是否有两个大于i的，依然没有

3、从右边数，看第三位f，有效字母中有g,h,i,j都大于f，取前三个f开始的三个进行替换，变成b d g i j

同理，再计算b d g i j的下一个即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

int s, t, w;
string str;

int main()
{
    cin >> s >> t >> w >> str;

    int cnt = 0;
    while(true)
    {
        bool yes = false;
        for(int i = 1; i <= w; i++) //从右边第1个开始，一直到第w个
        {
            int x = str.size() - i; //右边第i个的下标
            if(t - (str[x] - 'a' + 1) >= i) //计算是否有超过i个比右边第i个大的字母
            {
                //有的话用前i个替换str[x]到最后
                char tmp = str[x];
                for(int j = 1; j <= i; j++)
                {
                    str[x + j - 1] = tmp + j;
                }
                cnt++;
                yes = true;
                cout << str << endl;
                break;
            }
        }
        if(!yes || cnt == 5) break;
    }

    return 0;
}

2、DFS

类似于火星人的全排列，需要从指定排列开始，填w个空

不同的是，需要保证字母都是升序的，即开始枚举的字母必须比前一位的字母大1

另外，由于字母是升序的，天然保证了不会有重复，因此不需要标记数据

100分代码：

#include <bits/stdc++.h>
using namespace std;

int s, t, w;
string str;
int line[30]; //排列
int cnt;
bool start = false;

void dfs(int k)
{   
    if(k == w)
    {
        if(!start) start = true;
        else
        {
            for(int i = 0; i < w; i++) cout << char(line[i] - 1 + 'a');
            cout << endl;
            if(++cnt == 5) exit(0);
        }
        return;
    }
    int begin = s;
    if(k > 0) begin = line[k-1] + 1; //从上一个字母的后一个开始
    for(int i = begin; i <= t; i++)
    {
        if(!start)
        {
            i = str[k] - 'a' + 1;
        }
        line[k] = i;
        dfs(k + 1);
    }
}

int main()
{
    cin >> s >> t >> w >> str;
    dfs(0);

    return 0;
}