NOIP普及组 复赛2016-2011 解答.doc

NOIP 普及组 复赛 历年 试题

2018 年 03 月 13 日 08:44:30mrcrack阅读数：858

NOIP 普及组 复赛 历年 试题

NOIP2016普及组 复赛 试题

https://wenku.baidu.com/view/

c317cd8abdeb19e8b8f67c1cfad6195f312be89f.html?

rec_flag=default&mark_pay_doc=2&mark_rec_page=1&mark_rec_position=2&mark

_rec=view_r_1&clear_uda_param=1 可见试题

//57%30!=0 (57/30+1)*27=54

//该题是纯模拟的水题，重心在整数的整除，取余,找最值。

//有一个疑虑，int 是否会溢出

//试算了一下，10000/1*10000=10^8 即需求 10000 只笔，每包 1 只，每只花费

10000，故总花费 10000/1*10000=10^8，没有溢出

//同时也确定了,min 初始化要求 min>10^8

//为了拿 100 分，分析还是挺关键的。

//样例通过，信心满满，但还有些忐忑，提交，哇 20 个测试点，结果 AC 2018-3-13

#include <stdio.h>

int main(){

 if(c<min)min=c;

 }

 printf("%d",min);

 return 0;

}

2.回文日期

https://www.luogu.org/problemnew/show/P2010 可提交测评

//P2010 回文日期

//看了日期表示方式，发现正是自己平时常用的表示方式，心定了，题目读得进

//回文，发现平时也有联系

//写得过程中，发现第一年，最后一年需特殊处理

//建议，编写一个功能，测试一次，以防最后抓狂

//该题考点，分析出某个数的各个位置的值，字符串简单处理，整数取余

//样例通过，提交 AC。该题要求 程序代码 编写要比较熟练。 2018-3-13

//该题编写，新手耗时估计 1 小时

#include <stdio.h>

int y[3],m[3],d[3],a[3],c[]={0,31,0,31,30,31,30,31,31,30,31,30,31},cnt=0;

char s[10];

 int i;

 m[i]=a[i]/100,a[i]%=100;

 d[i]=a[i];

 }

}

int year(int a){//闰年判定，1 闰年 2 非闰年

 if(a%100==0)//整百年处理

 if(a%400==0)return 1;//闰年

 else return 0;

 else if(a%4==0)return 1;

 else return 0;

int check(int a){//判断回文，1 是，2 否

 return 1;

}

int main(){

 scanf("%d%d",&a[0],&a[1]);

 for(j=1;j<=12;j++){//生成 月 第一年处理

 if(j==2)//2 月单独处理

 if(year(y[0]))c[j]=29;//闰年

 else c[j]=28;//非闰年

 if(check(b))cnt++;

 }

 }

 if(j==2)//2 月单独处理

 if(year(i))c[j]=29;//闰年

 else c[j]=28;//非闰年

 for(k=1;k<=c[j];k++){//生成 日

 b=10000*i+j*100+k;

 if(check(b))cnt++;

 }

 }

 if(year(y[1]))c[j]=29;//闰年

 else c[j]=28;//非闰年

 for(k=1;k<=c[j];k++){//生成 日

 b=10000*y[1]+j*100+k;

 if(check(b))cnt++;

 }

 }

 printf("%d",cnt);

 return 0;

}

3.海港

//看了一眼数据范围,算法复杂度不能是 O(n^2)，而 O(nlogn) 比较合适

//q[100100] sum[1010]提交 MLE

//q[10010] sum[1010]提交 70 分，测试点 7-11,13 RE 很满意 2018-3-30 21:23

//以下代码为 70 分代码

//从 70 分跨越到 100 分，估计要改算法，想不下去了，考虑看看题解

//https://blog.csdn.net/c20190102/article/details/53761648 此文代码写得不错

//看了看，算法的区别在于，应选人为研究对象，而不是选船为研究对象，不过，一开

#include <stdio.h>

#include <string.h>

struct node{

 int time;

 int x;

}q[300100];//人

int h,t,vis[100100];

int main(){

 int n,time,k,i,x,cnt=0;//此处写成 int n,time,k,i,x,cnt; 忘记将 cnt 初始化

 memset(vis,0,sizeof(vis));

 scanf("%d",&n);

 h=t=1;

 while(n--){

 scanf("%d%d",&time,&k);

 while(h<t&&q[h].time+86400<=time){

 if(!vis[q[h].x])cnt--;//像不像 欧拉图 的计算

 h++;

 }

 for(i=1;i<=k;i++){

 scanf("%d",&x),q[t].time=time,q[t].x=x,t++;

 if(!vis[x])cnt++;

 vis[x]++;//有点像 欧拉图 的计算

 }

 printf("%d\n",cnt);

 }

 return 0;

//以下代码为 70 分代码，仅供参考

#include <stdio.h>

#include <string.h>

struct node{

 int time;

 int sum[1010];//此处开多少，没有把握

}q[10010];

int h,t;

int main(){

 scanf("%d",&n);

 h=t=1;

 while(n--){

 scanf("%d%d",&time,&k),q[t].k=k,q[t].time=time;

while(h<t&&q[h].time+86400>=time)h++;查了好久

 for(j=1;j<=1000;j++)q[t].sum[j]+=q[t-1].sum[j];

 t++;

 cnt=0;

 for(i=1;i<=1000;i++)

 if(q[t-1].sum[i]-q[h-1].sum[i])cnt++;

 printf("%d\n",cnt);

 }

 return 0;

https://www.luogu.org/problemnew/show/P2119 可提交测评

//P2119 魔法阵

//https://blog.csdn.net/c20181503csy/article/details/53319238 此文写得比较粗

//https://blog.csdn.net/c20182030/article/details/53289443 此文写得比较细

//可两篇文章，结合起来看

//需用到桶排序+排列组合知识

//样例通过，提交 AC 2018-4-5 12:54

#include <stdio.h>

#include <string.h>

#define maxn 15100

#define maxm 40100

#define LL long long

为物品魔法值 w[i]中 i 为魔法值,w[i]表示魔法值为 i 的物品个数 a[i]中 i 为魔法值 a[i]为该魔

}

LL max(LL a,LL b){

 return a>b?a:b;

}

int main(){

 scanf("%lld%lld",&n,&m);

 for(i=1;i<=m;i++)scanf("%lld",&h[i]),w[h[i]]+

+,min_n=min(min_n,h[i]),max_n=max(max_n,h[i]);//此处做了优化，找出魔法值的最小