NOIP2016普及组复赛试题讲解(c++版本)定稿.ppt

程序框架 输入数据 for i=day_start div 10000 // 取年份 =day_end div 10000 //循环起始到结束年份 if （check(i)） // 判断i年对应的日期是否符合要求 特别注意：还要判断这个日期是否在范围内 新版课件 - * - 第3题 “海港”简述 小K按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti (单位：秒)，船上的乘客数量ki，以及每名乘客的国籍 x(i,1), x(i,2),…，x(i,k)。? 小K统计了n艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的24小时(24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。? 形式化地讲，你需要计算n条信息。对于输出的第i条信息，你需要统计满足 ti - 86400 tp = ti的船只p，在所有的x(p,j)中，总共有多少个不同的数 输出n行，第i行输出一个整数表示第i艘船到达后的统计信息。? 新版课件 - * - 暴力算法（预计分数70分） h[100001];h[x]表示国籍为x的乘客到港的必威体育精装版时间。初始值为-86400. sum [100001]；sum [1-n]表示1-n个艘船到达海港对应的国籍数量。 每一艘船到达海港，更新对应国籍乘客的到港时间数组h 统计所有国籍的到港时间是否在24小时内，t为当前时间，t-h[x]86400，表示X国籍满足条件。 时间复杂度：O(kt+n*x) 新版课件 - * - 确定解题思路 题目明确告诉我们，要计算的是中间的一段时间的统计结果。 从数据结构的角度看，是“队列”：先进先出 所有 ki之和=300000，也就是总人数少于30万 队列中记录时间和国籍，到达的入队，超过86400秒的出队，时间复杂度 O(kt) 如何统计“总共有多少个不同的数” 呢？ 1=Xi,j=100000 ，当然用Hash (桶) 新版课件 - * - 数据结构 队列：用数组qt：时间，qx：国籍 int qt[300005], qx[300005]; 头指针: head，尾指针：tail Hash表： int hs [100005; 新版课件 - * - 参考程序 #includeiostream #includecstring using namespace std; int const maxn=300005; int qt[maxn],qx[maxn]; int hs[100005]; int head=1,tail=1,n,i,j,ti,tic,ki,xi,cnt=0; int main() { memset(hs,0,sizeof(hs)); cinn; for(i=1;i=n;i++) { cintiki; for(j=1;j=ki;j++) for(j=1;j=ki;j++) { cinxi; qt[tail]=ti; qx[tail]=xi; if (hs[xi]==0) cnt++; hs[xi]++; tail++; } tic=ti-86400; while(qt[head]=tic) { xi=qx[head]; hs[xi]--; if(hs[xi]==0) cnt--; head++; } coutcntendl; } return 0; } 新版课件 - * - 第4题 “魔法阵”简述 大魔法师认为，当且仅当四个编号为a,b,c,d的魔法物品满足 Xa Xb Xc Xd， Xb-Xa=2(Xd-Xc)， 并且Xb-Xa(Xc-Xb)/3时， 这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的A物品，B物品，C物品，D物品。? 现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的A物品出现的次数，作为B物品的次数，作为C物品的次数，和作为D物品的次数。 新版课件 - * - 确定解题思路 【分析】压轴题，当然要难 这题几乎是个数学题 首先要会画“线段图” 其次，“加法原理”“乘法原理”要熟练 最后，是“胆大心细”编程能力 新版课件 - * - 2017. 07. 28 试题分析 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版