NOIP2015 - 模拟考试Ⅶ

感觉良好。

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,…,a17a_1,a_2, … ,a_{17}表示，校验码用x表示，则下面的关系成立：

x+∑i=117218−i⋅ai≡1(mod 1)x+\sum_{i=1}^{17}2^{18−i}⋅a_i≡1(mod\ 1)

其中0≤x≤10，如果x=10，就用大写英文字母X表示。
按照前面的规定，可以验证11010519491231002X是一个合法的女性身份证号码（110105 是北京市朝阳区的地址码）。
现在要你写一个程序验证给定的身份证号码是否合法，并且对于合法的身份证，给出这位公民的性别。

[Hint]

不超过10510^5组数据。

[Solution]

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

Block

[Description]

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

[Hint]

n≤105n≤10^5

[Solution]

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

Gift

[Description]

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

[Solution]

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

Day 2

Sequence

[Description]

x的有趣数列f定义为：

{x,i=1x/2,i≠1 and f(i−1)≡0(mod 2)x−1i≠1 and f(i−1)≡01mod 2)\begin{cases} x, & i=1 \\ x/2, & i\neq 1\ and\ f(i-1)≡0(mod\ 2)\\ x-1 & i\neq 1\ and\ f(i-1)≡01mod\ 2) \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≤105)边形内的整点有多少（不算边界）。

[Solution]

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

皮克定理
a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积，若三角形顶点都为整点，那么它们三者满足：
S=a+b2−1
顿时感觉被神一脸啊…
然后多边形面积用叉乘或者前面提到的矩形割补都可算，边界上的点用gcd就能算了。
然后就这么神奇的做完了- -

Treasure
此题有毒，暂不宜放上来。

Summary
还是感觉良好。

Comment