题解 P1061 【Jam的计数法】

06ray · 2017-09-26 17:09:35 · 题解

其实这道题的思路比较简单（看到dalao们用dfs做这题，突然觉得自己好弱）。本蒟蒻的思路很简单，首先判断第n个位置的字母后继能不能填，如果不能填，那在看看第n-1位置的字母后继能不能填，如果还不能，那在看看第n-2位置的字母后继能不能填……以此类推，直到可以填了为止。那么每一个位置上的字母就是前一个位置上字母的后继字母。如果可填，字母就是它的后继。

然后再贴上华丽丽的代码（代码有解释）

#include <iostream>
using namespace std;
string s;
int n,x,y;
int js(int k)//计算第k-1位置上的字母的变化 
{
    if(k==0) return ' ';//如果k到零了，说明无解，返回空格，表示没有下一个Jam数
    char c=s[k];
    if(c+1>(char)96+(y-(n-1-k))) //如果第k-1个位置的字母的后继超过了这个位置所能填的最大字母 
    {
        char c=js(k-1);//递归调用，c表示前一个位置所填的字母 
        if(c==' ') return ' ';//如果无解，直接再返回空格 
        s[k]=c+1;//所填的字母是前面一个字母的后继 
        return s[k];//返回所填的数 
    }
    else//如果第k-1个位置的字母的后继没有超过了这个位置所能填的最大字母 
    {
        s[k]=c+1;//那就加一 
        return s[k];//返回 
    }
}
int main()
{
    scanf("%d%d%d\n",&x,&y,&n);//读入三个数，用scanf快一点点 
    getline(cin,s);//读入字符串 
    for(int i=1; i<=5; i++)
    {
        char x=js(n-1);//可以用x来判断是否有解 ，并且调用函数 
        if(x==' ') break;//如果无解则跳出循环 
        cout<<s<<endl;//输出其中一个解 
    }
}