hiho一下第85周《Numeric Keypad》题目分析

4
2

题目大意

已知手机键盘为

1 2 3
4 5 6
7 8 9
  0

我们采用一种特殊的方式在手机上输入数字,即当按下一个键之后,只能把手指向下或者向右移动。开始时手指默认放在1上。 比如按下2之后,就不能再回到1这个按键。 问对于给定的数字S,能够通过这种特殊方式输入的最大不超过S的数字是多少。

解题思路

我们考虑如何模拟输入数字的过程:

从高位到低位,一位一位输入数字。

在已知S的前提下,我们要使得打出的数字尽可能接近S。则最好的方法就是从高位到低位,每一位都输入和S相同的数字。

先不考虑按键限制的情况下,可以写出一个函数:

dfs(depth):
    If depth >= length Then
        // 找到一个合法解
        // 由于我们总是从高到低对数字进行枚举,因此第一个找到的解一定是最大解
        Output(result)
        Return True
    End If
    For i = 9 .. 0
        If (i <= S[depth]) Then
            result[depth] = i
            If (dfs(depth+1)) Then
                Return True
            End If
        End If
    End For
    Return False

接下来考虑如何按键限制条件。

当我们输入一个数字后,只能再输入键盘上在其右边或下边的数字。由此我们可以得到一个转移矩阵g[10][10]

g[i][j]表示按下数字i后能否移动到数字j。若能够g[i][j]=true,否则g[i][j]=false

比如:

g[1][2] = true,g[2][1] = false

当我们输入了前一位之后,后一位可以使用哪些数字也就确定了,所以我们再参数中增加最后一个输入的数字last

在枚举数字时,我们也需要加入条件判断是否满足要求。

因此将函数改造为:

dfs(depth, last):
    If depth >= length Then
        // 找到一个合法解
        // 由于我们总是从高到低对数字进行枚举,因此第一个找到的解一定是最大解
        Output(result)
        Return True
    End If
    For i = 9 .. 0
        If (i <= S[depth] and go[last][i]) Then
            result[depth] = i
            If (dfs(depth+1, i)) Then
                Return True
            End If
        End If
    End For
    Return False

但这个函数现在还是有问题的。

由于在该函数中,我们保证了每一位数字一定小于等于S的对应位。

比如当S=300时,用我们这个函数找出的最优解是200,而实际上可以打出299这个数字。

也就是说,当满足某一个条件后,最优解某些数位上的数字是可能大于S对应位的。

这个条件是:当答案的其中一位已经小于S的对应位时,这一位之后的数位可以选择任意一个数字。

为了保证答案尽可能大,因此在后面的数位上我们要选择能够移动到的最大数字。

再一次改进后的函数为:

dfs(depth, last, below):
    If depth >= length Then
        // 找到一个合法解
        // 由于我们总是从高到低对数字进行枚举,因此第一个找到的解一定是最大解
        Output(result)
        Return True
    End If
    If below == True Then
        // 已经有高位小于S的对应位置
        //将后面的数位填充为last能够移动到的最大数字
        result[depth..length-1] = max{i|go[last][i]==true}
        Output(result)
        Return True
    End If
    For i = 9 .. 0
        If (i <= S[depth] and go[last][i]) Then
            result[depth] = i
            If (dfs(depth+1, i, i < S[depth])) Then
                Return True
            End If
        End If
    End For
    Return False

到此,给出的dfs函数即可通过所有的测试点。

由于本题仍然是多组输入数据,所以一定要记得初始化。

9 answer(s)

1
为什么只有0分?
#include<cmath>

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

define ll long long

//作者:中国江苏南京丁天行 using namespace std; bool f[15][15]; int t,n,o; int a[505],ans[505]; bool b; bool cty(int k){ if(k==n+1) return 1; int u=b?9:a[k],y=o; bool v=0; for(int i=u;i>=0;i--){ if(i!=u&&!b)b=1,v=1; if(f[o][i]){ o=i; if(cty(k+1)){ o=y; b-=v; ans[k]=i; return 1; } o=y; } } b-=v; return 0; } int main() { f[1][2]=f[1][4]=f[2][3]=f[2][5]=f[3][6]=1;
f[4][5]=f[4][7]=f[5][6]=f[5][8]=f[6][9]=1; f[8][0]=1; for(int i=0;i<=9;i++)f[i][i]=1; for(int i=0;i<=10;i++){ for(int j=0;j<=10;j++){ for(int k=0;k<=10;k++)if(f[j][i]&&f[i][k])f[j][k]=1; } } scanf("%d",&t); while(t--){ char c=getchar(); while(c=='\n')c=getchar(); n=0; bool us=0; while(c!='\n'){ if(us||c!='0')a[++n]=c-'0',us=1; c=getchar(); } b=0; o=1; cty(1); int l=1; while(!ans[l]&&l

0

确实没找到哪有问题,谁能给点测试数据


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

#define maxn 600


char keypad[][10] ={
    "aaaaa",
    "a123a",
    "a456a",
    "a789a",
    "aa0aa",
    "aaaaa"
    };

bool isNext[20][20];

void Init(int x, int y)
{
    if(x==1 && y==1)
    {
        memset(isNext , false , sizeof(isNext));
    }

    isNext[keypad[x][y]-'0'][keypad[x][y]-'0'] = true;

    if(keypad[x+1][y] != 'a')
    {
        Init(x+1,y);
        for(int i=0; i<10; i++)
        {
            isNext[keypad[x][y]-'0'][i] |= isNext[keypad[x+1][y]-'0'][i];
        }
    }
    if(keypad[x][y+1] != 'a')
    {
        Init(x,y+1);
        for(int i=0; i<10; i++)
        {
            isNext[keypad[x][y]-'0'][i] |= isNext[keypad[x][y+1]-'0'][i];
        }
    }
}


int n;
bool isSlow;
int num[maxn];
int reNum[maxn];

bool Dfs(int index, int thumb)
{
    if(index == n)
    {
        return true;
    }

    if(!isSlow)
    {
        bool isFirst = true;
        for(int i=num[index]; i>=0; i--)
        {
            if(isNext[thumb][i])
            {
                if(!isFirst)
                {
                    isSlow = true;
                }
                isFirst = false;

                reNum[index] = i;
                if(Dfs(index+1, i))
                {
                    return true;
                }
            }
        }
        return false;
    }
    else
    {
        for(int i=index;i<n;i++)
        {
            reNum[i]=9;
        }
        return true;
    }
}



int main()
{
    Init(1,1);

    int t;
    char s[maxn];
    scanf("%d",&t);

    while(t--)
    {
        scanf("%s",s);
        n = strlen(s);
        for(int i=0;i<n;i++)
        {
            num[i] = s[i] - '0';
        }

        isSlow = false;
        Dfs(0,1);

        for(int i = 0; i< n; i++)
        {
            printf("%d",reNum[i]);
        }
        printf("\n");

    }


    return 0;
}
  • 这个例子12435432你的程序输出是12299999,应该是12399999

  • 谢谢帮助,问题解决了。 上面代码有两处问题,一处是对于每一位的第一次判断应该在if外面进行,另一个是在已经让了数的情况下,应还是按照按键规则取数,不应全取9.因为741这个例子,当第二位让为0时第三位只能取0而不是九,正确结果应该是700 bool Dfs(int index, int thumb) { if(index == n) { return true; } if(!isSlow) { bool isFirst = true; for(int i=num[index]; i>=0; i--) { if(!isFirst) { isSlow = true; } isFirst = false; if(isNext[thumb][i]) { reNum[index] = i; if(Dfs(index+1, i)) { return true; } } } return false; } else { for(int i=9;i>=0;i--) { if(isNext[thumb][i]) { reNum[index] = i; return Dfs(index+1,i); } } } }

  • 添加评论
  • reply
3

有人能帮我检查一下吗?自己的机器上调试了几个case,都没什么问题,但交上去就是WA,不知道哪里有问题,thanks!

#include <iostream>
#include <string>
using namespace std;

bool trans[10][10] = {
    {true,  false, false, false, false, false, false, false, false, false}, //0
    {true,  true,  true,  true,  true,  true,  true,  true,  true,  true }, //1
    {true,  false, true,  true,  false, true,  true,  false, true,  true }, //2
    {false, false, false, true,  false, false, true,  false, false, true }, //3
    {true,  false, false, false, true,  true,  true,  true,  true,  true }, //4
    {true,  false, false, false, false, true,  true,  false, true,  true }, //5
    {false, false, false, false, false, false, true,  false, false, true }, //6
    {true,  false, false, false, false, false, false, true,  true,  true }, //7
    {true,  false, false, false, false, false, false, false, true,  true }, //8
    {false, false, false, false, false, false, false, false, false, true }, //9
};

bool dfs(string& K, string& res, int depth, bool flag, int last)
{
    if (depth == K.length()) {
        return true;
    }

    if (flag) {
        int sub = K.length() - res.length();
        char ch = '9';
        if (res[depth] == '0') {
            ch = '0';
        }

        for (int i = 0; i < sub; i++) {
            res.push_back(ch);
        }

        return true;
    }

    for (int i = 9; i >=0 ; --i) {
        if (trans[last][i] && i <= K[depth] - '0') {
            res.push_back(('0' + i));

            if (dfs(K, res, depth + 1, res[depth] < K[depth], i)) {
                return true;
            }
            else {
                res.pop_back();
            }
        }
    }
    return false;
}

int main()
{
    int t = 0;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        string K;
        cin >> K;
        string res = "";
        dfs(K, res, 0, false, 1);
        cout << res << endl;
    }
}
  • 希望hihocoder能够提供像leetcode一样,给出错误case的功能

  • if (dfs(K, res, depth + 1, res[depth] < K[depth], i)) { return true; } else { res.pop_back(); } 这部分有问题,dfs的时候有可能push_back了很多字符,但是else里值pop_back一次。

  • 上面的pop_back没什么问题,因为会判断dfs的返回是不是true,错的是if (res[depth] == '0') { ch = '0';}出错了,depth要改成depth-1,就AC了~anyway, thanks

  • 添加评论
  • reply
0

include "string"

include "iostream"

include "cstring"

define MAX 600

using namespace std;

int T; char K[MAX]; int S[MAX]; int length; int result[MAX]; //go[i][j] = true,表示可以从数字i移动到数字j bool go[10][10] = {
{true, false, false, false, false, false, false, false, false, false}, //0 {true, true, true, true, true, true, true, true, true, true }, //1 {true, false, true, true, false, true, true, false, true, true }, //2 {false, false, false, true, false, false, true, false, false, true }, //3 {true, false, false, false, true, true, true, true, true, true }, //4 {true, false, false, false, false, true, true, false, true, true }, //5 {false, false, false, false, false, false, true, false, false, true }, //6 {true, false, false, false, false, false, false, true, true, true }, //7 {true, false, false, false, false, false, false, false, true, true }, //8 {false, false, false, false, false, false, false, false, false, true }, //9 };

bool dfs(int depth, int last, bool below) { int i, j; if(depth >= length) { /* // 找到一个合法解 // 由于我们总是从高到低对数字进行枚举,因此第一个找到的解一定是最大解 */ return true; }

if(below == true)
{
    /*
    已经有高位小于S的对应位置
    将后面的数位填充为last能够移动到的最大数字
    */
    for(j=9; j>=0; j--)
        if(go[last][j] == true)
            break;
    for(i=depth; i<length; i++)
        result[i] = j;

    return true;
}

for(i=9; i>=0; i--)
{
    if(i<=S[depth] && go[last][i])
    {
        result[depth] = i;
        if(dfs(depth+1, i, i < S[depth]))
            return true;
    }
}
return false;

}

int main() { scanf("%d", &T); int i, j; for(i=0; i> K; length = strlen(K); memset(result, -1, sizeof(S)); for(j=0; j

    dfs(0, S[0], false);
    if(result[1] == -1)  //如K = 300时,最高位为3-1=2
        dfs(0, S[0]-1, false);

    for(j=0; j<length; j++)
        cout << result[j];
    printf("\n");
}

return 0;

}

0
#include "string" 
#include "iostream"
#include "cstring"
#define MAX 600
using namespace std;

int T;
char K[MAX];
int S[MAX];
int length;
int result[MAX];
//go[i][j] = true,表示可以从数字i移动到数字j
bool go[10][10] = {  
{true,  false, false, false, false, false, false, false, false, false}, //0
{true,  true,  true,  true,  true,  true,  true,  true,  true,  true }, //1
{true,  false, true,  true,  false, true,  true,  false, true,  true }, //2
{false, false, false, true,  false, false, true,  false, false, true }, //3
{true,  false, false, false, true,  true,  true,  true,  true,  true }, //4
{true,  false, false, false, false, true,  true,  false, true,  true }, //5
{false, false, false, false, false, false, true,  false, false, true }, //6
{true,  false, false, false, false, false, false, true,  true,  true }, //7
{true,  false, false, false, false, false, false, false, true,  true }, //8
{false, false, false, false, false, false, false, false, false, true }, //9
};

bool dfs(int depth, int last, bool below)
{
int i, j;
if(depth >= length)
{
    /*
    // 找到一个合法解
    // 由于我们总是从高到低对数字进行枚举,因此第一个找到的解一定是最大解
    */
    return true;
}

if(below == true)
{
    /*
    已经有高位小于S的对应位置
    将后面的数位填充为last能够移动到的最大数字
    */
    for(j=9; j>=0; j--)
        if(go[last][j] == true)
            break;
    for(i=depth; i<length; i++)
        result[i] = j;

    return true;
}

for(i=9; i>=0; i--)
{
    if(i<=S[depth] && go[last][i])
    {
        result[depth] = i;
        if(dfs(depth+1, i, i < S[depth]))
            return true;
    }
}
 return false;
}

  int main()
 {
    scanf("%d", &T);
int i, j;
for(i=0; i<T; i++)
{
    cin >> K;
    length = strlen(K);
    memset(result, -1, sizeof(S));
    for(j=0; j<length; j++)
        S[j] = K[j] - '0';

    dfs(0, S[0], false);
    if(result[1] == -1)  //如K = 300时,最高位为3-1=2
        dfs(0, S[0]-1, false);

    for(j=0; j<length; j++)
        cout << result[j];
    printf("\n");
}

return 0;
}
  • 不知为什么,只得了20分

  • dfs(0, S[0], false); 改成 dfs(0, 1, false); 然后去掉if(result[1] == -1) dfs(0, S[0]-1, false);

  • 嗯,是的,谢谢啊

  • 添加评论
  • reply
0

WA, can't find reason

 #include <iostream>
 #include <string>
 using namespace std;

bool g[10][10]=
    {{true,  false, false, false, false, false, false, false, false, false}, //0
    {true,  true,  true,  true,  true,  true,  true,  true,  true,  true }, //1
    {true,  false, true,  true,  false, true,  true,  false, true,  true }, //2
    {false, false, false, true,  false, false, true,  false, false, true }, //3
    {true,  false, false, false, true,  true,  true,  true,  true,  true }, //4
    {true,  false, false, false, false, true,  true,  false, true,  true }, //5
    {false, false, false, false, false, false, true,  false, false, true }, //6
    {true,  false, false, false, false, false, false, true,  true,  true }, //7
    {true,  false, false, false, false, false, false, false, true,  true }, //8
    {false, false, false, false, false, false, false, false, false, true } //9
};

bool getmaxnumber(string &s,string &t, bool flage,int depth, int last){
    if(flage){ // 如果高位t已经小于s ,补9
        for(int i=0; i<s.size()-depth; i++)
            t.push_back('9');
        return true;
    }
    if(depth==s.size()) return true;
    if(depth!=0 && t[depth-1]=='0'){
        for(int i=0; i<s.size()-depth;i++){
            t.push_back('0');
        }
        return true;
    }
    for(int i = s[depth]-'0';i>=0; i--){
        if(g[last][i]){ 
            t.push_back(char(i+'0'));
            if(s[depth]>t[depth]) flage = true;
            if(getmaxnumber(s,t,flage,depth+1,i)) return true;
            else{
                t.pop_back();
            }
        }
    }
    return false;
}

int main(){
    int N;
    string s;
    cin>>N;
    while(N--){
        cin>>s;
        string t="";
        getmaxnumber(s,t,false,0,1);
        cout<<t<<endl;
    }
    return 0;
}
  • “如果高位t已经小于s ,补9” 这里不见得一定补9。

  • 添加评论
  • reply
0

感觉把矩阵变成每个数字后面可出现数字的集合,并排序会更简单些

int keysNexts[N][N] = 
{
    {0},
    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
    {0, 2, 3, 5, 6, 8, 9, 9, 9, 9},
    {3, 6, 9, 9, 9, 9, 9, 9, 9, 9},
    {0, 4, 5, 6, 7, 8, 9, 9, 9, 9},
    {0, 5, 6, 8, 9, 9, 9, 9, 9, 9},
    {6, 9, 9, 9, 9, 9, 9, 9, 9, 9},
    {0, 7, 8, 9, 9, 9, 9, 9, 9, 9},
    {0, 8, 9, 9, 9, 9, 9, 9, 9, 9},
    {9, 9, 9, 9, 9, 9, 9, 9, 9, 9}
};
0

请问dfs的初始状态last为什么不能是s[0],什么样的测点不能通过啊,求解,想不通。。。

0

C#的一直WA,有没有高人看一下

using System;
using System.Collections.Generic;

public class test{
    private static Dictionary<int,HashSet<int>> dic=null;
    private static void Main(){
        dic = createDic();
        int count = 0;
        string line;
        if ((line = Console.ReadLine()) != null)
        {
            count = int.Parse(line);
            //string[] total = new string[count];
            for (int i = 0; i < count; i++)
            {
                if ((line = Console.ReadLine()) != null)
                {
                    Console.WriteLine(Output(line));
                }
            }

        }
}

private static Dictionary<int,HashSet<int>> createDic(){
    Dictionary<int,HashSet<int>> dic=new  Dictionary<int,HashSet<int>>();
    dic.Add(0,new HashSet<int>(){0});
    dic.Add(1,new HashSet<int>(){1,2,3,4,5,6,7,8,9,0});
    dic.Add(2,new HashSet<int>(){2,3,5,6,8,9,0});
    dic.Add(3,new HashSet<int>(){3,6,9});
    dic.Add(4,new HashSet<int>(){4,5,6,7,8,9,0});
    dic.Add(5,new HashSet<int>(){5,6,8,9,0});
    dic.Add(6,new HashSet<int>(){6,9});
    dic.Add(7,new HashSet<int>(){7,8,9,0});
    dic.Add(8,new HashSet<int>(){8,9,0});
    dic.Add(9,new HashSet<int>(){9});
    return dic;
}

private static string Output(string x){
    int length=x.Length;
    char[] chars=x.ToCharArray();
    if (length==1){
        return x;
    }
    for(int i=1;i<length;i++){
        int a=x[i-1]-'0';
        int b=x[i]-'0';
        int max=-1;
        if (!dic[a].Contains(b)){
            foreach(int k in dic[a]){
                if (k<b && k>=max){
                    max=k;
                }
            }
            if (max==-1){
                chars[i-1]=(char)(a-1+48);
                for(int j=i;j<length;j++){
                    chars[j]='9';
                }
            }else if (max==0){
                for(int j=i;j<length;j++){
                    chars[j]='0';
                }
            }else{
                chars[i]=(char)(max+48);
                for(int j=i+1;j<length;j++){
                    chars[j]='9';
                }
            }
            return new string(chars);
        }
    }
    return new string(chars);
}

}

write answer 切换为英文 切换为中文


转发分享