减舟's Blog

D1T1 vigenere密码

  维吉尼亚方表是个好东西，多表替代相比神奇的单表替代的凯撒密码什么的是差距大了去了。随机性分析也是无效的。手工的话只有猜密钥位数攻击了。然并卵。

  模拟大法好啊，觉得自己还是写的比较漂亮的。

#include <cstdio>
#include <cstring>
int n, m;
char key[101], arr[1001];

inline int solve(int a, int b) {
	return (a + (26 - b)) % 26;
}

int main() {
	scanf("%s", key); m = strlen(key);
	scanf("%s", arr); n = strlen(arr);
	for (int i = 0; i < n; i++) {
		int t;
		if ('a' <= key[i % m] && key[i % m] <= 'z') t = key[i % m] - 'a';
			else t = key[i % m] - 'A';
		if ('a' <= arr[i] && arr[i] <= 'z')
			printf("%c", (char) ('a' + solve(arr[i] - 'a', t)));
		else
			printf("%c", (char) ('A' + solve(arr[i] - 'A', t)));
	}
	printf("\n");
	return 0;
}

D2T2 国王游戏

  贪心+高精度。正确性证明我拉一段。

假设相邻的两个人左右手分别是(a, b), (A, B)。设a * b <= A * B，i之前所有人的左手乘积为S。
则，ans1 = max{S / b, S * a / B}
若交换
则，ans2 = max{S / B, S * A / b}
因为，a * b <= A * B
所以，S * a / B <= S * A / b
又因为，S / B <= S * a / B
所以，ans2 = S * A / b
ans1 = max{S / B[i], S * a / B}
所以，ans1 <= ans2
证毕

  自己写的高精度乘单精度一开始返回大数的位数判错了，后来改对了。

#include <algorithm>
#include <cstring>
using std :: sort;
struct Sec {
	int a, b;
} sec[1001], king;
struct bignum {
	int l, a[5000];
	
	bignum () {
		l = 1; memset(a, 0, sizeof(a));
	}
	
	bignum (int n) {
		l = 0; memset(a, 0, sizeof(a));
		while (n) {
			a[++l] = n % 10; n /= 10;
		}
	}
};
int n;

bool cmp(Sec x, Sec y) {
	if (x.a * x.b < y.a * y.b) return true;
		else return false;
}

bignum operator + (bignum A, bignum B) {
	bignum ret;
	ret.l = A.l > B.l ? A.l : B.l;
	for (int i = 1; i <= ret.l; i++) {
		ret.a[i] += A.a[i] + B.a[i];
		if (ret.a[i] > 9)
			ret.a[i + 1]++, ret.a[i] -= 10;
	}
	if (ret.a[ret.l + 1]) ret.l++;
	return ret;
}

bignum operator / (bignum A, int B) {
	bignum ret;
	int cnt = 0;
	for (int i = A.l; i >= 1; i--) {
		cnt += A.a[i];
		if (cnt >= B) {
			ret.a[i] = cnt / B;
			cnt %= B;
		}
		cnt *= 10;
	}
	ret.l = A.l;
	while (ret.a[ret.l] == 0 && ret.l > 1) ret.l--;
	return ret;
}

bignum operator * (bignum A, int B) {
	bignum ret; ret.l = A.l;
	for (int i = 1; i <= A.l; i++) {
		ret.a[i] += A.a[i] * B;
		int k = i;
		while (ret.a[k] > 9) {
			ret.a[k + 1] += ret.a[k] / 10; ret.a[k++] %= 10;
		}
		if (k > ret.l) ret.l = k;
	}
	return ret;
}

bool operator > (bignum A, bignum B) {
	if (A.l != B.l) return A.l > B.l;
	for (int i = A.l; i >= 1; i--) {
		if (A.a[i] > B.a[i]) return 1;
		if (A.a[i] < B.a[i]) return 0;
	}
	return 0;
}

void print(bignum A) {
	for (int i = A.l; i >= 1; i--) printf("%d", A.a[i]);
	printf("\n");
}

int main() {
	scanf("%d", &n);
	scanf("%d%d", &king.a, &king.b);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &sec[i].a, &sec[i].b);
	sort(sec + 1, sec + n + 1, cmp);
	bignum tmp = king.a, ans = 0;
	for (int i = 1; i <= n; i++) {
		bignum k = tmp / sec[i].b;
		if (k > ans) ans = k;
		tmp = tmp * sec[i].a;
	}
	print(ans);
	return 0;
}