NOIp2018提高组初赛

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 表示按位与运算)

这题感觉很神,总不能32232^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