骗分导论

Copyright我是智障1骗分导论INTRODUCTIONTOCHEATINGINNOIP关于应付竞赛不会难题的策略我是智障大牛是稀有的，每道题都会的大牛更少。相信想我这样的人还是挺多的，那竞赛时遇到不会的难题怎么办呢？？？放弃？？？让100分就这样流去？？？当然不能放弃。目录1、心态2、非完美算法3、精彩的骗4、简单数学分析＋猜测5、分类讨论6、实战训练7、总结Copyright我是智障2【1】遇到难题时心态要稳定，先搞定简单的题目，最后思考难题。心态是第一位。【2】如果难题实在不能解决也不能放弃，虽然写不出完美的算法，但可以用象贪心，搜索之类的算法，虽然不能AC但一般能过几个，有分总比没分好。举个例子穿越磁场（cross）探险机器人在Samuel星球上寻找一块奇特的矿石，然而此时它陷入了一片神秘的磁场区域，动弹不得。探险空间站立刻扫描了这片区域，绘制出该区域的磁场分布平面图。这片区域中分布了N个磁场，每个磁场呈正方形，且边与坐标轴平行。例如下图中，存在3个磁场，白点表示机器人的位置，黑点表示矿石的位置：科学家们分析平面图，进一步发现：这些磁场为大小不一的正方形，可能相交，甚至覆盖，但是它们的边缘不会重合，顶点也不会重合。例如下面的两种情形是不会出现的：科学家们给探险机器人启动了磁力罩，这样它就可以在磁场中自由穿越了。初始时，探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制，XYOCopyright我是智障3在穿越过程中机器人只能够水平或垂直移动，且不能够沿着磁场的边缘行动。由于磁力罩的能量有限，科学家们希望探险机器人穿越尽量少的磁场边缘采集到这块矿石。例如上图中，探险机器人最少需要穿越两次磁场边缘。现在小联请你编写程序，帮助科学家们设计探险机器人的路线，统计探险机器人最少需要穿越多少次磁场边缘。输入（CROSS.IN）：第一行有一个整数N，表示有N个磁场（1N100）。随后有N行，每行有三个整数X、Y、C（0X,Y,C10000），表示一个磁场左下角坐标为（X,Y），边长为C。接下来有一行，共有四个整数SX,SY,TX,TY，表示机器人初始坐标为（SX,SY），矿石坐标为（TX，TY）（其中，0SX,SY,TX,TY10000）。输出（CROSS.OUT）：单行输出一个整数，表示机器人最少需要穿越多少次磁场边缘。样例：输入：21332140034输出：2当时我做这道题时很茫然，一点思路都没有。但我认为如果机器人和矿一个在磁场外面，一个在里面就一定要穿越一次。如果都在里面或外面那就不穿越。但有特殊情况，虽然想到了，但无法处理，所以我就用我错误的想法编了一个。特殊情况：如图，如果时这样用我的算法算出来就是0，但实际上是2。我的程序主要代码如下fori:=1tondoif((sxmap[i,1]+c[i])and(sxmap[i,1])and(symap[i,2]+c[i])and(symap[i,2]))Copyright我是智障4xor((txmap[i,1]+c[i])and(txmap[i,1])and(tymap[i,2]+c[i])and(tymap[i,2]))theninc(total);很短，但数据太弱了，没有一个有如上可能。所以我全过了这样是很划算的，如果当时放弃就一分都没有了～。附标准算法（2006全国冬令营汪晔）：（有点复杂，当时我绝对想不出来。）问题分析：方法1：将坐标中的所有整点坐标当作顶点，在每个点与坐标系中相邻的点间加一条无向边，如果穿过磁场，边的权值为1，否则权值为0。求机器人从起点到终点的最小耗费，也就是求构造的图中两点之间的最短路径，我们可以用Dijkstra解决。每次循环中寻找最大值的复杂度为O(V)，改进相邻点时由于要判断是否穿过磁场边，所以复杂度为O(N)。整个算法复杂度为就是O(VN+V2)，这里V=整个坐标中的点的个数=10000*10000，显然超时。当然，在实现过程中我们可以有所优化，比如确定查找点的范围。方法2：Dijkstra分为两大部分，第一部分是取所有未标记点中的最小值，第二部分是用当前最小值改进整个图。那么建立一个上小下大的堆，堆中保存所有起始点到图中未标记的点的最000101000101000101101000Oxy000000111011111000000000000000101122Copyright我是智障5短路径值，这样每次取出一个最小值的复杂度为O(1)；由于此图中，每个点的度最多为4，查找边的权值的复杂度为O(N)，更新堆的复杂度为O(Vlog2V)。因而算法复杂度降为O(V+NV+Vlog2V)。但由于V=10000*10000仍不能在时限中出解。方法3：此题的数据规模有一些特性——虽然坐标系的范围巨大，但有效坐标（机器人的坐标，宝藏的坐标和磁场顶点坐标）的个数却很小。上两个方法的主要复杂度都取决于V，也就是坐标系中的点数。如果我们可以把坐标系的范围缩小，也就相当于把V缩小，就可以大大降低问题的时间复杂度。在上种方法的构图中，我们会发现很多边的权值为0，也就是说，可能有很多连续点的最短路径值都相等。如图：那么我们将整个图中有效坐标抽出，建立一个新的坐标系，这个坐标系中相邻两个个坐标的间距为单位“1”，但此时单位长度的意义为有效坐标的序号。如图：这样我们依然用最短路径的方法在这个图中进行操作，算法复杂度为O(V+VN+Vlog2V)，但此时，V=204*204，问题得以解决。方法4：离散化后对整个图中的连续无磁场部分进行染色，如下图：问题就是求机器人所在点的颜色区域到宝藏所在点的颜色区域的最短路径。由于每相邻两个区域间的边的权值均为1，所以算法复杂度为O(V)。因而整个算法的复杂度为O(NV)。这里的N=100,V=204*204。如果先构图，复杂度为O(N)，再染色用宽搜求最短路复杂度为O(V)，所以总复杂VOxy00000000000000000000000000000000000000Copyright我是智障6度为O(N+V)。V【3】如果太难了，连一点思路都没有可以考虑只输出一个值，如果对了也有10分。但这个值也不能乱输出，也要有一定的依据，输样例的成功率太小了（noip2004除外）如果题目要求误解输出No之类的，输出这个肯定有分。如noip2005第三题，输出－1有10分。千万不要小看这10分，当时一等才130，很多人120～～～郁闷了吧～～要输出可能性最大的，骗要骗得精彩。如果天上能掉下来馅儿饼，那我就不用再学习了，天上能掉馅儿饼么？不能，所以我还得学习；如果天上能掉下来林妹妹，那我就不愁女友了，天上能掉林妹妹么？不能，所以我还得愁女友；如果天上能掉恐龙，那我就要时刻做好逃命的准备，天上能掉恐龙么？不能，所以我不用时刻做好逃命的准备；如果cheat能过很多数据是一种错，那我宁愿一错再错，cheat能过很多数据么？可以，所以，是的，我宁愿一错再错重建道路(roads)【问题描述】一场可怕的地震后，人们用N个牲口棚(1≤N≤150．编号1..N)重建了农夫John的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树，John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有P(1≤P≤N)个牲口棚的子树和剩余的牲口棚分离，John想知道这些道路的最小数目。【输入】第1行：2个整数，N和P第2．．N行：每行2个整数I和J，表示节点I是节点J的父节。【输出】单独一行，包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。【样例输出】roads．inroads.out1162Copyright我是智障7l2l3l41526272849410411【样例解释】如果道路1—4和1—5被破坏，含有节点(1．2，3，6，7，8)的子树将被分离出来。这道题也不是什么难题，但当时我就不知道怎么做。我用了垃圾的搜索，效率很低很低。为了检测我写的搜索是否正确，我随机生成了很多小数据（大的严重超时），一测发现结果怎么这么多2？？？难道2的机率这么大？？？不管这么多了，反正我也想输样例了（样例也是2），于是心一恨写下了如下代码writeln(2);吃惊的是我的成绩，80分啊～～～（数据太弱了）附标准算法：用树型动态规划求解。定义f(n,m)为在n为根的子树中取m个节点的最小代价，则状态转移方程为：f(n,m)=min{f(n0,m0)+f(n1,m1)+f(n2,m2)+…+f(nk,mk)}其中，n0,n1,n2,…,nk为n的k个儿子，m0+m1+m2+…+mk=m，并且定义f(ni,0)=1。最后的结果为：min{f(root,p),min{f(n,p)|n≠root}}看来writeln(2)的性价比还是挺高的～～【4】Copyright我是智障8简单数学分析＋猜测座位的争执描述Description文件名complain.pas;还记得Matrix67的“非常男女”计划吗？由Matrix67策划的学校大型男女配对活动将在大礼堂隆重举行，学校里许多人即将前来捧场。大礼堂一共有n个座位，为了方便管理，Matrix67对它们从1到n顺序编号。售票工作已经完成，经统计，共有k个人拿到了入场券。由于kn，因此大礼堂的座位完全足够。每张入场券上都印有座位号，入场者凭入场券对号入座。在这k个人即将陆续入场时，Matrix67发现了一个严重的错误：由于在入场券的销售过程中搞错了大礼堂总的座位数，入场券上印的座位号只有1到t。虽然这t个座位号中的每一个都在入场券中至少出现了一次，但有一个事实不能改变：tk。也就是说，这k个人中有一些人的入场券上印有相同的座位号。这样，入场时必将发生很多次座位的争执。我们假定，当一个人入场后发现了他该坐的位置上已经有了人，此时这两个人将发生一次争执，争执的结果总是这个人不能夺回座位；此时该人继续寻找下一个座位号并可能再次发生争执，直到找到一个空位置为止。Matrix67必须调整这k个人的入场顺序，使得总的座位争执发生的次数最少。输入格式InputFormat第一行有三个用空格隔开的正整数n、k、t，它们分别表示总的座位数、实际到场人数和入场券上的最大座位号，它们满足关系nkt。第二行有k个用空格隔开的正整数。这些正整数保证不超过t，且所有不超过t的正整数总会在这些数中出现至少一次。它们表示这k个人的入场券上印的座位号。对于30%的数据，n=10；对于50%的数据，n=1000；对于100%的数据，n=100000。输出格式OutputFormat输出发生争执的最少次数。样例输入SampleInput65312132样例输出SampleOutput6注释Hint说明：假设我们将入场顺序调整为1、1、3、2、2，下面说明此时发生的座位争执次数应该如何计算。第一个人入场后成功找到1号座位。第二个人入场后发现自己的入场券上印有的1号座位已经被占，此时发生一次争执；而后该人继续寻找2号座位并就座。第三个人入场后成功找到3号座位。第四个人入场后发现2号座位被占，争执后转而寻找3号座位并再次发生争执，直至成功找到4号座位。这里的争执有两次。Copyright我是智障9第五个人从2号座位开始寻找，接连三次寻找座位失败，最终在5号位置就座。这里一共发生了三次争执。这样的入场方案使得总的争执数为6次。可以证明，不存在更好的入场顺序使得发生争执的次数少于6次。看到这道题有什么感觉？？？如果你数学很强可能看出了什么。但我是什么都没有看出。于是我我用了随机算法，随机产生了进入的顺序。完了之后运行大数据超时（为了正确性我循环了很多次）～～～于是我慢慢改小～～～在改的过程中我发现不论我循环多少次结果都是一样的，难道我今天rp暴涨？？？于是就大胆的猜想结果是不是和进入顺序没有关系？我没有证明出来，但这样用了，后来同学将它证明了。所以这道题只需要tot:=k*(k+1)div2;fori:=1tokdobegi