Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

布吉岛,直接算是O(lg n),都要94ms,估计数据组数比较多。另外这题用不着dp啊(附代妈)

Posted by KatrineYang at 2016-07-15 09:03:28 on Problem 3286
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator