NOIP2015 - 模拟考试Ⅶ

2015.10.12

闲扯

感觉良好。

Day 1

Verify

[Description]

在中华人民共和国,每位公民都有一个唯一的身份证号码。中华人民共和国的居民身份证号码由17 位本体码和1 位校验码组成。
17 位的本体码由三部分组成:地址码、出生日期码和顺序码。其中地址码占6位、出生日期码占8位、顺序码占3位。顺序码的奇数分配给男性,偶数分配给女性,同时顺序码的3位不能为全0。出生日期码的前4位表示出生年份,接下来2 位表示出生月份,最后两位表示出生日期。考虑到实际的情况,我们约定出生日期必须在1900 年1月1日到2011年12月31日的范围内,并且对于闰年的2月有29日。最后对于地址码,它表示所属的行政区划,输入文件中会给出对于该测试点所有可行的地址码。
1 位的校验码是根据前面17 位计算得出的。将本体码从左到右用a1,a2, … ,a17表示,校验码用x表示,则下面的关系成立:
$$x+\sum_{i=1}^{17}2^{18-i}\cdot ai\equiv1(mod\ 1)$$
其中0≤x≤10,如果x=10,就用大写英文字母X表示。
按照前面的规定,可以验证11010519491231002X是一个合法的女性身份证号码(110105 是北京市朝阳区的地址码)。
现在要你写一个程序验证给定的身份证号码是否合法,并且对于合法的身份证,给出这位公民的性别。

[Hint]

不超过$10^5$组数据。

[Solution]

典型OpenJudge题…
地址用桶判断。日期注意闰年。性别只用看第17位。

Block

[Description]

Crash有n块长条状的积木,这些用正整数1~n编号。现在Crash将这些积木顺着排成一条直线,每块都有个正整数高度,为了保证一块积木倒下时不会将别的积木碰倒,两块相邻间距离为这两块积木高度的较大值。
Crash希望你帮他找到一种排列积木的方案,使得相邻两块间距离和最小。同时在满足上述条件的前提下,也希望你能给出字典序排列最小的方案。

[Hint]

$n≤10^5$

[Solution]

最小的距离和很容易算出,即为从小到大排成直线得到的距离。
然而这样不一定是字典序最优。还有什么情况总距离也能达到这个值呢?那就是高度先减后增排列。
所以我们很容易构造出一个字典序的排法:先从小到大放,只要比之前那个小,就把它放下,再把所有剩下的排序,第一关键字为高度,第二关键字为编号。这样构造的高-低-高序列一定是满足题意的字典序最小序列。

Gift

[Description]

Crash买来n件礼物,他要将这些送给的好(基)友们。
Crash先将礼物们排成一排,从左到右用正整数1~n编号,每件礼物有一个正整数的价值,依次用w1,w2, … ,wn表示。Crash送给每位好友的礼物一定是编号上连续的一段,满足这些礼物中任意两件的价值差不会超过m,同时送给每个好友的礼物数不少于k。
给出m,k和每件礼物的价值,问Crash最多能送出多少件礼物。

[Solution]

我若是找出所有满足要求的区间,即可用一个$O(n)$的DP求解答案了。
怎么找呢?用单调队列维护就好了!

Day 2

Sequence

[Description]

x的有趣数列$f$定义为:
$$f(i)=
\begin{cases}
x & i=1 \\
x/2 & i\not=1且f(i-1)为偶数 \\
x-1 & i\not=1且f(i-1)为奇数 \\
\end{cases}
$$
求闭区间[a,b]内有几个数的有趣数列存在整数k.

[Solution]

稍微写写写发现规律:
有序数列存在某奇数e的数:
e/2e,2e+1/4e,4e+1,4e+2,4e+3/8e,8e+1…
有序数列存在某偶数o的数:
o,o+1/2o,2o+1,2o+2,2o+3/4o,4o+1…
发现合法的数都是长度成两倍增长的一段区间,这样,我们可以写一个简单的倍增来$O(logn)$计算每个询问了。
一个小技巧,答案等于0~b内合法的数0~a-1内合法的数,这样统计起来比较方便。
注意特判区间越界的情况,还有k=0,1,2时也要注意。

[Code]

觉得我代码写得十分优美啊~那就贴出来吧er

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
#include<cstdio>

typedef long long ll;

ll bin[60];
void prework(){
bin[0]=1;
for(int i=1;i<60;i++) bin[i]=bin[i-1]<<1;
}

ll f(ll r,ll x){
ll res=0;
for(int k=!(x%2);x<=r;k++){
if(x+bin[k]>r){ res+=r-x+1; break; }
if(x<=bin[k]){ res+=r-x+1; break; }
res+=bin[k]; x<<=1;
}
return res;
}

int main(){
//freopen("sequence.in","r",stdin);
//freopen("sequence.out","w",stdout);
prework();
int kase; scanf("%d",&kase);
while(kase--){
ll k,a,b; scanf("%lld%lld%lld",&k,&a,&b);
printf("%lld\n",f(b,k)-f(a-1,k));
}
return 0;
}

Point

[Description]

统计整点$n(n≤10^5)$边形内的整点有多少(不算边界)。

[Solution]

天真的我以为脑补出矩形割补就可以秒了这道题…结果发现边界上的点根本不可处理啊!
要是知道有皮克定理这种东西早就秒了qwq

皮克定理
a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积,若三角形顶点都为整点,那么它们三者满足:
$$S=a+\frac{b}{2}-1$$

顿时感觉被神一脸啊…
然后多边形面积用叉乘或者前面提到的矩形割补都可算,边界上的点用gcd就能算了。
然后就这么神奇的做完了- -

Treasure

此题有毒,暂不宜放上来。

Summary

还是感觉良好。