版2014年8月4日到5-贪心与搜索

贪心与搜索向鹏达贪心与搜索是有相关性的，所以可能采取两种类型的题交杂的方式，有不少的题目会同时用到这两种方法贪心算法（摘自百度百科）

对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，而仅是做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。如果要用贪心算法得到最优解，那么要保证贪心算法所得到的局部最优解就是整体的最优解noip2012提高组

国王游戏

国王游戏

(game.cpp/c/pas)

【问题描述】

恰逢

H

国国庆,国王邀请

n

位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这

n

位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

【输入】

输入文件为

game.in。

第一行包含一个整数

n,表示大臣的人数。

第二行包含两个整数

a

和

b,

之间用一个空格隔开,

分别表示国王左手和右手上的整数。

接下来

n

行,每行包含两个整数

a

和

b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。

【输出】

输出文件名为

game.out。

输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

【输入输出样例】

game.in

3

1

1

2

3

7

4

4

6game.out

2

【数据范围】

对于

20%的数据,有

1≤

n≤

10,0

<

a、b

<

8;

对于

40%的数据,有

1≤

n≤20,0

<

a、b

<

8;

对于

60%的数据,有

1≤

n≤100;

对于

60%的数据,保证答案不超过

109;

对于

100%的数据,有

1

≤

n

≤1,000,0

<

a、b

<

10000。考虑相邻的两个人A，B设A左手上的数字是A.left,右手上的数字是A.right.B同理。当A位于B前面时答案是：max(C/A.right,C*A.left/B.right)当B位于A前面时答案是max(C/B.right,C*B.left/A.right)我们把max拆开来考虑，即通过分情况考虑来去掉max。情况一：A.left*A.right<B.right此时上一页的第一个max函数中的较大的一项是C/A.right，第二个max函数中较大的一项是C*B.left/A.right.（因为A.left*A.right<B.right可以推出A.right<B.left*B.right，再推出C/B.right<C*B.left/A.right）。那么比较的就是C/A.right与C*B.left/A.right.因为B.left是大于等于一的整数，所以后者要大（答案劣一些）。所以应该把A放在前面。此时B.left*B.right比较大。情况二：B.left*B.right<A.right那么比较的就是C*A.left/B.right与C/B.right因为A.left是大于等于一的整数，所以前者要大。所以应该把B放在前面。此时A.left*A.right比较大。情况三：其他情况。那么比较的就是C*A.left/B.right与C*B.left/A.right如果A.left*A.right大一些，那么应该把B放在前面。也就是说按照left*right从小到大排序我们发现情况一和情况二也满足‘最优做法是按照left*right从小到大排序’的性质，所以这样做就行了。这题难点其实在于高精度乘法除法。累了吧，让我们看一看搜索搜索的关键是，要找到合适的方法让效率提高。如果是裸的搜索是很容易编的，所以说其艺术性就在优化上。俗话说看起来越简单的东西，精通起来就越难。搜索分为深度搜索（DFS）与广度搜索（BFS），深度搜索又可以细分为记忆化搜索和迭代加深搜索(DFS-ID)等。NOIP2011提高组mayan用一句话来说题意，就是，给定一个存在重力的矩阵，每次只能向左或右交换方块，连续3个或以上的方块群会被消除。求操作次数为N时的操作步骤。搜索，进行优化虽然好像优化方法说出来之后很容易理解，但是考场上不是很容易都想到因为题目规定了游戏步数，而且并没有要你使用最少步数的方法，所以用DFS会很方便，用BFS会超空间。如何处理重力问题以及消除问题？深搜递归的时候参数要传一个结构体，即当前局面状态。写一个函数Down，传入一个局面，返回让当前局面中所有悬空的方块掉下去的局面再写一个函数Clear，传入一个局面，返回让当前局面中所有可消去的方块消去后的局面让当前局面轮流调用这两个函数，直到局面没有改变了为止。优化左右的交换是等价的如果当前局面某种颜色的方块个数小于等于二，显然这个局面就不可能通往胜利了（我当时居然没想到...什么？这个太容易了？大家都比我聪明TT）方块的掉落，不能改变方块的列，所以对于颜色i，如果某列l1上某颜色方块数量属于[1,2]区间，那么必须通过交换，来从其他的某列l2得到方块。取一个l1，且l2最远，设这个距离为Di，那么必须要把所有颜色的Di消到0。而一次操作最多减少两个颜色的Di，因此最少操作次数为：max{max{Di}(1<=i<=10),(sum(Di)(1<=i<=10)+1)/2}

NOIP2009提高组靶形数独搜索？搜索。依次枚举每一个没放置数的格子里所放置的数。用hh[i][j]记录第i行是否已经填过j这个数了，对于每个列和九宫格的记录同理。但是这样可能还会超时，怎么办？从右往左，从下往上搜。这个方法过于投机取巧？我们要领会出题者的意图——想让我们用常规的方法通过不了某个数据，而改用更高级的方法。但是一个数据只能让特定的搜索顺序进行的搜索变得特别慢，所以说如果我们事先随机一个搜索顺序，或许就能不被某个数据卡掉。还是感觉这种方法不够正义？对于每个局面，找出剩下未填的位置中的可填数字个数最少的位置，先填它。比如说A位置有4种合法填法，B位置有3种，C位置有5种，就先填B位置。每次进入递归函数都要进行一遍这个过程，太慢？其实只是让时间增加了一倍左右，但是通过‘先搜分支少的’的方法可以让运行速度呈指数地加快估计出题者是想让我们用dancing-links解决这个问题这是一种算法，用类似二维双向链表的结构优化了对于[精确覆盖问题]的搜索速度，所以说只要把原问题转化为这种[精确覆盖问题]再搜索就可以极大加快速度。有兴趣的同学可以百度搜一下这种算法，资料很多NOIP2007普及组纪念品分组普及组的题目都不会太难，增加信心用贪心每次考虑还没有被选过的最大的物品，然后找一个能与之价格加起来小于那个上限的最大的物品，组成一对。注意题目里说了每一组最多两个物品。如果找不到与之放在一组的物品，那么就单独放一组。由于那个与之放在一组的物品的最大允许价值是不降的，维护一个指针即可。为什么这样是正确的？如果当前考虑到物品A，B是A能组队的最大的物品，C的价值小于B。本来是A，B一组的，如果变成A，C一组，对于剩下的未选的物品集合的变化就是多了B少了C，这肯定是不会比变化之前更优的。考场上如果只能‘意会’到这种贪心是正确的，怎么办？写一个暴力的程序，再写一个数据生成器，与这种贪心方法的程序进行对拍。USACOBetsy'sTour一个正方形的镇区分为N*N个小方块（1<=N<=7）。农场位于方格的左上角，集市位于左下角。贝茜穿过小镇，从左上角走到左下角，刚好经过每个方格一次。当N=3时，贝茜的漫游路径可能如下图所示：1<=N<=7.搜索我们注意到，在任何时刻，都必须保证和当前所在位置不相邻的未经点至少有两个相邻的未经点。通过这种想法，我们可以采取这样的优化：1.对当前点周围的点D,如果只有一个与D相邻的未经点,则点D为必经点（下一步必须走到的点）2.如果当前点周围有两个或两个以上的符合上述条件的必经点，则无论走哪个必经点都会造成一个死胡同，需要剪枝3.如果当前点周围只有一个必经点，则一定要走到这个点N=7的时候还是会超时不能形成孤立的区域。如果行走过程中把路一分为二，那么肯定有一部分再也走不到了，需要剪枝。如果每次都使用floodfill算法找连通块，所耗时间会太多。我们必须有效率地进行剪枝。当前点左右都是已经点(或者是边界)，而上下都是未经点当前点上下都是已经点(或者是边界)，而左右都是未经点这样不管怎么走，必然是会有孤立的区域，只要将出现这种情况的状态都剪掉即可。HNOI2011赛车游戏简要题意给你一个道路每一段的长度与斜率s，对这段路来说，如果你用v的速度开，那么每公里的耗油量是max(0,a*v+b*s)，其中a,b是题目给定的常数。总油量是给定的，问开完这段道路最短时间。这题我当年得了多少分呢？贪心不妨设我们把路分成一公里一公里的小段。我们发现，对于一小段路，在其上提速1km/h的代价总是a既然总油量是确定的，综合上一条信息，这告诉我们，所有小段的速度的和是有限的假设路分为两个小段（每个小段1km，共2km），在这两个小段上的速度分别为x和y，那么我们要所用时间最少，也就是要1/x+1/y最小，并满足x+y=C（C是一个定值）当1/x+1/y最小时显然有x=y.所以说，最优的情况一定是所有路段的速度v都是相同的！（允许有一些下坡路段速度大于v，但是这些路段油耗都是零）具体做法？先不考虑下坡路段，算出此时在其他路段上的速度v如果v大于[最平缓的下坡路段零油耗时的速度]，说明这段下坡的速度不会比最终其他路段速度快，将其并入‘其他路段’的集合中，再次计算v。再比较v与[次平缓的下坡路段零油耗时的速度]，如果v是较大的，就并入，再次计算v...直到v是较小的为止。NOI2012骑行川藏

Input31000010000105200001585000056Output12531.34496464简要题意：一个道路有N段路，对于一段长度是s,风阻系数是k,风速是v的路，如果使用V的速度骑行，需要的能量是k*s*(V-v)^2.给定总能量，问骑完这个道路的最短时间。这道题与上道题有较大的相似性对于这道题而言，让一个小段（1km）的速度加快1km/h，需要的能量是与当前速度以及这段的性质有关的。我们需要将上题的方法推广到更普适的情况，以适应这道题设当前有一个方案，第i段路的速度是V[i]，且让走这段路所需的时间减小Δt所需要多耗的能量为de[i]*Δt。其实de[i]就是这段的耗能E对于耗时t的导数，将t=k[i]/V[i]代入E=k[i]*s[i]*(V[i]-v[i])^2再对t求导即得de[i]。最优方案中，de[1],....,de[N]的值都是相等的。这让我们先想到，二分最优方案的de的值，然后计算出此时每一段的速度（计算速度时需要解一个三次方程，可用三分法求解），然后求出总耗能，比较总耗能与给定的耗能，来决定二分的区间往哪边缩小。这种贪心的方法比较巧妙，关键是找出最优策略中的不变量——de的值。USACOlatinUSACO上的搜索题好多啊...搜索优化有哪些呢1.在第一行的排列已经确定以后，第一列的每一种排列对应的方案数都相同。所以只需要搜索(2,2)到(N,N)的边长为n-1的正方形即可（最后乘上第一列的可能方案数）。且对于(2,2)这个位置，填3，4……的方案数完全一样（与填1的可能不同），因此只要枚举填1或者3。2.最后一行不用搜，因为已经由之前的确定了（所以只要搜(2,2)-(n-1,n)的矩形）娱乐题有N个人，每个人有一个黑历史，一开始每个人只知道自己的黑历史。然后大家想来共享黑历史，目标就是让每个人都知道所有人的黑历史。传递信息的方式只能是两个人进行交流，这两个人可以把所有的自己已知的黑历史告诉对方。信息量再大也没事，都算是一次交流。问让每个人都知道所有人的黑历史，最少需要多少次交流比如说N=3的情况，A，B，C三个人。A先跟B交流，此时A知道A和B的黑历史，B知道AB的，C知道C的。B跟C交流，此时A知道AB的，B知道ABC的，C知道ABC的。B再跟A交流，此时大家都知道ABC其中每个人的了。需要3次。答案是2N-3第一个人先跟第2...N个人交流，其中跟第N个人交流之后，第一个人和第N个人都知道了所有人的信息。然后第一个人只需要跟第2...N-1个人交流，那么就让他们都知道了所有人的信息。真是这样吗~~~想一想N=4的情况，能不能比5次更少一点呢？比如说，4次？4次是可以做到的。A先跟B交流，此时A和B都知道了AB的信息。C跟D交流，此时C和D都知道了CD的信息。A跟C交流，此时A和C都知道了ABCD的信息。B跟D交流，此时所有人都知道了ABCD的信息。所以，2<=N<=3时答案是2N-3，N>3时答案是2N-4N>4时，方法是让第4个人跟5...N交流一遍来收集信息，然后再按照N=4的情况让1、2、3、4互换信息，然后第4个人再跟5...N交流一遍来下发信息。如上是2014年8月4日上午的讲课内容。此题作为中午的思考题被出出来。USACOmilk4超市中有P个桶(1<=P<=100)，每个桶有各自的容积你需要买回最少的桶，使得它们可以量出容积为Q的牛奶(1<=Q<=20000)。你每次可以使用一个桶，从巨大的牛奶池里装出等于这个桶容积的牛奶，放到一个大罐子里，你需要让这个罐子里的牛奶量为Q。你不能进行其他类型的操作。保证有解搜索因为题目中要求桶数最少，而深搜是不知道搜索的层数的，所以要用到迭代加深搜索。在主函数中，for循环从1开始枚举搜索层数（也就是使用的桶数），在for循环里面调用搜索函数（其中有一个参数是我们当前定下的搜索层数）。如果找到解，就跳出循环。可以用广搜做吗？应该可以，但太耗空间。你可能认为迭代加深搜索在定下深度为m+1层的搜索的时候，重复了深度为m的搜索已经做过的部分，但由于当深度上升时，搜索所用的时间呈指数上升，所以说重复的部分耗时可以忽略不计。（这段是应一些同学的要求写的，因为反映具体的递归过程不太会写。不过应该很多人都会吧..是比较基础的递归）在递归函数里要传入一个参数k，代表我们已经考虑完前k个桶了，那么当前只需考虑将第k+1~第P个桶中的哪个桶放入买桶的集合，然后再递归下去（传下去的参数为当前选择的桶的编号）。当搜索到一个组合，判断用这些牛奶桶是否可以得到解的时候，要结合动态规划的方法来做。设f[i]为用这些桶是否能够量出容量为i的牛奶，它是一个布尔型数组。初始条件为f[0]=1，其他f的值都为0.状态转移方程f[i]=f[i]orf[i-v[j]](j为使用的所有牛奶桶)目标状态为f[Q]如果f[Q]为1，则当前解合法，直接输出即可。

我们可以边搜索，边进行f数组的修改（要记录哪些位置被修改了，方便回溯）如果当前桶的容积是V，但是f[V]=1，说明通过之前的桶的组合就可以代替当前桶了，剪掉这种情况。由于直观上会觉得小的桶更加有用，所以事先将桶按照容积从小到大排序，再进行搜索，效果会更好。我们发现，对于一个桶的集合，如果是最优方法的话，肯定每一个桶都要用到。否则方法可以更优。也就是说，如果大小为x的容量可以不使用当前刚加入的桶就能达到了，我们不妨认为这种容量是‘达不到的’。也就是f[x]赋为0.具体来说，我们在每次加桶来更新f数组之前，把f数组复制一遍，设为g。更新之后，如果有某个i满足g[i]=1，那么就令f[i]=0，因为这个容量之前就已经是可以达到的了。让f中1的个数尽量少，为什么能够优化呢？注意到，我们的转移方程也可以看为，对于每个i

,若f[i]=1，则令f[i+v[j]]=1.（v[j]是刚刚加入的桶的容量）因为f[i]=1的i的个数比较少，我们可以用一个数组去记录哪些位置上的f[i]=1，于是我们更新一次f所需复杂度只是f中1的个数了。带权中位数问题SGU114给你N个东西，每个东西有两个性质a[i]（数值）和b[i]（权重）你要找到一个数X，使得sigma{abs(a[i]-x)*b[i]}最小。如果每个b[i]都是1，那么问题就等价于找中位数。贪心先将东西按照a从小到大排序。求出b[i]的和，设为B。先令temp=0。从前往后扫描东西，让temp+=b[i].当temp首次大于B/2时，当前的东西的a值就是x的最优值（之一）。最优性显然吧考虑将x变小或者变大，答案都不会更优。为便于理解，可以考虑每个东西的b值都为1的情况，那么就是朴素的中位数的问题，上一页所说的用temp进行的那个过程显然是对的。然后我们可以把第i个东西拆成b[i]个b值为1的东西。（如果b[i]是1.5，你就拆成1.5个b值为1的东西...虽然你会觉得很诡异，但的确可以这么理解）SGU313题目大意：在一个长为L（10^9）的环形跑道上，有n(n<=50000)个X，n个O，他们每个都位于跑道的某个整数位置上——我们以某个点为起点，位置即为顺时针离起点的距离。告诉你每个X和O的坐标，请你找出一种配对方案，使得每个X跑到自己心爱的O那里所经过的长度之和最短。输出每个X配对的是第几个O。如果不是一个环而是一个直线就很好做了，直接O（n）模拟扫一遍，开一个栈存放还未匹配的点编号，注意这些点可能是X集合的也可能是O，因为他们的先后没有规定。问题就是要找一个分割点，从这个分割点分割开后再对形成的一条直线进行上述操作。首先我们证明对最优方案，必定存在至少一根X、O中间的子线段，他们中间是没被任何匹配线覆盖的（即能找到一个分割点）。对上面这个图，他必定不是最优方案。为什么呢？我们可以对所有交叉的匹配进行调整，使得调整后肯定不比原来差，且有分割点存在。对于原来的X和O的顺序是X、X、O、O的一个子集，其中第1个和第3个连，2和4连，我们把它调整成1和4连，2和3连，这样答案不变。假设最优方案没有分割点，那么调整之后答案不变，但是必有一条最长的匹配已经包围了整个环了，这显然是荒谬的。下一步就是枚举分割点（其实是分割线段）。但是枚举是O(N)的，加上判断o（n），明显超时。我们要探寻神奇的性质。我们先随便假设一个点为起点（不妨设排序后第一个点）。若以此点所在线段进行分割，那么求得答案就是每条线段长度*架在它上面的匹配边的条数的和。架在它上面的匹配边的条数，这个有神奇的性质。扫一遍的过程中，每碰到一个黑点，下一截的线段标记+1，碰到白点就-1。我们发现架在它上面的匹配边的条数即为线段标记的绝对值.比如XXOOOX，架在相应线段上面的匹配边的条数即为1210|-1|0.（也就是121010）

那么，当匹配点往后移一位时，相当于是最左边的点移到了最右边，若最左边是X，那么线段变成了XOOOXX，新标记就是010|-1||-2||-1|我们惊奇的发现，所有边的标记都-1了！

假设我们枚举的分割点为k。k点的前缀和是vk(黑点为1，白点-1)。那么所有边新标记变成了原标记-vk!

那么，相当于找一个数，让它与所有线段原标记的差绝对值*对应线段长度的值尽量小。

我们发现，这就是一个带权中位数模型（sgu114是裸的带权中位数模型）折半搜索（双向广搜）比如这样一道题九宫格的华容道游戏大家都知道吧，每个格子有一个1~8的数，还有一个格子是空的给你初始状态和结束状态，问你有没有N步以内从初始状态变换到结束状态的方法，如果有的话输出步骤N很大怎么办呢？我们可以搜索（深搜广搜均可）出从初始状态开始走N/2步（向上取整）可以到达的状态，把这些状态用一个数字（就像MD5码一样！）表示，存在哈希表里（通过挂链的方式，也就是哈希表只是一个索引，在挂着的链上存储具体的九宫格状态。这样是为了避免两个实际上不同的状态却算出了同样一个数字）注意，搜索的时候要判重然后我们再从结束状态开始，搜索N/2（向下取整）步，然后对于每一种状态，也用一个数字表示，并且在哈希表内查找这种状态是不是被记录过。如果被记录过，就说明从两边的搜索到达了同样的一个状态，说明这是一个解。就像挖隧道一样如果你确定了隧道的开始点和结束点，选择只从一边挖的话，如果要恰好挖到结束点，需要尝试很多次但如果先从开始点开始挖一半的路程并且在挖到的地方做上标记（尝试许多次，做上许多标记），再从结束点开始挖一半的路程，只要找这种标记就行，就可以减少尝试次数折半搜索的搜索过程就像一个菱形如上是2014年8月4日的讲课内容。tyvj的一道题在烈日下工作了一个月的你，七夕了，你要给妹子送礼物，礼物当然是一块纯手工的砖，每次妹子看到这块砖就能想起你。这里有N个泥土块（N<=45），每个块有一定的质量，你可以选择其中一些泥土块去烧结成你的砖，而你对烧成的砖的质量有要求，它必须是一个精确的值，Q克(1<=Q<=10^8)，也就是你要找出一些块，他们的质量和恰好是Q。问是否有可行方案。看到N的大小，很诱人吧，很奇怪吧，45？45除以2大约等于22，而使用O(2^N)的爆搜所能承受的最大N值大约也是这么多。于是想到了折半搜索先搜索前22个土块能组成的质量，存在哈希表里，再搜索后22个土块能组成的质量，比如当前在后22个土块中搜到的质量和是x，然后在哈希表里查找是否存在Q-x这个值（也就是前22个土块中是否存在和为Q-x的组合）。USACOprime3在下面的方格中，每行，每列，以及两条对角线上的数字可以看作是五位的素数。方格中的行按照从左到右的顺序组成一个素数，而列按照从上到下的顺序。两条对角线也是按照从左到右的顺序来组成。这些素数各个数位上的和必须相等。左上角的数字是预先定好的。一个素数可能在方阵中重复多次。如果不只有一个解，将它们全部输出（按照这25个数字组成的25位数的大小排序）。一个五位的素数开头不能为0（例如：00003不是五位素数）输入：一行包括两个被空格分开的整数:各数位上的数字的和以及左上角的数字。输出：对于每一个找到的方案输出5行，每行5个字符,每行可以转化为一个5位的质数.在两组方案中间输出一个空行.如果没有解就单独输出一行"NONE"。搜索优化？一行行的顺序枚举连样例都过不了(....)先枚举两条对角线，因为他们控制的行列是最多的，而且左上角的数已经确定了。再枚举中间的一竖列,因为它同样控制的行列最多,再枚举最上面一行和最下面一行。此时第3行的2，4两个数也可以通过减法得到了。最后枚举第2，4行，第3行可以通过减法得到。于是所有格子都已经确定了，验证一下就行。由于要适应这种奇葩的搜索顺序，需要多个数组记录满足条件的素数，比如已知第1,3,5位的所有素数，或已知第1位的所有素数都要预处理出来。并且每个数用5个1位数储存（也就是用一个大小为5的数组储存...），这样操作方便而且效率高。你问我怎么想出来这种奇葩的搜索顺序的？呵呵，我也不知道，看题解才想出来的（如果是考场上想出来真的要靠功力和造化）不过如果知道了这种方法之后，理解起来还是不难的如果不知道哪种搜索方式比较快，可以编个数据生成器，自己试试一种方便的调试方法有某位弱得跟粉一样的渣询问我调试程序的一些技巧，所以我准备作为饭后甜点讲一讲~比如你有一个递归函数intwork(intp){...

}然后你发现好像有的时候p会变成负值，但是p是负值就是出现bug的时候，你想跳转到这种时候。那么你可以这么写intxxx（随便多定义一个全局变量）intwork(intp){if(p<0)xxx=0;...

}然后把断点设在xxx=0那一行处，再点调试，就可以在运行到那一行时停下，此时正好p是小于零的。为什么要写xxx=0呢？你写其他的也是一样的，比如用p=p代替xxx=0，总之目的就是让那里有一个语句，有一个东西..不过有的时候编译器会自动把p=p或者p=p+1-1这种语句过滤掉，因为它会认为这是码农们偶尔精神出问题时写下的废话HNOI2010matrix矩阵A和矩阵S都是N*M的非负整数矩阵。矩阵A的元素都小于P矩阵S的第一行和第一列均为0;且满足S[i,j]=A[i,j]+A[i-1,j]+A[i,j-1]+A[i-1,j-1]（i,j>1）给出N,M,P，以及矩阵S求字典序最小的矩阵A使得满足条件。30%：N,M≤10另30%：P=2100%：1＜N,M≤2001＜P≤10如果A的第一行与第一列已经确定，那么我们就可以按部就班地算出A的所有元素的值了。这样一来需要决策的元素个数就从200的平方变成了399。我们试图建立A[i,j]与第一行或第一列之间的直接等式关系。以下是一个较易理解的建立等量关系的方法：首先不看元素在0到P-1范围内的限制，设A1,k和Ak,1都为0，并计算将A补全。（此时A中可能有负数或者大于等于P的整数）我们只需要搜索A的第一行，每当确定一个元素，就可以更新A[j,1]的取值范围。根据公式，除了A[1,1]以外，A[i,1]的取值是互不影响的。不断更新第一列每个元素的可以取值的范围，一旦出现有某个元素下界大于上界的情况就剪枝。显然这样搜索的字典序是最优的。USACOcryptcow农民Brown和John的牛们计划协同逃出它们各自的农场。它们设计了一种加密方法用来保护它们的通讯不被他人知道。如果一头牛有信息要加密，比如"InternationalOlympiadinInformatics"，它会随机地把C，O，W三个字母插到到信息中（其中C在O前面，O在W前面），然后它把C与O之间的文字和O与W之间的文字的位置换过来。这里是两个例子：为了使解密更复杂，牛们会在一条消息里多次采用这个加密方法（把上次加密的结果再进行加密）。一天夜里，John的牛们收到了一条经过多次加密的信息。请你写一个程序判断它是不是这条信息经过加密（或没有加密）而得到的：搜索按从小到大的顺序依次找出C,O,W，然后交换中间的两个串并将这三个字符删掉。如此往复直到没有成对的C,O,W，判断一下最后生成的字符串是否是题目所给的串。由于添加的COW是一起的，因此给出的字符串的字符个数应该等于47（目标字符串的长度）+3*k。如果不满足就可直接判断无解。除了COW三个字符外，其他的字符的个数应该和目标串相一致。如果不一致也可直接判断无解。一个有解的字符串中，COW三个字母最早出现的应该是C，最后出现的应该是W，如果不满足则剪枝。搜索中间肯定会出现很多相同的情况，因此需要开一个hash来记录搜索到过哪些字符串，每搜索到一个字符串，就判重。对搜索到的字符串，设不包含COW的最长前缀为n前缀（同样也可以定义n后缀），那么如果n前缀不等于目标串的长度相同的前缀，那么当前字符串一定无解，剪枝。N后缀也可采取相同的判断方法。需要优化搜索顺序。经过试验我们可以发现，O的位置对于整个COW至关重要。可以说，O的位置决定了整个串是否会有解。因此，我们在搜索时，应该先枚举O的位置，然后再枚举C和W的位置。W要倒序枚举。在判断当前串的子串是否包含在目标串中的时候，可以先做一个预处理：记录每一个字母曾经出现过的位置，然后可以直接枚举子串的第一个字母的位置。这样比用pos要快2倍左右。APIO2011方格染色（这个题目不要求做）USACOfence8农民John准备建一个栅栏来围住他的牧场。他已经确定了栅栏的形状，但是他在木料方面有些问题。当地的杂货储存商扔给John一些木板，而John必须从这些木板中找出尽可能多所需的木料。当然，John可以切木板。因此，一个9英尺的木板可以切成一个5英尺和一个4英尺的木料(当然也能切成3个3英尺的，等等)。John有一把梦幻之锯，因此他在切木料时，不会有木料的损失。所需要的木料规格都已经给定。你不必切出更多木料，那没有用。（一看就觉得是美式翻译）在如下的说明中，rail代表的是‘目标块’，board代表的是‘原材料’。采用dfs-id（其实就是从小到大试验能切成的块数）来搜索每一个rail来源的board。以下技巧都是针对这种搜索顺序来制定的。很容易就能注意到，由于每块rail的价值是相等的——也就是说切小的要比切大的来的划算。那么我们在搜索能否切出i个rail的方案是自然要选最小的i个rail来切。经过一些实验可以发现，先切大的rail比先切小的rail更容易提前出解。先切大的board要比先切小的更快。由于r最大可能是1023，但是rail长度的范围却只有0~128，提醒了我们有很多rail的长度会是相同的。为减少冗余，若有rail[i+1]=rail[i]，则rail[i+1]对应的board一定大于等于rail[i]对应的board。如果board[i]=board[i+1]，那么从board[i]切下的最大的rail一定大于等于从board[i+1]切下的最大的rail。对于切剩下的board（无法再切下rail），统计一下总和。如果大于board长度总和-rail长度总和，一定无解。HNOI2011任务调度搜索+贪心+随机调整对于每个随便顺序的点，暴力搜索他属于类型1还是类型2。注意N<=20，这种指数复杂度是可以接受的。并且我们注意到，机器a一定是先处理完所有类型1的任务再处理完所有类型2的任务。机器b一定是先处理完所有类型2的任务再处理完所有类型1的任务。而且如果有两个第1类任务P,Q,在a机器上P先完成，那么在b机器上也是让P先完成。否则一定能够通过调整变成这种情况，且答案不变。贪心的部分然后我们对于先要在a机器上运行的任务，以需要在b机器上运行的时间(从小到大)作为第一关键字，需要在a机器上运行的时间作为第二关键字，进行排序。将排序结果作为a机器处理的先后顺序。对于先要在b机器上运行的任务，以需要在a机器上运行时间作为第一关键字，在b机器上运行时间作为第二关键字排序。这只是一个较优的安排。还是会有一个点过不了。随机调整的部分在此基础上，每次在第1类任务中随机选择两个任务，交换它们的位置。再在第2类任务中随机选择两个任务交换它们的位置。如果算出的答案比原来优，那么就接受这种调整。

即使交换2000次左右，依然很快。均分纸牌有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。SampleInput498176SampleOutput6贪心按照从左到右的顺序移动纸牌。如果第i堆的纸牌数不等于平均值v：1．若a[i]>v，则将a[i]-v张从第i堆移动到第i+1堆；2．若a[i]<v，则将v-a[i]张从第i+1堆移动到第i堆。若n=3，三堆纸牌数分别为为1，2，21的话，v=8,那么让第一堆的纸牌数达到8的时候，需要从第二堆拿7张过来，此时第二堆的纸牌数是-5。这样很奇怪嘛？其实我们只是改变了移动牌的顺序而已，而算出的最小操作次数是正确的。我们一定可以通过调整操作的顺序，使得每堆的牌数任何时候都大于等于零，比如每次只考虑将牌数大于v的牌堆的牌移到相邻位置（这样的操作一定存在）。NOIP2010提高组第三题简要题意：给你n个点，有些点之间有带权边，你要把这些点分为两个集合，使得两个端点在同一集合中的边的最大边权尽量小。二分答案，用二分图判断是否合法这样是O(nlogn)的有没有接近O(n)的做法？能贪心吗？如何贪心？假设题目一开始就把边按照边权从大到小排序了。从大到小考虑每一条边enemy-friend并查集这道题网上有很多题解，这里就不细讲了SGU246请问，在一个长度为P的圆环的整点上最多能够放置多少个1，使得所有的1之间在圆环上的距离都不为Q.1<=Q<=P<=10^18将那些整点标号为0~P-1.如果我们在0处放置一个1，那么Q处便不能够放置1了，于是根据贪心的思想，我们在2*Q处放置一个1....。如果这样能够把所有的位置都确定，那么答案就是Pdiv2。如果P与Q不互质，那么这样做是不能确定所有位置的。比如P=12，Q=3.考虑有几个这样的不相关的部分。应该是有gcd(P,Q)个的，而且每个部分的长度都是P/gcd(P,Q).所以答案就是gcd(P,Q)*(P/gcd(P,Q)div2)变成回文串给你一个小写字母组成的字符串，长度为N。每次操作，你可以交换串中相邻的两个字符。请你使用最少的操作次数，让字符串变成一个回文串。如果有解则输出最少操作次数，如果无解输出WTF.1<=N<=10^6看到这么大的数据范围，惊呆了，感觉应该是类似贪心的做法。最多只允许一种字符的出现次数是奇数，且它会出现在最中间位置。否则无解。如果有出现奇数次的字符，先将这种字符的排在最中间的那个（比如有7个这种字符，就选第4个）移到整个串的最中间去。然后如果对于某种字符，在串的左半边的数量跟在串的右半边的数量不等，则进行跨越中线的调整（调整时你可以让左半边的的一个调整到右半边去（刚调整到中间字符的右边就可以了），再让右半边的一个到左边去，这样交替调整...其实你也可以让所有需要从左边调整到右边去的先调整，但要注意由于此时原来中间那个字符的位置可能就不在中线上了，所以你需要调整到的位置是原来中间那个字符的位置的右边的相邻位置，而不一定是‘跨越中线’。）事实上不管用这里说的哪种方法调整，都是最优的。接下来，我们可以只调整左半边。先使得左半边最左的字符等于右半边最右的字符..然后再使左半边第二左的字符等于右半边第二右的字符...这样一定是最优的。如果只要求输出答案，也可以考虑上课时说的‘求逆序对个数’的方法。不过直接调整，得到的结果也是一样的。SGU296给你一个有N位的数n，你需要删去其中P位，并使得剩下的数尽量大。1<=P<N<=1000选取的最高位只能是原数的1~N–P+1位我们应该选取其中最大的数如果有多个最大的数，选取位置最靠前的（也就是高位）次高位的方法类似，注意要保证当前已经删的数不能超过题目要求。SGU165给你n个数a[1]..a[n],其中-50<=a[i]<=50对每个i都成立。且sigma{a[i](i=1~