NOIP 95 解题报告 北极天南星.docx
- 文档编号:18115405
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:16
- 大小:26.28KB
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年的题真是简单啊,数据暴小,时间又暴长,而且是人工测试,根本没有时限……
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 95 解题报告 北极天南星 解题 报告 北极 天南星