NOIP2015 - 模拟考试Ⅷ

2015.10.15

闲扯

只是感觉运气比较好。

Day 1

Sparta

[Description]

序列区间加值,区间修改,区间求和。

[Hint]

序列长和操作数均不超过$10^5$.

[Solution]

裸线段树咯,然后挂了。

Divisor

[Description]

求因数个数为x的最小自然数。

[Hint]

保证答案在long long范围内。

[Solution]

因数个数和+记忆化搜索(DP).

[Summary]

有人说这道题考过三次然而自己完全不记得…qwq
然后以一种奇怪的贪心骗到90分…

Competition

[Description]

n个人,每个人一个名字(长度不超过20的字符串),当前比赛分数。现在要进行最后一场比赛,给出这场比赛1~n名分别能拿多少分。
询问某个人经过这场比赛后最前和最后能拍到多少名(分数相同按名字字典序从大到小排列)。

[Solution]

贪心。
仅讲排名尽量靠前的做法,排名靠后与其类似。
将所有人以分数从高到低为第一关键字,名字从字典序小到大为第二关键字排序。把最高分给这个人。
分数从小到大考虑每个人,从大到小考虑每个分数,找到一个最大的分数使得这个人不能超过指定的人的最高分之后的排名(这样造成的浪费最少)。
依次考虑,即可求出最多能让多少个人不超过他,进而求出他的排名。
复杂度$O(n)$.

Day 2

PF

[Description]

求第x个斐波那契数的个位数。

[Hint]

$x≤10^{12}$.

[Solution]

x%=60;

[Summary]

看到题目就随手写了个矩乘…看到题解之后发现脑子简直秀逗了。

Poker

[Description]

将若干张纸牌分成n堆,摆成一个环。每次可以移动某中的若干张牌到一个相邻的牌堆中,求最少移动次数使得每张样多。

[Hint]

$n≤10^6$.

[Solution]

考虑链状的:
将每堆纸牌减去平均数,序列中的非零整数个数就是最小移动次数(非常好理解)。
考虑环状的:
即我们要选一个起点拆成一条链,使得序列中0最多。发现若把第一个数放到最后(即起点后移一位),这样得到的整个序列每个数都会减去这个数。所以整个序列与它相同的数都会变成零。
所以选择不同的起点,都会有一些相同的数变成0。所以最多的0的个数就是这个序列的众数个数。
然后得到答案。

ACnum

[Description]

一个数是ACnum,当且仅当它满足以下所有条件:

  1. 10进制表示中,奇数偶数出现的个数都不超过5次;
  2. 每个数字出现的次数不超过4次;
  3. 不包含前导0.

求区间[L,R]内有多少个ACnum.

[Hint]

源程序不超过150KB,不超过10组数据,$1≤L≤R≤10^{12}$.

[Solution]

分块打表…

[Summary]

正解简直神我一脸…竟然还有一人一狗AC了qwq跪跪跪