海清's profileCockhorse BlogPhotosBlogListsMore  |  Tools Help |
|
August 27 00-07冬令营论文索引也许复习可以用到
---------------------------------------------------------------------------------------- 2000 陈彧 信息学竞赛中的思维方法 方奇 动态规划 高寒蕊 递推关系的建立及在信息学竞赛中的应用 郭一 数学模型及其在信息学竞赛中的应用 江鹏 探索构造法解题模式 李刚 动态规划的深入讨论 龙翀 解决空间规模问题的几种常用的存储结构 骆骥 数学模型的建立和选择 施遥 人工智能在围棋程序中的应用 肖洲 数据结构的在程序设计中的应用 谢婧 规模化问题的解题策略 徐串 论程序的调试技巧 徐静 图论模型的建立与转化 杨江明 论数学策略在信息学问题中的应用 杨培 非最优化算法初探 张辰 动态规划的特点及其应用 张力 类比思想在解题中的应用 张一飞 冗繁削尽留清瘦——浅谈信息的充分利用 ---------------------------------------------------------------------------------------- 2001 符文杰 Pólya原理及其应用 高寒蕊 从圆桌问题谈数据结构的综合运用 高岳 中等硬度解题报告 江鹏 从一道题目的解法试谈网络流的构造与算法 李益明 计算几何 李源 树的枚举 刘汝佳 搬运工问题的启示 骆骥 由“汽车问题”浅谈深度搜索的一个方面———搜索对象与策略的重要性 毛子青 动态规划算法的优化技巧 俞玮 基本动态规划问题的扩展 张一飞 求N!的高精度算法 ---------------------------------------------------------------------------------------- 2002 戴德承 退一步海阔天空——“目标转化思想”的若干应用 方奇 浅谈必要条件的应用 符文杰 排序网络 何江舟 用高斯消元法解线性方程组 何林 猜想及其应用 黄芸 POI0110 跳舞蝇 金恺 浅谈网络流算法的应用 李澎煦 半平面交的算法及其应用 李睿 二分法与统计问题 骆骥 浅析解 “对策问题” 的两种思路 孙方成 偶图的算法及应用 孙林春 让我们做得更好——从《parity》的解法谈程序优化 王知昆 搜索顺序的选择 许智磊 二分，再二分！――从Mobiles(IOI 2001)一题看多重二分 杨旻旻 构造法——解题的最短路径 俞玮 Ulam的游戏和编码 张家琳 多项式乘法 张宁 遗传算法的特点及其应用 张一飞 由感性认识到理性认识——透析一类搏弈游戏的解答过程 周文超 树结构在程序设计中的运用 ---------------------------------------------------------------------------------------- 2003 方奇 染色法和构造法在棋盘上的应用 高正宇 答案只有一个——浅谈问答式交互问题 何林 一类称球问题的解法 侯启明 信息论在信息学竞赛中的简单应用 姜尚仆 模线性方程的应用——用数论方法解决整数问题 金恺 探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起 雷环中 结果提交类问题 林希德 求最大重复子串 刘才良 平面图在信息学中的应用 刘一鸣 一类搜索问题的优化思想——数据的有序化 陆可昱 长方体的体积并 饶向荣 病毒的DNA———剖析一道字符匹配问题解析过程 邵烜程 数学思想助你一臂之力 王知昆 浅谈用极大化思想解决最大子矩形问题 伍昱 由对称性解2-SAT问题 项荣璟 充分利用问题性质——例析动态规划的“个性化”优化 许智磊 浅谈补集转化思想在统计问题中的应用 张宁 猜数问题的研究——《聪明的学生》一题的推广 张云亮 论对算法的选择 周源 浅析“最小表示法”思想在字符串循环同构问题中的应用 ---------------------------------------------------------------------------------------- 2004 贝小辉 浅析树的划分问题 鬲融 浅谈特殊穷举思想的应用 韩文韬 论C++语言在信息学竞赛中的应用 何林 信息学中守恒法的应用 胡伟栋 减少冗余与算法优化 黄源河 浅谈图论模型的建立与应用 金恺 极限法——解决几何最优化问题的捷径 李锐喆 细节——不可忽视的要素 栗师 转化目标在解题中的应用 林涛 线段树的应用 楼天城 匹配算法在搜索问题中的应用 汪汀 最小生成树问题的拓展 吴景岳 最小生成树算法及其应用 肖天 “分层图思想”及其在信息学竞赛中的应用 许智磊 后缀数组 薛矛 解决动态统计问题的两把利刃 ——剖析线段树与矩形切割 杨思雨 伸展树的基本操作与应用 周源 浅谈数形结合思想在信息学竞赛中的应用 朱晨光 优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化 朱泽园 多串匹配算法及其启示 ---------------------------------------------------------------------------------------- 2005 何林 数据关系的简化 胡伟栋 浅析非完美算法在信息学竞赛中的应用 黄刚 数据结构的联合 黄源河 左偏树的特点及其应用 蒋炎岩 数据结构的联合——块状链表 金恺 杂题大拼盘 李羽修 Hash函数的设计优化 栗师 树的乐园——一些与树有关的题目 龙凡 序的应用 潘震皓 置换群快速幂运算 研究与探讨 钱自强 遗传算法应用的分析与研究 任恺 图论的基本思想及方法 唐文斌 正难则反–浅谈逆向思维在解题中的应用 汪汀 参数搜索的应用 王俊 浅析二分图匹配在信息学竞赛中的应用 吴景岳 解法讨论 杨俊 二分策略在信息学竞赛中的应用 杨思雨 美，无处不在——浅谈“黄金分割”和信息学的联系 杨弋 从《小H的小屋》的解法谈算法的优化 张伟达 用改进算法的思想解决规模维数增大的问题 周源 压去冗余 缩得精华——浅谈信息学竞赛中的“压缩法 朱晨光 浅析倍增思想在信息学竞赛中的应用 朱泽园 回到起点——一种突破性思维 ---------------------------------------------------------------------------------------- 2006 陈启峰 一张一弛，解题之道——“约制、放宽”方法在解题中的应用 陈首元 维护森林连通性——动态树 冯威 数与图的完美结合-------浅析差分约束系统 高逸涵 对于一道题目的深入分析--对猴子分桃问题的延伸 黄劲松 贪婪的动态规划——浅谈贪心思想在动态规划中的应用 黄晓愉 信息学竞赛中搜索问题的常见优化技巧 贾由 由图论问题浅析算法优化 李天翼 从特殊情况考虑 龙凡 一类猜数问题的研究 汤泽 从一类单调性问题看算法的优化 唐文斌 浅谈“调整”思想在信息学竞赛中的应用 汪晔 信息学中的参考系与坐标系 王栋 浅析平面Voronoi图的构造及应用 王赟 Trie图的构建、活用与改进 余远铭 最短路算法及其应用 俞鑫 棋盘中的棋盘——浅谈棋盘的分割思想 周戈林 浅谈类比思想 周以苏 论反汇编在时间常数优化中的应用 朱晨光 基本数据结构在信息学竞赛中的应用 朱泽园 半平面交的新算法及其实用价值 ---------------------------------------------------------------------------------------- 2007 高逸涵 与圆有关的离散化 王晓珂 解析一类组合游戏 仇荣琦 欧拉回路性质与应用探究 余江伟 如何解决动态统计问题 杨 沐 浅析信息学中的“分”与“合” 李宇骞 浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用 袁昕颢 动态树及其应用 杨 哲 凸完全单调性的加强与应用 王欣上 浅谈基于分层思想的网络流算法 陈启峰 Size Balanced Tree 杨 弋 Hash在信息学竞赛中的一类应用 古 楠 平面嵌入 郭华阳 RMQ与LCA问题 刘雨辰 对拟阵的初步研究 陈 雪 问题中的变与不变 何 森 浅谈数据的合理组织 胡伯涛 最小割模型在信息学竞赛中的应用 陈瑜希 多角度思考创造性思维——运用树型动态规划解题的思路和方法探析 周 冬 生成树的计数及其应用 刘家骅 浅谈随机化在信息学竞赛中的应用 ---------------------------------------------------------------------------------------- P1160坦克大战这道题真是做郁闷了，一道平衡树的题，我写了Splay、Treap、至顶向下伸展树、线段树但是都过不到，caesius还写了SBT他也没过，也不知道为什么，没办法vijos又不能给数据，这道题数据太大又不可能把它骗出来，或许是我们的RP还不够吧。 P1083一道很经典的线段树的题。 August 26 递推式的矩阵运算形如f[n]=x1*f[n-1]+x2*f[n-2]+....+xk*f[n-k](xi为实数)的递推式 用一个k*1的矩阵表示相邻的k个数 可以通过 x1,x2,x3,...,xk-1,xk f[n-1] f[n] 来计算f[n] 1 ,0 ,0 ,..., 0 ,0 f[n-2] f[n-1] 0 ,1 ,0 ,..., 0 ,0 f[n-3] f[n-2] ... × .. ＝ .. ... .. .. 0 ,0 ,0 ,..., 1 ,0 f[n-k] f[n-(k-1)] (k*k的矩阵) (k*1的矩阵) 当然这样计算看起来很复杂，其实矩阵的优点就在于它可以二分计算 由于矩阵运算遵循结合律，所以可以先把k*k的矩阵自乘若干次后再和前k个数组成的k*1的矩阵相乘，则可得到f[n]，算一个矩阵的n次幂可通过二分快速幂的方法求解，这样的话时间复杂度就只有O(k^2logn)。 August 22 LIS的O(nlogn)算法var a:array[1..10000]of longint; w,i,j,k,n:longint; function find(c,d,x:longint):longint; begin if c>d then exit(c); if c=d then if x>a[c] then exit(c+1) else exit(c); if x>a[(c+d)div 2] then exit(find((c+d)div 2+1,d,x)) else exit(find(c,(c+d)div 2,x)); end;{二分查找} begin readln(n); for i:=1 to n do begin read(k); j:=find(1,w,k); if j>w then inc(w); a[j]:=k; end; writeln(w); end. 线段树、Splay、Treep的时间比较Problem : inverse
逆序对 问题描述
在一个排列中，前面出现的某个数比它后面的某个数大，即当Ai>Aj且i<j时，则我们称Ai和Aj为一个逆序对。给出一个1到N的排列，编程求出逆序对的个数。 输入格式
第一行输入一个正整数N； 第二行有N个用空格隔开的正整数，这是一个1到N的排列。 输出格式
输出输入数据中逆序对的个数。 样例输入
4 3 1 4 2 样例输出
3 样例说明
在输入数据中，(3,1)、(3,2)和(4,2)是仅有的三个逆序对。 数据规模
对于30%的数据，N<=1000； 对于100%的数据，N<=100 000。 测了10个数据，还是线段树最快：
代码：
线段树：
var
f:array[1..200000]of longint; a:array[1..100000]of longint; i,n,o:longint; mo:int64; procedure go(x,i,c,d:longint); begin if c<d then if x<=(c+d) div 2 then go(x,i*2,c,(c+d)div 2) else begin inc(mo,f[i*2]); go(x,i*2+1,(c+d)div 2+1,d); end; inc(f[i]); end; begin readln(n); for i:=1 to n do read(a[i]); fillchar(f,sizeof(f),0); o:=1; while o<n do o:=o*2; mo:=0; for i:=n downto 1 do go(a[i],1,1,o); writeln(mo); end. Treap:
type
tree=^rec; rec=record left,right:tree; x,ld,rd:longint; e:double; end; var h:tree; i,j,k,l,n,m:longint; o:int64; function left(var p:tree):tree; var t:tree; begin t:=p^.left;p^.left:=t^.right;t^.right:=p; inc(t^.rd,p^.rd+1); dec(p^.ld,t^.ld+1); exit(t); end; function right(var p:tree):tree; var t:tree; begin t:=p^.right;p^.right:=t^.left;t^.left:=p; inc(t^.ld,p^.ld+1); dec(p^.rd,t^.rd+1); exit(t); end; function insert(x:longint;var p:tree):tree; begin if p=nil then begin new(p); p^.x:=x;p^.e:=random;p^.ld:=0;p^.rd:=0;p^.left:=nil;p^.right:=nil; exit(p); end; if x<p^.x then begin inc(o,p^.rd+1); p^.left:=insert(x,p^.left); inc(p^.ld); if p^.left^.e<p^.e then p:=left(p); end else begin p^.right:=insert(x,p^.right); inc(p^.rd); if p^.right^.e<p^.e then p:=right(p); end; exit(p); end; begin randomize; readln(n); o:=0; for i:=1 to n do begin read(k); h:=insert(k,h); end; writeln(o); end. Splay:
type
tree=^rec; rec=record ld,rd,x:longint; left,right:tree; end; var h:tree; n,i,k:longint; o:int64; function left(a:tree):tree; var b:tree; begin b:=a^.left;a^.left:=b^.right;b^.right:=a; inc(b^.rd,a^.rd+1); dec(a^.ld,b^.ld+1); exit(b); end; function right(a:tree):tree; var b:tree; begin b:=a^.right;a^.right:=b^.left;b^.left:=a; inc(b^.ld,a^.ld+1); dec(a^.rd,b^.rd+1); exit(b); end; function leftleft(a:tree):tree; var b,c:tree; begin b:=a^.left;a^.left:=b^.right;b^.right:=a; c:=b^.left;b^.left:=c^.right;c^.right:=b; inc(b^.rd,a^.rd+1); inc(c^.rd,b^.rd+1); dec(a^.ld,b^.ld+1); dec(b^.ld,c^.ld+1); exit(c); end; function rightright(a:tree):tree; var b,c:tree; begin b:=a^.right;a^.right:=b^.left;b^.left:=a; c:=b^.right;b^.right:=c^.left;c^.left:=b; inc(b^.ld,a^.ld+1); inc(c^.ld,b^.ld+1); dec(a^.rd,b^.rd+1); dec(b^.rd,c^.rd+1); exit(c); end; function leftright(a:tree):tree; var b,c:tree; begin b:=a^.left;c:=b^.right; a^.left:=c^.right;c^.right:=a; b^.right:=c^.left;c^.left:=b; a^.ld:=c^.rd; b^.rd:=c^.ld; inc(c^.rd,a^.rd+1); inc(c^.ld,b^.ld+1); exit(c); end; function rightleft(a:tree):tree; var b,c:tree; begin b:=a^.right;c:=b^.left; a^.right:=c^.left;c^.left:=a; b^.left:=c^.right;c^.right:=b; a^.rd:=c^.ld; b^.ld:=c^.rd; inc(c^.ld,a^.ld+1); inc(c^.rd,b^.rd+1); exit(c); end; function insert(x:longint;var p:tree):tree; begin if p=nil then begin new(p); p^.x:=x;p^.ld:=0;p^.rd:=0;p^.left:=nil;p^.right:=nil; exit(p); end; if x<p^.x then begin inc(o,p^.rd+1); inc(p^.ld); p^.left:=insert(x,p^.left); if p^.left^.x=x then begin if p=h then p:=left(p); end else if x<p^.left^.x then p:=leftleft(p) else p:=leftright(p); end else begin inc(p^.rd); p^.right:=insert(x,p^.right); if p^.right^.x=x then begin if p=h then p:=right(p); end else if x>p^.right^.x then p:=rightright(p) else p:=rightleft(p); end; exit(p); end; begin readln(n); for i:=1 to n do begin read(k); h:=insert(k,h); end; writeln(o); end. 至顶向下伸展树:
type tree=^rec; rec=record father,left,right:tree; ld,rd,x:longint; end; var h:tree; i,j,k,l,n,m:longint; o:int64; function left(var p:tree):tree; var t:tree; begin t:=p^.left;p^.left:=t^.right;t^.right:=p; inc(t^.rd,p^.rd+1); dec(p^.ld,t^.ld+1); exit(t); end; function right(var p:tree):tree; var t:tree; begin t:=p^.right;p^.right:=t^.left;t^.left:=p; inc(t^.ld,p^.ld+1); dec(p^.rd,t^.rd+1); exit(t); end; function insert(x:longint;var p:tree):tree; begin if p=nil then begin new(p); p^.x:=x;p^.left:=nil;p^.right:=nil;p^.ld:=0;p^.rd:=0; exit(p); end; if x<p^.x then begin inc(o,p^.rd+1); inc(p^.ld); p^.left:=insert(x,p^.left); end else begin inc(p^.rd); p^.right:=insert(x,p^.right); end; exit(p); end; function splay(x:longint;t:tree):tree; var p,head,leftmax,rightmin:tree; begin new(head); leftmax:=nil;rightmin:=nil; while x<>t^.x do if x<t^.x then begin if x<t^.left^.x then t:=left(t); if rightmin<>nil then rightmin^.left:=t else head^.right:=t; t^.father:=rightmin; rightmin:=t; t:=t^.left; end else begin if x>t^.right^.x then t:=right(t); if leftmax<>nil then leftmax^.right:=t else head^.left:=t; t^.father:=leftmax; leftmax:=t; t:=t^.right; end; if rightmin<>nil then begin rightmin^.left:=t^.right; p:=rightmin; while p<>nil do begin if p^.left<>nil then p^.ld:=p^.left^.rd+p^.left^.ld+1 else p^.ld:=0; p:=p^.father; end; t^.right:=head^.right; inc(t^.rd,head^.right^.ld+head^.right^.rd+1); end; if leftmax<>nil then begin leftmax^.right:=t^.left; p:=leftmax; while p<>nil do begin if p^.right<>nil then p^.rd:=p^.right^.ld+p^.right^.rd+1 else p^.rd:=0; p:=p^.father; end; t^.left:=head^.left; inc(t^.ld,head^.left^.ld+head^.left^.rd+1); end; exit(t); end; begin readln(n); for i:=1 to n do begin read(k); h:=insert(k,h); h:=splay(k,h); end; writeln(o); end. 高精乘法万进制var a,b,c:array[1..20000]of longint; k,i,j,k1,k2,l,p,o:longint; m:array[1..4]of longint; s1,s2:ansistring; begin readln(s1); readln(s2); l:=0;i:=length(s1);k1:=0; while i>0 do begin inc(l); if (l=4)or(i=1) then begin inc(k1);a[k1]:=0; for j:=i to i+l-1 do a[k1]:=a[k1]*10+ord(s1[j])-48; l:=0; end; dec(i); end; l:=0;i:=length(s2);;k2:=0; while i>0 do begin inc(l); if (l=4)or(i=1) then begin inc(k2);b[k2]:=0; for j:=i to i+l-1 do b[k2]:=b[k2]*10+ord(s2[j])-48; l:=0; end; dec(i); end; a[k1+1]:=0;b[k2+1]:=0; for i:=1 to k1+1 do begin p:=0; for j:=1 to k2+1 do begin o:=a[i]*b[j]+c[i+j-1]+p; p:=o div 10000; c[i+j-1]:=o mod 10000; end; end; l:=k1+k2; if c[l]=0 then dec(l); for i:=l downto 1 do begin fillchar(m,sizeof(m),0); k:=c[i];j:=0; while k<>0 do begin inc(j); m[j]:=k mod 10; k:=k div 10; end; if i<>l then for k:=4 downto 1 do write(m[k]) else for k:=j downto 1 do write(m[k]); end; writeln; end. LCIS(最长公共上升子序列)的O(nm)算法 (转)(转至 matrix67.com)
这里要说的这个算法利用了nlogn的最长上升子序列(LIS)的技巧：用f[k]表示长度为k的上升子序列最后一个数最小是多少。 在最长公共上升子序列中，令f[i,j][k]表示A串前i个数字，B串前j个数字，长度为k的公共上升子序列中，最后一个数最小是多少。 当A[i]=B[j]时，像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中，这需要线性的时间扫一遍f[i,j]； 当A[i]<>B[j]时，我们需要合并f[i-1,j]和f[i,j-1]，使得对于每个k满足f[i,j][k]:=min{ f[i-1,j][k],f[i,j-1][k] }。这需要线性的时间扫一边f[i-1,j]和f[i,j-1]并取k相同时的较小值。 最后输出f[n,m]的长度（使f[n,m][k]有意义的最大的k）。 这样的复杂度是三方的，我们需要优化。 考虑A[i]=B[j]的情况。当i固定时，随着j的增加，插入的位置一定也在后移，因为同样是插入的A[i]，但j的增加（B串长度的增加）使得f [i,j]更优，因此可以更新的值就更靠后。于是，对于每个i，我们可以按照k的顺序扫描f[i-1,j][k] 并在A[i]可以插入f[i-1][j]的k位置时增加j，从而预处理所有A[i]=B[j]时A[i]应该插入的位置。 再考虑A[i]<>B[j]的情况。从定义看，f[i-1,j-1]和f[i-1,j]只有一个地方不一样，因为多一个数最多只能造成一个k 的值变小；同样地，f[i-1,j-1]和f[i,j-1]也只有一个地方不一样。因此，f[i-1,j]和f[i,j-1]最多只有两个k所对应的值不相同，且当有两个不同的值时，总是f[i-1,j]中的某个值较小，f[i,j-1]中的某个值较小。这给我们优化的余地。在每次处理完f[i,j]时，我们可以记录一个值x[i,j]表示f[i,j][k]与f[i-1,j][k]中值不一样的k是多少，在A[i]=B[j]时直接赋值为插入的位置，在 A[i]<>B[j]时待后文说明。以后合并时，先让f[i,j]:=f[i-1,j]（由于此时的f[i-1,j]已经没有别的用处了，因此可以用滚动数组记录，直接令f[i-1,j]是f[i,j]，避免实际的赋值操作），然后将新的f[i,j]中的，使f[i,j-1][k]比f[i- 1, j][k]小的k所对应值更新。这个k是多少呢？显然应该是x[i,j-1]。这样的操作同时可以确定x[i,j]=x[i,j-1]。 这样，复杂度就达到了平方。 次小生成树O(n^2)算法(vijos p1070) var {深搜过程} {主过程} 高一寒假选拔赛前的学习内容(也可以当今后复习的目录) 信息学与计算机语言的发展（香农与信息论，图灵与图灵机，冯·诺伊曼与逻辑门，机器码，汇编语言，高级语言，面向对象的语言，开源化与多平台） 字符串的一种HASH据说是一个字符串HASH很好的方法。
function ELFHash(var s:String):Integer; var g,h,i:LongWord; {32位} begin h:=0; for i:=1 to Length(s) do begin h:=h shl 4 + Ord(s[i]); g:=h and $f0000000; {表示16进制(二进制为11110000000000000000000000000000)} if g<>0 then h:=h xor (g shr 24); h:=h and (not g); end; ELFHash:=h mod M; end; August 19 线段树＋离散化平衡树可以做的事情其实线段数也可以做。 用线段数，查第k大、插入元素、删除元素也都是O(logn)，但是由于它开的空间太大，一般情况下数组要开到2^k,刚好2^(k-1)大于最大的那个数max的时候。不过这样的话有很多的空间都浪费了，所以空间太大的话就不得不用平衡树了。 其实在处理数据之前可以把数据离散化，先排个序，用一个数组记录它们是第几大，这样就把非常大的数压缩得很小，线段数中叶子节点记录的就是压缩后的数据而不是原数，这样的化2^k只跟n有关，而和那个max无关。当然,如果是处理过程和数据的插入是一起进行的话，就先把处理过程记录下来。所以，这种算法的缺点是不能进行在线算法。不过线段数的代码比所有的平衡树都要简洁些（至少我是这么觉得的），所以线段数＋离散化还是比平衡树更科学。 n个数最大公约数和最小公倍数var function gcd(a,b:longint):longint;{两个数的最大公约数} function gcdn(n:longint):longint;{n个数的最大公约数} function lcm(a,b:longint):longint;{两个数的最小公倍数} function lcmn(n:longint):longint;{n个数的最小公倍数} begin 最优代价子母树的四边形优化var
August 18 石子合并除四边形不等式的另一个优化 石子合并的普通算法是做n次O(n^3)的DP，当然加上四边形不等式的优化总复杂度就是O(n^3)。 其实，没有必要做n次DP(做n次的原因是石子是围成一个圈的，要枚举哪个是开头)。为了一次DP就实现所有的石子的相邻性，我们做如下处理： a[1],a[2],a[3]...a[n],a[1],a[2]...a[n-1] 也就是： a[1],a[2],a[3]...a[n],a[n+1],a[n+2]...a[2n-1] 这样的话就只用做一次DP就行了，最后答案为max{f[i,i+n-1]|1<=i<=n}。所以石子合并加上这个优化和四边形不等式的优化后就可以优化到O(n^2)了。 p1194一道矩阵运算的经典题目,题解转至 matrix67.com
用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果  我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。 August 16 KMvar x,y:array[1..100]of boolean; d,lx,ly:array[1..100]of longint; a:array[1..100,1..100]of longint; i,j,k,n,m,o:longint; function find(t:longint):boolean;{寻找是否有增广路} var i:longint; begin x[t]:=true;{x顶点已找过，若无增广链则为待改d值的交错树} for i:=1 to n do if (not y[i])and(lx[t]+ly[i]=a[t,i]) then{lx,ly为顶标值，相加为w即为可连等边} begin y[i]:=true;{y顶点已找过} if (d[i]=0)or(find(d[i])) then begin d[i]:=t; exit(true); end; end; exit(false); end; begin readln(n); for i:=1 to n do for j:=1 to n do begin read(a[i,j]); if a[i,j]>lx[i] then lx[i]:=a[i,j]; end;{初始化，顶标取最大} for k:=1 to n do repeat fillchar(x,sizeof(x),0); fillchar(y,sizeof(y),0);{每次repeat清空已找过的点} if find(k) then break;{若有匹配则break并找下一x点的匹配} o:=maxlongint;{o的初始值} for i:=1 to n do if x[i] then for j:=1 to n do if (not y[j])and(lx[i]+ly[j]-a[i,j]<o) then o:=lx[i]+ly[j]-a[i,j];{寻找并改o值} for i:=1 to n do begin if x[i] then dec(lx[i],o);{x顶点减o} if y[i] then inc(ly[i],o);{y顶点加o} end; until false; o:=0; for i:=1 to n do inc(o,a[d[i],i]);{所有节点的顶标之和即为答案} writeln(o); end. August 03 07七月1.文科 2.佛祖 3.短信 4.作文 5.150 6.真心话 7.A选项 8.松子生日 9.唱歌 10.网络 11.拥抱 12.图与树 13.豪儿 14.梦 15.队列优化 16.海 17.科技馆 18.想念 19.见面 20.离开 21.睡不着 22.24 23.邮件 24.哥哥 25.电话 26.SPFA 27.IP卡 28.eat me 29.photos 30.主动 31.永恒 这个月发生了很多很奇妙的事情. |
|
|
