上海市计算机学会月赛2021年3月乙组

57 阅读 0 评论 38 点赞

我是靠谱客的博主高贵绿茶，最近开发中收集的这篇文章主要介绍上海市计算机学会月赛2021年3月乙组，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

平衡三进制

#include <iostream>
using namespace std;

void f(int x) {
	if (x == 0) return;
	
	if (x%3 == 2) f(x/3 + 1), cout << 'z';
	else if (x%3 == -2) f(x/3 - 1), cout << '1';
	else if (x%3 == -1) f(x/3), cout << 'z';
	else f(x/3), cout << x%3;
}

int main() {
	int n;
	cin >> n;

	if (n == 0) cout << 0;
	else f(n);

	return 0;
}

正规数

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

long long a, b, c;
int cnt, ans[10000];

int main() {
	for (int i = 0; i <= 31; i ++) {
		a = pow(2, i);
		for (int j = 0; j <= 20; j ++) {
			b = pow(3, j);
			if (a*b > 2e9) break;
			for (int k = 0; k <= 15; k ++) {
				c = pow(5, k);
				if (a*b*c > 2e9) break;
				ans[++cnt] = a*b*c;
			}
		}
	}

	sort(ans+1, ans+1+cnt);
	
	int n;
	cin >> n;
	cout << ans[n];

	return 0;
}

铺设地砖（二）

#include <iostream>
using namespace std;

const int N = 1e5+10, MOD = 1e9+7;
int n, a[N] = {1,2}, sum = 4;

int main() {
	cin >> n;
	for (int i = 2; i <= n; i ++) {
		a[i] = (sum + a[i-2] + 2) % MOD;
		sum = (sum + a[i]) % MOD;
		sum = (sum + a[i]) % MOD;
	}
	cout << a[n];

	return 0;
}

限时任务

#include <iostream>
#include <cstring>
using namespace std;

const int N = 5100, M = 1e4 + 10;
int n, m, w[N], c[N], f[M], g[M];

int main() {
	cin >> n >> m;
	
	int t = 0;
	for (int i = 1; i <= n; i ++) cin >> w[i] >> c[i];

	for (int i = 1; i <= n; i ++) {
		for (int j = m; j >= w[i]; j --) {
			f[j] = max(f[j], f[j-w[i]] + c[i]);
			
			g[j] = max(g[j], f[j-1] + c[i]);
			g[j] = max(g[j], g[j-w[i]] + c[i]);
//			cout << i << ' ' << j << ' ' << f[i][j] << ' ' << g[i][j] << endl;
		}
	}
	
	cout << 2 * g[m];

	return 0;
}