HDU 5936 Difference(折半列挙)
Difference
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1247 Accepted Submission(s): 335
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 K, x 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 x, K.
Limits 1≤T≤100 0≤x≤109 1≤K≤9
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
テーマの大意
2つの正の整数x,k(0⩽x⩽109,1⩽k⩽9)を入力、yの各数字のk次方からyを減算xに等しい正の整数yがどれだけあるかを問う.
問題を解く構想.
問題はyのデータ範囲を与えていないが,yが大きい場合に計算した結果が負数であることから,yは最大10桁の数字しか推定できないことが分かった.これを知ってから最も暴力的な方法を考えることができて、毎回すべての可能なyを列挙して、答えを統計します.これでTLEになるのは間違いありませんが、yの数字の答えへの貢献は互いに独立していることがわかります.だから、折半検索を使って、列挙後の5桁に1枚の表を打って、上位の5桁を列挙して後で検索することを考えることができます.総複雑度O(105⋅log 105).最後にもう1つの最適化があり,kは9つの可能性しかなく,テストグループ数は100グループあるので,各kの場合の後5ビットのテーブルを先に処理することができる.問題に注意しなければならない穴はもう一つあります.問題面はyが正の整数だと言っているので、x=0の場合、y=0を追加的に減らす案が必要です.
ACコード
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1247 Accepted Submission(s): 335
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 K, x 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 x, K.
Limits 1≤T≤100 0≤x≤109 1≤K≤9
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
テーマの大意
2つの正の整数x,k(0⩽x⩽109,1⩽k⩽9)を入力、yの各数字のk次方からyを減算xに等しい正の整数yがどれだけあるかを問う.
問題を解く構想.
問題はyのデータ範囲を与えていないが,yが大きい場合に計算した結果が負数であることから,yは最大10桁の数字しか推定できないことが分かった.これを知ってから最も暴力的な方法を考えることができて、毎回すべての可能なyを列挙して、答えを統計します.これでTLEになるのは間違いありませんが、yの数字の答えへの貢献は互いに独立していることがわかります.だから、折半検索を使って、列挙後の5桁に1枚の表を打って、上位の5桁を列挙して後で検索することを考えることができます.総複雑度O(105⋅log 105).最後にもう1つの最適化があり,kは9つの可能性しかなく,テストグループ数は100グループあるので,各kの場合の後5ビットのテーブルを先に処理することができる.問題に注意しなければならない穴はもう一つあります.問題面はyが正の整数だと言っているので、x=0の場合、y=0を追加的に減らす案が必要です.
ACコード
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
#define mem(a,b) memset((a),(b),sizeof(a))
const int ten[]={1, 10, 100, 1000, 10000, 100000};
int X, K;
int Pow[13][13];//i j
mapint > cnt[10];// i
void pre_work()//
{
for(int i=0;i<=9;++i)
{
Pow[i][0]=1;
for(int j=1;j<=9;++j)
Pow[i][j]=Pow[i][j-1]*i;
}
for(int k=1;k<=9;++k)// k
{
for(int i=0;i<=99999;++i)// 5
{
LL res=-i;
for(int j=0;j<=4;++j)
res+=Pow[i/ten[j]%10][k];
++cnt[k][res];
}
}
}
int main()
{
pre_work();
int T_T;
scanf("%d", &T_T);
for(int cas=1;cas<=T_T;++cas)
{
scanf("%d%d", &X, &K);
LL ans=0;
for(int i=0;i<=99999;++i)// 5
{
LL res=-i*100000ll;
for(int j=0;j<=4;++j)
res+=Pow[i/ten[j]%10][K];
LL obj=X-res;
if(cnt[K].find(obj)!=cnt[K].end())
ans+=cnt[K][obj];
}
if(X==0)// X==0
--ans;
printf("Case #%d: %lld
", cas, ans);
}
return 0;
}