2021.5.4 校内模拟赛游记

~~《比赛赛严重事故征候调查报告：2021 年 5 月 4 日校内模拟赛》~~

概述

做完一题就一直搞第二题，而且还想歪了，最终在模拟赛中取得了糟糕的成绩。

事实情况

A

输入张图两两间的最短路，求最少要几条边。

其实原题描述的还是有点不清楚的，不过读懂了题目就很好做了。

首先给它当做完全图全部连上，然后看看哪些是能够去掉的。如果两点之间有一条路径和两点直连的边长度一样，那么这条边肯定没用了。

参照弗洛伊德算法，三重循环即可解决。

去重的部分有点 low 了，居然真的是全部记下来去重，其实只需要打个标记就可以了，不过写代码前没有想到重复这一点，所以写出了下面这段代码。

#include <cstdio>
#include <vector>
#include <algorithm>
const int N = 305;
int n, f[N][N];
struct kkk { 
	int u, v; 
	bool operator < (kkk b) const {
		return u < b.u || (u == b.u && v < b.v);
	}
	bool operator == (kkk b) const {
		return u == b.u && v == b.v;
	}
};
struct twt {
	std::vector<kkk> a;
	int s;
	twt() { a.clear(); s = 0; }
	void push(int u, int v) {
		if(u > v) std::swap(u, v);
		a.push_back((kkk){u, v});
	}
	void unique() {
		std::sort(a.begin(), a.end());
		s = std::unique(a.begin(), a.end()) - a.begin();
	}
	int size() { return s; }
} e;
int main() {
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) 
			scanf("%d", &f[i][j]);
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if(i != j && i != k && j != k && f[i][k] + f[k][j] == f[i][j])
					e.push(i, j);
	e.unique();
	printf("%d", n * (n-1) / 2 - e.size());
	return 0;
}

B

大约半个小时完成了第一题之后就开始做第二题了。

对于 $0 \rightarrow 2^n-1$ 的二进制数 $x$ 有一个参数 $f(x)$ , 求最小的 $t$ , 使在保持 $t$ 个二进制位不变的情况下，其它位 $01$ 任意取，所产生的数 $y$ 的参数 $f(y) = f(x)$ .

同样是题意非常难理解的题目。

首先想到的当然是暴力做法，直接枚举，时间复杂度 $O(2^{3n})$ , 无法接受，所以考虑能否去掉一层枚举。

赛场上想到了一种做法，就是枚举 $y$ 并且将它的参数记录到其最大的和 $x$ 相同的部分中。但由于 $t$ 位相同其它的也可以相同，所以再来一次记忆化搜索，更新这些状态使它们成为最后的答案。

赛场上以为时间是 $O(2^{2n})$ 的，便认为可以过，然后又因为一些细节原因调了好久的代码，最后一测发现超时，分数还没有暴力高。

其实这个做法时间复杂度是仍然是暴力，因为虽然经过的状态只有 $2^n$ 级别，但转移很多，如果建成图的话，就是这个样子，边特别多，导致了超时。

C

赛时没有时间做。

分析

题目分析

A

在 A 题中，开始没有考虑好整个算法就贸然去写，然后要解决重复问题，没有仔细思考就采用了较为暴力的写法，耽误了一些时间。

B

在 B 题种使用了错误的时间复杂度分析。其实这个就和传递闭包的分析是一样的，虽然点只有这么一些，但是边时要全部遍历到的，时间复杂度就大大上升了。

而 B 题的正确做法其实并不难。只需要换一种思路去暴力就可以了。直接枚举所有的有太多的重复和不必要。

可以先枚举要定死的 $t$ 个，然后再分开枚举 $t$ 个之间的和之外的，这样就没有了重复，然后一分析时间复杂度，每一个仅有 $t$ 个之内 $0$ , $t$ 个之内 $1$ , $t$ 个之外 $0$ 和 $t$ 个之外 $1$ , 四种可能，时间复杂度是 $4^n$ 也就是 $2^{2n}$ 可以通过此题了。

C

$n$ 段区间选若干，令 $tot$ 为选中的个数， $x$ 为选中的都覆盖的长度，求 $\min\{tot, x\}$ 的最大值。

这个其实也属于最小值最大，应该考虑二分。

首先确认一下单调性，小的肯定比大的更容易获得，而且 $tot$ 增大了， $x$ 肯定会减小（或者不变），那么我们就可以只枚举一个 $x$ 再判断是否有更大的 $tot$ 了。因为如果 $tot$ 更小，而此时 $x$ 是可以的，那么我们在让二分的 $x$ 变小的时候同样可以满足取原先的 $tot$ 个，所以不需要再判断 $tot$ 了，直接二分 $x$ 即可以了。

感觉这个二分还是有点不一样的，略微有些只可意会不可言传的感觉。

#include <cstdio>
#include <cstring>
const int N = 300005;
struct twt { int l, r; } r[N];
int n, sumr[N], suml[N];
bool check(int x) {
    memset(sumr, 0, sizeof(sumr));
    memset(suml, 0, sizeof(suml));
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (x <= r[i].r - r[i].l + 1) cnt++, sumr[r[i].r]++, suml[r[i].l]++;
    for (int i = 2; i <= n; i++) sumr[i] += sumr[i - 1];
    for (int i = n - 1; i >= 1; i--) suml[i] += suml[i + 1];
    for (int i = x; i <= n; i++) {
        int l = i - x + 1;
        if (x <= cnt - sumr[i - 1] - suml[l + 1]) return true;
    }
    return false;
}
int main() {
    freopen("interval.in", "r", stdin);
    freopen("interval.out", "w", stdout);
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &r[i].l, &r[i].r);
    int l = 2, r = n, ans = 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    printf("%d", ans);
    return 0;
}

决策分析

我在进行这场比赛时，没有思考透彻和分析透彻便贸然写题，未遵循 SOP 要求，且 C 题调了很久后仍然死磕，未执行相关检查单。

根据 CVR 记录，我在 ~~一万英尺以下~~ 全程都未遵循 SCR, 没能静下心来冷静思考。

最终才导致了没能做出 B 题或获得 C 题的部分分/正解。

结论

本次模拟赛由于我未按照 SOP 和 SCR 要求放弃 B 题和冷静思考，导致构成构成严重事故征候。

建议：

比赛时严格遵照 SOP 做题，若一题超过一小时未果先完成后面部分分内容。
严格遵守 SCR 规定，独立冷静思考。
考虑暴力程序时应考虑不同的写法及重复和不必要尽可能少的写法。