比赛地址

A（博弈+思维）

题目链接
⭐⭐⭐

题目：
Alice与Bob玩游戏，有两个石子堆石子个数分别为\(n,m\)。Alice先走，每人可以从一堆中拿走\(k(k>0)\)个，并且从另一堆拿走\(s\times k(s\ge0)\)个，不能执行操作的人为负。

解析：
引理：每一堆确定数量的石子都与唯一确定数量的另一堆石子构成必败点
证明：假定有两个必败点\((a,b_1)(a,b_2)\ b_1<b_2\)，则存在\((a,b_1)\rightarrow(a,b_2)\)，则一定有一个点不是必败点，故反证成立
因此可以维护一个\(fail\)数组代表必败点组合，每次可以从之前的状态\(fail[j]\)进行转移，而\(i-j\)既可以作为某个数的倍数，也可以作为一个基数，对于第一种情况，预处理好范围内的所有数的因数即可

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e3 + 1;

vector<int> fac[maxn];
int fail[maxn];
bool vis[maxn];

int main() {
	for (int i = 1; i < maxn; ++i)
		for (int j = i; j < maxn; j += i)
			fac[j].push_back(i);
	fail[0] = 0;
	for (int i = 1; i < maxn; ++i) {
		if (fail[i]) continue;
		memset(vis, 0, sizeof(vis));
		for (int j = 0; j < i; ++j) {
			if (!fail[j] && j) continue;
			for (int k = fail[j]; k < maxn; k += i - j)
				vis[k] = true;
			for (auto& i : fac[i - j]) {
				if (fail[j] + i >= maxn) break;
				vis[fail[j] + i] = true;
			}
		}
		for (int j = i + 1; j < maxn; ++j)
			if (!vis[j]) {
				fail[i] = j;
				fail[j] = i;
				break;
			}
	}
	int T;
	scanf("%d", &T);
	int a, b;
	while (T--) {
		scanf("%d%d", &a, &b);
		printf("%s\n", fail[a] == b ? "Bob" : "Alice");
	}
}

B（计算几何）

题目链接
⭐

题目：
如给定图，求出圆心距离底部的距离

解析：
平面几何题目，构造一个相似三角形即可

#include<bits/stdc++.h>
 
using namespace std;
 
double r, a, b, h;
 
int main() {
    scanf("%lf%lf%lf%lf", &r, &a, &b, &h);
    if (2 * r < b) printf("Drop");
    else {
        printf("Stuck\n");
        printf("%.10f", (sqrt(((a - b) / 2) * ((a - b) / 2) + h * h) * r / h - b / 2) * h / ((a - b) / 2));
    }
}

D（水题）

题目链接
⭐

题目：
给出一个\(n\times n\)的01矩阵，找出\(1\times m\)值均为 \(0\) 的子矩阵个数

解析：
统计每行长度超过\(m\)的连续 \(0\) 的个数的和

#include<bits/stdc++.h>
using namespace std;
 
char t[2005][2005];
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", t[i]);
    }
    scanf("%*s");
    int ans = 0, cnt;
    for (int i = 0; i < n; ++i) {
        int j = 0;
        while (j < n) {
            cnt = 0;
            while (t[i][j] == '0' && j < n) ++j, ++cnt;
            if (t[i][j] == '1') ++j;
            ans += max(cnt - m + 1, 0);
        }
    }
    printf("%d", ans);
}

F（思维）

题目链接
⭐

题目：
如果一个数，如果对应字符串的含有连续子串所对应的数是\(3\)的倍数，则认为这个数是\(3-friendly\)的数，现在给定区间\([L, R]\)，求出区间内\(3-friendly\)的数的个数

解析：
定义\(f(x)\)代表小于等于\(x\)中\(3-friendly\)的数的个数，那么答案即为\(f(R)-f(L-1)\)。
对于任意大于三位的数而言，组成他们的数位模3后只有\(0,1,2\)三种可能，则必定含有子串满足\(3-friendly\)（根据三的倍数必定满足各位相加之和仍然位三的倍数）
那么只需要对小于等于100的数进行特判处理即可

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

bool check(int x) {
	int t[3] = { 0 };
	while (x) {
		++t[x % 10 % 3];
		x /= 10;
	}
	if (t[1] || t[2]) return (t[1] > 0 && t[2] > 0) || t[0] > 0;
	return true;
}

int t[100];

int main() {
	long long L, R;
	int T;
	for (int i = 1; i < 100; ++i)
		t[i] = t[i - 1] + check(i);
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &L, &R);
		--L;
		if (L < 100) L = t[L];
		else L = L - 99 + t[99];
		if (R < 100) R = t[R];
		else R = R - 99 + t[99];
		printf("%lld\n", R - L);
	}
}

G（贪心+思维+绝对值）

题目链接
⭐⭐⭐⭐

题目：
给出长度为\(N\)的\(A,B\)数组，现在可以任意更换\(A\)数组中元素的位置，求\(\sum_{i=1}^n|A_i-B_i|\)的最大值

解析：
可以把绝对值拆开，这样就变成了\(\sum_{i=1}^n (\pm A_i)+(\pm B_i)\)，即A中正号出现次数要等与B中负号出现次数，反之亦然。假设可以交换任意次，只要挑选\(A,B\)中最大前\(n\)个加正号
那么现在如果只能交换\(k\)次，考虑最大利益的贪心交换。不难发现对于两队值\((a_1,b_1)(a_2,b_2)\)，如果是\(\max(a_1,b_1)<\min(a_2,b_2)\)，即两个线段没有交集，此时的贡献是\(|b_2-a_2|+|b_1-a_1|\)，倘若交换\(a_1,a_2\)位置，则此时贡献为\(|b_2-a_1|+|a_2-b_1|\)，（画出线段图很容易发现）相比于前者多了\(2(\max(a_1,b_1)-\min(a_2,b_2))\)
那么就可以找出每一对的最大值和最小值，并将他们的最大值升序排列，最小值降序排序，找出最大的前\(k\)对，对应的操作自然也是将最大值与最小值对应的原元素进行交换

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
ll a[maxn], b[maxn];
ll mn[maxn], mx[maxn];
 
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%lld", a + i);
    for (int i = 0; i < n; ++i)
        scanf("%lld", b + i);
 
    ll ans = 0;
    if (n == 2) {
        if (k & 1) swap(a[0], a[1]);
        ans += abs(a[0] - b[0]) + abs(a[1] - b[1]);
    }
    else {
        k = min(k, n);
        for (int i = 0; i < n; ++i)
            ans += abs(a[i] - b[i]), mx[i] = max(a[i], b[i]), mn[i] = min(a[i], b[i]);
        sort(mx, mx + n), sort(mn, mn + n, greater<ll>());
        for (int i = 0; i < k && mn[i] - mx[i]>0; ++i)
            ans += 2 * (mn[i] - mx[i]);
    }
    printf("%lld", ans);
}

I（dp+前缀和优化）

题目链接
⭐⭐⭐⭐

题目：
Alice和Bob玩游戏，每个人可以轮流从P数组中选取元素（P数组为\(1\sim N\)的排列），但必须要满足以下规则

1. 每个人取的数都必须大于之前二人取过的所有数
2. 每个人取的数的下标都得大于之前自己取过的所有下标

如果有多种选择，则概率均匀分布，有一方无法进行操作时游戏结束
询问二人总操作数的期望（答案模取\(998244353\)）

解析：
首先暴力状态转移，一定是一个\(O(n^3)\)的做法，所以考虑用前缀和进行优化降维
考虑设置\(dp[i][j]\)，代表Alice取下标为\(i\)的元素时，Bob取下表为\(j\)元素时的期望，那么对于当前这个状态，需要判断\(P[i]\)与\(P[j]\)的大小关系，谁大证明谁刚操作过，当前轮到另一方操作，那么可以得到下列状态转移方程

\(sum,cnt\)分别代表当前状态可以达到状态的\(dp\)前缀和，以及状态的数量，由于是概率均匀分布所以可以采用前缀和进行优化，他们也不难利用倒序迭代去维护

注意：
除了最后一次\((0,0)\)的状态，其他\(i=j\)的状态均不合法。

#include <bits/stdc++.h>

constexpr int maxn = 5e3 + 5;
constexpr int mod = 998244353;
int p[maxn];
int inv[maxn], cnt[maxn], dp[maxn][maxn], sum[maxn];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &p[i]);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) 
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for (int i = n; i >= 0; --i) {
        int cnt2 = 0, sum2 = 0;
        for (int j = n; j >= 0; --j) {
            if (i != 0 && i == j) continue;
            if (p[i] > p[j]) {
                if (!cnt2) dp[i][j] = 0;
                else dp[i][j] = (1 + 1ll * inv[cnt2] * sum2) % mod;
                cnt[j] += 1;
                (sum[j] += dp[i][j]) %= mod;
            }
            else {
                if (!cnt[j]) dp[i][j] = 0;
                else dp[i][j] = (1 + 1ll * inv[cnt[j]] * sum[j]) % mod;
                cnt2 += 1;
                (sum2 += dp[i][j]) %= mod;
            }
        }
    }
    printf("%d", dp[0][0]);
}