Codeforces Round #741 (Div. 2)

A

显然,如果可以存在一个 \(x\) 使 \(r \equiv x - 1 \pmod x\),\(x - 1\) 为最优解。如果 \(2l - 1 \leq r\),显然答案为 \(\lfloor \frac{r - 1}{2} \rfloor\);否则,显然答案为 \(r \bmod l\)。

代码:

#include <stdio.h>

int main(){
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++){
		int l, r;
		scanf("%d %d", &l, &r);
		if (l * 2 - 1 <= r){
			printf("%d\n", (r - 1) / 2);
		} else {
			printf("%d\n", r % l);
		}
	}
	return 0;
}

B

大胆猜想:答案只可能为 \(1\) 或 \(2\) 位不必证明

代码:

#include <stdio.h>
#include <math.h>

int a[57];

inline bool is_prime(int n){
	if (n < 2) return false;
	if (n == 2) return true;
	if (n % 2 == 0) return false;
	int t = sqrt(n);
	for (int i = 3; i <= t; i++){
		if (n % i == 0) return false;
	}
	return true;
}

int main(){
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++){
		int k, ansa, ansb;
		bool flag = false;
		scanf("%d", &k);
		for (int j = 1; j <= k; j++){
			scanf("%1d", &a[j]);
			if (!flag && ((a[j] != 2 && a[j] % 2 == 0) || a[j] == 1 || a[j] == 9)){
				ansa = 1;
				ansb = a[j];
				flag = true;
			}
		}
		if (!flag){
			for (int j = 1; j < k; j++){
				for (int x = j + 1; x <= k; x++){
					int t = a[j] * 10 + a[x];
					if (!is_prime(t)){
						ansa = 2;
						ansb = t;
						goto END;
					}
				}
			}
		}
END:    printf("%d\n", ansa);
		printf("%d\n", ansb);
	}
	return 0;
}

C

显然,\(0\) 对我们构造非常有用,因为 \(0\) 接在一坨数字前面或后面都可以构造出合法解。

特判全是 \(1\) 的情况即可。

代码:

#include <stdio.h>
#include <stdbool.h>

int a[20007];

int main(){
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++){
		int n, m, pos;
		bool flag = false;
		scanf("%d", &n);
		m = n / 2;
		for (int j = 1; j <= n; j++){
			scanf("%1d", &a[j]);
			if (!flag && j > m && a[j] == 0){
				pos = j;
				flag = true;
			}
		}
		if (flag){
			printf("1 %d 1 %d\n", pos, pos - 1);
		} else {
			m = n - m;
			for (int j = 1; j <= m; j++){
				if (a[j] == 0){
					pos = j;
					flag = true;
					break;
				}
			}
			if (flag){
				printf("%d %d %d %d\n", pos, n, pos + 1, n);
			} else {
				printf("1 %d 2 %d\n", n - 1, n);
			}
		}
	}
	return 0;
}
上一篇:Codeforces Round #741


下一篇:预备役2.22学习总结