NOIP 提高组 复赛 历年 试题
NOIP 提高组 复赛 历年 试题
NOIP 2017 提高组 复赛 试题
https://wenku.baidu.com/view/70de9e29854769eae009581b6bd97f192279bf62.html可见试题
1.小凯的疑惑
https://www.luogu.org/problemnew/show/P3951可提交测评
NOIP 2016 提高组 复赛 试题
https://wenku.baidu.com/view/c58b2ffc9f3143323968011ca300a6c30d22f155.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&sxts=1525958761290可见试题
上述试题中的2018-5-15
第二试
1.组合数问题
样例2输出有误，应为：
0
7
第一试
1.玩具谜题
https://www.luogu.org/problemnew/show/P1563可提交测评
//P1563 玩具谜题
//忽左忽右，决定还是全转化到逆时针上来
//按上述思路进行模拟
//模拟一遍成功，逆时针+，顺时针-，注意负数处理，取模处理
//需编写一个函数，输入，小人站位，小人左右手，输出逆顺时针。
//处理数C(2,1)*C(2,1)=4编起来还方便
//0 0 顺时针 0
//0 1 逆时针 1
//1 0 逆时针 1
//1 1 顺时针 0
//样例通过，提交AC。2018-5-6 11:26
//翻看了一年半前 2016-12-30写的代码，发现，水平是明显上了一个台阶。
#include <stdio.h>
#define maxn 100100
int n,m,stand[maxn];
char name[maxn][15];
int judge(int stand,int hand){//判断逆时针1 顺时针0，该函数极为关键
if(stand==0){
if(hand==0)return 0;
else return 1;
}else{
if(hand==0)return 1;
else return 0;
}
}
int main(){
int i,hand,cnt,pos=0;//pos=0表示从第一个小人开始处理
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d%s",&stand[i],name[i]);
for(i=1;i<=m;i++){
scanf("%d%d",&hand,&cnt);
if(judge(stand[pos],hand)){//逆时针处理
pos=(pos+cnt)%n;
}else{//顺时针处理
pos=((pos-cnt)%n+n)%n;//注意，吃出已经包含了负数处理
}
}
printf("%s",name[pos]);
return 0;
}
2.天天爱跑步
https://www.luogu.org/problemnew/show/P1600可提交测评
//P1600 天天爱跑步
//看懂样例是关键
//" 在结点 j 的观察员会选择在第 Wj 秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj秒也理到达了结点 j "
//通过样例，弄明白了，观察员，只能在某一时刻进行观察，前后时刻都观察不了
//手动模拟了样例
//看了数据范围，si=ti应可以得分 2*5=10
//wj=0也应该可以得分2*5=10
//树退化成一条链，该类型应该也可以得分3*5=15
//该题得35分应该容易
//以下代码为20分代码,测试点1,12,14,15正确 2018-5-8
#include <stdio.h>
#include <string.h>
#define maxn 300100
int n,m,s[maxn],t[maxn],w[maxn],head[maxn],cnt=0,c[maxn],time[maxn];//c[]统计观察到的玩家数
struct node{
int to;
int next;
}e[maxn*2];
void add_edge(int u,int v){
cnt++,e[cnt].to=v,e[cnt].next=head[u],head[u]=cnt;
}
int main(){
int i,u,v,s_flag=0,w_flag=0;
memset(head,0,sizeof(head)),memset(time,0,sizeof(time));
scanf("%d%d",&n,&m);
for(i=1;i<n;i++){
scanf("%d%d",&u,&v);
add_edge(u,v),add_edge(v,u);//无向图
}
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
for(i=1;i<=m;i++)
scanf("%d%d",&s[i],&t[i]);
for(i=1;i<=m;i++)
if(s[i]!=t[i]){
s_flag=1;
break;
}
for(i=1;i<=n;i++)
if(w[i]!=0){
w_flag=1;
break;
}
if(s_flag==0){//si==ti 5*2=10
for(i=1;i<=m;i++)
if(w[s[i]]==0)
c[s[i]]++;
for(i=1;i<=n;i++)
printf("%d ",c[i]);
return 0;
}
if(w_flag==0){//w[i]=0
for(i=1;i<=m;i++)
c[s[i]]++;
for(i=1;i<=n;i++)
printf("%d ",c[i]);
return 0;
}
return 0;
}
3.换教室
https://www.luogu.org/problemnew/show/P1850可提交测评
//P1850 换教室
//根据样例，弄懂题意
//看了数据范围，得分是第一关键，不要求拿满分
//最短路径，决定采用floyd算法，存储图 采用 邻接矩阵
//为了弄懂样例1，先要进行部分编码，floyd算法，邻接矩阵
//看了数据范围，发现m=0的测试点有6个，预计可以得分5/25*100=20
//m=1的测试点有7个，预计可以得分5/25*100=20
//基本是该题在考试时的得分极限。
//分块处理，先处理m=0,编好后，将样例数据略作修改，进行测试，提交，测试点4,8,21,24正确，得分16，还算满意
//最大答案测算300*90000=2.7*10^7
//再处理m=1,编好后，将样例数据略作修改，进行测试，提交，测试点4,8,21,24正确,测试点1,14,22正确，总得分28，还算满意。
//考试中，这样的得分，还算理想。2018-5-14
#include <stdio.h>
#include <string.h>
#define maxn 2100
#define maxv 310
#define INF 200000000
int e[maxv][maxv];//最大边长 2000*90000=1.8*10^8
int N,M,V,E,c[maxn],d[maxn],tmp_c[maxn];
double p[maxn];
double min(double a,double b){
return a<b?a:b;
}
void floyd(){
int i,j,k;
for(k=1;k<=V;k++)
for(i=1;i<=V;i++)
for(j=1;j<=V;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
}
int main(){
int i,j,k,u,v,w;
double ans_0=0,ans_1,ans_min=999999999;
scanf("%d%d%d%d",&N,&M,&V,&E);
for(i=1;i<=N;i++)scanf("%d",&c[i]);
for(i=1;i<=N;i++)scanf("%d",&d[i]);
for(i=1;i<=N;i++)scanf("%lf",&p[i]);
for(i=1;i<=V;i++)//邻接矩阵初始化
for(j=1;j<=V;j++)
if(i==j)e[i][j]=0;
else e[i][j]=e[j][i]=INF;
for(i=1;i<=E;i++){//读入边
scanf("%d%d%d",&u,&v,&w);
e[u][v]=e[v][u]=w;
}
floyd();
//print();
for(i=2;i<=N;i++)//M==0测算
ans_0+=e[c[i-1]][c[i]];
if(M==0){
printf("%.2lf",ans_0);
return 0;
}
if(M==1){
ans_min=min(ans_min,ans_0);
for(i=1;i<=N;i++){
memcpy(tmp_c,c,sizeof(c)),tmp_c[i]=d[i],ans_1=0;;
for(j=2;j<=N;j++)
ans_1+=e[tmp_c[j-1]][tmp_c[j]];//此处写成 ans_1+=e[tmp_c[i-1]][tmp_c[i]];通过跟踪才查出
ans_1=ans_1*p[i]+ans_0*(1-p[i]);
ans_min=min(ans_min,ans_1);
}
printf("%.2lf",ans_min);
return 0;
}
return 0;
}
第二试
1.组合数问题
https://www.luogu.org/problemnew/show/P2822可提交测评
//P2822 组合数问题
//看懂题目，模拟样例是关键
//样例1很快模拟成功
//样例2也很快模拟成功，发现同样n情况下，0-n之间的数据具有对称性
//在看数据范围之前，担心组合数的计算 容易 溢出int 或是long long
//该题目标，还是要部分得分
//看了数据范围，朴素算法，测试点1-6应可以拿下
//剩下的数据,t=1应该也可以拿下部分，
//该题总体目标，希望能拿到50分以上
//统计个数 推算 (1+2000)*2000/2*10^4=2*10^6*10^4=2*10^10故int 溢出 需采用 long long
//计算 组合数 int 2^31-1 可算到 12!
//long long 2^63-1 可算到 20！
//计算组合数，采用 杨辉三角
//测试了数据，n=2000，程序中途退出
//n=110比较流畅
//充满信心，估计60分有望
//一个不当心，提交，全RE，一看 此处写成 for(i=0;i<=maxn;i++) Dev-C++4.9.9.2 测不出数组越界
//略作修改，提交，70分，测试点6,8WA,9,10,11,13RE
//数组越界,用Dev-C++4.9.9.2如何测试，想了想，测不出，是该编译器的Bug
//只能在编写的时候留个心，担心数组越界，写代码的过程，长个心眼，看看有无越界
//到目前为止，已进入 国二 水平 2018-5-15 100+20+28+70=218 目前还有两题未做
//胆子大一点，将数组开到2100*2100，提交70分，测试点6,8,9,11 WA;10,13TLE
//仔细想一想，考试还是要求稳，提交时，将数组开小些，确保部分得分。
//以下为70分代码。
//在想，需要高精度算法吗，不过，考试中若真的是高精度算法，应该不会再写下去了。
//该题，主要问题是,long long 溢出，既然最后结果是%k，何不中间结果%k
//c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;//此句此前写成 c[i][j]=(c[i-1][j-1]+c[i-1][j]) 70分，修改后90分
//测试点10,13TLE,很满意90分。2018-5-19 15:18
//以下为90分代码
//超时，发生在多次查询，因结果在查询前，已成定局，何不开个数组存储统计结果.
//因程序大动，需对样例进行重新测试，测试通过后，还要与之前的代码进行对拍，这就是大改代码的后果。
//突然想起两个名词，最后10分，两个测试点，考察的是，将“在线查询”改成“离线查询”
//没做对拍，提交30分，测试点2-11,13,15,17,19WA,所以，100分有比较大的风险。
//重新评估了该题，70分最没有风险，90分风险较小，100分，风险巨大。
//以下代码为为了得100分，而实际得30分的代码。2018-5-19 15:45
//经 对拍
//发现以下代码确实有问题，也查出了问题，提供一组 输入 输出 数据 给大家
输入：
1 2
4 0
输出：
0
#include <stdio.h>
#define LL long long
#define maxn 2100
LL c[maxn][maxn],d[maxn][maxn];
LL min(LL a,LL b){
return a<b?a:b;
}
int main(){
LL i,j,n,m,k,t,cnt=0;
for(i=0;i<=2000;i++)c[i][0]=1;//此处写成 for(i=0;i<=maxn;i++) Dev-C++4.9.9.2 测不出数组越界
for(i=0;i<=2000;i++)c[i][i]=1;//此处写成 for(i=0;i<=maxn;i++)
scanf("%lld%lld",&t,&k);
for(i=1;i<=2000;i++)
for(j=1;j<=i;j++)//此处写成 for(j=1;j<=2000;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;//此句此前写成 c[i][j]=(c[i-1][j-1]+c[i-1][j]) 70分，修改后90分
for(i=0;i<=2000;i++)//此处写成 for(i=0;i<=n;i++) 查了会
for(j=0;j<=i;j++){
if(c[i][j]%k==0)
cnt++;
d[i][j]=cnt;//d[i][j]表示[0][0]->[i][j]之间的统计数量
}
while(t--){//查询耗时，故，算法要进行修改
scanf("%lld%lld",&n,&m);
printf("%lld\n",d[n][min(n,m)]);
}
return 0;
}
对拍程序如下：
---------------------------------------------------------------------------------------------------------------
test.cpp
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int main(){
int i;
double st,ed;
for(i=1;i<=1000;i++){
system("random");
st=clock();
system("p2822-3");
ed=clock();
system("p2822-2");
if(system("fc data.out data.ans")){
printf("#%d Error\n",i);
break;
}
printf("#%d Success time is %.0lfms\n",i,ed-st);
}
return 0;
}
random.cpp
//该代码编好后，在cmd看了运行结果，之后输出到文件，又看了文件里的数据，基本确认无误，该代码编写完成.2018-5-19 16:16
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LL long long
#define max_t 3
#define max_k 5
#define max_n 6
#define max_m 10
int random(int n){
return (LL)rand()*rand()%n;
}
int main(){
int t,k,n,m,i;
freopen("data.in","w",stdout);
srand((unsigned int)time(0));
t=random(max_t)+1;//范围1<=t<=max_t
k=random(max_k)+2;
printf("%d %d\n",t,k);
while(t--){
n=random(max_n);
m=random(max_m);
printf("%d %d\n",n,m);
}
return 0;
}
p2822-2.cpp
#include <stdio.h>
#define LL long long
#define maxn 2100
LL c[maxn][maxn];
LL min(LL a,LL b){
return a<b?a:b;
}
int main(){
LL i,j,n,m,k,t,cnt;
freopen("data.in","r",stdin);
freopen("data.ans","w",stdout);
for(i=0;i<=2000;i++)c[i][0]=1;//此处写成 for(i=0;i<=maxn;i++) Dev-C++4.9.9.2 测不出数组越界
for(i=0;i<=2000;i++)c[i][i]=1;//此处写成 for(i=0;i<=maxn;i++)
scanf("%lld%lld",&t,&k);
for(i=1;i<=2000;i++)
for(j=1;j<=2000;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;//此句此前写成 c[i][j]=(c[i-1][j-1]+c[i-1][j]) 70分，修改后90分
while(t--){
cnt=0;
scanf("%lld%lld",&n,&m);
for(i=0;i<=n;i++)
for(j=0;j<=min(i,m);j++)
if(c[i][j]%k==0)
cnt++;
printf("%lld\n",cnt);
}
return 0;
}
p2822-3.cpp
#include <stdio.h>
#define LL long long
#define maxn 2100
LL c[maxn][maxn],d[maxn][maxn];
LL min(LL a,LL b){
return a<b?a:b;
}
int main(){
LL i,j,n,m,k,t,cnt=0;
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
for(i=0;i<=2000;i++)c[i][0]=1;//此处写成 for(i=0;i<=maxn;i++) Dev-C++4.9.9.2 测不出数组越界
for(i=0;i<=2000;i++)c[i][i]=1;//此处写成 for(i=0;i<=maxn;i++)
scanf("%lld%lld",&t,&k);
for(i=1;i<=2000;i++)
for(j=1;j<=i;j++)//此处写成 for(j=1;j<=2000;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;//此句此前写成 c[i][j]=(c[i-1][j-1]+c[i-1][j]) 70分，修改后90分
for(i=0;i<=2000;i++)//此处写成 for(i=0;i<=n;i++) 查了会
for(j=0;j<=i;j++){
if(c[i][j]%k==0)
cnt++;
d[i][j]=cnt;//d[i][j]表示[0][0]->[i][j]之间的统计数量
}
while(t--){//查询耗时，故，算法要进行修改
scanf("%lld%lld",&n,&m);
printf("%lld\n",d[n][min(n,m)]);
}
return 0;
}
--------------------------------------------------------------------------------------------------------------
//P2822 组合数问题
//看懂题目，模拟样例是关键
//样例1很快模拟成功
//样例2也很快模拟成功，发现同样n情况下，0-n之间的数据具有对称性
//在看数据范围之前，担心组合数的计算 容易 溢出int 或是long long
//该题目标，还是要部分得分
//看了数据范围，朴素算法，测试点1-6应可以拿下
//剩下的数据,t=1应该也可以拿下部分，
//该题总体目标，希望能拿到50分以上
//统计个数 推算 (1+2000)*2000/2*10^4=2*10^6*10^4=2*10^10故int 溢出 需采用 long long
//计算 组合数 int 2^31-1 可算到 12!
//long long 2^63-1 可算到 20！
//计算组合数，采用 杨辉三角
//测试了数据，n=2000，程序中途退出
//n=110比较流畅
//充满信心，估计60分有望
//一个不当心，提交，全RE，一看 此处写成 for(i=0;i<=maxn;i++) Dev-C++4.9.9.2 测不出数组越界
//略作修改，提交，70分，测试点6,8WA,9,10,11,13RE
//数组越界,用Dev-C++4.9.9.2如何测试，想了想，测不出，是该编译器的Bug
//只能在编写的时候留个心，担心数组越界，写代码的过程，长个心眼，看看有无越界
//到目前为止，已进入 国二 水平 2018-5-15 100+20+28+70=218 目前还有两题未做
//胆子大一点，将数组开到2100*2100，提交70分，测试点6,8,9,11 WA;10,13TLE
//仔细想一想，考试还是要求稳，提交时，将数组开小些，确保部分得分。
//以下为70分代码。
//在想，需要高精度算法吗，不过，考试中若真的是高精度算法，应该不会再写下去了。
//该题，主要问题是,long long 溢出，既然最后结果是%k，何不中间结果%k
//c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;//此句此前写成 c[i][j]=(c[i-1][j-1]+c[i-1][j]) 70分，修改后90分
//测试点10,13TLE,很满意90分。2018-5-19 15:18
//以下为90分代码
#include <stdio.h>
#define LL long long
#define maxn 2100
LL c[maxn][maxn];
LL min(LL a,LL b){
return a<b?a:b;
}
int main(){
LL i,j,n,m,k,t,cnt;
for(i=0;i<=2000;i++)c[i][0]=1;//此处写成 for(i=0;i<=maxn;i++) Dev-C++4.9.9.2 测不出数组越界
for(i=0;i<=2000;i++)c[i][i]=1;//此处写成 for(i=0;i<=maxn;i++)
scanf("%lld%lld",&t,&k);
for(i=1;i<=2000;i++)
for(j=1;j<=2000;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;//此句此前写成 c[i][j]=(c[i-1][j-1]+c[i-1][j]) 70分，修改后90分
while(t--){
cnt=0;
scanf("%lld%lld",&n,&m);
for(i=0;i<=n;i++)
for(j=0;j<=min(i,m);j++)
if(c[i][j]%k==0)
cnt++;
printf("%lld\n",cnt);
}
return 0;
//P2822 组合数问题
//看懂题目，模拟样例是关键
//样例1很快模拟成功
//样例2也很快模拟成功，发现同样n情况下，0-n之间的数据具有对称性
//在看数据范围之前，担心组合数的计算 容易 溢出int 或是long long
//该题目标，还是要部分得分
//看了数据范围，朴素算法，测试点1-6应可以拿下
//剩下的数据,t=1应该也可以拿下部分，
//该题总体目标，希望能拿到50分以上
//统计个数 推算 (1+2000)*2000/2*10^4=2*10^6*10^4=2*10^10故int 溢出 需采用 long long
//计算 组合数 int 2^31-1 可算到 12!
//long long 2^63-1 可算到 20！
//计算组合数，采用 杨辉三角
//测试了数据，n=2000，程序中途退出
//n=110比较流畅
//充满信心，估计60分有望
//一个不当心，提交，全RE，一看 此处写成 for(i=0;i<=maxn;i++) Dev-C++4.9.9.2 测不出数组越界
//略作修改，提交，70分，测试点6,8WA,9,10,11,13RE
//数组越界,用Dev-C++4.9.9.2如何测试，想了想，测不出，是该编译器的Bug
//只能在编写的时候留个心，担心数组越界，写代码的过程，长个心眼，看看有无越界
//到目前为止，已进入 国二 水平 2018-5-15 100+20+28+70=218 目前还有两题未做
//胆子大一点，将数组开到2100*2100，提交70分，测试点6,8,9,11 WA;10,13TLE
//仔细想一想，考试还是要求稳，提交时，将数组开小些，确保部分得分。
//以下为70分代码。
#include <stdio.h>
#define LL long long
#define maxn 2100
LL c[maxn][maxn];
LL min(LL a,LL b){
return a<b?a:b;
}
int main(){
LL i,j,n,m,k,t,cnt;
for(i=0;i<=2000;i++)c[i][0]=1;//此处写成 for(i=0;i<=maxn;i++) Dev-C++4.9.9.2 测不出数组越界
for(i=0;i<=2000;i++)c[i][i]=1;//此处写成 for(i=0;i<=maxn;i++)
for(i=1;i<=2000;i++)
for(j=1;j<=2000;j++)
c[i][j]=c[i-1][j-1]+c[i-1][j];
scanf("%lld%lld",&t,&k);
while(t--){
cnt=0;
scanf("%lld%lld",&n,&m);
for(i=0;i<=n;i++)
for(j=0;j<=min(i,m);j++)
if(c[i][j]%k==0)
cnt++;
printf("%lld\n",cnt);
}
return 0;
}
2.蚯蚓
https://www.luogu.org/problemnew/show/P2827可提交测评
3.愤怒的小鸟
https://www.luogu.org/problemnew/show/P2831可提交测评