ZOJ Monthly, November 2010解题报告 » ZOJ3436

ZOJ3436
ZOJ3436.cpp


#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int ten[] = {
	1,
	10,
	100,
	1000,
	10000,
	100000,
	1000000,
	10000000,
	100000000,
	1000000000
};

vector<int> v;

void gen(int n, int d, int x, int y) {
	if (0 <= d && d < 10) {
		--n;
		y += d;
		if (n == 0) {
			v.push_back(y);
		} else {
			int t = x / ten[n - 1];
			x -= t * ten[n - 1];
			y *= 10;
			gen(n, d - t, x, y);
			gen(n, d + t, x, y);
		}
	}
}

int main() {
	int x, y;
	vector<int> a(1, 6);

	for (int l = 2; l <= 9; ++l) {
		v.clear();
		for (vector<int>::const_iterator i = a.begin(); i != a.end(); ++i) {
			for (int d = 1; d <= 9; ++d) {
				gen(l, d, *i, 0);
			}
		}
		a.insert(a.end(), v.begin(), v.end());
		sort(a.begin(), a.end());
		a.erase(unique(a.begin(), a.end()), a.end());
	}
//	for (int i = 0; i < (int)a.size(); ++i) {
//		printf("%d\n", a[i]);
//	}
//	printf("%d\n", a.size());
//	return 0;
	while (scanf("%d%d", &x, &y) != EOF) {
		printf("%d\n", upper_bound(a.begin(), a.end(), y) - lower_bound(a.begin(), a.end(), x));
	}

	return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//377 	2010-11-10 01:10:40 	Accepted 	J 	C++ 	340 	7360 	watashi@Zodiac 	Source
8 Responses to “ZOJ3436”
  1. Zh says:

    void gen(int n, int d, int x, int y) 请问这四个参数都是做什么,有点没看懂。

  2. Yuan says:

    请问下神牛
    这题,我用你的代码在本地运行了下,初始化要20,30秒
    我自己写的就10几秒,但我那个交上去超时了,不过我用了一些map,不知哪里超时了

    这一句
    40 vector a(1, 6);
    应该是a(1, 7);

  3. zt says:

    好精简的代码,佩服佩服

  4.  
Leave a Reply