第一次熬夜肝CF比赛，感觉ABCD都不难的，只是B题最初公式没推对花了不少时间。

另外E题许多人都做出来了，可惜我赛时没能想出来。

A. Arena

Problem - A - Codeforces

Solution

显然，只要不是最弱的英雄，都可以欺负与最弱的战斗 \(100^{500}\) ，然后成为获胜者。

纯属是比赛的签到题。

Code

#include <bits/stdc++.h>
using namespace std;

int t, n, a[105], ans, minn;

int main() {
	scanf("%d", &t);
	
	while (t--) {
		ans = 0, minn = 2003;
		
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			minn = min(minn, a[i]);
		}
		
		for (int i = 1; i <= n; i++)
			if (a[i] != minn) ans++;
			
		printf("%d\n", ans);
	}
	
	return 0;
}

B. Cat Cycle

Problem - B - Codeforces

Solution

显然 \(n\) 为偶数时两只猫不会相遇。

而当 \(n\) 为奇数时，我们可以发现猫 B 每过 \(\lfloor \frac{n}{2} \rfloor\) 小时都会与猫 A 相遇。

所以过了 \(k\) 小时后猫 B 会比计划多移动 \(\lfloor \frac{k-1}{\lfloor \frac{n}{2} \rfloor} \rfloor\) 个睡觉地点。

Code

#include <bits/stdc++.h>
using namespace std;

int t, n, k, length;

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &k);
		
		if (n&1) k += (k-1)/(n/2); 
		printf("%d\n", (k-1)%n+1);
	}
	
	return 0;
}

C. Mininum Ties

Problem - C - Codeforces

Solution

显然每只队伍需要比 \(n-1\) 场比赛。可以考虑根据奇偶分类讨论。

如果 \(n\) 为奇数，我们可以让每一队都赢一半比赛，可以做到 \(0\) 场平局。

如果 \(n\) 为奇数，我们计算出在使得平局数量最少的情况下每一队的得分，再使用 \(num\) 数组维护每一队在比完每一场比赛后的得分。

接着比较 \(num_i\) 与期望得分的大小就可以判定这一场的胜负了。

Code

#include <bits/stdc++.h>
using namespace std;

int t, n, num[105], score;

int main() {
	scanf("%d", &t);
	while (t--) {
		memset(num, 0, sizeof(num));
		
		scanf("%d", &n);
		
		if (n == 2) {
			printf("0\n");
			continue;
		}
		
		if (n & 1) {
			for (int i = 1; i < n; i++) {
				for (int j = i+1; j <= n; j++) {
					if (num[i] <= 0) {
						printf("1 ");
						num[i]++;
					} else {
						printf("-1 ");
						num[i]--;
					}
				}
			}
			printf("\n");
		} else {
			score = (3*(n-1)-1)/2;
			
			for (int i = 1; i < n; i++) {
				for (int j = i+1; j <= n; j++) {
					if (num[i] <= score-3) {
						printf("1 ");
						num[i] += 3;
					} else if (num[i] < score) {
						printf("0 ");
						num[i] += 1;
						num[j] += 1;
					} else {
						printf("-1 ");
						num[j] += 1;
					}
				}
			}
			
			printf("\n");
		}
	}
	
	return 0;
}

D. Pythagorean Triples

Problem - D - Codeforces

Solution

一道纯的推柿子题。

假设元组 \((a, b, c)\) 满足要求，则显然有

\(\begin{equation} \left\{ \begin{array}{lr} a^2 + b^2 = c^2 & \\ a^4 - 2a^2b + b^2 = c^2 \end{array} \right. \end{equation}\)

两式相减，得

\(a^4 = a^2(2b+1)\)

因此

\(a^2 = 2b + 1\)

带入①式，有

\(b^2 + 2b + 1 = c^2\)

是不是很熟悉？所以

\((b+1)^2 = c^2\)

\(b + 1 = c\)

这时我们来看看范围，\(1 \le a \le b \le c \le n\)，所以 \(b \le n-1\)，从而有 \(a^2 \le 2n-1\)

因此 \(a \le \sqrt{2n-1}\)

而因为 \(b\) 为正整数而 \(a^2 = 2b+1\)，故 \(a\) 必为奇数

注意 \(a\) 为 \(1\) 时 \(b = 0\) 不成立

Code

#include <bits/stdc++.h>
using namespace std;

int t, n, maxn;

int main() {
	scanf("%d", &t);
	
	while (t--) {
		scanf("%d", &n);
		n = 2*n-1;
		maxn = int(sqrt(n));
		printf("%d\n", (maxn-1)/2); 
	}
	
	return 0;
}