hdoj4696

除了x[1]以外,其他x[]都是通过t[]数组转移的,so,显然x数组的值是在c数组中选的。
分情况:
(1)m<=0 显然无解
(2)若c数组中全是2:<1>那么如果m是奇数,无解.<2>m是偶数,有解
(3)若c数组中有1:第一个x选1,然后扩展,直到x数组的和>=m,由于x数组元素的值只可能是1或2,so,最终的和要么等于m,要么等于m+1,如果是等于m+1,只要去掉第一个1,从把x[2]的值作为x[1]扩展x数组即可。

hdoj4686 ——多校第9场A题

还是比较简单的题
思路;看到n的范围10^18,第一反应lg级别算法,然后发现时递推式,瞬间想到矩阵,既然是矩阵,自然是要推出aibi,然后很自然的会去想aibi有哪些组成部分推出来的呢,于是就会去把a和b的递推式左右分别乘乘一下。但是求的是所有aibi的和,简单,矩阵加一阶用来存储后面的aibi加起来的和即可。

hdoj4705–2013多校第10场Y题

树形dp:
dp[i]表示结点i为根的子树中无法形成简单路径的点对数。有如下几种情况:
(1)对于以点i为根的子树,两个点在i的一颗子树中(不成祖先后代关系),还有一个点在i的另一棵子树中。
(2)3个点分散在i的三棵子树中(i存在三个儿子的情况下)
比赛的时候很快就想到了这个,思路很简单,但是在想细节的时候,发现对于第二种情况是3次方枚举,然后队友说这题差不多了,我就没再想,去看其他题了,交给队友敲。后来发现队友TLE了,才知道他也是三次方的枚举。。。这,早点交流其实可以避免。。三次方必然超时嘛。。
然后俩队友讨论出了线性时间的方法,后来我又回来看这题(==这场的网络流好难。。),听队友讲了线性时间解决方法,似懂非懂。于是决定自己推。。推出来和队友的还是有些不一样的。。多算了些东东,多减了些东东
本质:对于n个数,a1~an,O(n)时间求其中下标不重复的三个数的积的总和(组合而非排列:a1*a2*a3和a2*a3*a1是一样的)。
设s=a1+a2+……+an,c=a1^2+a2^2+……+an^2所求答案为ans
在稿纸上算一下:ans=(s^3-[a1*(c-a1^2)+a2*(c-a2^2)+……+an*(c-an^2)]+[a1^2*(s-a1)+a2^2*(s-a2)+……+an^2*(s-an)]+s*c)/6;
仔细打下草稿还是可以出来的,最后除以3!是因为三个数进行了全排列。

双连通专题

前段时间空间和域名超期了,刷的几个专题都没记录,忘了一大半。。
hdoj:
2242考研路茫茫——空调教室 双联通缩点+树形DP
2460Network 边双连通
3849By Recognizing These Guys, We Find Social Networks Useful 双连通求桥
3896Greatest TC 双连通
4005 The war 边双连通
3394Railway 双连通求块

hdoj4628——2013多校第三场Pieces

题意:给定一个长度不超16的字符串,每次可以去掉一个回文序列(序列亦即可以不连续,但要顺序不变),问最少几次可以使原字符串为空?
思路:状压dp,(比赛时队友用bfs也过了,貌似速度比状压还要快。。)dp[i]表示到达i状态所需的最小步数。
先预处理出所有状态是否是回文序列。然后dp更新的时候有两种方法:一种是访问到i,用比它大的状态更新它,即填表,一种是访问到i,则更新所有它的子状态,即刷表。但是无论哪种,在更新时都要用到一个奇技淫巧:假如j是i的子状态(i为0的位,j必为0),那么i&(j-1)就表示比j小一点的i的子状态。因为i&sth保证了是i的子状态,(j-1)&sth保证了这个状态比j小一点。这个技巧减少了许多无用状态。效率大幅提高。
复杂度分析:对于每个状态,都要枚举他的子状态:c(n,n)*2^n+c(n,n-1)*2^(n-1)+……+c(n,1)*2^1+c(n,0)*2^0=(2+1)^n=3^n
代码:
填表

强连通专题

按着风神大大的博客切啊切~
提示在每道题后面,选中即可显示
HDOJ
hdoj1269 迷宫城堡 判断是否是一个强连通★
hdoj2767Proving Equivalences 至少加几条边让整个图变成强连通★
hdoj3836 Equivalent Sets 至少加几条边让整个图变成强连通★
hdoj1827 Summer Holiday 传递的最小费用★★
hdoj3072 Intelligence System 传递的最小费用★★
hdoj3861The King’s Problem 强连通+二分匹配★★

这题必须好好记下,题意木有读懂,orz。。
题意:在有向图G中,相互可达的两个点必须划分在一个区,并且一个区里的任意两个点,至少存在一条单向路径(不经过其他区的点)。问原图最少需要划分成几个区。
思路:首先相互可达的点必须在一个区,那么强连通缩点,这样形成了一个DAG森林。问题转化为:给定一个DAG森林,最少用几条路径可以覆盖所有点,每个点只能属于一条路径。其实就是求DAG森林的最小路径覆盖,拆点转化成二分图,最小路径覆盖=原图顶点-最大匹配
通过这道题顺便学了最小路径覆盖,然后整理了一些覆盖集、独立集之间的关系,爽。
代码(匹配还没学,,用sap跑的。。囧~)

树形dp专题(更新ing)

前段时间做线段树,结果做不下去了。。感觉dp太弱,遂打算做个专题,tree dp之后是状压,往后是数位dp和概率dp,不过图论也要抓起来
几个链接:
背包九讲:http://wenku.baidu.com/view/519124da5022aaea998f0f22.html
论文《几类背包问题》:http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html
依赖背包博文:http://www.cnblogs.com/GXZC/archive/2013/01/13/2858649.html
zero clock背包总结:http://blog.csdn.net/woshi250hua/article/details/7636866
开个树形dp专题:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25888#overview
(一)一般树形dp
(二)树形dp+分组背包
因为有分支,所以树上的背包要容量要分配,但是因为是依赖背包,所以根一定要选。从根往下看是分配,代码中实际是从叶子往上合并的,这种合并其实就是dd神牛的背包九讲里面的泛化物品,实质是把对一棵子树的决策(分配多少容量给该子树,因为决策互斥)作为一件物品,这样,合并=实际上就是做一次分组背包,一棵子树就是一个组,每组物品有dp[son][0]~dp[son][V-w[fa]]。为什么是V-w[fa]呢,因为父节点时一定要选的,所以给子节点的容量最多也就V-w[fa]。
////////////////////////////////////
hdoj1561
典型的依赖背包,因为可能是深林,所以以0为虚拟根,val[0]=0,w[0]=1;

最大公约数原理(转)

源地址:http://blog.sina.com.cn/s/blog_67e046d10100reqb.html
1、最大公约数原理
设d = gcd(A1, A2, …, An),则必然可以找到或正或负的整数Xi, 使
A1X1 + A2X2 + … + AnXn = d
证明:回想一下多个数求gcd的方法,可知gcd(A1, A2, …, An) = gcd(A1, gcd(A2, A3, …, An))。对序列(A1, A2, …, An)进行如下操作:从i = 1开始,设j = i + 1,若gcd(Ai, Aj) = k > 1,则将Aj修改为k,注意k是可以由Ai*p + Aj*q得到的。操作一直进行到最后,若全部修改完后,左边必为gcd(A1, A2, …, An),而右边必可写成A1X1 + A2X2 + … + AnXn,得证!
2、A1X1 + A2X2 + … + AnXn = 1有解的充要条件是d = gcd(A1, A2, …, An) = 1
证明:
①、方程左边必整除d,故方程右边必整除d,因而方程有解 => d = 1。
②、若d = 1,则由最大公约数原理可知,必存在一系列或正或负整数Xi,使A1X1 + A2X2 + … + AnXn = d = 1。
统合①、②,命题得证!