noip历届签到题题解

历年NOIP选题题解汇总 联赛前上vijos板刷往年联赛题，使⽤在线编辑编写代码，祝我rp++。

废话不多说，挑⽐较有意思的记⼀下。

题⽬是按照年份排序的，最早只到了03年。

有些题⽬因为我还没写/很早之前写的忘了所以就没写题解。

NOIP2003 神经⽹络：按照题⽬怎么说怎么做，BFS即可。

注意输出层是指出度为0的层，不是指深度最⼤的。

传染病防治：爆搜题，枚举每⼀层减掉哪个。

复杂度不可算，理论在O(2^30*8!)左右，但好像强势不满。

想了⼀会貌似卡不掉？ NOIP2004 ⾍⾷算：知⼆推三，边搜边判。

NOIP2005 篝⽕晚会：⾸先你得知道两个排列可以看成若⼲个环，⽽且每个点只要转⼀次就可以转出来……⽽这题正好是两个排列的形式，即找到⼀个1-n的环和原环匹配最多就是不要动的⼈。

把每个⼈在环中的1的位置记下来取最多的就好了。

过河：把边权>=100的缩成100，因为长度过长没有意义，⼤于100了前⾯的情况必然可以凑出来，然后在1000下暴⼒DP即可。

注意特判S=T的情况，还有不要以为给出的点都在L内。

等价表达式：随便找⼏个数字(1~20)带进去算在模意义下都相等就可以了(跟解⽅程的思想有点像？)，重点是化为后缀表达式处理的trick。

NOIP2006 2^k进制数：⼤整数组合数。

NOIP2007 先坑着 NOIP2008 传纸条：显然的⽹络流，其实化为四维DP可做。

双栈排序：若存在i<j且A[i]>A[j]，即A[j]在A[i]前⾯弹栈。

因为A[i]最终也要出栈，所以⽐A[i]还要⼤的、在[i,j]中间的⼀定不能和A[i]在同⼀个栈中，即构成⼆分图。

判断有解就是⼆分图染⾊。

输出……反正我铁定WA的输出因为数据⽔过去了，不予置评。

NOIP2009 Hankson的趣味题：醉题，复杂度O(nsqrt(B)logB)但是跑得过？反正我是不会什么更好的解法…… 最优贸易：SPFA求出从1出发能买进的最低阶，从n出发沿反向边能卖出的最⾼价，最后枚举边减掉就好了。

八 1/ | （初中部分）1排序：（有些排序因涉及贪心，所以我放在贪心那一节里了）历届试题：NOIP分数线划定奖学金明明的随机数排序法使用：选择排序。

快速排序。

桶排序。

分析：1.分数线划定：ci）这是一道具有代表性的排序题，可使用选择或快排，使用选择排序整体难度较小，但因此题数据量较大，选择排序不可过全部数据。

（2）使用快速排序是解决本题的最好方法，但不可直接套用，因为有儿个排序条件，排序内最好添加几个辅助变量。

2.奖学金：（1）这道题和上题大体相同，但其测试数据较小，可使用选择排序得全分。

3.明明的随机数：（1）本题可用选择或快排，但代码设计较难，使用桶排序解绝此题是较为理想的选择。

2模拟：分为三类：〈1〉普通模拟（完全模拟的较少，大多为结合贪心。

排序的，贪心。

排序的不单独讨论）历届试题：NOIP多项式输出数列1. NOIP多项式输出.：（1）多项式输出:这道题想要拿分很容易，但要注意一下模拟过程，此题实际上需有4个判段过程，其中有一个是极易遗漏的。

（2）数列:这道题竟是第4题，很简单的模拟题，还可用转成2进制的方式直接算.〈2〉罕符模拟历届试题：NOIP ISBN号码Jam记数法立体图（1）ISBN号码：总体难度不大，这道题如果是使用C语言的话，可以用每个字符都减去字符0的方式，直接把它们从字符转为数字，再进行处理。

（2）Jam记数法:很绝对的模拟，一开始我还认为是数学知识模拟题,就是从后往前推.（3）立体图:很难的很考细心的一道模拟题,没说的，就是上机不断的调程序.〈3〉数学知识模拟历届试题：NOIP细胞分裂（1）初中组目前唯一一道数学知识模拟题，掌握了相关的知识就应该不难，这道题要满分还是比较难的，需要高精度运算（用LONG LONG型不知道可不可以），还有一定要注意时间问题，这道题极易超时.3贪心：历届试题：NOIP排座椅纪念品分组守望者的逃离.注意：任何贪心之前都必需排序。

（1）排座椅:这道题初看不像一道贪心，但实际上只要细细的看，就可以发现了,跟实际生活联系很紧密的一道题。

NOIP普及组初赛历年试题及答案求解题篇问题求解：每次共2题，每空5分，共计10分。

每题全部答对得 5 分，没有部分分。

注：答案在文末在NOIP初赛问题求解中，经常会遇到排列组合问题。

这一类问题不仅内容抽象，解法灵活，而且解题过程极易出现“重复”和“遗漏”的错误，这些错误甚至不容易检查出来，所以解题时要注意不断积累经验，总结解题规律。

解答排列组合问题，首先必须认真审题，明确是属于排列问题还是组合问题，或者属于排列与组合的混合问题，其次要抓住问题的本质特征，灵活运用基本原理和公式进行分析解答。

同时还要注意讲究一些策略和技巧，比如采用分类、分步、捆绑等方法，也可以借助表格、方程等工具，使一些看似复杂的问题迎刃而解。

NOIP2011-1. 每份考卷都有一个8位二进制序列号。

当且仅当一个序列号含有偶数个1时，它才是有效的。

例如，0000000、01010011都是有效的序列号，而11111110不是。

那么，有效的序列号共有______个。

NOIP2011-2. 定义字符串的基本操作为: 删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。

将字符串A变成字符串B的最少操作步数，称为字符串A到字符串B的编辑距离。

字符串“ ABCDEFG ”到字符串“BADECG ”的编辑距离为_______。

NOIP2012-1. 如果平面上任取n 个整点(横纵坐标都是整数) ，其中一定存在两个点，它们连线的中点也是整点，那么n至少是_____。

NOIP2012-2. 在NOI期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。

在第十八桌，有5名大陆选手和5名港澳选手共同进膳。

为了增进交流，他们决定相隔就坐，即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。

那么，这一桌共有_____种不同的就坐方案。

注意：如果在两个方案中，每个选手左边相邻的选手均相同，则视为同一个方案。

NOIP2013-1. 7 个同学围坐一圈，要选2 个不相邻的作为代表，有_____种不同的选法。

noip历届签到题题解石头剪刀布 //2014/problem/3716/联合权值/problem/3728/无线网络发射器/problem/3578/寻找道路/problem/3731/石头剪刀布打表，找出对应关系。

#include<cstdio>#include<cstdlib>using namespace std;const int m[5][5]={0,0,1,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1,1,0,0,0,};int a[205],b[205];int main(){int n,na,nb;scanf("%d %d %d",&n,&na,&nb);for(int i=0;i<na;i++)scanf("%d",&a[i]);for(int i=0;i<nb;i++)scanf("%d",&b[i]);int sa=0,sb=0;for(int i=0;i<n;i++){sa=sa+m[a[i%na]][b[i%nb]]; sb=sb+m[b[i%nb]][a[i%na]]; }printf("%d %d",sa ,sb);return(0);}联合权值#include <iostream>#include <cstdio>#include <vector>#include <algorithm>using namespace std;long long n,p,k,w[200010];bool vis[200010];vector <int> edge[200010];void dfs(int x,int last1,int last2) {v is[x]=1;l ong long t=0,t2=0,t3=0,t4=0;f or (int i=0;i<edge[x].size();i++) {int y=edge[x][i];if (!vis[y]){vis[y]=1;if (last1!=0){k=(k+w[y]*w[last1])%10007;p=max(p,w[y]*w[last1]);}t2+=t*w[y]; t+=w[y];if (w[y]>=t3){t4=t3; t3=w[y];}if (w[y]<t3) t4=max(t4,w[y]);dfs(y,x,last1);}}p=max(t3*t4,p); k=(k+t2)%10007;}int main(){c in>>n;f or (int i=1;i<n;i++){int u,v;cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}f or (int i=1;i<=n;i++) cin>>w[i];d fs(1,0,0);cout<<p<<' '<<k*2%10007<<endl;r eturn 0;}有关图的问题，到时候再解决。

第十三届全国青少年信息学奥林匹克联赛初赛试题（普及组Pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1．在以下各项中，（）不是CPU的组成部分。

A．控制器B．运算器C．寄存器D．主板2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。

A．二叉树B．多叉树C．哈希表D．二维表3．在下列各项中，只有（）不是计算机存储容量的常用单位。

A．Byte B．KB C．UB D．TB4．ASCII码的含义是（）。

A．二→十进制转换码 B．美国信息交换标准代码C．数字的二进制编码D．计算机可处理字符的唯一编码5．一个完整的计算机系统应包括（）。

A．系统硬件和系统软件B．硬件系统和软件系统C．主机和外部设备D．主机、键盘、显示器和辅助存储器6．IT的含义是（）。

A．通信技术B．信息技术C．网络技术D．信息学7．LAN的含义是（）。

A．因特网B．局域网C．广域网D．城域网8．冗余数据是指可以由其它数据导出的数据。

例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。

冗余数据往往会造成数据的不一致。

例如，上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。

下面关于冗余数据的说法中，正确的是（）。

A．应该在数据库中消除一切冗余数据B．用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据C．为了提高查询效率，在数据库中可以保留一些冗余数据，但更新时要做相容性检验D．做相容性检验会降低效率，可以不理睬数据库中的冗余数据9．在下列各软件，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。

A．gcc B．g++ C．Turbo C D．Free Pascal10．以下断电后仍能保存数据的有（）。

noip 2018 第二轮题解NOIP (全国青少年信息学奥林匹克联赛)是中国的一个重要的信息学竞赛，每年都有许多优秀的学生参与。

第二轮是NOIP的选拔赛，对参赛者的算法和编程能力有一定的挑战。

下面是对2018年NOIP第二轮题目的解析。

1.题目一：最短编辑距离这道题目给出了两个字符串A和B，要求通过最少的操作（插入、删除和替换字符）将A转换成B。

首先我们可以使用动态规划的方法解决这个问题。

定义一个二维数组dp[i][j]表示将A的前i个字符转换成B的前j个字符所需要的最小操作数。

初始状态是dp[i][0] = i和dp[0][j] = j。

然后我们根据A[i]和B[j]是否相等来更新dp[i][j]。

如果相等，那么dp[i][j] = dp[i-1][j-1]，即不需要进行任何操作。

如果不相等，要么进行替换操作，那么dp[i][j] = dp[i-1][j-1] + 1；要么进行删除操作，那么dp[i][j] = dp[i-1][j] + 1；要么进行插入操作，那么dp[i][j] = dp[i][j-1] + 1。

最后返回dp[A.length()][B.length()]就是最短编辑距离。

2.题目二：修电线这道题目给出了一个无向图，你需要修复其中一条电线，使得修复后的图是一个树。

首先我们可以将该图表示为一个邻接矩阵，然后使用深度优先搜索(DFS)来遍历图。

在进行DFS的过程中，记录下每个节点的父节点，并检查是否存在回路。

如果存在回路，则将回路中的任意一条边删除即可得到一个树。

如果不存在回路，则对于任意一个非树边，将其替换成树边即可。

3.题目三：双链表这道题目给出了一个长度为n的双链表，每个节点包含一个值和指向前后节点的指针。

要求在双链表中执行以下操作：插入节点、删除节点、查询节点值、查询区间最大值、查询区间和。

为了高效地执行这些操作，我们可以使用双端队列(Deque)来实现双链表。

双端队列是一种具有队列和栈的特性的数据结构，可以在队列的前端和后端进行插入和删除操作，时间复杂度均为O(1)。