【周考】Round1 2024.7.6

cqbz_dxm / 2023-07-18 / 原文

【周考】Round1 2024.7.6

Summary

Score: \(100+90+0+50+4=244\)

T1 减法操作

Algorithm: 思维

考虑对 \(n\) 分奇偶讨论：

偶数：显然最小质因子为 \(2\)，而每次减 \(2\) 后仍是偶数。所以偶数一定进行了 \(\dfrac n 2\) 次操作；
奇数：因为是奇数，所以最小质因子一定也是奇数，减去后则变为偶数，接着可以转化为偶数处理。

code

#include <cstdio>
long long n, ans;
int main () {
	scanf("%lld", &n);
	if (n & 1) {
		for (long long i = 3; i * i <= n; i++)
			if (!(n % i))
				return printf("%lld", 1 + (n - i) / 2), 0;
		ans = 1;
	} else
		ans = n / 2;
	printf("%lld", ans);
	return 0;
}

T2 匹配数

Algorithm: 爆搜 / DP

考场思路：

感觉直接爆搜的时间复杂度实在是玄学，一下子想到了贪心（为什么不是 DP。。。

设最终答案数组为 \(a\)，对于 \(a[i]\)，从贪心的角度分类讨论：

对于 <：\(a[i]=a[i-1]+1\)；

code for 贪心

#include <cstdio>
#include <cstring>
const int MAXN = 2005;
char s[MAXN];
int n, l, a[MAXN];
int main () {
	scanf("%s", s + 1), n = strlen(s + 1);
	a[0] = 1;
	for (int i = 1; i <= n; i++) {
		if (s[i] == '>') {
			a[i] = 0;
			if (a[i - 1] == 0) {
				for (int j = i - 1; j >= 0; j--) {
					a[j]++;
					if (s[j] == '!') {
						if (a[j] == a[j - 1]) {
							a[j]++;
							for (int k = j + 1; k <= i; k++) {
								if (s[k] == '=' || s[k] == '<') {
									a[k]++;
								} else if (s[k] == '!') {
									//根本就不可能。。。
								} else break;
							}
						}
						break;
					}
					if (s[j] == '<' && a[j - 1] < a[j]) break;
					if (s[j] == '>' && a[j - 1] > a[j]) break;
				}
			}
		}
		if (s[i] == '<') {
			a[i] = a[i - 1] + 1;
		}
		if (s[i] == '=') {
			a[i] = a[i - 1];
		}
		if (s[i] == '!') {
			if (a[i - 1] == 0) a[i] = 1;
			else a[i] = 0;
		}
	}
	for (int i = 0; i <= n; i++) putchar(a[i] + '0');
	return 0;
}
/*
<>!=<>!=<>!=<>!=<>!=
120112011201120112011

=!!!>
110120

==>>>
333210

 ><!=>
101220

 <>>=>
132110

<<<<<<<<><<<<<<<<><<<<<<<<><<<<<<<<!
*/