程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 478E Wavy numbers

CodeForces 478E Wavy numbers

編輯：C++入門知識

CodeForces 478E Wavy numbers

題意：

如果一個數它的每一位（除了最高最低位）都大於或小於它兩邊的數字則這個數字叫波浪數輸入n和k （10^14）求%n==0的第k小的波浪數如果沒有或者大於10^14就輸出-1

思路：

這也算是一種分治的搜索策略吧 meet-in-mid

由於數字最多14位因此可以暴力高7位和低7位（均為80+w種）然後枚舉高位和低位去拼

這題對於代碼書寫要求較高！！我的方法如下：

暴力高7位

暴力低7為放進vector 同時記錄對於一個number 它的首位和首位與第二位大小情況（為了拼接）同時做一個hash 記錄cnt[i][j][k] 其中i為number首位 j為0或1表示首位與第二位大小情況 k為number%n的余數的hash值（為了方便查找）cnt記錄ijk情況的number個數

然後開始尋找答案

枚舉高7位的number 表示只有不用拼接的情況

判斷n是否大於等於10^7 如果是那麼只要i=n開始不斷的+n就可以找數字了

如果不是枚舉高7位再枚舉低7位的首位利用剛才記錄的cnt不斷的使k減小直到確定了高7位後暴力低7位拼答案

注意：hash不能用map 會TLE 在叉姐的提醒下我改成了離散再hash（因為種類不多！！）現在是CF上跑的最快的代碼哈哈哈哈哈哈哈~~~

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define N 850000
#define M 10000000

LL n, k;
int tothigh;
int anshigh[N];
vector anslow[10][2];
int id, to[M], cnt[10][2][N];
int dig[10];

void get_high(int bit) {
	int num = 0, i = bit;
	while (i) {
		num = num * 10 + dig[i];
		i--;
	}
	anshigh[tothigh++] = num;
}

void find_high(int bit) {
	for (int i = 0; i <= 9; i++) {
		if (i != dig[bit - 1]) {
			if (bit <= 2
					|| (bit > 2
							&& ((i > dig[bit - 1] && dig[bit - 2] > dig[bit - 1])
									|| (i < dig[bit - 1]
											&& dig[bit - 2] < dig[bit - 1])))) {
				dig[bit] = i;
				if (i)
					get_high(bit);
				if (bit < 7)
					find_high(bit + 1);
			}
		}
	}
}

void get_low() {
	int num = 0, i = 7;
	while (i) {
		num = num * 10 + dig[i];
		i--;
	}
	if (dig[7] < dig[6]) {
		anslow[dig[7]][0].push_back(num);
		if (!to[num % n])
			to[num % n] = ++id;
		cnt[dig[7]][0][to[num % n]]++;
	} else {
		anslow[dig[7]][1].push_back(num);
		if (!to[num % n])
			to[num % n] = ++id;
		cnt[dig[7]][1][to[num % n]]++;
	}
}

void find_low(int bit) {
	for (int i = 0; i <= 9; i++) {
		if (i != dig[bit - 1]) {
			if (bit <= 2
					|| (bit > 2
							&& ((i > dig[bit - 1] && dig[bit - 2] > dig[bit - 1])
									|| (i < dig[bit - 1]
											&& dig[bit - 2] < dig[bit - 1])))) {
				dig[bit] = i;
				if (bit == 7)
					get_low();
				else
					find_low(bit + 1);
			}
		}
	}
}

bool check(LL x) {
	int a = x % 10;
	x /= 10;
	int b = x % 10;
	x /= 10;
	while (x) {
		int c = x % 10;
		x /= 10;
		if ((b > a && b > c) || (b < a && b < c))
			;
		else
			return false;
		a = b;
		b = c;
	}
	return true;
}

int main() {
	scanf("%lld%lld", &n, &k);
	dig[0] = -1;
	find_high(1);
	find_low(1);
	sort(anshigh, anshigh + tothigh);
	for (int i = 0; i < tothigh; i++) {
		if (anshigh[i] % n == 0) {
			k--;
			if (!k) {
				printf("%d\n", anshigh[i]);
				return 0;
			}
		}
	}
	if (n >= M) {
		for (LL i = n; i <= 100000000000000LL; i += n) {
			if (check(i)) {
				k--;
				if (!k) {
					printf("%lld\n", i);
					return 0;
				}
			}
		}
	} else
		for (int i = 0; i < tothigh; i++) {
			int r = to[(n - (LL) anshigh[i] * M % n) % n];
			if (!r)
				continue;
			if (anshigh[i] < 10) {
				for (int j = 0; j <= 9; j++) {
					if (j == anshigh[i])
						continue;
					if (j > anshigh[i]) {
						if (cnt[j][1][r]) {
							if (k > cnt[j][1][r])
								k -= cnt[j][1][r];
							else {
								sort(anslow[j][1].begin(), anslow[j][1].end());
								for (int it = 0; it < anslow[j][1].size();
										it++) {
									if (to[anslow[j][1][it] % n] == r) {
										k--;
										if (!k) {
											printf("%d%07d\n", anshigh[i],
													anslow[j][1][it]);
											return 0;
										}
									}
								}
							}
						}
					} else {
						if (cnt[j][0][r]) {
							if (k > cnt[j][0][r])
								k -= cnt[j][0][r];
							else {
								sort(anslow[j][0].begin(), anslow[j][0].end());
								for (int it = 0; it < anslow[j][0].size();
										it++) {
									if (to[anslow[j][0][it] % n] == r) {
										k--;
										if (!k) {
											printf("%d%07d\n", anshigh[i],
													anslow[j][0][it]);
											return 0;
										}
									}
								}
							}
						}
					}
				}
			} else {
				if (anshigh[i] % 10 > anshigh[i] / 10 % 10) {
					for (int j = 0; j < anshigh[i] % 10; j++) {
						if (cnt[j][0][r]) {
							if (k > cnt[j][0][r])
								k -= cnt[j][0][r];
							else {
								sort(anslow[j][0].begin(), anslow[j][0].end());
								for (int it = 0; it < anslow[j][0].size();
										it++) {
									if (to[anslow[j][0][it] % n] == r) {
										k--;
										if (!k) {
											printf("%d%07d\n", anshigh[i],
													anslow[j][0][it]);
											return 0;
										}
									}
								}
							}
						}
					}
				} else {
					for (int j = anshigh[i] % 10 + 1; j <= 9; j++) {
						if (cnt[j][1][r]) {
							if (k > cnt[j][1][r])
								k -= cnt[j][1][r];
							else {
								sort(anslow[j][1].begin(), anslow[j][1].end());
								for (int it = 0; it < anslow[j][1].size();
										it++) {
									if (to[anslow[j][1][it] % n] == r) {
										k--;
										if (!k) {
											printf("%d%07d\n", anshigh[i],
													anslow[j][1][it]);
											return 0;
										}
									}
								}
							}
						}
					}
				}
			}
		}
	printf("-1\n");
	return 0;
}