#
Astar队成立已经一个多月了，还记得我们集体参加的第一场比赛是8.8号南航的官方练习赛，由于正值暑假期间，各大OJ都没有正式的比赛，所以这个比赛吸引了众多的大牛参加。我认为这次比赛对于我们队的意义倒不是比赛的结果，而是通过这场比赛我们有了初步的磨合，队员与队员之间开始达成默契。最后通过几个小时的努力，我们AC了6题，排名大概在15左右。这是我们队参加的第一次正式比赛^_^。
当时是计划暑假至少参加两次练习比赛的，第二次的比赛本来想选择天大，后来听说8.23号有北大的月赛，于是便坚定地再战POJ了.比赛前我们分好了题，开始的时候先各自看了一会题，我时不时盯一下board,比赛开始不久我发现A题已经有人过了，于是大家一起商量了下，决定dfs暴力这道题，并且由沸腾来写这个题，其它人看别的题，过了没多久，A题AC了。我们开的第二道题是一道概率题，求安全通过不踩到雷的概率，我初步分析了下，这道题可以转化成一个递推数列的问题，我直接敲了一个递归的算法，交上去，TLE了，于是不得不考虑其他的算法。其实这道题可以用差分方程直接算出来，这样可以跳过中间的递推，大家商量后，由张俊华推公式，开始Wa了1，2次，最终AC了，由于有公式，代码非常短。这道题也提醒了我差分方程的重要性，尤其在对数列方面的题上。最终我们队AC了两题，大致排在前100位左右，比赛完后很以外的看到了“another crazy man"队 ，神奇的是，和我们队贴在一起了 呵呵。
再来看网络赛的情况，第一场合肥网络赛。题目比较“友好”，和平时做的题目，衔接度比较大，但是也有所创新，我觉得说它完全是陈题是不恰当的。分好题之后，大家各自开始看题，我首先看到了上升子序列那道题，和阿义商量了一下，很熟悉，不过暂时没有想法，所以直接跳过看别的题，于是看到了那道计算几何，由于暑假在家里做了计算几何的专题，这样的题目做了很多，主要是叉积的运用，不过由于早已总结出模板，直接套用模板，处理了一下输入输出就过了。等过了第一题，貌似开始觉得有希望的题已经被别的队做出来了，只好开始看另外的题。这时候注意到了已经有很多人过的A题，压力比较大，刚开始的时候大家都没有什么想法，后来我想到了背包问题，大家一起讨论，阿义突然说他有想法，貌似是他见过的一道题，航电上面的，当时听到很多队说它们用N^3的算法超时了，阿义说他用的是N^2的算法，敲好了之后处理了一下模除，顺利AC.这时剩下的只有两道同构的题目还有一道通过率为0的题目，由于同构的题目以前从来没有接触，图的同构更是NP问题，几乎没有什么想法，只能上网搜索资料，后来听说窦煜峰组过了，问了一下，原来用充分条件巧妙地AC了那道题，思路并不复杂，数据比较弱而已。这次比赛给我们的启示主要出自同构的那两道题，其实有的时候并不需要使用标准算法，比赛亦有技巧可用的。像图的同构本为NP问题，既然标程都不可能使用绝对正确的算法，那么这题肯定可以使用做题技巧来解的。
接下来，第二场网络赛，刚开始的时候非常郁闷，网络不是很好，等真正拿到题目开始做题，几乎半个小时过去了，然后看到了那道通过率比较高的hello,world,看到题目我的第一反应是汇编，不过显然不可能，后来看到每一行代表一个字符，每一行有5个16进制数，而每一个字符由5个竖行表示，应该是一个16进制数代表一列的信息，数进制转换无疑。不过正准备敲的时候，有同学发消息说这题已经过了，于是只好放弃看其他的题目。之后的1个小时，大家在看题，互通每道题目的意思，前两个小时大致弄明白了没道题目的意思，这一点我们做得很好。沸腾说题目难的话就做一道模拟题，于是他着手做了A题，我和阿义两个人同时写一道点线关系的题目。
关于那道计算几何题，我们使用的是扫描+hash，可惜一直TLE，优化了很多次，还是TLE，直到比赛结束。赛后问了下中山大学的ACMer，它们用的也是hash判重的方法，过了，不过为什么我们的一直TLE？至于沸腾的那道题，应该是很有希望过的，不过由于时间原因，最后没有写完，略微有些遗憾。
哈尔滨网络赛，写总结之前，忽然听说了现场赛要推迟的消息，原因是为了控制流感疫情，哈尔滨的几所大学要采取应急措施，取消近期一切室内活动。不知道比赛究竟会被推到哪天进行。。。BTW，比赛开始以后，还是按照惯例，先分好题，阿义看的是后面，发现很快就有人AC了J题，我们想会不会是一个模拟题呢？于是我首先去模拟这个题，用了数组模拟然后优化，可惜TLE了，后来联想到树，不过好像已经被其他组过掉了，只好放弃，做别的题目。等大家把题目都看的差不多了，我们开了一道数列的题，我们很直观的想到了差分方程求解数列的通项公式，然后再求位数。张俊华负责推出公式，可是后来我发现发现这个想法无法实现，因为计算中会出现小数，大数模板没法处理小数。。。一时陷入了僵局。最终我们决定放弃这道题，不过时间已经所剩无多。赛后有人说这道题可以用模拟科学计算器的方法来做，这才恍然大悟。这次网络赛对大家的启示在于对题目的灵活转换上面，有的问题并不是你不能，而是你没有意识到。 爱因斯坦说的对，想象力比知识更重要。
总结就到这里，所说的一切只属于过去，我相信，我们还会继续不断地向前走，不断地超越自我，我们的集训队也会变得更加强大。
5个16进制数代表一个符号，这个符号用5个竖行来表示，显然一个数字代表一竖行的信息，将那个十六进制数转换为2进制后会有8位，取前7位在适当的位置输出'#'即可！这题也可以算作一道密码破译题。
#include<iostream>
using namespace std;
char s[100][500];
char t[10];
void trans(int n)
{
int p=0;
memset(t,'0',sizeof(t));
while(n!=0)
{
p++;
if(n%2==1)
t[p]='1';
n/=2;
}
}
int main()
{
int testcase;
int i,j;
int k;
int n;
scanf("%d",&testcase);
for(i=1;i<=testcase;i++)
{
memset(s,' ',sizeof(s));
scanf("%d",&n);
for(j=1;j<=n;j++)
{
for(k=1;k<=5;k++)
{
int num;
scanf("%x",&num);
trans(num);
int l;
for(l=1;l<=7;l++)
{
if(t[l]=='1')
s[8-l][(j-1)*6+k]='#';
}
}
}
printf("Case %d:\n\n",i);
for(j=7;j>=1;j--)
{
for(k=1;k<=6*n-1;k++)
{
printf("%c",s[j][k]);
}
printf("\n");
}
printf("\n");
}
return 0;
}
今天终于将后缀数组总结完了，开个贴庆祝一下，顺便总结一下字符串的相关问题，字符串问题按做法分大概可以是以下几类：
1.暴力brute force ,这个没什么可说的，一般正规的比赛这种方法必然超时。。。（山寨比赛似乎可以考虑。。。）
2.字典树问题，通常和多个字符串的前缀有关。能写出模板基本上就没问题了，比赛的时候稍微改改，套上去就能用。
3.KMP问题，单串匹配，求一个字符串在另一个字符串中的匹配情况，可重复，不可重复均可。Next函数扩展问题，这个我已经总结过。
4.后缀数组问题，重点之所在，结合罗穗骞同学的论文，总结了使用后缀数组的13中重要情况，几乎可以覆盖所有的字符串问题。
5.AC自动机 这个多串匹配，模板很重要。
２．２．２子串的个数
例5：不相同的子串的个数（spoj694,spoj705）
给定一个字符串，求不相同的子串的个数。
算法分析：
每个子串一定是某个后缀的前缀，那么原问题等价于求所有后缀之间的不相
同的前缀的个数。如果所有的后缀按照suffix(sa[1]), suffix(sa[2]),
suffix(sa[3]), …… ,suffix(sa[n])的顺序计算，
不难发现，对于每一次新加
进来的后缀suffix(sa[k]),它将产生n-sa[k]+1 个新的前缀。但是其中有
height[k]个是和前面的字符串的前缀是相同的。所以suffix(sa[k])将“贡献”
出n-sa[k]+1- height[k]个不同的子串。累加后便是原问题的答案。这个做法
的时间复杂度为O(n)。
看的时候怎么都没看懂为什么要加一，从他论文里给出的模板来看，sa[i]的取值应该从0 to n-1,带了一下1111这个数据，显然加一是错误的。后来用模板做了下spoj 694，加1WA,反之AC，证明了我的想法，看来罗同学的表达有些前后不一致了。
另外，罗同学在给出的标程中并没有使用他给出的解法，而是转了个弯，等差数列求和算出所有后缀长度的总和，然后在减去height[i](i from 1 to n),
这个做法比直接累加要好些。
记得以前读过苏轼的《范增论》，原文的第一段是：
汉用陈平计，间疏楚君臣，项
羽疑范增与汉有私，稍夺其权。增大怒曰：“天下事大定矣，君王自为之，愿赐骸骨，归卒伍。”未至彭城，疽发背死。
一直好奇陈平用的是什么计策，呵呵，今天在现代生物导论上看了陈丞相世家，才豁然开朗。
上大学以后就一直在抽时间看《史记》，毕竟是史家之绝唱，无韵之离骚嘛，以前看的人物虽然战功累累，但是论智谋却只能算平平。也许因为我也属于智慧型，所以对陈平颇为看好吧，尤其是他的智谋^_^
陈丞相平者，阳武户牖乡人也。这是第一段的收获，个人感觉看完史记至少得记住这人的封号还有籍贯 呵呵。
原来他还属于倒插门类型的，他家里很穷，但是他娶了一个富人的女儿张氏，记得李白也属于这种类型，难道有才之人都有这共通之处吗？呵呵
第三段对我来说印象较为深刻，“里中灶，平为宰，分肉食甚均。父老曰：“善，陈孺子之为宰！”平曰：“嗟乎，使平得宰天下，亦如是肉矣！”聪明的你一定看出来了吧，陈平一句“使平得宰天下，亦如是肉矣”道出了陈平的雄心壮志，宰肉算什么，要宰，就宰天下！
事实上，他做到了。
我觉得陈平最过人之处就是他的智谋，这从他使金离间项羽和亚父范增中体现的淋漓尽致。“陈平既多以金纵反间于楚军，宣言诸将钟离昧等为项王将，功多矣，然而终不得裂地而王，欲与汉为一，以灭项式而分王其地。项羽果意不信钟离昧等。”接着刘邦与平一唱一和，“吾以为亚父使，乃项王使”复持去，更以恶草具进楚使。这招可够聪明的，既散播谣言，动摇项羽内心，又区别对待楚使，这让项羽不得不信他的将领怀有二心。中国的政治斗争中，要想取胜，最重要的一点就是互相信任，一旦互相猜忌，后果就不堪设想。在想想战场上，忠心耿耿的岳飞吧，为了保卫国家，将生死置之度外，但是他最终没有死在敌人的利刃下，而是死在同朝幕僚的谗言中，不亦哀乎！。。。。。。防人之口，甚于防川啊。
再看陈平所献之第二计：诱捕韩信。韩信这个人，太傲气，功高盖主，竟自立为齐王。难道他没有像样一点的谋士吗？难道他不知道鸟尽弓藏，兔死狗烹,卸磨杀驴吗？稍微懂点历史的人都知道，在平定天下之后，功高盖主的必然是帝王的首要铲除对象。哎，韩信的下场大家都知道了，我只是可惜，因为我也很喜欢韩信的。闲话不多说，还是说陈平吧，当韩信自立为齐王后，各种各样有关他要谋反的谣言就自然而然地传到刘邦的耳朵里，问问武官,怎么办？武官们说，打！再问陈平，平曰“人之上书直言信反，有知之者乎？”曰：“未有。”曰:“信知之乎？”曰：“不知。”陈平曰：“陛下精兵孰与楚？”上曰：“不能过”。正由于陈平一番话，把问题的实质给揭露出来，既然打不过，这样做不是自取灭亡吗？况且出师无名，又如何取信于天下？韩信献计：不如来个天子南游，等群诸侯来谒之时，因而擒之，不过几个力士的事罢了？又何必动用军队？^_^
再看陈平做人，拿捏有度，不自矜其能，不功高盖主，为人谦让，这才是真正的做人之道啊!再看看你身边的那些人吧，一旦有了点权利就自高自傲，目空一切，殊不知这是在为自己买棺材呢。俞敏洪上次来演讲的时候还这样说，天上有座云做的沙发，位置很高，但是你敢做吗？座上去，还不摔死你？绛侯勃，为右丞相时，平为左丞相，首先必须知道，古代尚右。又一次孝文帝问：天下一年有多少刑事案件啊？勃不知，又问国家一年有多少钱谷收入呀？勃又不知，天子有些不高兴了。陈平这时显得很聪明，他没有落井下石，而是帮勃下台，说这些事情自有专门的人处理，左右丞相只不过是帮天子您管理好您的臣子罢了，我们的职责是“主臣！”这让勃自愧不如，只能自愿地将右丞相的位置拱手送给陈平。这不是很高明吗？个人认为陈平的做人是很值得我们学习的
呵呵 司马迁对他的评价也很高，说其“常出奇计，救纷纠之难，振国家之患。及吕后时，事多故矣，然平竟自脱，定宗庙，以荣名终，称贤相，岂不善始善终哉！非智谋孰能当此者乎？”纵观历史风云，最后得善始善终的寥寥无几，陈平这个人做到了，又岂能说是历史的偶然呢？
毛泽东二十岁左右的时候也读过史记,据闻他很喜欢做批注，不知道他对陈平的评价如何，是否英雄所见略同呢？
摘要: POJ 2485 Highways 标准的prim模板题，只是输出的不是最小生成树的总权值，而是MST中的最长边。
#include<iostream>#include<cmath>#include<cstdio>using namespace std;#define MAX 501int n;int ...
阅读全文
摘要: 北京赛区的经典题目，最优比率生成树，传说中楼哥1A的G题。。。什么是最优比率生成树呢？说白了很简单，已知一个完全图，每条边有两个参数（b和c），求一棵生成树，使(∑xi×ci)/(∑xi×bi)最小，其中xi当第i条边包含在生成树中时为1，否则为0。其实也可以看成一个0，1的整数规划问题。我的做法是LRJ《算法艺术与信息学竞赛》中介绍的二分，详细的证明请看书，这里只是简单的介绍...
阅读全文
二分图最小覆盖的Konig定理及其证明
二分图：
顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。
最小覆盖：
最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数
Konig定理：
二分图的最小顶点覆盖数等于最大匹配数。
证明：
为主便叙述，假设G分为左边X和右边Y两个互不相交的点集。。。。。。
假设G经过匈牙利算法后找到一个最大匹配M，则可知G中再也找不到一条增广路径。
标记右边未匹配边的顶点，并从右边未匹配边的顶点出发，按照边：未匹配->匹配->未匹配...，的原则标记途中经过的顶点，则最后一条经过的边必定为匹配边。重复上述过程，直到右边不再含有未匹配边的点。
记得到的左边已标记的点和右边未标记的点为S， 以下证明S即为所求的最小顶点集。
1。| S | == M
显然，左边标记的点全都为匹配边的顶点，右边未标记的点也为匹配边的顶点。因此，我们得到的点与匹配边一一对应。
2。S能覆盖G中所有的边。
上途S中点所得到的边有以下几种情况：
（1）左右均标记；
（2）左右均无标记；
（3）左边标记，右边未标记；
若存在一条边e不属于S所覆盖的边集，则e 左边未标记右边标记。
如果e不属于匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果e属于匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的左端点就应该有标记。
3。S是最小的覆盖。
因为要覆盖这M条匹配边至少就需要M个点。
转自:http://yejingx.ycool.com/post.2801156.html#
在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集．
由上面可以得出：
１.一个单独的顶点是一条路径；
２．如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．
最小路径覆盖就是找出最小的路径条数，使之成为Ｐ的一个路径覆盖．
路径覆盖与二分图匹配的关系：
最小路径覆盖＝｜Ｐ｜－最大匹配数；
其中最大匹配数的求法是把Ｐ中的每个顶点pi分成两个顶点pi'与pi''，如果在p中存在一条pi到pj的边，那么在二分图Ｐ＇中就有一条连接pi'与pj''的无向边；这里pi' 就是p中pi的出边，pj''就是p中pj 的一条入边；
对于公式：最小路径覆盖＝｜Ｐ｜－最大匹配数；可以这么来理解；
如果匹配数为零，那么Ｐ中不存在有向边，于是显然有：
最小路径覆盖＝｜Ｐ｜－最大匹配数＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路径覆盖数为｜Ｐ｜；
Ｐ＇中不在于匹配边时，路径覆盖数为｜Ｐ｜；
如果在Ｐ＇中增加一条匹配边pi'－－＞pj''，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在一条路径上，于是路径覆盖数就可以减少一个；
如此继续增加匹配边，每增加一条，路径覆盖数就减少一条；直到匹配边不能继续增加时，路径覆盖数也不能再减少了，此时就有了前面的公式；但是这里只 是说话了每条匹配边对应于路径覆盖中的一条路径上的一条连接两个点之间的有向边；下面来说明一个路径覆盖中的每条连接两个顶点之间的有向边对应于一条匹配 边；
与前面类似，对于路径覆盖中的每条连接两个顶点之间的每条有向边pi--->pj，我们可以在匹配图中对应做一条连接pi'与pj''的边， 显然这样做出来图的是一个匹配图（这一点用反证法很容易证明，如果得到的图不是一个匹配图，那么这个图中必定存在这样两条边 pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路径覆盖图中就存在了两条边pi-->pj, pi--->pk ，那边从pi出发的路径就不止一条了，这与路径覆盖图是矛盾的；还有另外一种情况就是存在pi'---pj'',pk'---pj''，这种情况也类似可证）；
至此，就说明了匹配边与路径覆盖图中连接两顶点之间边的一一对应关系，那么也就说明了前面的公式成立！
转自:http://hi.baidu.com/cjhh314/blog/item/ded8d31f15d7510c304e1591.html
摘要: 最长上升子序列问题是各类信息学竞赛中的常见题型，也常常用来做介绍动态规划算法的引例，笔者接下来将会对POJ上出现过的这类题目做一个总结，并介绍解决LIS问题的两个常用算法(n^2)和(nlogn).问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列（设为s1,s2,...sn），使得这个子序列满足这样的性质，s1<s2<s3<...<...
阅读全文
想想去年7月份的时候，我才刚刚开始接触ACM，短短一年的时间，就到400题了，虽然过程曲折回环，但终究还是走了过来，特留此贴纪念。
昨天有位同学帮我重新温习了下稼轩先生的 贺新郎，想了想，词中的千古名句，我见青山多妩媚，料青山见我应如是放在此处，当是很贴切吧。只不过，我的心境和稼轩先生的略有不同，稼轩先生的两句诗，与其说是真正的乐观，还不如说是不得志时，聊以疗伤的借口！今天，我借稼轩先生的两句诗，以我的心境，赋给它全新的含义：自古英雄多磨难，但是只要拥有乐观的姿态，又有什么做不到的呢？我见青山多妩媚，料青山兄见我也应当如此吧。呵呵^_^
50，100，200，300，400
几个寻常的数字，却藏着一段难忘的人生经历。
从水题，到基本贪心，动态规划等算法，再到最短路生成树，再到网络流，匹配，线段树，后缀树，后缀数组，差分约束，计算几何，组合数学，从一无所知，到写出模板并熟练的运用模板解题，几乎完全自学，从不可能到可能，now ,you should believe, everything is possible~
今后的日子，当然还要继续努力，亚洲区预赛马上就要到了，我要全力以赴，so please trust me , yes we can~
最后，我要感谢在ACM道路上帮助过我的教练，学长和我的同学们，谢谢你们对我的鼓励和帮助。