首页 > 代码库 > HDU 5936 Difference 【中途相遇法】(2016年中国大学生程序设计竞赛(杭州))

HDU 5936 Difference 【中途相遇法】(2016年中国大学生程序设计竞赛(杭州))

Difference

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 62    Accepted Submission(s): 19


Problem Description
Little Ruins is playing a number game, first he chooses two positive integers y and K and calculates f(y,K), here

f(y,K)=z in every digits of yzK(f(233,2)=22+32+32=22)


then he gets the result

x=f(y,K)?y


As Ruins is forgetful, a few seconds later, he only remembers Kx and forgets y. please help him find how many y satisfy x=f(y,K)?y.
 

 

Input
First line contains an integer T, which indicates the number of test cases.

Every test case contains one line with two integers xK.

Limits
1T100
0x109
1K9
 

 

Output
For every test case, you should output ‘Case #x: y‘, where x indicates the case number and counts from 1 and y is the result.
 

 

Sample Input
2 2 2 3 2
 

 

Sample Output
Case #1: 1 Case #2: 2
 

 

Source
2016年中国大学生程序设计竞赛(杭州)
 

 

Recommend
liuyiding   |   We have carefully selected several similar problems for you:  5947 5946 5945 5944 5942 
 

 

Statistic | Submit | Discuss | Note

 

题目链接:

  http://acm.hdu.edu.cn/showproblem.php?pid=5936

题目大意:

  技术分享(y每位上的数字的K次幂之和)

  X=f(y,K)-y。现在给定X和K,求有多少Y满足题意。

  数据范围 技术分享

题目思路:

  【中途相遇法】

  数据范围x在[0,109],y的位数不会超过10位。

  所以想直接对半分,先枚举前5位,记下相应的值,再枚举后5位,与前面的匹配看是否能够凑成x,最后统计答案即可。

  一开始用map写,T了。一脸懵逼。

  后来改成将每个出现的值都记下来,排序,正反扫一遍。。过了。

  可以预处理一些操作、运算。

 

技术分享
  1 //
  2 //by coolxxx
  3 //#include<bits/stdc++.h>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<string>
  7 #include<iomanip>
  8 #include<map>
  9 #include<stack>
 10 #include<queue>
 11 #include<set>
 12 #include<bitset>
 13 #include<memory.h>
 14 #include<time.h>
 15 #include<stdio.h>
 16 #include<stdlib.h>
 17 #include<string.h>
 18 //#include<stdbool.h>
 19 #include<math.h>
 20 #pragma comment(linker,"/STACK:1024000000,1024000000")
 21 #define min(a,b) ((a)<(b)?(a):(b))
 22 #define max(a,b) ((a)>(b)?(a):(b))
 23 #define abs(a) ((a)>0?(a):(-(a)))
 24 #define lowbit(a) (a&(-a))
 25 #define sqr(a) ((a)*(a))
 26 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
 27 #define mem(a,b) memset(a,b,sizeof(a))
 28 #define eps (1e-8)
 29 #define J 10000
 30 #define mod 1000000007
 31 #define MAX 0x7f7f7f7f
 32 #define PI 3.14159265358979323
 33 #define N 14
 34 #define M 100004
 35 using namespace std;
 36 typedef long long LL;
 37 double anss;
 38 LL aans;
 39 int cas,cass;
 40 int n,m,lll,ans;
 41 LL e[N];
 42 LL mi[N][N],c[N][M],d[N][M];
 43 bool cmp(int a,int b)
 44 {
 45     return a<b;
 46 }
 47 void init()
 48 {
 49     int i,j;
 50     for(e[0]=1,i=1;i<11;i++)e[i]=e[i-1]*10;
 51     for(i=0;i<10;i++)
 52     {
 53         mi[i][0]=1;
 54         for(j=1;j<10;j++)mi[i][j]=mi[i][j-1]*i;
 55     }
 56     for(j=1;j<10;j++)
 57     {
 58         for(i=0;i<e[5];i++)
 59             c[j][i]=mi[i/e[4]][j]+mi[i%e[4]/e[3]][j]+mi[i%e[3]/e[2]][j]+mi[i%e[2]/e[1]][j]+mi[i%e[1]][j]-i*e[5],
 60             d[j][i]=mi[i/e[4]][j]+mi[i%e[4]/e[3]][j]+mi[i%e[3]/e[2]][j]+mi[i%e[2]/e[1]][j]+mi[i%e[1]][j]-i;
 61         sort(c[j],c[j]+e[5],cmp);
 62         sort(d[j],d[j]+e[5],cmp);
 63     }
 64 }
 65 int main()
 66 {
 67     #ifndef ONLINE_JUDGE
 68 //    freopen("1.txt","r",stdin);
 69 //    freopen("2.txt","w",stdout);
 70     #endif
 71     int i,j,k;
 72     int x,y,z;
 73     init();
 74 //    for(scanf("%d",&cass);cass;cass--)
 75     for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
 76 //    while(~scanf("%s",s))
 77 //    while(~scanf("%d%d",&n,&m))
 78     {
 79         printf("Case #%d: ",cass);
 80         ans=0;
 81         scanf("%d%d",&n,&m);
 82         for(i=0,j=e[5]-1;i<e[5] && j;)
 83         {
 84             if(c[m][i]+d[m][j]>n)j--;
 85             else if(c[m][i]+d[m][j]<n)i++;
 86             else
 87             {
 88                 x=y=1;
 89                 while(c[m][++i]==c[m][i-1] && i<e[5])x++;
 90                 while(d[m][--j]==d[m][j+1] && j)y++;
 91                 ans+=x*y;
 92             }
 93         }
 94         printf("%d\n",ans-(n==0));
 95     }
 96     return 0;
 97 }
 98 /*
 99 //
100 
101 //
102 */
View Code

 

HDU 5936 Difference 【中途相遇法】(2016年中国大学生程序设计竞赛(杭州))