foj 1982 dp 设其中一个已知
/*
http://hi.baidu.com/topman3758/blog/item/a19e4af91effb975034f56d2.html
别人说的简单dp，我都不会做....#_#
题目给出一个串n<=1000 串只会出现a,b,c三种字符
abc或bca可切成一块
设最后切出m0个abc , m1个bca，则答案为min{m0,m1}
求试答案最大
dp[i,j]表示前面i个字符切出了j个abc，能获得的最多dp[i,j]个bca
转移是看最后这个三个字母是什么
dp[i-3,j-1] “abc”
dp[i-3,j]+1 "bca"
dp[i-1,j]
注意dp[i,j] 3*j<=i ， 对于不存在的值不能引用，否则会出错！！
貌似这种有两个要求值的，都是设成一个已知
如这里前i个，有j个abc
*/
zoj 3449
/*
一个数字a（最多100000位），本来a = ∑ai*10^i，不断变为a' = ∑ai*x^i (x=1,2...9) 。
直至a‘<10 ，求此时的a'
比较变化前后的结果，发现变化后减少了∑ai(10^i-b^i)
一开始我就用Java大整数去逼近（减去10^i-b^i），使得结果趋近于10且小于10
超时了
看了watashi的，∑ai*10^i = ∑ai*x^i (mod 10-x)
“于是我们知道对10-b求模是关于这种运算的不变量，可以发现答案就是b+(n-10)%(10-b)”
其实我之前的那个不断逼近，其实就是 mod 10 - x 而已，脑残了！！！
因为(a^n - b^n) % (a-b) = 0
可以几位合在再mod会快点
最后结果要不断加上10-x，使得逼近于10
*/
zoj 3450
/*
一个定点p0，n个目标点 ，每个目标点有敌人wi,要消灭该点需要ti时间
弱目标点在同一直线，必须先消灭近的才能消灭远的
问在T时间内最多能消除的敌人
分组背包
注意的是，坐标比较大，用double会精度不够
看了watashi的做法
他将坐标都除以他们的gcd ，相等的就是同一直线了，而gcd就用来判断距离了！！
这样将大数变小了！！！
注意的是gcd(abs(x),abs(y))要加绝对值
*/
zoj 3451
/*
给出足球起点坐标，初速度大小，初速度方向，问球能不能进。
球每碰地一次速度减半
参考watashi的
注意有力量不足的情况
*/
zoj 3453
/*
一列敌人，每个敌人有生命值l[i]
哆啦A梦可以发射m个糖衣炮弹，每个炮弹会攻击最靠近右边的且生命值>=ki的敌人
被攻击的敌人生命值变为1，该敌人会将他的朋友的生命值+1，其朋友区间为a[i],b[i]
如果找不到敌人，则所有敌人生命值+1
求最后生命值最大的
note : 线段树查找满足条件的最靠近右边的写法
*/
zoj 3354
/*
给出一种映射f,问一个序列经过任意次映射的复合，问能得到多少种不同的文本
"he may encrypt the letter for several times. "
here may be ai=aj when i≠j. 不是一一映射
如果是一一映射的，就是一个一个的环了（因为出度、入度为 1）
看watashi的
这题就变成环引出尾巴出来了
答案就成了：max{x[i]} + LCM{y[i]}
x[i]为尾巴长度，y[i]为环长度
注意求x[],y[]数组的方法，用栈
而求LCM时，要分解质因子才行
因为LCM(a%MOD,b%MOD) != LCM(a,b)%MOD
*/
zoj 3456
/*
给出一个图，每增加一条边，问能否从0点遍历所有点回到0点，求最小时间
在一个点有停留时间stay[i]，经过边也有时间，但最多只能经过n-1条不同的边
题目说了是一棵树，可以令 边权 = 2*原边权+stay[u]+stay[v]
则MST即为答案了
答案是求能否在一年内访问完，注意有闰年
看watashi写法的
保留原有MST的边即可了，新加入的边，需小于MST的最大边，才允许加入，然后看能否得到更小的值
但每次下来，只需保留n-1条边（MST的边）
*/
cf 56E
/*
n张多米诺骨牌排成一行，每一张在位置xi，高度为hi
它倒下的话会影响到[xi,xi+hi-1]，问每张骨牌最多能影响右边的多少张骨牌
令dp[i]表示第i张骨牌能影响到的最远的骨牌为dp[i]
dp[i] = max{dp[j]} x[i] <= x[j] <= x[i] + h[i] - 1
则第i张骨牌能影响到的骨牌数目为dp[i] - i + 1
我一开始用线段树搞，用单调队列也行
看了别人代码，神奇，直接算就行了
第i张骨牌，检查的范围是[x[i],x[i]+h[i]-1]
如果在检查过程中发现j，其中dp[j]能影响的最远范围已经超过x[i]+h[i]-1的话，就不用再检查j之后到x[i]+h[i]-1
的骨牌了，因为从x[j]到x[i]+h[i]-1的已经被j考虑过了（也可认为是j到x[i]+h[i]-1最后只会收敛到dp[j]）
直接return dp[j]即可
反之，若未超过，则令 j = dp[j] + 1
跳跃性检查
（认为j到dp[j]收敛到dp[j]了，所以下次检查dp[j]+1）
*/
CF57D
/*
题意：n,m的网格，有一些static particles，规定任意两个不能在同一行、列，不能在相邻的对角线
A dynamic particle选择非static的cell作为起点和终点，然后从起点选择最短路径走到终点（不经过
static particles）。问平均路长
参见解题报告：http://www.codeforces.com/blog/entry/1171
题目的那种规定，发现，对于同一行、列，如果要跨过那个'X'，就需要多加2
而对于连续行的'X'，如下图：
1..X.....
2....X...
3......X.
1的左边到1、2、3的右边需要多加2
2的左边到2、3的右边也需要多加2
...
另外，对于下图：
1..X.....
2......X.
3....X...
1的左边到2的右边需多加2，而到3的右边不需加
2的右边到3的左边需多加2
所以，从上往下，对于连续的行，寻找递增或递减的一块，然后对于这一连续的块，统计从左边到右边
或右边到左边需要多加的步数2
解题报告的框架，两两点距离之和（包括'X'）- 'X'到所有点距离和*2 + 'X'到'X'距离和*2
这里多减了2倍'X'到'X'的，所以要加上
最后，再加上因为'X'存在要绕路需要多加的距离
*/
CF 58D
/*
题意：n个单词（lowercase），先要分成n/2行，每行2个单词，两个单词用分隔符d隔开
要使得所有行串起来字典序最小，问如何安排每两行的单词
分隔符d可以<'a' , > 'z'
若已知第一个单词，那么要使字典序最小，第2个单词肯定是长度为avg-lena中字典序最小的单词
avg是每一行两个单词的长度和
可以先按照 单词+d 来排序，然后按从小到大安排
每个排在前面的单词，然后加上长度为avg-lena中字典序最小的单词
*/
SRM 496 PalindromfulString 容斥写法 ★★★★
/*
问长度为N的字符串(uppercase)中，至少有K个长度为M的回文串的个数
N<=11
一开始我在那里dp推，发现有重复之类的东西不好搞
看了Sevenkplus的，容斥，感觉好神奇
最多有P = N - M + 1个回文串
由于规模比较小，枚举选出哪几个作为回文串，使得至少有K个，令这个模式为Ti
（如N = 3, M= 2 , K = 1 ，一个合法的模式为 010）
则答案为|T0∪T1...∪Tc|，这里就要用到容斥了
= ∑|Ti|
-∑|Ti∩Tj|
+∑|Ti∩Tj∩Tk|
...
直接套用的话复杂度为2^(2^P) ！！
与平常的容斥有点不一样，这里存在很多“Tj包含于Ti”，即其交集就是子集了
如011包含于010
因为满足011的肯定满足010，所以011是010的子集，这里注意了！！二进制枚举Ti的超集Tj，是模式Ti的子集
画个韦恩图，一个集合Tj要计算的次数就是先减去其余集合Ti在这部分算的次数（减完就为空了），再加上1
即为 1 - 其余集合Ti在这部分算的次数
用num[i]表示集合Ti需要算的次数，则num[i] = 1 - ∑num[ii] ii为i的超集
for(int j = i+1 ; j < (1<<P) ; j++)
{
if((j & i) == i)//j是i的子集
num[j] -= num[i];
}
所以集合Ti对答案的贡献为 ans += num[i]*26^cnt
O((2^p)^2)
cnt为集合Ti独立变量的个数
对Ti,求独立变量的个数，可以先建图（利用回文串两端相等的性质），然后dfs算出连通块的个数就是独立变量的个数了
*/
TCO'10 Qualification Round 1A 1000pt MegadiamondHunt
/*
将只含有'<','>'的串，每次去掉<..<>..>连着的几个
如果去掉中有n对，则得分为n^2
求最大得分
一开始以为去掉的顺序没关系，过不了最后一个sample
看了LayCurse的代码，它是每次选择 极大的<..<>..>中最小的一个去掉
这样子去贪心...
如 <<<>><>>
如果先去掉<<>>，然后剩下<<>> 得分为 2^2+2^2
但若先去掉<>，则剩下<<<>>> 得分为 1 + 3^2
因为，考虑一个极大的<..<>..>,若它能扩大，则它的左右肯定先去掉了一个
极大的<..<>..>，如果已去掉的那个比当前的大，得分是不会比先去掉当前
这个较小的大，所以每次选极大中的最小那个去掉
*/
zoj 3458
/*
0 < b - a < 1 + 2sqrt(a) 求 floor(sqrt(a)+sqrt(b))^n % 2(a+b)
看watashi的，没接触过这种问题，做法挺神奇( ⊙ o ⊙ )！
由 0 < b - a < 1 + 2sqrt(a)
=> 0 < sqrt(b) - sqrt(a) < 1
令Xn = (sqrt(b)+sqrt(a))^2n = (b+a+2sqrt(ab))^n
Yn = (sqrt(b)-sqrt(a))^2n = (b+a-2sqrt(ab))^n
Zn = Xn +Yn = (b+a+2sqrt(ab))^n + (b+a-2sqrt(ab))^n
由于X1 = b+a+2sqrt(ab) , Y1 = b+a-2sqrt(ab)
是方程(U-X1)(U-Y1) = 0 ，即 U^2 - 2(a+b)U + (a-b)^2 = 0 的根
则Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
用矩阵乘法可以求得Zn
由于Yn<1 ，所以floor(Xn) = Zn - 1，所以最后答案Zn-1即可
以上方法有个地方
“
由于X1 = b+a+2sqrt(ab) , Y1 = b+a-2sqrt(ab)
是方程(U-X1)(U-Y1) = 0 ，即 U^2 - 2(a+b)U + (a-b)^2 = 0 的根
则Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
”
我不太懂，查了下特征根的一点东西
若An+2 = pAn+1 +qAn
则An = C1α^n + C2β^n
上面应该是逆过来
由Zn = Xn +Yn = (b+a+2sqrt(ab))^n + (b+a-2sqrt(ab))^n
推出Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
*/
zoj 3461
/*
给出一个无向图，有边权，点权。点权val[i]为正的表示要将val[i]分出给点权为负的，每个点可以作为中间节点
点权val[i]为负的表示要接收val[i]，传送的花费为路径的距离，求最小距离
n<=16
按照题意，花费即为∑val[i] = 0 的树的MST
我有想过需要划分成几部分，起初没想过怎么划分
解题报告是枚举子集作为一部分树，dp求解（n那么小，要往集合方面想吧！）
即dp[mask] = dp[mask^i] + mst[i];
注意需要sum[mask] = 0 的才有意义
*/
zoj 3463
/*
一只手，相对拇指不动，至少要占5个键的位置，至多可以弹到9个键。
拇指移动距离x需要花费floor(sqrt(x))，已知左右手初始位置和接下来
需要弹奏的1000个键，求最小花费。
状态比较明显，dp[n,l,r]表示已经弹了n个音符，左、右手拇指分别在l,r
的最小代价
无效状态很多，不能计算，否则会超时
枚举左右手到需要弹的位置，其他情况不用考虑，不会更优
这句话不太懂："But, one finger touching the key between two fingers of the other hand is fobidden."
貌似不用处理？
看watashi的代码的
sqrt的初始化很漂亮
hdu 3651是简化版，都是无效状态不用算，决策是直接到需要的位置
*/
zoj 3464
/*
N个人，起初在一条线上。
每个人有速度vi，且每个人最多只能跑带着棒Ts，问最快时间接棒跑完L
贪心，最快的人跑最后Ts，倒数第二快的跑倒数第二Ts...
*/
TCO'10 Wildcard Round 500pt CalculationCards
/*
n<=50张卡 如3张：+1 ,-2 , *3 其排列有
0 + 1 - 2 * 3 = -5
0 + 1 * 3 - 2 = 1
0 - 2 + 1 * 3 = 1
0 - 2 * 3 + 1 = -5
0 * 3 + 1 - 2 = -1
0 * 3 - 2 + 1 = -1
期望为-1.6666666666666667
求给定的n张卡的期望值
看解题报告http://www.topcoder.com/wiki/display/tc/TCO'10+Wildcard+Round
以及bmerry代码的
不可能n!的枚举
设+、-卡共有s张
按照一个+、-卡后接连续的*卡分类，则有s部分，其全排列不影响期望（总共s!种，但期望都一样）
所以只考虑无序的（无序可以用默认的一种顺序，即卡出现的先后顺序，或者说编号）
***a1***a2*** ... as***
***表示*卡
由于是等概率的，所以总体来统计，每个+、-卡都会接同样的*卡，
既然每张+、-卡情况一样，那就考虑a1卡
其后会接0,1...,m张*卡
答案就是 sum * (0,1,...m)张*卡的期望 sum = ∑ai
求k张*卡的期望可以用dp做
看bmerry代码的做法，解题报告的麻烦一点吧
一开始只有s张a卡排着，然后插入一张张*卡
dp[i,j]表示插入了前面i张*卡，a1后接j张*卡，它们构成的期望值
分第i张卡插不插入到a1之后构成j张连续的*卡，概率为 该插入的位置/总位置
dp[i,j] =
dp[i-1,j] * (n-j-1)/n
+ m[i]*dp[i-1,j-1] * j/n
n为s+i
这道题一个很好的想法就是答案为sum * (0,1,...m)张*卡的期望 sum = ∑ai ！！！！！！
而求后接k张*卡的期望，bmerry的做法是一张一张卡插入，然后求得期望
小规模到大规模，通过考虑插入位置来实现，这个做法应该较好
*/
TCO 2010 Qualification Round 1 250pt
/*
题意：一个只有B,G组成的串，要将他们swap相邻的，变成BB...GG或GG...BB
求最少的次数 串长<=50
我用n^2的求逆序对，太慢了
看了别人的，直接就是累计将每个字母B移到左边的步数
if(row[i] == 'B')
{
tot += i - x;
x ++;
}
x是当前需要放B的位置，交换后就++移到下个位置
*/
TCO'10 Qualification Round 2 1000pt HandlesSpelling
/*
给出一个文本串，一些模式串
现要将模式串覆盖文本串，不能有重叠部分
求使得A^2 - B 最大
A是最长覆盖的长度，B是还未覆盖的个数
一开始一直关注A^2 - B ，不知怎么做
解题报告是分开来做
要求得A^2 - B的最大值，可以通过枚举A
枚举某一段作为最大覆盖值，然后看其左右未覆盖的个数
而计算为覆盖的个数可以通过dp了
dp[i,j]表示[i,j]为覆盖的个数
枚举[i,i']一段是被覆盖的，则答案就是min(dp[i'+1,j])
注意的是，初始化有些dp[i,j]=0，就直接continue
*/
SRM 216 Refactoring
/*
问一个数n<=2*10^9 可以拆分成多少种因子相乘的情况
24 = 2*2*2*3
= 2*2*6
= 2*3*4
= 2*12
= 3*8
= 4*6
不需要高深的数学知识！！！
暴力dfs做
f(n) = 1 + ∑f(n/i)
i 为其因子,i > 1 && i <= n/i（保证不会进入多余的分支）
为了保证无序，可以多加一个参数start，表示该轮的因子>=start
*/
SRM 223 PrimeAnagrams
/*
给出一个数字串len<=8
求将其分为三部分，每部分都是素数，且乘积最小
看解题报告的
8! = 40320 ，而分成3部分情况为C(7,2) = 21种
所以枚举全排列，然后分成3部分来做
Brute Force ！！！！！！
*/
zoj 3471 mask dp
/*
n<=10个球，i碰j会产生a[i,j]的能量，j同时会消失
问最多产生的能量之和
我知道跟mask有关，为啥还是想不出？
要从整体来看！！
现在有一些球，掩码为mask
假设最先碰撞的是u->v，然后v消失了
局面就变成了没有v的一些球了, mask^(1<<v)，一个子问题了
所以转移就是枚举u,v
dp[mask] = max(dp[mask^(1<<v)+a[u][v])
从局面来看吧！！！
一开始我是像zoj 3461 dp[mask] = dp[mask^i] + mst[i];
发现会出问题，这样子是隔离了一部分，但显然隔离了后会丢失了连接着两部分的那个值
*/
zoj 3470
/*
如图，问某个数字上下左右的数字是多少
既然题目给了一副对应的坐标，发现，问题的重点就在于点坐标跟数字的转换
我是先找出数字val在第n圈 即 (n-1)^2 < val <= n^2
然后该圈的起点start就是(n-1)^2 + 1 ， 然后通过比较start，就能求出坐标了
发现奇数圈会使minx--,miny-- ; 偶数圈会使maxx++,maxy++
数量关系是minx = miny = -(n-1)/2 , maxx = maxy = n/2
然后点(x,y)转化为值，跟上面类似的
求出第n圈 二分判断 minx<=x<=maxx , miny<=y<=maxy
然后求出角落的点等等...
*/
zoj 3468
/*
Dice游戏，一开始Attacker Defender各有骰子n,m个
双方拿出一定骰子来投，累计和
谁多点谁赢
Attacker拿出至少1个来攻击
问Attacker一次攻击赢的概率
骰子数目<=8
枚举Attacker投出的和为j，然后计算达到j的方法数，以及Defender投出的和小于j的方法数
用背包的方法计算方法数
*/
CF 60D
/*
n<=10^6个点，每个点有权值a[i]<=10^7 各不相同
若存在一个数x，使得a[i],a[j],x is a beautiful triple
即a^2 + b^2 = c^2 a,b,c互素
则i可以传播laugh到j
问最少需要需要让多少个顶点自行laugh，然后传播到全部的顶点
看了解题报告的
并查集做
但如何判断beautiful triple 两两判断O(n^2)会超时
有个性质：对于满足a^2 + b^2 = c^2的数，可用勾股数公式生成：
(x^2-y^2 , 2xy , x^2+y^2) x>y
该公式能生成所有的素勾股数（互质），需1奇1偶 ，且gcd(x,y) = 1
也能生出部分派生勾股数(如 6 8 10) ， 2奇或2偶
由于a[i]<=MAX MAX= 10^7
所以必有x^2-y^2 <= MAX , 2xy <= MAX 但x^2+y^2不一定<= MAX
2y^2<=MAX
x^2<=MAX+y^2<=3MAX/2
=> x<=sqrt(3MAX/2) , y <= sqrt(MAX/2)
所以枚举x,y复杂度为O(MAX)
(注意x,y是1奇1偶且gcd(x,y) = 1)
参考watashi代码写的
*/
CF60E
/*
一开始 n <= 10^6 个 Mushroom 按升序排成一条直线 ， 每个Mushroom重为a[i]
下一秒时，a[i] , a[i+1] 之间会出现一个a[i]+a[i+1]的Mushroom
而x秒时，某人重新排序这些Mushroom
问再经过y秒，所有Mushroom的重量之和
0 a1 a2 a3
1 a1 a1+a2 a2 a2+a3 a3
2 a1 2a1+a2 a1+a2 a1+2a2 a2 2a2+a3 a2+a3 a2+2a3 a3
3 ...
设时间i时重量为Ti 则Ti = 3Ti-1 - (a1+an)
所以前x可用矩阵乘法求出Tx
然后由于sort，最大的值是Fx-1*an-1 + Fx*an （找规律 Fx-1*ai-1 + Fx*ai , Fx*ai-1 + Fx-1*ai）
F是斐波那契数列 F[-1] = 0 , F[0] = 1
然后修改a1+an值即可，再次矩阵乘法 算出后来的y秒
*/
noip2002 G2 字串变换 双向BFS
/*
给出A,B串
以及一些变化方法，即x->y
求A变到B的最短步数
bfs慢点
双向会快点
由于x->y是单向的，所以两边的结构不同，优先扩展队列长度短的优化就有用了
注意反向BFS时扩展的顺序是y->x
*/
poj 2411
/*
问n*m的棋盘放置1*2的骨牌的方案数
n,m<=11
枚举行，递推计算列
dp[row,col,s] row行之前已经放好,且当前row行处于s状态
递推 通过在row行，col列之后放置，扩展计算
dp[row,col,s1] += dp[row-1,col,s2]
不是记忆化搜索 是从0递推
为了打表，在每个分支都计算了 即:dp[row][col][s1] += dp[row-1][col][s2];
否则，可以在最后的时候才计算的
*/
sgu 131
/*
n*m棋盘，问用1*2, 2*2去掉一个角的骨牌覆盖完的方案数
状态定义为 dp[row,s]表示当前第row行状态为s，且前row-1行已经覆盖完的方案数
则 dp[row,s] <-- dp[row-1,s']
转移是枚举row这一行每个位置（注意是整行）怎么放
同时，若枚举了row怎么放，则由状态的定义，row-1之前的必须覆盖完，就知道了s'是什么了！！！
每个位置有7种放法，除了被之前的方法限制了，就不足
*/
hdu 2640
/*
n*m的棋盘，有一些位置不能放，问最多能放多少个十字架
@
@@@
@
注意的是，每个@都需要放，所以棋盘相应的位置需要是空的
*/
xmu 1118
/*
求用1*1,1*2,1*3的砖块铺满 3*N的板的方案数目
1*3，最多影响3行 所以状态需要记录当前行以及前一行的情况 2bit 共4种
_ * _ *
_ _ * *
_表示空，*表示被覆盖
dp[row,s]表示row-1之前的已经覆盖完了，row-1,row的状态为s时的值
对row这一行的每个位置，枚举其放的方法
虽然说4种状态，实际上转移时很多是不需要的。因为为了满足row-1之前的是覆盖完的
不放，可以转移两种，即上面的1,2种类型
*/
hdu 2240
/*
给出如图n*5棋盘，其中第一块最多只能用c个，其余的不限
问能否铺满
跟sgu 131类似
不过这里dp的值是记录最少使用的1
b1,b2是之前的方法对当前的影响
*/
hdu 2606
/*
用1*1, 2*2, 3*3, 4*4覆盖完N*4的棋盘的方案总数
递推
dp[n] = dp[n-1] 最底部放4个1*1
+ 4*dp[n-2] 最底部组合出2*4的，总共有4种
+ 4*dp[n-3] 最底部组合出3*4的，总共有4种 2个是2块2*2上下交错 2个是一块3*3
+ 3*dp[n-4] 最底部组合出4*4的，总共有3种 2个是3块2*2上下交错 1个是一块4*4
+ 2*(dp[n-5]+dp[n-6]...+dp[0]) 用2*2上下交错放的
则dp[n-1] = ....
两式相减，得到dp[n] = 2dp[n-1] +3dp[n-2] - dp[n-4] - dp[n-5] n>=5
至于n<=4的，结合上面的dp[n]的式子计算
脑残了，wa了好几次
没想到可以2*2上下交错 脑残
*/
hnu 10816 ugly number
/*
题意：给出n个素数<=10000 n<=10
问[x,y]区间内只包含这些素数因子的数，要求全部打印出来
x,y<=2^31
一开始看到规模吓了一跳
事实上，只含有这些因子的数是很少的
注意不是倍数！！之前第一印象看成倍数，搞个容斥了，算了下2和3的，数据巨大....
像poj 的 ugly number那样子做
由于每个数都得乘以这些素数来扩展
用num[]数组存储生成的所有数
pos[i]表示素数pr[i]当前要乘以num[pos[i]]
初始num[0] = 1 pos[i] = 0
然后每一步扩展一个数，该数为num[tot] = min(num[pos[i]]*pr[i])
然后判断每个num[pos[i]]*pr[i] 是否 = num[tot]，是的话 pos[i]+1
这种思想还是没能很好掌握...
肯定的是，每个数都得乘以pr[1],pr[2]...
要用pos[i]记录当前pr[i]乘到哪个数了！！！
*/
08 ZhuHai Contest E Magic Squares 双向bf
/*
问一个排列变为3*3幻方的最小步数
每一步可以选择一个角进行旋转
状态数不多9!
先全排列得到目标状态
再双向bfs 挺快的
用康托展开（变进制）判重更快
*/
poj 3255 无向图值次短路 ★★★
/*
给出一个无向图 n<=5000, m <= 30000
求1到n的值次短的路，如果有多条最短路，但次短的还是需要大于最短的
允许点、边走多次
靠解题报告保养~~~ T_T
求1到其他点的最短路dist[] ，再求n到其他点的最短路rdist[]
枚举每条边，找到次短的 dist[u] + (u,v) + rdist[v]
启示: 枚举哪条边作为中间的必须经过的边u->v，然后连接1->u, v->n
*/
scu 3904
/*
一个序列seq[i] n<=10^5 -10000<=seq[i]<=10000
将其划分成几部分，使得每一部分之和>=0
求所有的划分方法数
显然dp[i] = ∑dp[j] (sum[i] - sum[j] >= 0)
O(n^2)会超时
用线段树加速
我一开始是以下标作为线段树的数轴，记录该段Min[p],Max[p],还有一个sDp[p]记录该段所有dp值
但这样比较慢，维护相对多了点
看了标程，是先计算所有的sum[]，然后离散化
以sum值作为数轴来搞，用树状数组就很容易写了
*/
中大第三本 ch2 负权数
/*
平时 N = anR^n + ... + a0R^0 其中R>0
负权数是R < 0,使用负权数表示的优点是对于负数，不用前置的符号
比如 -15 = 1*(-2)^5 + 1*(-2)^4 + 0*(-2)^3 + 0*(-2)^2 + 0*(-2)^1 + 1*(-2)^0
现给出N, -16<= R <=-2
求N的负权数R表示（题目的答案输出一行，表明表示是唯一的）
(无论正权、负权，系数ai都是 0<=ai<|R|)
因为取余运算只使用语正整数除法，所以不能通过连续连除求余的方法！！！！
写成普通形式时：
N >= 0
N = an|R|^n + ... + a0|R|^0 R < 0
i为奇数时:
ai|R|i = R(i+1) + (|R|-ai)Ri 为了保证a'>=0
i为偶数
ai|R|i = aiRi
所以先将N写成正权形式，然后再修改为负权的
同理
N < 0
N = -(an|R|^n + ... + a0|R|^0) R < 0
i为奇数时:
-ai|R|i = aiRi 为了保证a'>=0
i为偶数
-ai|R|i = R(i+1) + (|R|-ai)Ri
最后对a'[]进行修正，使得0 <= a'i < |R|
感觉挺不错的一道题，通过对正权的形式，修正为负权的
*/