zqs`s blog

有朋自远方来，虽远必诛

1/23期末考试总结与反思

发表于 分类于 Valine：

赛时过程

期末考试一共6题。题号ABCDEF。IOI赛制。

A题觉得是个很麻烦的BIT，虽然一眼想到正解但是觉得码量大，身为一个签到题应该有更简单的做法就跳了。

B题一看兴冲冲地打完堆解法愉快地TLE60。于是发现时间复杂度不对，爬了。

C题一眼priority_queue，愉快地A掉。

D题笔算了一下式子转化成了顺序对问题仍然很愉快地A掉。怎么这场比赛A没A都这么愉快啊（危

E题觉得是神仙题，没管看F。F题我记得做过一道很相似的题是并查集。这道题好像就是在那道题的基础上跑个最小生成树貌似就是正解了？？？

A了过后反应过来A题是个sb前缀和又AC。滚回B题。开始在BE之间来回游走。此时我是460rk1，rk220。hh这场说不定能AK至少rk1稳了（大危

然后想了很久很久没思路，xhw巨佬已经400了。赶紧打了E题地错解贪心，没想到骗了整整50分。我510rk1，xhw巨佬400rk2（xhw巨佬没打暴力比我多A一题stO xhw Orz（大大大大危

于是xhw巨佬顺利500，在比赛最后十分钟眼睁睁看着xhwAK全场干掉了我。难受qwq。

赛后总结

感觉这次没能rk1甚至AK只能怪自己tcl。学过的知识总是不能灵活运用啊，菜啊。贪心的题目总是不擅长，菜啊。每次总是抢到rk1然后眼睁睁看着被别人吊打，菜啊。

听完别人的讲解就觉得自己更菜了qwq。讲完了瞬间秒杀，考试的时候就是想不出来。

还是不能在一个想法死磕太久啊，自己还是不太会迅速的转换一道题的解法。直接导致如果一开始的想法不对这道题基本上整场考试都A不掉了。

赛后题解

啥JB A题就不说了。

B题，NKOJ5811，思路是二分需要发射多少次光弹，设为 $mid$。验证的时候先将每个怪的生命值减 $B\times mid$，然后判断每个怪需要单独被击中多少次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <cmath>
#define int long long

int N, A, B, monster[100005];
inline bool check(const int k) {
	int cnt(0);
	for (int i(1); i <= N; ++ i) if (monster[i] > B * k)
		cnt += ceil((monster[i] - B * k) * 1.00 / (A - B));
	return cnt <= k;
}

signed main() {
	scanf("%lld%lld%lld", &N, &A, &B);
	for (int i(1); i <= N; ++ i) scanf("%lld", monster + i);
	int l(1), r(1e9), ans(0);
	while (l <= r) {
		int mid(l + r >> 1);
		check(mid) ? ans = mid, r = mid - 1 : l = mid + 1;
	}
	return printf("%d", ans), 0;
}

C题，NKOJ5832，二分分界点 $k$，前 $N$ 棵树一定在 $k$ 的左边，后 $N$ 棵树一定在 $k$ 右边。$k$ 的范围很显然。快速求出对于每个 $k$，左边的高度最大的 $N$ 棵树，右边高度最小的 $N$ 棵树。显然扫一遍用堆维护就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <queue>
#define int long long

inline int max(const int x, const int y) {return x > y ? x : y;} 
std::priority_queue<int, std::vector<int>, std::greater<int> > q1;
std::priority_queue<int> q2;
int h[300005], s1[300005], s2[300005];

signed main() {
	int n, ans, sum(0);
	scanf("%lld", &n);
	for (int i(1); i <= 3 * n; ++ i) scanf("%lld", h + i);
	for (int i(1); i < n; ++ i) q1.push(h[i]), sum += h[i];
	for (int i(n); i <= n << 1; ++ i) {
		q1.push(h[i]), sum += h[i];
		while (q1.size() > n) sum -= q1.top(), q1.pop();
		s1[i] = sum;
	}
	sum = 0;
	for (int i(3 * n); i > (n << 1) + 1; -- i) sum += h[i], q2.push(h[i]);
	for (int i((n << 1) + 1); i > n; -- i){
		q2.push(h[i]), sum += h[i];
		while (q2.size() > n) sum -= q2.top(), q2.pop();
		s2[i] = sum;
	}
	ans = s1[n] - s2[n + 1];
	for (int i(n + 1); i <= n << 1; ++ i) ans = max(ans, s1[i] - s2[i + 1]);
	return printf("%lld", ans), 0;
}

D题，NKOJ5810，就是让你找有多少个平均值大于 $k$ 的子序列。设这个子序列为 $(L,R]$，$s_i$ 表示数列前 $i$ 项的和。则这个子序列需要满足 $s_R-s_L\ge k\times (R-L)$，化简可得 $s_R-k\times R\ge s_L - k\times L$。令 $g_i=s_i-k\times i$，则问题就变成了求 $g$ 的顺序对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <algorithm>
#define int long long

int a[200005], s[200005], N;
struct node {
	int id, v;
	inline bool operator < (const node x) const {return v < x.v;}
} b[200005];
int c[200005];
inline void update(const int x) {
	for (int i(x); i <= N; i += (i & ~i + 1)) ++ c[i];
}
inline int query(const int x) {
	int sum(0);
	for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
	return sum;
}

signed main() {
	int n, k, ans(0);
	scanf("%lld%lld", &n, &k);
	for (int i(1); i <= n; ++ i) scanf("%lld", a + i);
	for (int i(1); i <= n; ++ i)
		s[i] = s[i - 1] + a[i] - k; 
	for (int i(0); i <= n; ++ i) b[i].id = i, b[i].v = s[i];
	std::sort(b, b + n + 1);
	s[b[0].id] = 2;
	for (int i(1); i <= n; ++ i)
		s[b[i].id] = s[b[i - 1].id] + (b[i].v != b[i - 1].v);
	N = s[b[n].id];
	update(s[0]);
	for (int i(1); i <= n; ++ i)
		ans += query(s[i]), update(s[i]);
	return printf("%lld", ans), 0;
}

E题，NKOJ5831。贪心。先按难度系数排序。将最难的 $k$ 道题先做了来。然后在剩下的题目中，可能会考虑用某些题目替换已选的 $k$ 题。那么发生这种可能的前提是，被替换的题目的种类已经出现过了，且难度系数不是相同种类的题目中最大的（如果相同种类的题目存在难度系数和它一样的也算）。替换的则需要满足他贡献了一个新的种类。并且我们替换一定是按照难度系数由大到小替换的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <queue>
#include <vector>
#define int long long

inline int min(const int x, const int y) {return x < y ? x : y;}
bool mark[100005];
struct node {
	int t, d;
	inline bool operator < (const node x) const {return d < x.d;}
};
std::priority_queue<node> q;

signed main() {
	int n, k, cnt(0), ans(0), t(1);
	scanf("%lld%lld", &n, &k);
	for (int i(1); i <= n; ++ i) {
		int t, d;
		scanf("%lld%lld", &t, &d);
		q.push(node{t, d});
	}
	while (q.size() && cnt < k) {
		int x(q.top().d), cnt1(0);
		while (q.top().d == x && cnt < k) {
			if (!mark[q.top().t])
				++ cnt, ans += x + t, mark[q.top().t] = true, t += 2;
			else ++ cnt1;
			q.pop();
		}
		ans += min(k - cnt, cnt1) * x, cnt += min(k - cnt, cnt1);//尝试替换并更新答案吧
	}
	return printf("%lld", ans), 0;
}

F题，NKOJ4922。先举个例子，如果分别知道了区间 $[L,R]$ 和 $[R + 1, K]$ 总和的奇偶性，就知道 $[L,K]$ 总和的奇偶性了。那么对于每个 $C_{i,j}$，由 $i-1$ 向 $j$ 连一条边权为 $C_{i,j}$ 的边。在图上跑一个联通了 $0\sim n$ 的所有点的最小生成树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>

struct Line {
	int u, v;
	long long w;
	inline bool operator < (const Line x) const {return w < x.w;}
} e[4000005];
int fa[2005], tot;
inline int find(const int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

signed main() {
	int n, cnt(0), k(0);
	long long ans(0LL);
	scanf("%d", &n);
	for (int i(1); i <= n; ++ i) fa[i] = i;
	for (int i(1); i <= n; ++ i)
	for (int j(i); j <= n; ++ j)
		++ tot, scanf("%d", &e[tot].w), e[tot].u = i - 1, e[tot].v = j;
	std::sort(e + 1, e + tot + 1);
	while (cnt < n) {
		++ k;
		if (find(e[k].u) == find(e[k].v)) continue;
		else fa[find(e[k].u)] = find(e[k].v), ans += e[k].w, ++ cnt;
	}
	return printf("%lld", ans), 0;
}
-------------本文结束感谢您的阅读-------------