NOIp2018提高组初赛

发表于 更新于 阅读次数： 本文字数： 4.4k 阅读时长 ≈ 4 分钟

NOIp2018初赛在10月13日下午在建功进行。总体上讲，今年难度和去年差不多，但是选择题比以前减少了5题，一题从1.5分到2分。另外感觉更加考察数学了。lzh说这意味着复赛优秀的人可以不再花很多时间看初赛，还能卡掉只搞初赛的某些学校。

下面以quiz的形式回顾一些有趣的或我错的题目。完整的题目相信不久之后就会出现在洛谷有题。另参考https://www.luogu.org/blog/zcysky/noip2018-chusai-tg-sol。

单选T3

中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。

考历史？或者你知道今年是第几届NOI，并且中间没断过也可以。我凭印象写出了1984。另一种方法是在去年在sxyz举行NOI时，旗子上写着令人吐槽的“34rd”，不过我记错了，导致算出来是1985，但我还是选了1984。蒙对*1。

单选T7

在一条长度为1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（ ）。

并不会做，于是蒙了1 / 2。但这次蒙错了，正解是固定一点，期望是1 / 2，而不固定显然小于1 / 2。也有严格证明，但看起来很麻烦。

单选T9

假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（ ）。

又是奇怪的概率题，不过这次还和无穷数列有关。我没认真做，不想用数学方法，大概估算了一下极限，选了1 : 2。蒙错*2。目前我还没完全理解。

不定项T1

NOIP 初赛中，选手可以带入考场的有（ ）。

又是神奇的题目，如果你认真听考试说明应该就不会错了，可知后两项是错的。不过当时我很纠结橡皮能不能带，因为考试说明好像没提到。

不定项T5

下列关于图灵奖的说法中，正确的有（ ）。

常识题，B让我想到zyy前几天说过的，但那是华裔；A和C我不太记得；D显然是对的。于是根据一般情况，我选了ABCD，又错了。原来图灵奖是ACM设立的，名称就是“ACM Turing Award”。

问题求解T2

方程 a*b = (a or b) * (a and b)，在 a,b 都取 [0, 31] 中的整数时，共有_____组解。（*表示乘法；or 表示按位或运算；and 表示按位与运算）

这题感觉很神，总不能$32^2$暴力吧。一开始我在想按位考虑，但显然是假的。回头再做时，想到一个结论，只有a和b二进制表示下“1”一个为另一个的子集才能满足条件，装作是对的，因为举不出反例。因为只有32，设a<b，直接暴力枚举再加起来*2-32。后来Fop_zz指出可以用杨辉三角算出答案。

阅读程序T4

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
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];
bool isSmall() {
	for (int i = 1; i <= n; ++i)
	if (a[i] != b[i]) return a[i] < b[i];
	return false;
}
bool getPermutation(int pos) {
	if (pos > n) {
		return isSmall();
	}
	for (int i = 1; i <= n; ++i) {
		if (!isUse[i]) {
			b[pos] = i; isUse[i] = true;
			if (getPermutation(pos + 1)) {
				return true;
			}
			isUse[i] = false;
		}
	}
	return false;
}
void getNext() {
	for (int i = 1; i <= n; ++i) {
		isUse[i] = false;
	}
	getPermutation(1);
	for (int i = 1; i <= n; ++i) {
		a[i] = b[i];
	}
}
int main() {
	scanf("%d%d", &n, &t);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= t; ++i) {
		getNext();
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d", a[i]);
		if (i == n) putchar('\n'); else putchar(' ');
	}
	return 0;
}

输入1：6 10 1 6 4 5 3 2

输出1：_________（3 分）

输入2：6 200 1 5 3 4 2 6

输出2：_________（5 分）

容易看出是全排列向后枚举，尽管写得很奇怪。部分分也很合理，10可以暴力模拟，200就不太现实了。我记得全排列是有唯一编码方案的，不久我就想出来了：从左往右按位考虑，每次加上右边比当前小的数个数*(右边!)即可。用10可以验证这样是对的，于是我写了200。回来没记答案，好像是对的(280)。看了洛谷题解，才发现这好像就是康托展开，好像乱搞就能过。

感觉和去年T4接近，有暴力分和需要数学分析的分，区分度较好。

完善程序T2

一只小猪要买N 件物品（N 不超过1000）。

它要买的所有物品在两家商店里都有卖。第i 件物品在第一家商店的价格是a[i]，在第二家商店的价格是b[i]，两个价格都不小于0且不超过10000。如果在第一家商店买的物品的总额不少于50000，那么在第一家店买的物品都可以打95 折(价格变为原来的0.95 倍)。

求小猪买齐所有物品所需最少的总额。

输入：第一行一个数N。接下来N 行，每行两个数。第i 行的两个数分别代表a[i]，b[i]。

输出：输出一行一个数，表示最少需要的总额，保留两位小数。

试补全程序。（第一空2 分，其余3 分）

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <algorithm>
using namespace std;
const int Inf = 1000000000;
const int threshold = 50000;
const int maxn = 1000;
int n, a[maxn], b[maxn];
bool put_a[maxn];
int total_a, total_b;
double ans;
int f[threshold];
int main() {
	scanf("%d", &n);
	total_a = total_b = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", a + i, b + i);
		if (a[i] <= b[i]) total_a += a[i];
		else total_b += b[i];
	}
	ans = total_a + total_b;
	total_a = total_b = 0;
	for (int i = 0; i < n; ++i) {
		if ( (1) ) {
			put_a[i] = true;
			total_a += a[i];
		} else {
			put_a[i] = false;
			total_b += b[i];
		}
	}
	if ( (2) ) {
		printf("%.2f", total_a * 0.95 + total_b);
		return 0;
	}
	f[0] = 0;
	for (int i = 1; i < threshold; ++i)
		f[i] = Inf;
	int total_b_prefix = 0;
	for (int i = 0; i < n; ++i)
	if (!put_a[i]) {
		total_b_prefix += b[i];
		for (int j = threshold - 1; j >= 0; --j) {
			if ( (3) >= threshold && f[j] != Inf)
				ans = min(ans, (total_a + j + a[i]) * 0.95 + (4) );
			f[j] = min(f[j] + b[i], j >= a[i] ? (5) : Inf);
		}
	}
	printf("%.2f", ans);
	return 0;
}

这题比上一题随便乱填、对称就可以过不同，而且居然考了DP。

(1)我没怎么想就填了a[i] <= b[i]，虽然前面一样出现过。错了，还好只有2分。

(2)(3)比较简单。

(4)(5)又比较难，但有个优点：显然f[]、total_b_prefix一定要用，否则就不用算了。(4)需要计算在B商店的消费，可以发现f[]只有前i个相关的信息，后面的只能都买了。再看(5)，显然要用到f[j-a[i]]，但和背包又不太像。

结果

可以发现如果没有未发现的错误，估分92。%%%lzh AK，其他OIer结果不一。

最终获得了94，应该是a[i] <= b[i]认为是对的，并且似乎左边只要不小于a[i] * 0.95就是对的，理论上0/false也是对的……swwind 68，fks 73（虽然估分72或75），一直感觉危险，其他都比较高。最终浙江提高68，普及77，借助唯一的名额，高二就只有sgr退出了。不过高一就惨多了，有不少进不了复赛。

浙江还出了疑似泄题，最终认定是博客的问题，不能显示更新的时间。不过写博客本来就是为了“吸引点击量”的。吓得我都不敢提前开复赛游记之类的了，还好我用的主题早就支持显示更新时间了。详见http://www.noi.cn/newsview.html?id=760&hash=02E485&type=1。