首页 > ACM题库 > HDU-杭电 > HDU 3443-Shift Number[解题报告]HOJ
2014
03-23

HDU 3443-Shift Number[解题报告]HOJ

Shift Number

问题描述 :

If a number is the sum of an integer’s several shifting forms, it is called the Shift Number.
For example, by shifting 123 four times and adding the four numbers together, we get 136653, which is a Shift Number.
However, a shift number may be the sum of more than one integer’s shifting forms. Such as, 45177 is a Shift Number, which could be generated from both 407 and 4107.
123+1230+12300+123000=136653
407+4070+40700=45177
4107+41070=45177
Given a Shift Number x , would you please help us find the least integer which could generate x by shifting.

输入:

A shift number x.
Input ends with x=0.

输出:

A shift number x.
Input ends with x=0.

样例输入:

136653
45177
0

样例输出:

123
407
Hint

If you are not familiar with “long long”, you can consult to FAQ.

【题目大意】

一个整数右移若干次,每次得到的数相加得到的和,称为shift number。例如:

123+1230+12300+123000=136653
407+4070+40700=45177
4107+41070=45177

可见45177可有多个数转移相加得到。

给定shift 数 n,求按此规则能得到n的最小的数。

【解题思路】

以136653和45177为例:

136653=123*1+123*10+123*100+123*1000=123*(1+10+100+1000)=123*1111

45177=407*1+407*10+407*100=407*(1+10+100)=407*111

可知,每个shift数是111···的倍数。推出这些,代码就简单了。

#include <cstdio>
#define LL __int64
int main()
{
    LL x,k;
    while(scanf("%I64d",&x)&&x){
        k=1;
        while(k<x)k=k*10+1;
        k/=10;
        while(x%k!=0)k/=10;
        printf("%I64d/n",x/k);
    }
    return 0;
}

解法2:

/* 
 * File: main.cpp
 * Author: Prowindy
 *
 * Created on 2011��10��17��, ����2:21
 */

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
/*
 * 
 */
char str[100000];
char s[100000];
int Len;
vector<int> ans[100000];
int ansT;

void check(int cnt) {
 int i,j,carry;
 s[0] = str[0];
 carry = 0;
 for (i = 1; i < Len; i++) {
 int tmp = 0;
 for (j = 1; j <= min(i, cnt - 1); j++)
 tmp += s[i - j];
 s[i] = (str[i] + 10 - tmp % 10 + 10 - carry % 10) % 10;
 carry = (carry + s[i] + tmp) / 10;
 }
 int tmp = 0;
 for (j = 1; j <= min(i, cnt - 1); j++)
 tmp += s[i - j];
 if (tmp + carry == 0) {
 ansT++;
 ans[ansT].clear();
 for (j = Len - 1; j >= 0; j--)
 ans[ansT].push_back(s[j]);
 }
}

int main(int argc, char** argv) {
 int i,len;
 while (gets(str)) {
 if (strcmp(str, "0") == 0) break;
 Len = strlen(str);
 ansT = -1;
 reverse(str, str + Len);
 for (i = 0; i < Len; i++)
 str[i] -= '0';
 for (len = 1; len <= Len; len++) {
 check(len);
 }
 sort(ans,ans+ansT+1);
 i = 0;
 while(ans[0][i]==0) i++;
 for (;i<ans[0].size();i++)
 printf("%c",ans[0][i]+'0');
 printf("\n");

 }
 return (EXIT_SUCCESS);
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。