首页 > ACM题库 > HDU-杭电 > hdu 2410 Barbara Bennett’s Wild Numbers-模拟-[解题报告]C++
2014
01-26

hdu 2410 Barbara Bennett’s Wild Numbers-模拟-[解题报告]C++

Barbara Bennett’s Wild Numbers

问题描述 :

A wild number is a string containing digits and question marks (like 36?1?8). A number X matches a wild number W if they have the same length, and every non-question mark character in X is equal to the character in the same position in W (it means that you can replace a question mark with any digit). For example, 365198 matches the wild number 36?1?8, but 360199, 361028, or 36128 does not. Write a program that reads a wild number W and a number X from input, both of length n, and determines the number of n-digit numbers that match W and are greater than X.

输入:

There are multiple test cases in the input. Each test case consists of two lines of the same length. The first line contains a wild number W, and the second line contains an integer number X. The length of input lines is between 1 and 10 characters. The last line of input contains a single character #.

输出:

There are multiple test cases in the input. Each test case consists of two lines of the same length. The first line contains a wild number W, and the second line contains an integer number X. The length of input lines is between 1 and 10 characters. The last line of input contains a single character #.

样例输入:

36?1?8
236428
8?3
910
?
5
#

样例输出:

100
0
4

题意:将W中的?换成数字,在所有这些数字中求W>X的个数,模拟,

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int main()
{
    freopen("in.txt","r",stdin);
    int ans,len;
    char a[20],b[20];
    while(1)
    {
        scanf("%s%s",a+1,b+1);
        if(a[1]=='#') break;
        ans = 0;
        len = strlen(a+1)+2;
        int f= 0;
        int dp[20][2];
        memset(dp,0,sizeof(dp));
        a[len-1] = '0';
        b[len-1] = '1';
        for(int i=1; i<len; i++)
        {
            if(f==0)
            {
                if(a[i]=='?')
                {
                    dp[i][0] = dp[i-1][0]*10+('9'-b[i]);
                    dp[i][1] = 1;
                }
                else
                {
                    if(a[i]>b[i])
                    {
                        f=1;
                        dp[i][0]=max(dp[i-1][0]+dp[i-1][1],1);
                    }
                    else if(a[i]<b[i])
                    {
                        f=-1;
                        dp[i][0]=dp[i-1][0];
                    }
                    else
                    {
                        dp[i][0] = dp[i-1][0];
                        dp[i][1] = dp[i-1][1];
                    }
                }
            }
            else
            {
                if(a[i]=='?')
                    dp[i][0]=dp[i-1][0]*10;
                else
                    dp[i][0]=dp[i-1][0];
            }
        }
        printf("%d\n",dp[len-1][0]);
    }
    return 0;
}

解题转自:http://blog.csdn.net/binwin20/article/details/7833943


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环