减舟'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;
}

D1T1 铺地毯

#include <cstdio>
const int MAXN = 100001;
int n, x, y, a[MAXN], b[MAXN], g[MAXN], k[MAXN];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &a[i], &b[i], &g[i], &k[i]);
	scanf("%d%d", &x, &y);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] <= x && x <= a[i] + g[i] && b[i] <= y && y <= b[i] + k[i])
			ans = i;
	printf("%d\n", ans);
	return 0;
}

D1T2 选择客栈

#include<cstdio>
using namespace std;
int f[200001], sav[200001], ans[200001], num[200001];
int n, p, k, cnt = 0;

int main() {
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i <= n; i++) {
		int color, cost;
		scanf("%d%d", &color, &cost);
		if (cost <= p) f[i] = f[i - 1] + 1; 
    		else f[i] = f[i - 1];
    	if (sav[color] == 0) {
        	sav[color] = i; num[color]++; continue;
    	}
      	if (f[i] - f[sav[color] - 1] > 0) ans[i] = num[color];
      		else ans[i] = ans[sav[color]];
      	sav[color] = i;
      	num[color]++;
    }   
    for (int i = 1; i <= n; i++) cnt += ans[i];
    printf("%d\n", cnt);
    return 0;
}

D1T3 Mayan游戏

    Mayan游戏写起来比较棘手，做法的话，就是上DFS。有两个剪枝操作：某种颜色存在但是个数小于3没法消除；如果一个方块左边也是方块就不必左移，因为右移效果一样字典序更小。

#include <cstdio>
#include <cstdlib>
#include <cstring>
void swap(int &a, int &b) {
	int c = a; a = b; b = c;
}

int n;

struct map {
	int a[5][7];
	bool d[5][7];
	
	void Read() {
		memset(a, 0, sizeof(a));
		memset(d, 0, sizeof(d));
		for (int i = 0; i < 5; i++) {
			int t1, t2 = 0;
			scanf("%d", &t1);
			while (t1) {
				a[i][t2++] = t1; scanf("%d", &t1);
			}
		}
	}
	
	void Falldown(int i) {
		int pop = 0;
		for (int j = 0; j < 7; j++)
			if (a[i][j]) {
				a[i][pop++] = a[i][j];
				if (j >= pop) a[i][j] = 0;
			}
	}
	
	void Fall() {
		for (int i = 0; i < 5; i++) Falldown(i);
	}
	
	bool Combo() {
		memset(d, 0, sizeof(d)); bool ret = 0;
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++) {
				if (a[i][j] == 0) continue;
				
				if (0 < i && i < 4)
					if (a[i - 1][j] == a[i][j] && a[i][j] == a[i + 1][j]) {
						d[i - 1][j] = d[i][j] = d[i + 1][j] = 1;
						ret = 1;
					}
				if (0 < j && j < 6)
					if (a[i][j - 1] == a[i][j] && a[i][j] == a[i][j + 1]) {
						d[i][j - 1] = d[i][j] = d[i][j + 1] = 1;
						ret = 1;
					}
			}
		return ret;
	}
	
	void Collapse() {
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++)
				if (d[i][j]) a[i][j] = 0;
		memset(d, 0, sizeof(d));
	}
	
	void Move(int i, int j, int k) {
		swap(a[i][j], a[i + k][j]);
		Falldown(i), Falldown(i + k);
		while (Combo()) {
			Collapse(); Fall();
		}
	}
	
	bool Empty() {
		for (int i = 0; i < 5; i++)
			if (a[i][0]) return 0;
		return 1;
	}
	
	int GetMin() {
		int cnt[11] = {0};
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++)
				if (a[i][j]) cnt[a[i][j]]++;
		int min = 35;
		for (int i = 1; i <= 10; i++)
			if (cnt[i] && cnt[i] < min) min = cnt[i];
		return min;
	}
} sta;

struct Node {
	int a, b, c;
	
	void Load(int A, int B, int C) {
		a = A, b = B, c = C;
	}
} ans[100];
	
void dfs(int t) {
	if (sta.Empty()) {
		for (int i = 1; i <= t; i++)
			printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
		exit(0);
	}
	if (t == n) return;
	if (sta.GetMin() <= 2) return;
	map bak = sta;
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 7; j++) {
			if (sta.a[i][j] == 0) continue;
			if (i < 4 && sta.a[i][j] != sta.a[i + 1][j]) {
				ans[t + 1].Load(i, j, 1); sta.Move(i, j, 1);
				dfs(t + 1);
				sta = bak;
			}
			if (i > 0 && sta.a[i - 1][j] == 0) {
				ans[t + 1].Load(i, j, -1); sta.Move(i, j, -1);
				dfs(t + 1);
				sta = bak;
			}
		}
}
	
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%d", &n);
	sta.Read();
	dfs(0);
	printf("-1\n");
	return 0;
}

D2T1 计算系数

    杨辉三角就可以了～

#include <cstdio>
#include <algorithm>
const int M = 10007;
using namespace std;

int f[1001][1001];
int a, b, k, n, m;

int main() {
	long long ans = 1;
	scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);
	f[1][1] = f[1][2] = 1;
	for (int i = 2; i <= k; i++) 
		for (int j = 1; j <= i + 1; j++)
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % M;
	ans = f[k][m + 1];
	for (int i = 1; i <= n; i++) ans = (ans * a) % M;
	for (int j = 1; j <= m; j++) ans = (ans * b) % M;
	printf("%d", ans);
	return 0;
}

D2T2 聪明的质检员

    二分法计算就可以了。P.S.VIJOS是windows评测，我一开始%lld没过，然并卵

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

long long n, m, S, w[200001], v[200001], l[200001], r[200001], arr[200001];
long long sum1[200001], sum2[200001];

long long fun(int k) {
	long long ret = 0;
	for (int i = 1; i <= n; i++) {
		if (w[i] >= k) {
			sum1[i] = sum1[i - 1] + 1;
			sum2[i] = sum2[i - 1] + v[i];
		} else {
			sum1[i] = sum1[i - 1];
			sum2[i] = sum2[i - 1];
		}
	}
	for (int i = 1; i <= m; i++)
		ret += (sum1[r[i]] - sum1[l[i] - 1]) * (sum2[r[i]] - sum2[l[i] - 1]);
	return S - ret;
}

long long find(int L, int R) {
	if (L == R) return abs(fun(L));
	long long M = (L + R) / 2; 
	long long tmp = fun(arr[M]);
	long long ret = abs(tmp);
	if (tmp > 0) ret = min(find(L, M), ret);
		else if (tmp < 0) ret = min(find(M + 1, R), ret);
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%I64d%I64d%I64d", &n, &m, &S);
	for (int i = 1; i <= n; i++){
		scanf("%I64d%I64d", &w[i], &v[i]);
		arr[i] = w[i];
	}
	sort(arr + 1, arr + n + 1);
	for (int i = 1; i <= m; i++)
		scanf("%I64d%I64d", &l[i], &r[i]);    
	long long ans = find(1, n);
	printf("%I64d", ans);
	return 0;
}

D2T3 观光公交

    易见每个旅客上车时间都已固定，答案取决于下车时间，所以得出贪心操作正确性。然后就是每次氮气都用在在车上人最多的时候。

#include <cstdio>
int n, m, k, t, a, b;
int d[1001], lim[1001], sce[1001], up[1001], down[1001];
	
	int max(int a, int b) { return a > b ? a : b; }
	
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int p = 0;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i < n; i++) scanf("%d", &d[i]);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &t, &a, &b);
		up[a]++, down[b]++;
		sce[a] = max(sce[a], t);
		p += t;
	}
	for (int i = 1; i <= n; i++)
		lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
	while (k--) {
		int cnt = 0, _max = 0, t = 0;
		for (int i = n; i > 1; i--) {
			if (lim[i] <= sce[i]) cnt = 0;
			cnt += down[i];
			if (d[i - 1] && cnt > _max) _max = cnt, t = i - 1;
		}
		if (!t) break;
		d[t]--;
		for (int i = t + 1; i <= n; i++)
			lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
		ans += down[i] * lim[i];
	}
	printf("%d\n", ans - p);
	return 0;
}