NOIP2016 普及组 解题报告

T1 买铅笔

题目来源：洛谷 1909

思路：

实现一下向上取整的步骤，对三种决策取最小值。 时间复杂度： O(1)

代码：

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int num, val, n, res = 2e9; int main(){ scanf("%d", &n); for(int i = 1; i <= 3; i ++){ scanf("%d%d", &num, &val); res = min((int)((double)n/(double)num+0.999)*val, res); } printf("%d", res); return 0; }

T2 回文日期

题目来源：洛谷 2010

思路：

良心的noip普及组难度的字符串处理题，按照题目描述按部就班的做，只要不怕麻烦，就可以过啦。 时间复杂度： O(两个日期差的天数∗8)<O(3×107)

代码：

#include <iostream> #include <cstdio> #include <cstring> using namespace std; char ch1[10], ch2[10], ch3[10]; int year1, mon1, day1; int year2, mon2, day2; int time1[15] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int ans; int main(){ scanf("%s%s", ch1+1, ch2+1); year1 = (ch1[1]-'0')*1000 + (ch1[2]-'0')*100 + (ch1[3]-'0')*10 + (ch1[4]-'0'); mon1 = (ch1[5]-'0')*10 + (ch1[6]-'0'); day1 = (ch1[7]-'0')*10 + (ch1[8]-'0'); year2 = (ch2[1]-'0')*1000 + (ch2[2]-'0')*100 + (ch2[3]-'0')*10 + (ch2[4]-'0'); mon2 = (ch2[5]-'0')*10 + (ch2[6]-'0'); day2 = (ch2[7]-'0')*10 + (ch2[8]-'0'); for(int i = year1; i <= year2; i ++){ int begin1 = (i == year1 ? mon1 : 1), end1 = (i == year2 ? mon2 : 12); for(int j = begin1; j <= end1; j ++){ int begin2 = ((i == year1 && j == mon1) ? day1 : 1); int end2 = ((i == year2 && j == mon2) ? day2 : time1[j]); if((j==2) && ((i%400)||(i%4==0 && i%100!=0))) end2 = 29; for(int k = begin2; k <= end2; k ++){ ch3[1] = '0'+(i/1000)%10; ch3[2] = '0'+(i/100)%10; ch3[3] = '0'+(i/10)%10; ch3[4] = '0'+(i/1)%10; ch3[5] = '0'+(j/10)%10; ch3[6] = '0'+(j/1)%10; ch3[7] = '0'+(k/10)%10; ch3[8] = '0'+(k/1)%10; ch3[9] = '\0'; bool ok = 1; for(int l = 1; l <= 4; l ++){ if(ch3[l] != ch3[8-l+1]){ ok = 0; break; } } if(ok) ans ++; } } } printf("%d", ans); return 0; }

T3 海港

题目来源：洛谷 2058

思路：

考虑来一艘船，就把船上所有人的信息记录到一个队列里，时间超过了以后，直接把超出时间限制的弹出去，具体的来说：用两个指针控制时间轴向后扫逐个到来的乘客，用数组维护一下当前的国籍，时间复杂度： O(∑ki) 。

代码：

#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node{ int time, pos; }; node boat[100010]; int nation[100010], person[300010], res; int main(){ int n; scanf("%d", &n); int p1 = 1, p2 = 0, now = 1; for(int i = 1; i <= n; i ++){ int t; scanf("%d%d", &boat[i].time, &t); boat[i].pos = p2 + t; while(boat[i].time - boat[now].time >= 86400){ for( ; p1 <= boat[now].pos; p1 ++){ nation[person[p1]] --; if(nation[person[p1]] == 0) res --; } now ++; } for(int j = 1; j <= t; j ++){ scanf("%d", &person[++p2]); if(nation[person[p2]] == 0) res ++; nation[person[p2]] ++; } printf("%d\n", res); } return 0; }

T4 魔法阵

题目来源：洛谷 2119

思路：

先观察题目里的三个条件： Xa<Xb<Xc<Xd Xb−Xa=2(Xd−Xc) 3(Xb−Xa)<(Xc−Xb) 第一个条件告诉我们，选择的四元组必须是一个严格递增的。 对于后两个条件，先转换成数学模型，不难发现其中 Xd−Xc 是最小的单位，所以我们可以令 t=Xd−Xc ，则整理式子后可以写成： Xd−Xc=t Xb−Xa=2t Xc−Xb>6t 到现在为止我们找到了一组关于 a,b,c,d 的连续的关系，于是就可以计算了。 因为题目里的数字的范围比数字的数量要少，所以用桶排序，根据乘法原理，一个数要是出现了多次直接乘上就好了。 然后我们枚举长度 t ，在分别枚举a,d的位置，当枚举了 t 和任意一个点的位置以后，其余的点根据上面的连续的关系都可以直接确定。 不难发现有一部分的计算是重复的，所以可以用一个变量记录一下前缀和，每次跟新以后直接加在后面。 时间复杂度O(n29)

代码：

#include <cstdio> #include <cstring> #include <cstdlib> #include <cstring> using namespace std; int n, m; int val[40010], num[15010]; int a[15010], b[15010], c[15010], d[15010]; int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++){ scanf("%d", &val[i]); num[val[i]] ++; } for(int i = 1; i*9+1 <= n; i ++){ int sum = 0; for(int j = i*9+2; j <= n; j ++){ sum += num[j-7*i-1] * num[j-9*i-1]; c[j-i] += num[j] * sum; d[j] += num[j-i] * sum; } sum = 0; for(int j = n-i*9-1; j >= 1; j --){ sum += num[j+i*9+1] * num[j+i*8+1]; a[j] += num[j+2*i] * sum; b[j+2*i] += num[j] * sum; } } for(int i = 1; i <= m; i ++){ printf("%d %d %d %d\n", a[val[i]], b[val[i]], c[val[i]], d[val[i]]); } return 0; }