| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
布吉岛,直接算是O(lg n),都要94ms,估计数据组数比较多。另外这题用不着dp啊(附代妈)In Reply To:写了个数位dp,还是超时,这个数据到底有几组阿? Posted by:201907 at 2016-07-14 16:15:09 #include <iostream>
#include <stdio.h>
using namespace std;
long long int mi10[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
int main() {
while(1){
long long int low, high;
cin >> low >> high;
if(low == -1 && high == -1) break;
long long int res = 0;
if(low == 0){
low ++;
res ++;
}
res += high/10 - (low-1)/10;
for(int i = 1; i < 9; i++){
long long int i1, j1, i2, j2;
i1 = low/mi10[i+1];
i2 = high/mi10[i+1];
j1 = low%mi10[i+1];
j2 = high%mi10[i+1];
if(i2 == 0) break;
if(i1 == 0){
i1 = 1;
j1 = 0;
}
long long int zhengtou, zhengwei;
zhengwei = i2 - 1;
if(j1 == 0) zhengtou = i1;
else zhengtou = i1+1;
long long int gs = zhengwei - zhengtou + 1;
res += gs * mi10[i];
if(j2 >= mi10[i]) res += mi10[i];
else res += (j2+1);
if(j1 < mi10[i] && j1 > 0) res += (mi10[i] - j1);
}
cout << res << endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator