【codeforces 758D】Ability To Convert
2024-08-31 02:38:55
【题目链接】:http://codeforces.com/contest/758/problem/D
【题意】
给你一个n进制的数k;
问你它可能的最小的十进制数是多少;
【题解】
从右往左;
获取数字;
如果这个数字小于n就一直往左扩大;
尽量大;
这样把尽可能多的数字放在权值的低位;
这样n进制数的位就会尽可能地少;
十进制数也就尽可能地小了;
但是有前导0的情况;
这个判断前导0有点麻烦;
即
10011
你不好获取
0011这个数字的信息;
即是不是到了从右往左数第二个0的时候,就该停下来了;
这个可以先预处理出101..12
然后看看当前处理的数字的可能最小值是不是小于n;如果最小的都大于等于n了就不用继续了;
必须得这样做不然对于
2
10000000000000000000000000
这样的数据;
如果你算到了第一个数字才发觉大于n了;
那么你算出来的数字 10000000000000000000000000可能会爆long long
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define ps push_back
#define fi first
#define se second
#define rei(x) cin >> x
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
int n;
char s[100];
LL temp = 1,ans = 0,tenpow[15];
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false);
rei(n);
cin >> (s+1);
int len = strlen(s+1),pre = len;
LL dd = 0,now = 1;
tenpow[0] = 1;
rep1(i,1,12)
tenpow[i] = tenpow[i-1]*10;
rep2(i,len,1)
{
LL tdd = dd+now*(s[i]-'0');
LL ju = (pre-i+1);
now=now*10;
if ((s[i]!='0' ||(s[i]=='0' && tenpow[ju]<n)||i==len )&& tdd<n)
{
dd = tdd;
}
else
//tdd>=n
{
int j = i+1;
while (s[j]=='0' && j+1<=pre)
{
j++;
}
ans += dd*temp;
temp=temp*n;
i = j-1;
pre = i;
dd = s[i]-'0';
now = 10;
}
}
ans += dd*temp;
cout << ans << endl;
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
最新文章
- Memcached初探
- socket (一)
- c++初步实现的一个LRU
- 关于tomcat小知识
- Java最全文件操作实例汇总
- Xcode插件管理以及Xcode7 升级
- 转:sql server索引碎片和解决方法
- Android实例-为程序创建快捷方式(未测试)
- 在VS Nuget命令行下进行EF数据库迁移
- Unity3D中的Coroutine详解
- JMeter基础概念
- C# devExpress GridControl 行中行 子行 多级行
- Hibernate 再接触 性能优化
- Linux上强制踢出其他正在登录的用户
- 收集到的关于 freeCodeCamp 中文社区
- 更优雅的使用Git
- JS—-this指向
- BZOJ1002輪狀病毒 暴搜 + 找規律 + 高精度
- hiho 1015 KMP算法 &;&; CF 625 B. War of the Corporations
- Windows 7 下 Node.js 连接 Oracle