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