happy_lcj

链接：poj 1026题意：给定n个大小1-n的不同的整数作为密钥，给定一个字符串，      求将该字符串经过k次编码后的字符串分析：暴力求解会超时，可以利用置换群的知识解题置换群：一个有限集合的一一变换叫做置换,一对对置换组成了置换群。对于一个集合a(a[1],a[2],a[3]...a[n]) 通过置换可以变成     (b[a[1]],b[a[2]],b[a[3

题意：有2^n个队，相邻的两两打淘汰赛，n轮后必定会决出冠军，      求最后哪个队夺冠的概率最大分析：dp[i][j]表示第i轮的时候，第j去支队伍赢的概率则dp[i][j]的前提就是i-1轮的时候，j是赢的，且第i轮赢了对方

题意：有n个村庄，给出每个村庄的坐标和海拔，benifit为两点之间的水平距离，cost为两点的高度差，现要求一棵树使得 cost / benift 最小，即求一个最优比例生成树分析：01规划的应用设x[i]等于1或0, 表示边取或者不取则所求的比率 rate = ∑(cost[i] * x[i]) / ∑(benifit[i] * x[i])

链接:poj 2976题意：给定n和k,a1,a2...an和b1，b2...bn求扔掉k组数ai,bi 后,下面式子的最大值为多少分析：01规划的基本应用假设最大值为x可得：   100*sigma(a[i])/sigma(b[i])=x---->    100*sigma(a[i])-x*sigma(b[i])=0

题意：生产一些零件，已知零件种数，记录条数记录只记录了某次生产从周几开始，周几结束，以及生产了哪些产品。每件商品生产所需天数为3-9天。求每样产品需要多少天才能完成。若无解输出Inconsistent data.有无穷解输出Multiple solutions.有唯一解，输出其解

链接：poj 1905截取自某大牛的blog,详情请关注：链接：Enumz题意：一根两端固定在两面墙上的杆长度为L，受热弯曲后变弯曲，长度L′=（1+nc)*L 求前后两个状态的杆的中点位置的距离分析：设L′对应的半径为r，弧长为2α，要求的距离为x

题意：我生日派对时，准备了n个圆柱形的pie,半径比一定相同，但高都为1，邀请了f个朋友，加上自己一共f+1人，需要将n个pie分给f+1个人要求：每个人分得的pie尺寸要一样大，并且同一个人所分的pie要是从同一个pie上得到的，n个pie分完后可以有剩余求：每个人最多可以分多少

题意：在m*n的网格盘上，每个格子大小都是t*t,现将一个直径为c的硬币扔在向网格盘上，求硬币覆盖1,2,3,4个格的概率分别为多少注：圆心只可能落在在网格盘上分析：问题可转化为求覆盖1,2,3,4个格硬币圆心活动的面积分别推出公式即可求解注意输出格式、、、

题意：探险家想娶酋长的女儿，需要昂贵的聘礼，但可以用其他物品加优惠价替代，其他物品也可用另外的物品和优惠价替代，求探险家最少需多少金币可以娶到酋长的女儿？注意：等级限制：如果两人地位等级差距超过了M，就不能"间接交易"，但酋长的等级不一定最高分析：这是一道求有等级限制的最短路，可以将每个物品（包括酋长允诺）看成一个结点，替代品间的优惠价为边的权值，

题意：已知两圆的圆心和半径，求两圆相交部分的面积分析：两圆的位置关系有三种：相离，相交，内含相离时：相交面积为0相交时，大扇形面积+小扇形面积-四边形面积内含时，相交面积为小圆面积

题意：判断最小生成树是否唯一，若唯一，输出最小权值和，否则，输出 Not Unique!判断最小生成树是否唯一的思路：1、对图中的每一条边，扫描其他边，如果存在相同权值的边，则对该边做标记2、然后用Kruskal算法或Prim算法求MST3、求得MST后，如果该MST中未包含做了标记的边，即可判断MST唯一；如果包含做了标记的边，则依次去掉这些边的一条边，再求MST，如果求得的MST权值和原来的MST的权值一样，即可判断MST不唯一。

其实质是给定一个度序列，判断是否可图，若可图，输出YES，并输出各顶点之间的连边的情况否则，输出NO思路：判断一个序列是否可图，直接利用Havel-Hakimi定理即可

题意：合法的字符串序列:由小写字母组成，每一个字符比后一个字符ASCII码要大。将这样的字符串序列按字典序排列编码，第一小的编码为1，第二小的编码为2...依次类推如：a->1，b->2……z->26，ab->27……vwxyz->83681.给定一个字符串，若其合法，输出其编码，否则输出0分析：先判断是否合法，若合法，再算其编码计算编码即计算比该字符串小的字符串的个数，再加1即为其编码

题意：一个数转化成二进制之后，0的个数大于等于1的为round数，给定一个区间[m,n]，问这区间内有多少round数分析：要求[m,n]间的的round数，可以用[1,n+1）的个数减去[1,m)的个数，

题意：给一个n*m的矩阵网格，问有多少种方法从左下角走到右上角。注意n，m都是32位无符号整形范围内，可以直接用64位存，从左下角走到右上角的过程中，每次只能向上或向右走一个单位长度。分析：向上走要走n步，向右走要走m步，就相当于n+m个位置选n个向上或选m个向右

题意：在这个城市里有2个黑帮团伙，现在给出N个人，M条信息输入D x y代表x于y不在一个团伙里输入A x y要输出x与y是否在同一团伙或者不确定他们在同一个团伙里分析：虽说是并查集的题，但又有所不同，本题给出的信息为x,y不在一个团伙，而并查集确定的是关于有关系的操作假设x与x+N不在一个团伙，y与y+N不在一个团伙，又x与y不在一个团伙，一共只有2个黑帮团伙，所以x与y+N在一个团伙，y与x+N在一个团伙，

题意:有一个由数字组成的序列规律为112123123412345123456123456712345678123456789123456789101234567891011 ...输入位置n，计算这一串数字第n位是什么数字

题意：给出n类珍珠，所需它们的数量，以及它们的单价，要求用最少的钱就可以买到相同数量的，相同（或更高）质量的珍珠。注：价格更高的珍珠等级更高，支付规则为：买任一类的珍珠n个(单价：p)，都要支付(n+10)*p的钱

题意：给出了两个瓶子的容量A,B, 以及一个目标水量C，对A,B可以进行如下操作：FILL(i) 将瓶i装满水DROP(i) 将瓶i倒空POUR(i,j) 将瓶i中的水倒入瓶j,此操作后要么瓶j装满水，要么瓶i为空求至少要几次操作能使A或者B装的水为C，并输出具体操作分析：可以从6个方面bfs，因为要输出具体操作，可以用数组模拟队列，并记录前一次操作的状态，最后再回溯路径

题意：有一种新的碎纸机，要用新的碎纸机将纸条上的数字切成几部分， 求切完后的和最接近而不超过target的值。比如，target的值是50，而纸条上的数字是12346，应该把数字切成四部分，分别是1、2、34、6。所得到的和43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50，而12, 34, 6也不可以，因为它们的和超过50了。

题意：给定一个未完成的数独，0是待填位置，其他均为已填入的数字。 如果能将其补充完整，则输出补充完整的数独（有多组答案输出任意一组），否则原样输出数独：一个9行9列的网格，包括9个3*3的子网格，要求每行、每列、每个子网格内都只能使用一次1-9中的一个数字，即每行、每列、每个子网格内都不允许出现相同的数字。

题意：给定一个完全图，求将其分为两部分的边权值和最大如：题中第一组样例：30 50 3050 0 4030 40 0将顶点分为两个集合A={2}，B={1,3}，sum=C21+C23=90为最大权值和

题意：如果相邻的中继器使用不同的频道，就不会相互干扰。给定一些中继器的相邻关系，问至少要选几个不同的频道，使得中继器都不互相干扰。分析：这题可以转化为无向图的染色问题，即相邻的点不能染同一种颜色，求至少需要的几种颜色？本题顶点数最多为26，可以直接用暴力搜索即可

题意：给定一个大数k，k是两个大素数的乘积的值,再给定一个int内的数L 问这两个大素数中最小的一个是否小于L，如果小于则输出这个素数。分析：因为k达到了10^100,只能用字符串读入，再转化为千进制，用int数组存储， 然后枚举小于L的素数，看是否能被整除，即判断k%L是否为0， 这样就得先用筛选法求素数打表，但是注意要打表到大于10^6 关于高精度取余，就需要用到同余定理

题意：有一个数x，给定k组ai和ri,使得x%ai=ri 求x最小为多少分析：求解模线性方程组　　x = a1(mod m1)　　x = a2(mod m2)　　x = a3(mod m3)　　　　先求解方程组前两项。 x=m1*k1+a1=m2*k2+a2　-> m1*k1+m2*(-k2)=a2-a1

题意：对于C语言的循环语句for(i=A ; i!=B ;i +=C)， 问在k位存储系统中循环几次才会结束。若在有限次内结束，则输出循环次数,否则输出死循环。注：利用了 k位存储系统的数据特性进行循环(会溢出)

题意：求A^B的所有因子的和对9901取余后的值如：2^3=8,8的因子有 1,2,4,8,所有和为15，取余后也是15应用定理主要有三个：（1）整数的唯一分解定理： 任意正整数都有且只有一种方式写出其素因子的乘积表达式。 A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数

题意：给出长度为n的序列，每次只能交换相邻的两个元素问至少要交换几次才使得该序列为递增序列分析：冒泡排序每次只能交换相邻两个元素，也就是求用冒泡排序使其为递增序列的交换次数，每交换一次记录一次就好但是这题数据较大，冒泡排序效率比较低，会超时的这里就可以利用归并排序了

题意:给定一个主串，和单词序列，问最少在主串删除多少字母，可以使其匹配到单词序列，如browndcodwcowmilkwhiteblackbrownfarmer删除主串中的两个d,brown和cow就与整个主串匹配了

题意：给定一系列关系（只存在大写字母），判断是否存在矛盾，或无法确定关系，或可以确定唯一的关系分析：利用拓扑排序，但是需要边输入关系边排序矛盾：判断是否存在环确定关系：能找出唯一的拓扑排序不能确定关系：不存在环，且所有关系处理后，关系仍无法确定

题意：士兵站成一行，求最少要多少的士兵出列，使得每个士兵都能至少看到一个最边上的士兵中间某个人能看到最边上的士兵的条件是:该士兵的身高一定强大于他某一边（左边或右边）所有人的身高，

题意：给定两个字符串，求它们对齐匹配的最大值要求：可以两个字符匹配，也可以一个字符和‘-’匹配，但是不能两个‘-’匹配

题意：给定一些树的种类名，求每种树所占的百分比，并按字典序输出分析：实质就是统计每种树的数量n，和所有树的数量m,百分比就为 n*100./m由于数据达到一百万，直接用数组查找肯定超时，可以用trie树，空间换取时间

题意：给定一些木棒，木棒两端都涂上颜色，不同木棒相接的一边必须是相同的颜色，求是否能将木棒首尾相接，连成一条直线.分析：可以用欧拉路的思想来解，将木棒的每一端都看成一个结点由图论知识可以知道，无向图存在欧拉路的充要条件为：① 图是连通的；② 所有节点的度为偶数，或者有且只有两个度为奇数的结点。

题意：一个矩形中，有n个城市‘*’，‘o’表示空地，现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖本身和相邻的一个城市，求至少放置多少个基站才能使得所有的城市都覆盖无线？思路：求二分图的最小路径覆盖（无向图）最小路径覆盖=点数-最大匹配数注：因为为无向图，每个顶点被算了两次，最大匹配为原本的两倍，因此此时最小路径覆盖=点数-最大匹配数/2

题意：有一个n*n的矩阵,在矩阵上有m个行星,一个武器可以消灭同一行或者同一列的星星求最小的要用多少武器消灭所有的星星思路：把方阵看做一个特殊的二分图（以行列分别作为两个顶点集V1、V2，其中|V1|=|V2|）然后把每行x或者每列y看成一个点，而障碍物(x,y)可以看做连接x和y的边。按照这种思路建图，问题就转化成为选择最少的一些

题意：有n个点和m条有向边，现在要在点上放一些伞兵，伞兵可以沿着图走，直到不能走为止，每条边有且仅有一个伞兵走过，问最少放多少个伞兵思路：求的最小路径覆盖，用二分图来做对于这样的一个有向图做最小路径覆盖，首先建图然后每一条有向边对应左边的点指向右边的点这样建好图之后求最大匹配数最小路径覆盖=点数-最大匹配数

题意：有n个学生，每个学生都和一些人有关系，现在要你找出最大的人数，使得这些人之间没关系思路：求最大独立集，最大独立集=点数-最大匹配数分析：建图时应该是一边是男生的点，一边是女生的点连边，但是题目中没说性别的问题，只能将每个点拆成两个点，一个当作是男的点，一个当作是女的点了，然后连边.由于关系是相互的，这样就造成了边的重复。也就是边集是刚才的二倍，从而导致了最大匹配变成了原本的二倍，因此，此时最大独立集=点数-最大匹配数/2.

题意：没看题的具体意思，本质是求最长升序子序列的长度

题意：在n*m的房间有num个机器，它们的坐标和方向已知，现给定一些指令及机器k执行的次数，L代表机器方向向左旋转90°，R代表机器方向向右旋转90°，F表示前进，每次前进一米若前进时机器i撞到机器j,输出“Robot i crashes into robot j ”若机器走出了n*m的房间，输出“Robot i crashes into the wall ”当出现上述情况，只需输出第一次出现上述的情况若所有指令执行完，所有机器都没碰到上述情况，输出“OK”