学长出的比赛，膜拜！

A

观察样例找规律，发现答案为 \(\frac{2n!}{2}\)。

代码：

#include <stdio.h>

typedef long long ll;

const int N = 2e5 + 7, mod = 1e9 + 7, inv2 = 500000004;
ll fac[N];

inline void init(){
	fac[0] = 1;
	for (int i = 1; i < N; i++){
		fac[i] = fac[i - 1] * i % mod;
	}
}

int main(){
	int t;
	scanf("%d", &t);
	init();
	for (int i = 1; i <= t; i++){
		int n;
		scanf("%d", &n);
		printf("%lld\n", fac[n * 2] * inv2 % mod);
	}
	return 0;
}

B

赛时 FST 了 /kk

首先，如果原图不可能联通或原图不可能无重边和自环或 \(k \leq 1\)，答案为 NO；

如果 \(n = 1\)，答案为 YES；

如果 \(k = 2\)，答案为 NO；

如果原图不是完全图，如果 \(k > 3\)，答案为 YES；否则，答案为 NO；

如果原图是完全图，如果 \(k > 2\)，答案为 YES；否则，答案为 NO。

代码：

#include <stdio.h>

typedef long long ll;

int main(){
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++){
		int n, m, k;
		ll t;
		scanf("%d %d %d", &n, &m, &k);
		t = (ll)n * (n - 1) / 2;
		if (m < n - 1 || m > t || k <= 1){
			printf("NO\n");
		} else if (n == 1){
			printf("YES\n");
		} else if (k == 2){
			printf("NO\n");
		} else if (m < t){
			if (k > 3){
				printf("YES\n");
			} else {
				printf("NO\n");
			}
		} else if (k > 2){
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}

C

二维前缀和 + 容斥我不想再写一遍了。

代码：

#include <stdio.h>

int a[407][407], sum[407][407], b[407][407], c[407][407];

inline int get_sum(int x1, int y1, int x2, int y2){
	return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}

inline int min(int a, int b){
	return a < b ? a : b;
}

int main(){
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++){
		int n, m, mi, ans = 0x7fffffff;
		scanf("%d %d", &n, &m);
		mi = m + 1;
		for (int j = 1; j <= n; j++){
			for (int k = 1; k <= m; k++){
				scanf("%1d", &a[j][k]);
				a[j][k] = 1 - a[j][k];
				sum[j][k] = sum[j][k - 1] + sum[j - 1][k] - sum[j - 1][k - 1] + a[j][k];
			}
		}
		for (int j = 1; j + 4 <= n; j++){
			for (int k = j + 4; k <= n; k++){
				c[k][mi] = 0x7fffffff;
				for (int l = 2; l <= m; l++){
					b[k][l] = b[k][l - 1] + a[j][l] + a[k][l] + (k - j - 1) - get_sum(j + 1, l, k - 1, l);
				}
				for (int l = m; l >= 4; l--){
					c[k][l] = min(c[k][l + 1], b[k][l - 1] + get_sum(j + 1, l, k - 1, l));
				}
				for (int l = 1; l + 3 <= m; l++){
					ans = min(ans, c[k][l + 3] + get_sum(j + 1, l, k - 1, l) - (l > 1 ? get_sum(j, 2, j, l) + get_sum(k, 2, k, l) + ((k - j - 1) * (l - 1) - get_sum(j + 1, 2, k - 1, l)) : 0));
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}