Home > OI > 省赛备战实录

省赛备战实录


2010.06.10

ditch

usaco 原题 4.2.1

裸网络流

用以练习sap算法

sort

NOI 1997 day 1 第一题

模拟 快速排序

transform

NOI 2009 day 1 第一题

二分图匹配

倒序匹配or调整匹配or贪心

2010.06.11

travel

NOI 1997 day 1 第二题

广度优先搜索

tour

NOI 1997 day 2 第一题

贪心+DP

贪心得纵向最大值,转化为经典的最大连续子段和问题

数据有错:第8个点骗分 m=20 n=5001 输出449324

3378

POJ 3378 Crazy Thairs

离散化+树状数组

首先要离散化数据,因为后面要用具体数据值作为数组下标

树状数组支持两种操作,修改元素值和访问元素和(lgn)

思路:

可参考树状数组求逆序对的方法

首先求长度为2的

首先将树状数组data[]清零

每读入一个a[i] 对data进行下标为a[i]的加1修改操作

然后求和b[i]=sum(a[i]-1)

b[i]就是以i结尾的长度为2的有序对

然后长度为3的

改为“对data进行下标为a[i]的加b[i]的修改操作”

……

2010.06.12

cover

NOI 1997 day 2 第三题

立方体切割

分x轴方向、y轴方向、z轴方向进行切割

删除立方体时要注意,易错

参见国家队论文 2004 薛矛

3368

POJ 3368 Frequent values

RMQ问题

首先模型转换(参见cai0715解题表格):

先对数列进行变换,变换后数列中的A[I]代表与其相同的左面的节点

数,例如,( -1 -1 1 1 1 1 3 10 10 10)==>(1 2 1 2 3 4 1 1 2 3),然后定义Sum[I]

代表与它相同的总共有多少个,即(2 2 4 4 4 4 1 3 3 3)。然后,我们对A 数

组进行RMQ 预处理。对于每一个询问,Ans=Max{该区间最左面相同的数的

个数,该区间最右面相同的数的个数,该区间中间相同的数的个

数}=Max{ Sum[L]-A[L]+1 , A[R] , Rmq[中间区间]}

1147

Ural 1147 Shaping Regions

切割矩形 cover的平面简化版,用以温习矩形切割

2010.06.13

1195

poj 1195&IOI 2001 Mobile Phones

二维树状数组

2104

poj 2104

归并树 将归并排序的每一层的结果存起来,具有线段树的结构。二分答案,依据是将区间映射到相应线段,二分得到相应的小于或等于k的个数的和。由于将区间映射到相应线段的复杂度也是logn。这一部分复杂度是mlognlognlogn。

2010.06.14

1330

poj 1330 Nearest Common Ancestors

朴素Tarjan算法

726

SPOJ 726

平衡树(SBT),未AC 与标程对拍无数组数据无错 问题未知

2010.06.15

177

sgu 177

矩形切割

1149

poj 1149

网络流。若某个顾客第一次拥有某个猪圈的钥匙,则从源点到这个顾客连一条权值为猪圈容量的边(注意,从源点到某顾客可能不止有一条边!);若不是第一次,则从前一个拥有该猪圈钥匙的顾客向该顾客连一条权值为正无穷大的边。对于每个顾客,向汇点连一条权值为其需求的边。最大流即为答案

1459

poj 1459

网络流,构图较易想到。若是发电站,则从源点向该顶点连一条权值为发电量的边;若是用电点,则从该顶点向汇点连一条权值为耗电量的边。最大流即为答案。

3281

Poj 3281

网络流。将牛、食物、饮料均视为点,每个点拆为两个,如食物i,i和i’之间连一条权值为1的边,每个牛对应的食物i’、饮料j之间连权值为1的边,源点和食物i连权值为1的边,饮料j’和汇点连权值为1的边。求最大流即为答案。

1698

Poj 1698

网络流。源点到每个film连一条权值为所需天数的边,每个film向限制星期内每个可以出演的日期连一条权值为1的边,每个日期向汇点连一条权值为1的边。若最大流等于总天数则Yes。

2010.06.16

1005

poj 1005

水题 模拟即可

2112

poj 2112

最短路/二分/网络流

先求最短路。二分答案后用网络流,源点向牛连容量为1的边,机器向汇点连容量为1的边,若牛和机器之间的距离不超过所二分的答案,则在它们之间连一条容量为1的边,若最大流为N说明当前可行,缩小答案,否则增大。

2010.06.17

1038

poj 1038

参见鱼牛的状态压缩DP。

2010.06.18

1112

poj 1112

图论、DP

难于构图,若某两个点间只有一条有向边则连一条无向边,则得到一个无向图,进行01染色,任意一个联通分量中统计不同色的个数,若存在某两个顶点同色而连了边则无解,否则可用背包得出答案。

1692

poj 1692

设f(i,j)为a数组前i个点和b数组前j个点互相匹配的最大值,若a[i]=b[j]显然不可能,否则f(i,j)=max(f(i-1,j),f(i,j-1),f(mb(i,j)-1,ma(i,j)-1)),其中mb(i,j)代表b的第j个同a的第i个相匹配最靠后的一个位置

2010.06.19

1946

poj 1946 Cow Cycling

DP

设f[i][j][k]代表现在是第i头牛领跑,已经跑到第j圈,第i头牛所用掉的能量为k所能得到的最小时间,容易得到f[i][j][k]=min(f[i-1][j][x],f[i][j-p][k-p*p]+1),即第i头牛不领跑,而第i-1头牛耗体力x,或第i头牛在一分钟内领跑p圈,时间+1

注意几个边界:由于其它牛在不领跑时也会耗费能量,若搜索到一个j>k的状态,则为不合法的。一开始f[1][0][i]=0对所有0<=i<=E,最后答案为min{f[N][D][i]}

1947

有点难想的树形DP,设f[x][k]代表以x为根恰保留有k个结点的子树需删除的最少边数,显然有f[x][1]=son[x],即与x相连结点数量。进一步可得到f[x][k]=min{f[x][k-j]+f[son of x][j]-2},最后减2是因为分别考虑x和它的儿子结点时,都把它们之间的边删掉了,所以这里要补回来。

2010.06.20

1015

poj 1015 Jury Compromise

DP。设f[x][y][z]代表在前x个jury members里面选y个,D和P的差为z时能达到的最大的D+P的值。需注意的是不能简单地将z设为|d[i]-p[i]|,正负要分别考虑,所以这里要将z加上一个常数使所有数组下表都大于0,状态转移很好写,类似背包,这里就略去了。

1442

poj 1442 Black Box

数据结构 平衡树

题目要求支持两种操作:加入和查找第k小,我选择SBT来实现,具体略。

1636

poj 1636 Prison rearrangement

背包DP/二分图染色

首先对二分图进行01染色,统计各连通块两边的点的数量,同一连通块中的点必同时交换。最后用背包判断每一状态是否可达。

2892

poj 2892 Tunnel Warfare

数据结构 平衡树

维护一个SBT,采取与题目叙述中相反的操作,若炸毁村庄,则加入结点,修复村庄则删除结点。若查询某节点i,则找到最靠近i的左边一个结点t1和最靠近的右边一个结点t2,答案即为t2-t1-1。为避免边界情况,可加上两个虚拟的被炸毁的村庄0和n+1。最后要注意阴人的数据,可能会多次炸毁或修复某村庄,开一个数据记录即可。

3481

poj 3481

数据结构 平衡树/大根小根堆

由于之前有现成的SBT代码,所以就偷懒继续用它了。也可以维护一个大根堆和一个小根堆,若取最大则删去大根堆堆顶元素,同时标记相应id为false,以后若取小根堆则先弹出堆顶所有id为false的元素;反之亦然。

2010.06.21

176

Sgu 176

有上下界的网络流 未AC 原因未知

arctan

NOI 2001 反正切函数的应用

数学 枚举优化

首先得出一个c关于a和b的公式,然后将b+c化为a和b的关系式,利用不等式可得到a<b<=2*a+1,且b+c是关于b的单调递减函数,故只需倒序枚举,找到第一个可行解就输出即可。

eat

NOI 2001 食物链

并查集 路径压缩

建立一个并查集,对关系进行编码(即除了记录father[x]之外还记录一个key[x]),0代表同类,1代表根节点是x的食物,2代表根节点是x的天敌,每次路径压缩时对key值做模3的加法即可。

equation

NOI 2001 方程的解数

很恶心的一道题。先搜索方程左边,hash记录所得到的值及其相应的数量,再hash右边相应的值并做统计。用线性探查法解决冲突。

frog

NOI 2000 青蛙过河

慢慢推,最后可得到结果为f[i][j]=2^i*(j+1)。其中i为桥墩数,j为荷叶数。

2010.06.22

1088

poj 1088 滑雪

经典的DP,充分显示记忆化搜索的威力。f[i][j]记录格子(i,j)开始的最长长度,其周围四个格子中,若某格子的高度小于当前格子高度,则dfs该格,若均小于周围格子则定长度为1。

即f[i][j]=max{f[x][y]+1},(x,y)与(i,j)相邻且h(x,y)<h(i,j)。

2068

poj 2068 Nim

博弈 DP

设f[i][j]为轮到第i个人,还剩j个石子,是否有必胜策略,转移很好写,此处省略。

2960

poj 2960 S-Nim

博弈 SG函数

弄懂SG函数的含义就很容易做了,具体用记忆化搜索来实现。

2975

poj 2975 Nim

博弈 经典Nim取子游戏

先对每一块石子异或,存为x值,再将x值对每一石子异或,因(x^a[i])^a[i]=x,若有x^a[i]<a[i],则拿走a[i]-(x^a[i])个石子就可以让异或值变成0。

cashier

NOI 2004 郁闷的出纳员

数据结构 线段树/平衡树/树状数组等

我采取的是平衡树,依旧用SBT,需要插入、查找和删除3种操作。保存一个数chg记录工资变化。

若为I操作(若k小于最小工资,不计入离开公司的人数!),则向树中插入值为k-chg的节点。

若为A或S操作,则将chg加上或减去k,其后不断删除树中最小元素直到最小元素+chg不小于最小工资,再将该节点加回去。

若为F操作,直接查找即可。

galaxy

NOI 2002 银河英雄传说

数据结构 并查集

维护一个并查集,增加以下关键字:loc[x]代表x到根节点的距离,dis[x]代表x到其父节点的距离,end[x]代表x所在的舰队的尾舰编号。路径压缩时更新相应值即可。

game

NOI 2003 木棒游戏

枚举

又是一道简单的猥琐题。预处理所有可能的变化,change[i][0]记录数字i内部移动火柴棒能变成的所有数值,change[i][1]代表数字i增加了一根火柴棒后能达到的所有数值,change[i][2]记录数字i减少了一根火柴棒后能达到的所有数值。然后枚举就可以了。

1029

poj 1029 False coin

枚举

枚举每一枚硬币是否是假币,以及它的重量是轻或是重,做好判断就可以了。

1036

poj 1036 Gangster

DP

设状态f[i]代表最后一个来的强盗编号为i所能拿到的最多钱,一开始将所有强盗按到达时间排序,注意一开始时门的状态值必须为0,我们只需增添一个虚拟强盗,到达时间为0,强度值为0,钱数为无穷大,最后答案再减去这个值即可。

1042

poj 1042 Gone Fishing

贪心

黑书上的例题,此处省略。

1635

poj 1635 Subway tree systems

最小表示法

该题考察树的最小表示法,方法为每个叶子节点标为一对括弧”()”,对每个内部结点,先得到其儿子的最小表示,将它们字典序排列得到c数组,该节点的最小表示即为’(’+sigma(c)+’)’。

3164

poj 3164 Command Network

最小树形图

朱刘算法。未AC。原因不明。

penguin

GDKOI 2008 第六题

DP

设f(i,j)为企鹅在i行j列的棋盘上走出的路径数

状态转移方程 f(i,j)=f(i-1,j)+f(j-1,i)+f(i,1)  边界f(i,1)=i,f(1,i)=1

2010.06.24

1050

poj 1050 To the Max

DP

枚举纵向的连续和,将原问题转化为一维的最大连续子段和,复杂度O(n^3)。

1080

poj 1080 Human Gene Functions

DP

类似于LCS,f[i][j]=max{f[i-1][j-1]+cmp[s1[i]][s2[i]],f[i-1][j]+cmp[s[i]][‘ ’],f[i][j-1]+cmp[‘ ’[s[j]]]}。

1160

poj 1160 Post Office

DP

f[i][j]代表前i个村庄里设置j个邮局,最小路程和,则

f[i][j]=min{f[i-k][j-1]+cost[i-k+1][i]},cost[i][j]代表在第i个村庄到第j个村庄里设置1个邮局的最小路程和,可以证明,该点必位于编号为(i+j)/2的村庄处。

1163

poj 1163 The Triangle

DP

OI界人人皆知的DP题..略

1170

poj 1170 Shopping Offers

DP

设f[x1][x2][x3][x4][x5]为买xi个第i种商品,所需花费的最小钱数,则

f[x1][x2][x3][x4][x5]=min(x1*sprice[1]+x2*sprice[2]+x3*sprice[3]+x4*sprice[4]+x5*sprice[5],min{f[t1][t2][t3][t4][t5]+price[i]}); 其中t1,t2,t3,t4,t5为用了优惠i之后剩余的各项商品数。

1191

poj 1191 棋盘分割

DP

可将式子变形为,平均值是一定的,所以只需让划分的棋盘各块的分数平方和最大,具有明显的最优子结构,可采取动态规划。

先预处理(x1,y1)到(x2,y2)的所有分值的和的平方((x1,y1)为左上角坐标,(x2,y2)为右下角坐标),设f[x1][y1][x2][y2][k]为将(x1,y1)到(x2,y2)的这一片棋盘划分为k块,得到的最大平方和。可得状态转移方程

f[x1][y1][x2][y2][k]=min{f[i+1][y1][x2][y2][k-1]+sum[x1][y1][i][y2]}; 竖着切

f[x1][y1][x2][y2][k]=min{sum[i+1][y1][x2][y2]+f[x1][y1][i][y2][k-1]}; 横着切

最后的结果即为sqrt(f[1][1][8][8][n-1]/n-ave*ave)。

1753

poj 1753 Flip Game

BFS

如上

2288

poj 2288 Islands and Bridges

基于哈密顿回路的状态压缩DP

设f[i][j][S]表示倒数第一个走到的岛为i,倒数第二个走到的岛为j,总的走过的岛的“清单”为S(二进制存储)所能得到的最大分值,则

f[i][j][S]=max{f[j][k][S-{i}]+score}

2411

Poj 2411 Mondriaan’s Dream

棋盘覆盖 状态压缩DP

设第i行状态为S1,第i-1行状态为S2,则有f[i][S1]=sigma(f[i-1][S2])要求S1和相应S2合法。

具体状态可用二进制数表示,0代表空,1代表被占据。采取DFS的方法来DP,由

dfs(row,now,s1,s2)转移到:

dfs(row,now+1,s1*2,s2*2+1) 表示该格不放,上一行该格应是填满的

dfs(row,now+1,s1*2+1,s2*2) 表示在该格竖放一个,上一行该格应是空的

dfs(row,now+2,s1*4+3,s2*4+3) 表示在该格横放一个,上一行相应两格应是空的

2479&2593

poj 2479 Maximum sum 2593 Max Sequence

最大2连续子段和

f1[i]为从左到右,以a[i]结尾的最大连续子段和;

f2[i]为从右到左,以a[i]结尾的最大连续子段和;

max1[i]为从左到右,到i为止的最大连续子段和;

max2[i]为从右到左,到i为止的最大连续子段和;

f1[i]=max(a[i],a[i]+f1[i-1])

f2[i]=max(a[i],a[i]+f2[i+1])

max1[i]=max(max1[i-1],f1[i])

max2[i]=max(max2[i+1],f2[i])

3254

poj 3254 Corn Fields

状态压缩DP

f[i][j]代表第i行为第j种状态时的方法数,用一个line数组保存每行的所有状态,用dfs得到,f[i][j]+=f[i-1][k]当且仅当line[i][j]&line[i-1][k]=0

a

某codeforces脑残题 略

2010.06.25

3013

Poj 3013 Big Christmas Tree

图论 最短路 邻接表

乍一看像最小生成树,但仔细分析后可发现,与某顶点有关的边是且仅是从它到达根节点的路径上的边,那么求最小的价格就相当于要求单源最短路径(邻接表写法)。

3613

Poj 3613 Cow Relays

图论 恰包含N条边的最短路

该题的解法巧妙地利用了floyd算法的性质。Floyd算法利用了DP以及矩阵自乘的思想,第k次矩阵自乘(将元素间的加法运算变成了取最小值的运算)后得到的就是顶点间恰经过k条边的最短路。用快速幂结合矩阵乘法即可完成此题。

3463

Poj 3463

图论 求最短路和比最短路大1的路径的数量

注意到dijkstra算法在执行时贪心地选取当前到源点路径最短的一个点加入已访问点集中,更新各顶点到源点距离,那么维护一个长度为2的单调队列,记录每个顶点最短的路径和第二短的路径,同时用一个数组记录数量。

2010.06.27(26号考托福没有做题)

1062

Poj 1062 昂贵的聘礼

可将问题抽象为找一条单源最短路径,使得路径上任意两点之间L值之差不大于M。可枚举路径上地位等级Li最高的人,将地位等级大于Li和小于Li-M的人标记为不可访问,求单源最短路径,最后取其中最小值即可。

具体构图:加一个附加源点,向每个物品连一条权值为该物品价格的边,每个物品为一个顶点,若存在某优惠,则从替代品向该物品连一条权值为优惠Vi的边。

1659

Poj 1659 Frogs’ Neighborhood

贪心

经典问题,采取贪心方法:

每次选取当前度数d最大的,向d个度数次大的顶点连边,并将连边的d个顶点度数减一,直到:若所有顶点度数为0则输出解,否则无解。

注意若所有顶点度数和为奇数可直接输出无解。

1679

Poj 1679 The Unique MST

图论 判断最小生成树是否唯一

只需判断最小生成树权值和是否等于次小生成树权值和即可。

首先用Kruskal算法求最小生成树,枚举删去MST上的边再求其中最小值即为次小生成树,判断是否相等即可。

2728

Poj 2728 Desert King

最优比率生成树

二分答案ans,将边权重设为h[i,j]-ans*v[i,j],若最小生成树小于零,说明答案太大,反之说明答案太小。控制精度即可。

3621

Poj 3621 Sightseeing Cows

最优比率闭合环

二分答案ans,将边权重设为v[i][j]*ans-f[i],用spfa判断是否有环,若有环则说明答案太大,反之答案太小。控制精度即可。

2010.06.28

1737

组合计数

设n个顶点的连通图数量为F(n),我们来计算它的补集的数量S(n),显然有F(n)=2^C(n,2)-S(n)

考虑顶点1,设它和其余顶点组成一个共有k个顶点的连通块,选择方法有C(n-1,k-1)种,组成连通块的方法有F(k)种,剩余顶点任意组合的方法有2^C(n-k,2)种,故

S(n)=sigma(C(n-1,k-1)*F(k)*2^C(n-k,2)),1<=k<=n-1

注意要用高精度计算

1848

Poj 1848 Tree

树形DP

f[x][0]为以x为根结点的子树,每个结点恰属于一个环所需加的最小边数;

f[x][1]为以x为根结点的子树,不考虑x,每个子树满足题目条件所需加的最小边数;

f[x][2]为以x为根结点的子树,除一个子树连同x结点形成一条链(即比环少一条边)之外,其余各顶点满足条件所需删去的最小边数。

则有f[x][1]=sigma(f[son[x][i]][0])

即各子树独自解决

f[x][0]=min(

min{min(f[son[x][i]][1],f[son[x][i][2]])+min(f[son[x][j]][1], f[son[x][j][2]])+sigma(f[son[x][k]][0])}+1,

min{f[son[x][i]][2]+sigma(f[son[x][k]][0])}+1)

即x结点和某两个子树连成一个环,或和某个子树形成的链连成一个环

f[x][2]=min{(f[son[x][i]][1],f[son[x][i]][2])+sigma(f[son[x][k]][0])}

即x结点接到某个点或某个链上连成一条链

边界条件:当x为叶子结点时,f[x][1]=0,f[x][0]=f[x][2]=INF

答案即为f[1][0]

2010

Poj 2010 Moo University

数据结构 堆

先将牛按score排序,用堆维护并求出每头牛前面与后面的牛中(N-1)头牛的aid的最小值,倒序枚举每头牛是中位数的情况,找到第一个满足条件的就可以输出答案。

2188

Poj 2188 Cow Laundry

数据结构 树状数组

求逆序数的题目,这里用树状数组来做

2449

Poj 2449 Remmarguts’ Date

图论 K短路 堆结构 A*算法

首先用dijkstra算法+堆优化求得所有顶点到根结点的最短路,将它设为A*的评估函数,然后用A*算法从源点开始扩展。每个结点最多扩展k次,当第k次扩展到T点时就得到了k短路。由于要维护一个能访问最小值和加入、删除元素的优先队列,故需要用堆来优化。

2823

Poj 2823 Sliding Window

数据结构 单调队列

维护两个单调队列,一个负责最大值,一个负责最小值。

以最小值为例,加入a时,每次从队尾删除不在窗口中的数,弹出队头大于a的数,插入a,该区间最小值就是队尾的第一个数。

3250

Poj 3250 Bad Hair Day

数据结构 栈模拟

上网搜的,自己可能讲不太清楚

步骤1:假设栈顶为 top,每输入一个数 in,就把它和栈顶数比较,如果大于栈顶数,就把栈顶数弹出,即 top-=1,并且把此时栈顶的对应的编号的 c 值加上刚才弹出去的对应的 c 值+1
直到找不到比 in 小的,把in入栈,即 top+=1
直到输入完成
步骤2:此时栈顶可能不为空,然后开始弹出栈里面的数,每弹出一个,就把下面一个的 c 值+ 弹出的c 值+1
直到栈空
步骤3:按顺序求出c 值和输出即可

画画图就能理解了

3320

Poj 3320 Jessica’s Reading Problem

数据结构 堆

维护一个堆,堆中元素为每个数在数据中最后出现的位置,若所有数都已出现,且当前是第i个数据,则ans = min(ans, i – getmin() + 1)

2010.06.29

1167

Poj 1167 The Buses

DFS

猥琐搜索题,搜索每辆车是某线路的第一辆车或第二辆车,若是第一辆车则新建一条线路,若是第二辆则其它车均已确定。剪枝:若当前解大于已得解则剪去;注意到时间是0~59,而车最多有300辆,可以将车映射到时间的区间上进行统计。

1338

Poj 1338 Humble Numbers

杂题

出自usaco上的一道题,用2、3、5分别去乘已经得到的丑数,找到第一个比之前大的,取其中最小的数作为下一个。为加快速度,可存储上次搜索到的位置,下次直接从上次的位置开始搜即可。

1794

Poj 1794 Castle Walls

数据结构 逆序数 树状数组

又是求逆序数的,从略。

1990

Poj 1990 MooFest

数据结构 树状数组

转换思路,考虑每头牛的声音能被多少牛听到,维护一个树状数组c1记录坐标和,另一个树状数组c2记录小于当前坐标的牛的个数。首先将所有牛按音量升序排序,每次向c1的xi处加上xi,向c2的xi处加上1,答案加上

v[i]*(x[i]* getsum(c2,x[i])- getsum(c1,x[i])+

getsum(c1,MAXN)- getsum(c1,x[i])-x[i]*(i-1- getsum(c2,x[i])));

2699

Poj 2699 The Maximum Number of Strong Kings

网络流

考虑构这样一个图:源点向所有人连权值为该人分数的边,所有比赛向汇点连权值为1的边,所有人向其参加的比赛连权值为1的边。首先将所有players按score降序排序,然后枚举每个player,若当前player为i,他能成为strong king,当且仅当他打败了他之前所有的players。那么就从图中删去他之前的players与他们和他比赛的场次之间的边。求一次最大流,若等于所有人的分值之和则继续,否则说明不行,答案即为i之前的所有人。

3469

Poj 3469 Dual Core CPU

网络流 最小割

两个CPU一源一汇,相应的cost连上边,若某两个不在同一个执行时有附加cost,则在它们之间连两条边v(a,b)=v(b,a)=cost。最小割即为答案。

这题用SAP挂了,可能是写的效率太低。未AC。

131

Sgu 131

状态压缩DP

仍旧采取DFS+DP的方法,dfs六个参数row,now,s1,s2,b1,b2分别表示当前行,当前格子,当前行状态,上一行状态,当前行前一格对这一格影响(即是否已被占据),上一行前一个对这一格的影响。占据为1,空闲为0,二进制编码。状态转移f[row][s1]+=f[row-1][s2]

Dfs转移:

dfs(row,x+1,(s1<<1)+b1,(s2<<1)+1-b2,0,0);

若b1=0且b2=0

dfs(row,x+1,(s1<<1)+1,s2<<1,0,0);

若b1=0

dfs(row,x+1,(s1<<1)+1,(s2<<1)+1-b2,1,0);

若b1=0且b2=0

dfs(row,x+1,(s1<<1)+1,s2<<1,1,0);

若b1=0

dfs(row,x+1,(s1<<1)+1,(s2<<1)+1-b2,1,1);

若b1=0且b2=0

dfs(row,x+1,(s1<<1)+1,s2<<1,0,1);

若b2=0

dfs(row,x+1,(s1<<1)+b1,s2<<1,1,1);

1141

Poj 1141

DP

OI界经典DP题,f[i][j]=min{f[i][k]+f[k+1][j]}

1285

Poj 1285

DP

首先处理输入数据,c[i]代表i出现了多少次

f[i][j]代表在前i个里面选j个的方法数

则f[i][j]=sigma(f[i-1][j-k]),0<=k<=c[i]

注意结果用64位整型存储

1306

Poj 1306

数学

水题,求组合数即可

1850

Poj 1850

数学

用类似康托展开的方法统计当前排列之前有多少个

1942

Poj 1942

数学

水题,答案即为C(n+m,n),需注意同时乘除防止溢出,可用double类型

1958

Poj 1958

DP

四柱汉诺塔问题,设f(i)表示四个柱子移动i个盘子需要的最小步数,g(i)表示传统三柱汉诺塔需要的最小步数,则f(i)=min{f[j]*2+g(i-j)}

2304

Poj 2304

数学

题目叙述的很怪,看懂就水了,答案为

9*(120+(k-x+40) mod 40+(y-x+40) mod 40+(y+40-z) mod 40)

2356&3370

Poj 2356&3370

数学,鸽巢原理

设s[i]为前i个数的和,对其取模得n+1个数(包括s[0]),而模的可能取值为0~n-1共n个,所以必有2个s的值相等,它们之间的一段连续和即满足条件。

3601

Poj 3601

设g(i)表示前i种盘子不考虑顺序移到第3个柱子上所需要的最小步数,f(i)为考虑顺序的,则

若当前盘子数只有1个则不用考虑顺序,f(i)=2*g(i-1)+t

否则f(i)=2*g(i-1)+2*t+f(i-1)

而g(i)=2*g(i-1)+t

具体实现时不需要数组储存,直接迭代运算即可

Categories: OI
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: