在讲进制转换的题之前,先说一个qpow的问题。
//WA
ll qpow(int a,int k)
{
ll ans=1;
while(k){
if(k&1) ans=ans*(1l*a);
a*=a;
k>>=1;
}
return ans;
}
这段程序错误的地方就在于传入的是两个int数,在while循环语句中,会出现相乘爆int(即使是在赋值给ll的过程中)。
先贴前两天个人赛的一道进制转换。
题意就是给你一个进制n和一个在n进制下的数s。其中大于9的数字不会用A,B,C...表示,让你求这串数字可能的最小的十进制数。
我WA的想法是从后往前,每次在s中取len(n)长度,然后转换成十进制数字,比较与n的大小关系。这样会造成一个问题,就是比如n=124 s=123456789,我在取的时候在123就会退出,然后一个一个pow上去。
而这个A的代码,用tmp记录取出的数字的大小,用j判断是否因为0过多而造成爆ll(如果因为前导的0爆掉的话在第一个while和if将i移送至正确位置并标记),真正记录答案位数的是k!
/********************************
Author: Audrey_H
Motto:talk is cheap,show me the code.
********************************/
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#define lowbit(x) (x&(-x))
#define ll long long
#define PI acos(-1.0)
#define FILEIN freopen("in.txt","r",stdin)
#define FILEOUT freopen("out.txt","w",stdout)
#define CLR(x) memset(x,0,sizeof(x))
#define mem(a,x) memset(a,x,sizeof(a))
#define debug printf("!!");
const int INF = 0x3f3f3f3f;
using namespace std;
//const double eps = 1e-6;
const ll mod = 1e9+7;
const int maxn = 1e6+100;
const int maxe = 1e6+100;
using namespace std;
ll n;
ll m;
int vis[1005];
ll qpow(ll a,ll b)
{
ll ans=1;
while(b){
if(b&1) ans*=a;
a*=a;
b>>=1;
}
return ans;
}
void Solve()
{
int n;
string a;
cin>>n>>a;
int len=a.size();
ll ans=0; ll tmp=0; ll k=0;
CLR(vis);
int j=0;
for(int i=len-1;i>=0;i--){
if(j>=18 || tmp+(a[i]-'0')*qpow(10,j)>=n){
i++;
while(a[i]=='0'&&!vis[i]&&i<len-1) i++;
if(i-1>=0&&a[i-1]=='0') vis[i-1]=1;
ans+=tmp*qpow(n,k); k++;
j=0; tmp=0;
continue;
}
tmp+=(a[i]-'0')*qpow(10,j);
j++;
}
ans+=tmp*qpow(n,k);
printf("%I64d\n",ans);
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
//100
//1000000
//1000000000000 WA
//100000000000 AC
网友评论