首页 > ACM题库 > HDU-杭电 > HDU 3925-Substring-数论-[解题报告]HOJ
2015
04-14

HDU 3925-Substring-数论-[解题报告]HOJ

Substring

问题描述 :

Give you two number a, b. Output the smallest number that can be added to a to contain the number b as a substring.

输入:

The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: Two number a,b;
  0 <= a <= 10^100, 0 <= b <= 10^7

输出:

The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: Two number a,b;
  0 <= a <= 10^100, 0 <= b <= 10^7

样例输入:

2
9 1
9 2

样例输出:

Case #1: 1
Case #2: 3

从a的最低位开始枚举和B比较。

import java.math.BigInteger;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner cin = new Scanner(System.in);
        BigInteger zero = BigInteger.valueOf(0);
        BigInteger ten = BigInteger.valueOf(10);
        int i, j, ncase;
        BigInteger a, b, min;
        ncase = cin.nextInt();
        for(j=1;j<=ncase;j++)
        {
            min = new BigInteger("99999999999999999999999999");
            a = cin.nextBigInteger();
            b = cin.nextBigInteger();
            if (a.toString().indexOf(b.toString()) != -1)//a包含b
            {
                min = zero;
            }
            else
            {
                BigInteger tmp1, tmp2;
                for (i = b.toString().length(); i <= 105; i++)
                {
                    tmp1 = a.mod(ten.pow(i));//a的后几位
                    if(tmp1.compareTo(b)==0) 后几位和b相等
                    {
                        min=zero;
                        break;
                    }
                    else if(tmp1.compareTo(b)==-1)//小于b
                    {
                        tmp2 = b.subtract(tmp1);
                        if(tmp2.compareTo(min)==-1)
                        {
                            min=tmp2;
                        }
                    }
                    else //大于b,在b的前面加1
                    {
                        tmp2 = b.add(ten.pow(b.toString().length()));
                        tmp2 = tmp2.subtract(tmp1);
                        if (tmp2.compareTo(min) == -1&& tmp2.compareTo(zero) != -1)
                        {
                            min = tmp2;
                        }
                    }
                    b = b.multiply(ten);//b乘以10
                }
                
            }
            System.out.println("Case #" + j +": " + min);
        }
    }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/chl_3205/article/details/8874183


  1. 这个方法是错的,不信你试试:
    20 5
    1 A:9
    1 A:9
    1 A:9
    1 A:6
    1 A:4
    正确答案应该是19,这个答案是18

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  4. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  5. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?