<?xml version="1.0" encoding="utf-8" ?><rss version="2.0"><channel><title><![CDATA[happy_lcj]]></title><description><![CDATA[此博客暂停更新，详情请见 http://happylcj.github.io/]]></description><link>https://blog.csdn.net/acm_code</link><language>zh-cn</language><generator>https://blog.csdn.net/</generator><copyright><![CDATA[Copyright &copy; acm_code]]></copyright><item><title><![CDATA[2014 多校赛 第一场]]></title><link>https://blog.csdn.net/acm_code/article/details/46858779</link><guid>https://blog.csdn.net/acm_code/article/details/46858779</guid><author>acm_code</author><pubDate>Mon, 13 Jul 2015 09:56:01 +0800</pubDate><description><![CDATA[题目链接

A - Couple doubi
题意：桌上共有 k 个球，第i个球的值为 (1^i+2^i+...+(p-1)^i )mod p
DouBiXp 和 他的女朋友 DouBiNan 轮流拿球，DouBiNan先拿，
所有的球都拿完后，谁手上球的值总和更大谁就赢，
已知 k,p，且p为素数，
若DouBiNan赢输出"YES",否则输出"NO"]]></description><category></category></item><item><title><![CDATA[poj 1026 Cipher (置换群)]]></title><link>https://blog.csdn.net/acm_code/article/details/43273721</link><guid>https://blog.csdn.net/acm_code/article/details/43273721</guid><author>acm_code</author><pubDate>Thu, 29 Jan 2015 17:18:38 +0800</pubDate><description><![CDATA[链接：poj 1026

题意：给定n个大小1-n的不同的整数作为密钥，给定一个字符串，
      求将该字符串经过k次编码后的字符串
分析：暴力求解会超时，可以利用置换群的知识解题
置换群：一个有限集合的一一变换叫做置换,一对对置换组成了置换群。
对于一个集合a(a[1],a[2],a[3]...a[n]) 通过置换可以变成
     (b[a[1]],b[a[2]],b[a[3]]></description><category></category></item><item><title><![CDATA[poj 3071 Football （概率 dp）]]></title><link>https://blog.csdn.net/acm_code/article/details/43273417</link><guid>https://blog.csdn.net/acm_code/article/details/43273417</guid><author>acm_code</author><pubDate>Thu, 29 Jan 2015 17:00:28 +0800</pubDate><description><![CDATA[题意：有2^n个队，相邻的两两打淘汰赛，n轮后必定会决出冠军，
      求最后哪个队夺冠的概率最大
分析：dp[i][j]表示第i轮的时候，第j去支队伍赢的概率
则dp[i][j]的前提就是i-1轮的时候，j是赢的，且第i轮赢了对方]]></description><category></category></item><item><title><![CDATA[poj 2728 Desert King (最优比率生成树)]]></title><link>https://blog.csdn.net/acm_code/article/details/43273003</link><guid>https://blog.csdn.net/acm_code/article/details/43273003</guid><author>acm_code</author><pubDate>Thu, 29 Jan 2015 16:36:43 +0800</pubDate><description><![CDATA[题意：有n个村庄，给出每个村庄的坐标和海拔，
benifit为两点之间的水平距离，cost为两点的高度差，
现要求一棵树使得 cost / benift 最小，即求一个最优比例生成树
分析：01规划的应用
设x[i]等于1或0, 表示边取或者不取
则所求的比率 rate = ∑(cost[i] * x[i]) / ∑(benifit[i] * x[i])]]></description><category></category></item><item><title><![CDATA[poj 2976 Dropping tests (01规划，二分查找)]]></title><link>https://blog.csdn.net/acm_code/article/details/43272385</link><guid>https://blog.csdn.net/acm_code/article/details/43272385</guid><author>acm_code</author><pubDate>Thu, 29 Jan 2015 16:00:48 +0800</pubDate><description><![CDATA[链接: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]]></description><category></category></item><item><title><![CDATA[poj 2947 Widget Factory (高斯消元，解模线性方程)]]></title><link>https://blog.csdn.net/acm_code/article/details/43271603</link><guid>https://blog.csdn.net/acm_code/article/details/43271603</guid><author>acm_code</author><pubDate>Thu, 29 Jan 2015 15:09:57 +0800</pubDate><description><![CDATA[题意：生产一些零件，已知零件种数，记录条数
记录只记录了某次生产从周几开始，周几结束，以及生产了哪些产品。
每件商品生产所需天数为3-9天。
求每样产品需要多少天才能完成。
若无解输出Inconsistent data.
有无穷解输出Multiple solutions.
有唯一解，输出其解]]></description><category></category></item><item><title><![CDATA[poj 1905 Expanding Rods (二分查找)]]></title><link>https://blog.csdn.net/acm_code/article/details/43233273</link><guid>https://blog.csdn.net/acm_code/article/details/43233273</guid><author>acm_code</author><pubDate>Wed, 28 Jan 2015 17:10:35 +0800</pubDate><description><![CDATA[链接：poj 1905
截取自某大牛的blog,详情请关注：链接：Enumz
题意：一根两端固定在两面墙上的杆长度为L，受热弯曲后变弯曲，长度L′=（1+nc)*L
     求前后两个状态的杆的中点位置的距离
分析：设L′对应的半径为r，弧长为2α，要求的距离为x]]></description><category></category></item><item><title><![CDATA[poj 3122 Pie (二分查找)]]></title><link>https://blog.csdn.net/acm_code/article/details/43232591</link><guid>https://blog.csdn.net/acm_code/article/details/43232591</guid><author>acm_code</author><pubDate>Wed, 28 Jan 2015 16:37:21 +0800</pubDate><description><![CDATA[题意：我生日派对时，准备了n个圆柱形的pie,半径比一定相同，但高都为1，
邀请了f个朋友，加上自己一共f+1人，需要将n个pie分给f+1个人
要求：每个人分得的pie尺寸要一样大，
并且同一个人所分的pie要是从同一个pie上得到的，n个pie分完后可以有剩余
求：每个人最多可以分多少]]></description><category></category></item><item><title><![CDATA[poj 3440 Coin Toss (概率)]]></title><link>https://blog.csdn.net/acm_code/article/details/43232053</link><guid>https://blog.csdn.net/acm_code/article/details/43232053</guid><author>acm_code</author><pubDate>Wed, 28 Jan 2015 16:07:10 +0800</pubDate><description><![CDATA[题意：在m*n的网格盘上，每个格子大小都是t*t,
现将一个直径为c的硬币扔在向网格盘上，
求硬币覆盖1,2,3,4个格的概率分别为多少
注：圆心只可能落在在网格盘上
分析：问题可转化为求覆盖1,2,3,4个格硬币圆心活动的面积
分别推出公式即可求解
注意输出格式、、、]]></description><category></category></item><item><title><![CDATA[poj 1062  昂贵的聘礼 (有限制的最短路)]]></title><link>https://blog.csdn.net/acm_code/article/details/43231603</link><guid>https://blog.csdn.net/acm_code/article/details/43231603</guid><author>acm_code</author><pubDate>Wed, 28 Jan 2015 15:44:38 +0800</pubDate><description><![CDATA[题意：探险家想娶酋长的女儿，需要昂贵的聘礼，
但可以用其他物品加优惠价替代，其他物品也可用另外的物品和优惠价替代，
求探险家最少需多少金币可以娶到酋长的女儿？
注意：等级限制：如果两人地位等级差距超过了M，就不能"间接交易"，但酋长的等级不一定最高
分析：这是一道求有等级限制的最短路，可以将每个物品（包括酋长允诺）看成一个结点，
替代品间的优惠价为边的权值，]]></description><category></category></item><item><title><![CDATA[hdu 5139 Formula]]></title><link>https://blog.csdn.net/acm_code/article/details/41788109</link><guid>https://blog.csdn.net/acm_code/article/details/41788109</guid><author>acm_code</author><pubDate>Sun, 07 Dec 2014 15:52:33 +0800</pubDate><description><![CDATA[即先将多组输入输出存起来，转化为一组，再排序后暴力求解，
这样数组只需开到100000]]></description><category></category></item><item><title><![CDATA[poj 2546 Circular Area （两圆相交面积）]]></title><link>https://blog.csdn.net/acm_code/article/details/41623511</link><guid>https://blog.csdn.net/acm_code/article/details/41623511</guid><author>acm_code</author><pubDate>Sun, 30 Nov 2014 16:01:15 +0800</pubDate><description><![CDATA[题意：已知两圆的圆心和半径，求两圆相交部分的面积
分析：两圆的位置关系有三种：相离，相交，内含
相离时：相交面积为0
相交时，大扇形面积+小扇形面积-四边形面积
内含时，相交面积为小圆面积]]></description><category></category></item><item><title><![CDATA[poj 1679 The Unique MST (判断最小生成树是否唯一)]]></title><link>https://blog.csdn.net/acm_code/article/details/41211537</link><guid>https://blog.csdn.net/acm_code/article/details/41211537</guid><author>acm_code</author><pubDate>Mon, 17 Nov 2014 16:27:40 +0800</pubDate><description><![CDATA[题意：判断最小生成树是否唯一，
若唯一，输出最小权值和，否则，输出  Not Unique!

判断最小生成树是否唯一的思路：
1、对图中的每一条边，扫描其他边，如果存在相同权值的边，则对该边做标记
2、然后用Kruskal算法或Prim算法求MST
3、求得MST后，如果该MST中未包含做了标记的边，即可判断MST唯一；
如果包含做了标记的边，则依次去掉这些边的一条边，再求MST，
如果求得的MST权值和原来的MST的权值一样，即可判断MST不唯一。]]></description><category></category></item><item><title><![CDATA[poj 1659 Frogs' Neighborhood (Havel-Hakimi定理，判断序列是否可图)]]></title><link>https://blog.csdn.net/acm_code/article/details/41210329</link><guid>https://blog.csdn.net/acm_code/article/details/41210329</guid><author>acm_code</author><pubDate>Mon, 17 Nov 2014 15:30:54 +0800</pubDate><description><![CDATA[其实质是给定一个度序列，判断是否可图，
若可图，输出YES，并输出各顶点之间的连边的情况
否则，输出NO
思路：判断一个序列是否可图，直接利用Havel-Hakimi定理即可]]></description><category></category></item><item><title><![CDATA[度序列与Havel-Hakimi 定理]]></title><link>https://blog.csdn.net/acm_code/article/details/41209929</link><guid>https://blog.csdn.net/acm_code/article/details/41209929</guid><author>acm_code</author><pubDate>Mon, 17 Nov 2014 15:16:52 +0800</pubDate><description><![CDATA[度序列：若把图G所有顶点的度排成一个序列s，则称s为图G的度序列
序列是可图的：一个非负整数组成的有限序列，
如果是某个无向图的度序列，则称该序列是可图的可图的
判断一个序列是否是可图的，可以用 Havel-Hakimi定理]]></description><category></category></item><item><title><![CDATA[hdu 4323 Magic Number (dp,编辑距离)]]></title><link>https://blog.csdn.net/acm_code/article/details/41082201</link><guid>https://blog.csdn.net/acm_code/article/details/41082201</guid><author>acm_code</author><pubDate>Thu, 13 Nov 2014 16:39:23 +0800</pubDate><description><![CDATA[题意：给定n个串和m次询问，对于每次询问，给定一个字符串t，和最大操作次数a,
问在n个字符串中有多少个能在规定的次数之内变成字符串t.
说明：字符串的基本操作仅为：删除、插入和修改一个字符这三种操作
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。
两个字符串的编辑距离：两个字符串a和b，通过上述的基本操作，把a变成b或b变成a，
需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离]]></description><category></category></item><item><title><![CDATA[poj 1850 Code (组合数学)]]></title><link>https://blog.csdn.net/acm_code/article/details/41013585</link><guid>https://blog.csdn.net/acm_code/article/details/41013585</guid><author>acm_code</author><pubDate>Tue, 11 Nov 2014 16:49:23 +0800</pubDate><description><![CDATA[题意：合法的字符串序列:由小写字母组成，每一个字符比后一个字符ASCII码要大。
将这样的字符串序列按字典序排列编码，第一小的编码为1，第二小的编码为2...依次类推
如：a->1，b->2……z->26，ab->27……vwxyz->83681.
给定一个字符串，若其合法，输出其编码，否则输出0
分析：先判断是否合法，若合法，再算其编码
计算编码即计算比该字符串小的字符串的个数，再加1即为其编码]]></description><category></category></item><item><title><![CDATA[poj 3252 Round Numbers （组合数学）]]></title><link>https://blog.csdn.net/acm_code/article/details/41012937</link><guid>https://blog.csdn.net/acm_code/article/details/41012937</guid><author>acm_code</author><pubDate>Tue, 11 Nov 2014 16:13:32 +0800</pubDate><description><![CDATA[题意：一个数转化成二进制之后，0的个数大于等于1的为round数，
给定一个区间[m,n]，问这区间内有多少round数
分析：要求[m,n]间的的round数，
可以用[1,n+1）的个数减去[1,m)的个数，]]></description><category></category></item><item><title><![CDATA[poj 1942 Paths on a Grid (组合数学)]]></title><link>https://blog.csdn.net/acm_code/article/details/41012249</link><guid>https://blog.csdn.net/acm_code/article/details/41012249</guid><author>acm_code</author><pubDate>Tue, 11 Nov 2014 15:31:29 +0800</pubDate><description><![CDATA[题意：给一个n*m的矩阵网格，问有多少种方法从左下角走到右上角。
注意n，m都是32位无符号整形范围内，可以直接用64位存，
从左下角走到右上角的过程中，每次只能向上或向右走一个单位长度。
分析：向上走要走n步，向右走要走m步，就相当于n+m个位置选n个向上或选m个向右]]></description><category></category></item><item><title><![CDATA[poj 1703  Find them, Catch them （并查集）]]></title><link>https://blog.csdn.net/acm_code/article/details/41007069</link><guid>https://blog.csdn.net/acm_code/article/details/41007069</guid><author>acm_code</author><pubDate>Tue, 11 Nov 2014 09:21:42 +0800</pubDate><description><![CDATA[题意：在这个城市里有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在一个团伙，]]></description><category></category></item></channel></rss>