2019信息学奥赛试题和答案（原noip）

信息学奥赛作为传统五大学科竞赛，具有很高的含金量，和一定的难度，但是经过系统的学习，拿下奖项并不难，我们来看看19年的信息学奥赛都考了哪些知识吧。

还不了解信息学的同学可以翻我以前的文章，或者加文后公众号联系我喔！

恭喜J组同学完成了一项赛事挑战，这里把J组的4道编程题代码梳理一下，帮助同学们查漏补缺。

第一题：数字游戏

该题主要考察字符串的定义和使用，考察选手基本的C++语法知识

参考代码：

第二题：公交换乘

本题属于模拟类，考察选手C++基本语法知识

参考代码：

第三题：纪念品

纪念品价格每天都波动，通过手中现有金币数购买尽可能多的纪念品，T天内卖出获得最多金币。可以使用背包。

参考代码：

第四题：加工零件

参考代码（有点长，考察最短路径算法）：

#include

#include

#include

#include

using namespace std;

const int MAXN=1e5+5;

const int MAXM=2e5+5;

int n,m,que;

int head[MAXN],v[MAXM],next[MAXM],cnt=0;

int dis[MAXN][2];

void add_edge(int s,int t){

v[++cnt]=t;

next[cnt]=head[s];

head[s]=cnt;

}

void spfa(){

//0表示偶数

//1表示奇数

memset(dis,0x3f,sizeof(dis));

dis[1][0]=0;//起始路径0

queue q;//队列实现

q.push(1);

while(!q.empty()){

int cur=q.front();

q.pop();

for(int i=head[cur];i;i=next[i]){

int np=v[i];

if(dis[cur][0]+1

q.push(np);

dis[np][1]=min(dis[np][1],dis[cur][0]+1);

dis[np][0]=min(dis[np][0],dis[cur][1]+1);

}

}

}

int main(){

scanf("%d%d%d",&n,&m,&que);

for(int i=0;i

int u,v;

scanf("%d%d",&u,&v);

add_edge(u,v);

add_edge(v,u);

}

spfa();

while(que--){

int a,l;

scanf("%d%d",&a,&l);

if(head[1]&&dis[a][l&1]<=l)printf("Yes\n");

else printf("No\n");

}

return 0;

}

每个孩子都有机会学习计算机