NOIP 95 解题报告 北极天南星.docx
《NOIP 95 解题报告 北极天南星.docx》由会员分享，可在线阅读，更多相关《NOIP 95 解题报告 北极天南星.docx（16页珍藏版）》请在冰点文库上搜索。
NOIP95解题报告北极天南星
NOIP2005解题报告 北极天南星 2005-12-1121:
44:
24 原创
1.谁拿了最多奖学金（scholar）
我承认今年的题是历届最难的一次，除了这道。
对输入信息进行整理，判断奖金，比较最大值，加和，最后输出就行了。
没什么好说的。
2.过河（river）
动态规划
这道题的方程很好想，设dp[i]表示到i点最少碰到的石子数
dp[i]=dp[i-k]+s[i]（s<=k<=t），i处是石头则s[i]=1，否则=0。
但题目的规模是10^9，我们要解决两个问题，一是空间问题，二是时间问题。
空间问题：
我们发现k的值最大只有10，所以可以用滚动数组，问题解决。
时间问题：
朴素的做法是O（lt）的肯定要超时，但我们发现l最大10^9，m最大只有100，也就是说，在大多数情况下，两个石子的距离是相当大的，而动态规划却在这个相当大的距离上耗费太多的时间，算法的瓶颈就在这里。
不知道大家有没有看过星战，两个距离非常大的地方可以通过超时空来瞬间到达，这是个很好的思路。
顺着这个思路，我们设想一下，在这个距离内没有石子，意味着dp不会增加，只能不断调用之前的值。
这时如果走了一圈发现没有任何变化，那么再走一圈呢？
肯定依然没有变化，所以这时就可以“超时空”到下一个石头附近。
我们设rn记录重复次数，如果这个次数>=t，就是循环了一圈，这时直接到下一个石头附近，算法的复杂度是O（mt），问题解决。
3.篝火晚会（fire）
原有圈1..n，根据每个人的相邻情况，我们可以做一个新的圈，设为s1,s2..sn，从原有圈到新圈，我们要求的就是最小置换数。
来看一个简单的情况：
1..3.....
1..3.....
上图的.表示两个数不匹配，需要置换。
我们不管这些点最多会组成多少个置换圈，其置换数一定是.的个数。
进一步的，为了求最小置换数，就是让点最数最少，让匹配的数最大。
于是我们有了一种算法，让新圈和旧圈中的每个数对齐，一共有n中可能，统计其中匹配数的最大值，记做max，所求即为n-max。
但这个算法是O（n^2）的，n=50000时会超时，需要优化。
我们可以统计新圈中每个数i向右移多少位可以和旧圈中的i对齐，记做k，如果两个数的k相同，那么右移k位后一定都对齐。
这样，只要我们统计出所有k出现的次数，从中找出最大值，就是max。
算法复杂度是O（n）的。
需要注意，做完这以后，要讲新圈翻转一下，再做一遍。
4.等价表达式（equal）
表达式是比较复杂的，特别是加上^后，如果要化简的话还要用到多项式展开公式，高精度运算，组合，链表，等等很多复杂的东西，就算用3个小时也做不出来（我是说我，如果有大牛可以的话我甘拜下风）。
其实可以投机的，让我们设想一下，对于两个表达式s1,s2，如果随意带入5个不同的a，得出的结果都相同，那么这两个表达式不等价的几率几乎是0，为了计算简便，我们不妨将0..4带入表达式求解。
这样，接下来的问题就是将a带入求解了，我们调用二分求解。
具体地说，就是从当前表达式中找到一个优先级最低且最靠后的运算符（不包括括号里的），然后以这个运算符为界把表达式分成两部分继续求解。
至于如何判断是否在括号里，我们可以记录设s=当前左括号数-当前右括号数，当s=0时在括号外，s>0时在括号内，s<0的情况不会出现。
在计算表达式的时候，我们可以记录结果mod一个大质数的值，这个值相同，我们就认为两个数相同。
在经过这样的投机策略后，这道看来很难的题就相当简单了。
~把题重做一遍后，感觉今年的题也不是很难。
今年没考好，主要是考试的时候有些紧张，又临窗户，反射非常厉害。
如果发挥正常的话除了river都可以作出来的，考完我本以为进不了省队了，没想到大家竟然都没考好，稀里糊涂的拿了个第一。
◎＃￥％……※
NOIP2004解题报告 北极天南星 2005-12-1017:
42:
04 原创
1.津津的储蓄计划（save）
从今年开始NOIP的第一题就是送分题了。
简单的模拟加判断，连数组都不用开，save和cash记录储蓄和现金。
需要注意最后要加上save*1.2。
2.合并果子（fruit）
二叉堆+贪心
本题其实和Huffman树的构造很类似，每次选出两个最小的数，删除这两个数，将和放入。
但如果就是朴素的找，可能会超时（我不太清楚，不过听说这么小的数据朴素的不会超，寒），需要用二叉堆来加速。
关于二叉堆的相关知识，我会在近期放出，敬请期待。
当然任何一本竞赛书上都会有。
3.合唱队形（chorus）
动态规划
本题就是动态规划的典型－最长上升、下降序列。
关于状态方程可以查阅NOIP1999导弹拦截，这里不再赘述。
只需要枚举中间的人，然后求出这个人左边的最长上升序列长度，右边的最长下降序列长度，总人数减去这两个数就是需要踢出去的人数，要求踢出人数最少，所以我们求最长的长度。
4.虫食算（alpha）
本题如果用朴素的搜索毫无疑问的要超时，所以一定要剪枝。
首先确定搜索顺序，因为要考虑进位，我们从低位向高位搜索每个字母代表的数。
剪枝1：
如果某一位时已有两个数已知，就直接求出未知数。
当前位向下一位过渡时，检查加法是否成立，如果不成立就剪枝。
（过8个数据）
这个剪枝就可以过大部分的数据，在剪枝1的基础上继续剪枝：
剪枝2：
设现在搜索到第i位，从i+1到n位中，如果某一位已经知道3个数，从上到下设为a,b,c，在不知道进位的情况下，c=（a+b+1）modn，或（a+b）modn，如果c不是上述两个值，就剪枝。
剪枝3：
如果i+1到n位中，某一位已知两个数，那么可以求出未知数的两个值（进位1或0），如果这两个值都已取过，就剪枝。
剪枝4：
最高位没有进位，所以如果最高位的两个加数已知，且和大于n时，剪枝。
加上这3个剪枝后，过9个数据，剩下一个1s多。
我查阅了其它解题报告，说要从n-1到0枚举每个字母代表的数，而不是从0到n-1，这个其实只是针对某些特殊数据（第一个未知数特别大）时才适用。
不过受其启发，我把枚举顺序设为随机（就是随机一个开始数，模循环），对原来超时的点进行测试，10次只有1次超时。
官方的答案是用高斯消元+枚举进位做的，不过我至今对高斯消元的很多特殊情况还没有搞清楚，就没敢用。
至此这道题还算比较完满地解决了。
NOIP2003解题报告 北极天南星 2005-12-921:
07:
12 原创
1.神经网络（network）
拓扑排序
每次选一个入度为0且未检查的点i，将从i出发的所有边[i,j]扩展，记i检查标志，所谓扩展就是c[j]=c[j]+c[i]*w[i,j]，如果[i,j]是最后一条通往j的边，则c[j]=c[j]-u[j]。
当检查到某点i未检查且出度为0时，输出c[i]。
关于拓扑排序的问题，可以在任何一本竞赛书中找到，在此不赘述了。
2.侦探推理（logic）
枚举
本题作为历年NOIP公认最复杂的题，真是当之无愧了。
1个数据格式错误，2个数据把guilty写成guity，1个数据有错误，题目的描述又有很多模糊不清的地方（比如没说话的人算说假话还是真话）。
花了一下午时间总算过了，汗。
本题就是枚举罪犯和日期，然后对每句话（不包括废话）进行判断，如果有人没说话就设一个弹性值，卡一个范围，如果在该范围内有n个说谎的人，就枚举成了。
建议本题分两步做，先把所有的有用的话整理备案，然后再枚举处理，只要脑子不晕掉，这题其实不难。
3.加分二叉树（tree）
动态规划
二叉树的中序遍历具有一个很好的性质，就是点i的左子树的点都在i的左边，点i的右子树的点都在i的右边。
根据这个性质，我们只要在一个中序遍历中枚举根节点，然后以根节点为界划分左右子树，递归求解。
设dp[i,j]表示中序遍历的第i至j位形成的二叉树的最大分数，于是有：
dp[i,j]=max（dp[i,k-1]*dp[k+1,j]+s[k]），其中s[k]是点k的分数。
为了求该树的前序遍历，我们设一个root[i,j]，root[i,j]={k|dp[i,j]=dp[i,k-1]*dp[k+1,j]+s[k]}，然后递归求解。
4.传染病控制（epidemic）
贪心+搜索+剪枝
这道题试过用贪心、动态规划做，但都会WrongAnswer。
如果纯搜索的话又会超时。
一定要剪枝！
但本题好像又没有特别明显的剪枝，只能比较当前最优解剪枝。
我们可以先用贪心求出一个较优解，然后再搜索剪枝。
事实上，这个剪枝是非常强的。
我的贪心策略是，在当前周期会被传染的点中，找到一个儿子结点最多的结点i，把i的父亲到i的边截断。
为了加快速度，我用链表存储周期i被传染的点和点i的儿子结点，用DFS预处理求出以上两个值。
然后搜索，记录当前被感染的人，如果当前深度被感染的人已经超过当前已求出的最优解，剪枝。
NOIP2002解题报告 北极天南星 2005-12-822:
33:
12 原创
1.均分纸牌
这道题就好像要推平一堆崎岖的土堆，我们可以试着把它“抹”平。
num[i]记录每堆的纸牌数，ave记录平均值，我们从左往右推，
如果num[i]>ave，那么就把多余的部分推到num[i+1]，累计1次；
如果num[i]2.字串变换
一眼看去就知道用宽度优先搜索搜了，但如果仅仅是朴素的宽搜需要用最多6^11-1=362797055的空间，我估计会mle，没敢开。
一定要优化，我想到用双向广度优先，就是从两边一起搜，这样最多只需要2*（6^6-1）=93310的空间，大大节省了空间。
实际上这道题的数据用双向光搜只需要开2个3000的数组就可以了。
至于双向宽度优先搜索可以在任何一本竞赛书上找到，本站也会在近期推出相关专题，敬请期待。
3.自由落体
本题就是数学题，比较繁琐的是误差和特殊情况。
假设一个球i，它掉落到车顶的时间为t1，掉落到地上的时间为t2，则如果掉落到车顶时车的后排已经经过该点，或掉落到地上时车的前排还没有到达该点，则该点不会被接受。
于是有：
i<=s+l-vt1，i>=s-vt2
综合考虑1e-5的误差，我们得出i的区间：
[s-vt2-e,s+l-vt1+e]∩[0,n-1]，
而接受的球数就是该区间内的整数个数。
4.矩形覆盖
简单的几何和分治
设rec（s,k）表示将集合s中的点用k个矩形覆盖的最小面积。
我们先从最简单的开始，rec（s,1）：
在s中的点中找到边界x1,y1,x2,y2，rec（s,1）=（x2-x1）*（y2-y1）。
对于较一般的rec（s,k），我们任选其中一个点，以这个点为标准，将s中的点横向或纵向切开成两个点集合s1,s2，s1中的点用1个矩形覆盖，s2中的点用k-1个矩形覆盖。
所有的划分方案中最小的面积就是rec（s,k）的值，即rec（s,k）=min（rec（s1,1）+rec（s2,k-1））。
我们可以递归调用过程来实现，复杂度是（n^k），50^4=6.25e6，不会超时。
NOIP2001解题报告 北极天南星 2005-12-60:
05:
16 原创
1.一元三次方程求解
二分
这道题就是小数据和误差比较麻烦，我们以0.99为一个单位，从-100开始按区间搜索，如果此区间内有解，即f（x1）*f（x2）<0，然后再调用二分算法进行计算。
如此重复3次就可以求出所有的解。
这里我们不得不考虑，如果解正好在区间的边界该怎么处理？
我们可以加一个判断，如果在边界，就退出，这样可以使得二分的边界上没有解。
还有在判断解是否为0时，我们要设一个极小数e，然后在看解是否小于e，这样可以避免误差。
最后，为了进一步减小误差，把real换成extended。
2.数的划分
整数拆分，递推式f（n,k）=f（n-1,k-1）+f（n-k,k）。
上面的递推式比较好理解，为了拆出不同的解，我们只要拆分出的数排序后两两不同即可。
每种拆分方案中，排序后最小的数为e，按照e的不同，我们可以把拆分方案分成2类：
e=1，我们把1除去，则剩余部分正好是n-1拆分成k-1部分，一共有f（n-1,k-1）个；
e>1，因为e是最小的数，所以所有的数都>1，我们把所有的数-1，则正好是n-k拆分成k部分，一共有f（n-k,k）个。
根据加法原理，得出以上递推式。
知道递推式后，就比较简单了，我们用动态规划的方法（如果直接递归，会有很多重复运算）。
3.统计单词个数
这道题很显然是用动规做，设dp[i,j]表示自i始分成j个部分最多的单词数，状态转移方程：
dp[i,j]=max（s[i,k]+dp[k+1,j-1]）,k∈[i,l-j+1]，l是字串总长，s[a,b]是字串a到b间的单词个数。
为了求出所有s[i,j]，我们设一个辅助变量b[i]，表示位置i开头的单词的结束位置，则有：
s[i,j]=s[i+1,j]+ord（b[i]<=j）
算法复杂度是O（nkl^2）
4.Car的旅行路线
题目给出了矩形的3个顶点，我们可以用数学方法计算出第4个顶点的坐标，然后以机场为点，费用为边作图，题目要求即此无向图的最短路，用Dijkstra或Bellman-Ford皆可。
已知顶点a,b,c，要求出第4个顶点，用叉积判断a,b,c中的垂足，然后根据矩形的性质，即对角线互相平分，我们可以得出：
x4=x1+x2-x3
y4=y1+y2-y3
其中垂足是（x3,y3）
对于最短路的算法，在我的"最短路总结"中有详细的说明，这里不再赘述。
NOIP2000解题报告 北极天南星 2005-12-323:
20:
56 原创
1.进制转换
对于一个给定的数n，它的-R进制肯定可以表示成:
n=a[0]*r^0+a[1]*r^1+a[2]*r^2+a[3]*r^3.....
我们只要求出所有的a即可。
按照升幂顺序求a[i]：
a[i]=（nmodr+r）modr（i是偶数）
a[i]=（nmodr-r）modr（i是奇数）
然后从n的代数式中把这项删除，整体降幂，反复这样做求出所有的a。
然后就是输出的问题了。
2.乘积最大
算法：
高精度+动态规划
数据范围是40，但实际数据中没有这么大的，所以其实不用写高精度的。
动态规划很简单，设dp[i,j]表示第i位开头的数字添加j个乘号可以得到的最大乘积，状态转移方程：
dp[i,j]=max（dp[k,j-1]*s[i,k-1]）（k>i）
s[a,b]表示a到b所组成的数字。
3.单词接龙
简单的搜索
把每个单词模拟成一个点，如果单词i后可以接单词j，就在ij之间练一条线，我们还需记录单词ij的重复长度，以及每个单词被取过的次数（最多为2）。
然后深度优先搜索，不断更新最优解，因为n很小，所以不用担心会超时。
4.方格取数
动态规划
这道题初看似乎可以分两次，每次都尽可能取最多，其实这样的局部最优不一定就是全局最优，因为第一次的取数会对第二次造成影响，即有后效性。
这样看来似乎不能用动态规划，其实我们还是可以用动规来做这道题的。
我们可以把一个人分两次取看成两个不同的人同时取，基于这个思想，我们只需稍做修改即可。
设dp[x1,y1,x2,y2]表示第1人在（x1,y1），第2人在（x2,y2）是取到的最大数，状态转移方程：
dp[x1,y1,x2,y2]=max（dp[t1,t2,t3,t4]+map[x1,y1]+map[x2,y2]）（第1人上次在（t1,t2），第2人上次在（t3,t4））
这个方程似乎还有些问题，即如果两人在同一地方，那么就取了2次，这与题目要求矛盾。
我们可以加一个简单的判断，这道题至此完美解决。
NOIP1999解题报告 北极天南星 2005-12-123:
36:
12 原创
1.拦截导弹
算法：
动态规划
要求最多拦截的导弹数，就是求最长不上升序列。
设dp[i]表示i以后的最长不上升序列，状态转移方程：
dp[i]=dp[j]+1（h[j]<=h[i]）（j>i）
要求最少配备的系统数，就是求最长不上升序列的最小分划。
我们可以证明它等于最长上升序列的长度，证明略。
2.回文数
算法：
搜索+高精度
用高精度加法模拟，30步内不能出解就输出无解。
3.旅行家的预算
算法：
贪心
假设现在在第i站，那么在这站加满油可以到达的最远距离是dis[i]+c*dd，
如果在这个范围内存在一个加油站j，它的价格pri[j]如果在这个范围内不存在这样的加油站，那么就在i加满油，然后走到尽量远的加油站j，如果无法走到j，即dis[j]>dis[i]+c*dd，此时无解。
4.邮票面值设计
算法：
深度优先搜索+动态规划这道题的最大数据是（5,5），用搜索是不会超时的。
如果已知邮票的不同面值，我们可以用动态规划求出其能组合出的最大连续数：
设dp[i]表示组合出面值为i所需最小邮票数，我们把不同的邮票面值存在num中，则有：
dp[i]=min（dp[i-j]+1）（j∈num）
解决了这个问题后，剩下的问题就比较简单了，num[1]一定为1，我们按升序枚举以后的邮票面值，并且
当前枚举的邮票面值最多是当前最大连续数+1。
NOIP1998解题报告 北极天南星 2005-11-2323:
54:
58 原创
1.火车
设第2站上车人数为u，则显然有以下关系：
车站12345……
现有人数aa2a2a+u3a+2u……
上车人数aua+ua+2u2a+3u……
不难发现，上车人数up是一个Fibonacci数列，而现有人数now[i]=now[i-1]+up[i]-down[i]=now[i-1]+up[i]-up[i-1]=now[i-1]+up[i-2]
有了这个递推式，我们可以用数组求出a和u的系数，然后根据m求出u，然后就可以根据x求now[x]了。
2.最大整数
只要把数按照特定的顺序排序就可以了：
对于长度一样的数a，b，自然要把大的数放在前面；
对于长度不一样的数a，b，假设len（a）按照上面的顺序将所有的数进行排序后输出就可以了。
3.加法表
比较繁琐的枚举。
首先要枚举进制。
接下来就是在已知进制的情况下枚举所有未知数。
朴素的做法是按从左往右的顺序枚举每个未知数，知道满足所有的等式为止。
其实当我们将某个未知数x带入表中时，很可能求出一个新的未知数y，我们同样可以将y带入表中，在反复带入的过程中一旦发现等式不成立剪枝，这样可以大大提高速度。
NOIP1997解题报告 北极天南星 2005-11-2218:
20:
30 原创
1.填棋盘
首先用筛法求素数，然后按坐标顺序进行枚举，如果和不是素数就剪枝，但如果光是这样还是会超时。
输出要求是第一行和第一列的和最小的方案，所以可以记录当前求出的最小和，在枚举过程中，如果现在的和已经超过最小和，就可以剪枝。
2.代数表达式
非常简单的题，用集合判断ERROR1。
用s记录当前左括号的数目，然后从左向右扫描，如果某时s<0，则ERROR2，如果最后s>0，则ERROR2。
ERROR3只要检查是否出现连续两个字母和运算符即可。
3.骑士漫游
第一问深度优先搜索就可以了，当找到一个解是退出。
第二问用动态规划，设dp[i,j]表示到（i,j）的路径数，状态转移方程为：
dp[i,j]=∑dp[i-dx[k],j-dy[k]]（k=1..4）
要按照x的增序求解。
需要注意的是，结果可能会很大，数组类型定义为int64
NOIP1996解题报告 北极天南星 2005-11-2215:
37:
57 原创
1.比赛安排
简单的枚举，用数组判重，一天一天的枚举，注意两个条件，一队一天只比一次，所有的队伍都要比过，因为不管怎么放都不会回溯，所以只要大胆枚举就行了
2.数制转换
先把数字转换成10进制，然后再把数转成p进制。
转换方法很简单，这里就不赘述。
3.挖地雷
题目不是很清楚，不过看数据应该是按无向图算的，回溯加判重就可以了
4.砝码称重
因为已知总重不超过1000，所以定义一个1000的数组，模仿母函数的多项式相乘即可。
具体来说，就是枚举每个砝码的数量，加到已经求出的重量上，累计tot，注意当前砝码扩展出的点不能再扩展（除非该点在扩展前已存在），加一个临时数组tt即可。
～除了第4题第一次做的时候搜索超时外，其他题都是一遍AC，寒
NOIP1995解题报告 北极天南星 2005-11-220:
31:
58 原创
1.编码问题
相当简单的模拟算法，应为数据很小（20），所以用O（n^2）的模拟完全可以过，第一问直接模拟，第二问用一个数组记录数是否被取过
2.灯的排列问题
不妨先不考虑各种颜色出现的先后顺序，那么只要算出每种颜色的终点（即在保持现有颜色顺序的情况下可以被放的最后的位置），然后用递归枚举每种颜色的起点，累计次数。
然后我们来考虑颜色的变化，很容易知道，不管是怎样的颜色排列，其累计次数都是一样的，所以我们只要在刚才的累计次数上乘上cn!
，cn是颜色个数，就是所求。
3.积木块
可以先从左下角的三个数算起，递归枚举ABC的关系式，并在枚举出一种方案时检查是否满足所有的已知数。
知道关系式后，就可以轻松的求出所有的块。
~95年的题真是简单啊，数据暴小，时间又暴长，而且是人工测试，根本没有时限……
升级会员 