Climber.pI的OI之路

NOIp 2011 初赛备考

posted @ 2011-10-15 11:27 Climber.pI 阅读(380) | 评论 (0) | 编辑 收藏

Problem List (9.7 ~ 9.29)

posted @ 2011-10-01 21:53 Climber.pI 阅读(193) | 评论 (0) | 编辑 收藏

USACO Training Chapter 4 ~ 6 Summary

posted @ 2011-08-23 13:26 Climber.pI 阅读(470) | 评论 (0) | 编辑 收藏

Problem List (8.13 ~ 8.21)

8.13

prime3[DFS + 手动指定搜索顺序], 4h, 0.1s左右出解
1.构造所有五位素数, 可以先做一个313以内的素数表, 试除即可. 注意素数末尾不是偶数和0.
*官方题解中枚举6n-1和6n+1, 同时判断末位5和0, 从素数7开始枚举即可, 枚举量进一步减少
2.手动指定搜索顺序, 对于每种情况分别处理, 代码很长. 对角线优先, 末尾数组优先(显然素数末尾数字只能是1\3\7\9)
 0 21 18 22  5
12  2 13  8  9
16 23  3 24 10
14  7 15  4 11
 6 19 17 20  1
大致分为几种情况:
1)非末位. 边界条件是 0 <= i <= min{sum(除去已使用位), 9}
2)末位. 边界条件是i = 1, 3, 7, 9(i <= sum)
3)可计算位(即该行或列或对角线已经填了4个数). sum < 10, 判断是否为素数, dfs下一层时, sum-下一层已填充位置.
4)对于由情况3)转移而来的状态, 需要检查sum >= 0
*可以把情况1)和2)分别合并, 利用数组指定顺序亦可(代码长度可能变化不大)
*官方题解在这里以行\列\对角线为单位填数, 需要预处理某些位为某些数的素数.
3.对保存的结果进行排序, 利用qsort间接排序即可.
*NOCOW上有人写15重for循环, 效率比这个低10倍. 但是15重for加上缩进实在不好看.

race3[DFS判断连通性], 40min
第一问, 去掉每个点后判断是否能够到达终点, 利用DFS+vis数组标记即可.
第二问, 第二问是第一问答案的子集. 从原点(标记A不可访问)和第一问某个点A分别DFS, 如果不存在某点在两次同时被访问, 那么满足题意.
证明: 假设第二问不是第一问的子集, 那么不经过第二问中某个点, 必然可以到达终点, 与题目中对于分割的定义矛盾.
*用Floyd判断连通性亦可(有向图传递闭包).

shuttle[BFS/数学], 4h
1)BFS做法(n <= 7)
1.利用位运算保存状态, 1表示'W', 2表示'B'或空格, 附加k表示空格所在位
2.按照字典序转移状态(共4种方式), k的方向可以任意理解, 不影响结果. k从0开始, 显然W只向右, B只向左.
*在草稿纸上写好状态转移的具体代码(if部分), 注意变量
*读题, 一开始认为棋盘长度不超过12于是就BFS, 实际上棋盘长度不超过25, 位运算保存状态会爆内存. 此外输出限制每行20个数字.
2)数学 by NOCOW
我们凭借极其敏锐的眼光发现这组序列为
4 35 642 1357 642 35 4 (n=3,样例)
5 46 753 2468 97531 2468 753 46 5 (n=4)
即长度为1,2,3,4,...,n,n+1,n,...,4,3,2,1这样的2n+1组等差序列
我们讨论第1~n+1组序列，这些序列满足
　　*公差的绝对值为2
　　*奇数组为降序列，偶数组为升序列
　　*对于第i组(1<=i<=n+1),若为奇数组则首项为n+i，偶数组则首项为n-i+2
对于第n+2~2n+1组，可以由对称性求出.
*官方题解做法类似数学做法, 观察后得出每次都是空格向右移动2格, 直到不能移动(如果不能向右移动1格的话转向)或者达到状态.
*如果输出字典序最小解, 不妨找规律; 如果输出所有解, 只能搜索.

milk6[最小割+贪心], 按计划cheat.

frameup[拓扑排序]
1.构造有向图. 在读入图的同时计算每种矩形的坐标边界, 然后按照边界遍历, 若矩形A上存在B, 则G[A][B] = 1.
2.拓扑排序并输出. 注意到这里并没有明显层次性, 答案可能远远超过所得序列长度. 如果标记层次的话, 若图中指向复杂, 那么会少输出一部分答案(如测试点7).
*一开始没有看出来是拓排, 一门心思想怎么DFS.
*打错变量调了1h, 没有看出来输出序列的不同浪费了1h. -> 开始的分析非常重要, 边写边改时间成本太高.

8.14

theme[二分], 1.5h, O(N^3logN)
1.对序列做差, d[i] = A[i+1] - A[i].
2.二分求最大值. 注意l=m+1, 可能存在m为最大值的情况, 所以需要check(l).
3.分别枚举两个序列的开端(序列1开端为i, 序列2开端为i+l+1), 如果相同, 继续比较.
*数组开小, 导致诡异错误 -> 读题!!!, 20min
*注意编写的程序前分析边界情况 -> 1h

8.15

调教laptop.

8.16

frameup[拓扑排序], 20min -> 参照 北极南天星 的题解, 意简言赅
构图这里不再赘述. 注意到题目要求输出拓扑序列, 长度一定, 并不像DP中出现明显层次性.
dfs状态(当前序列长度), 按照定义做: 每次找入度为0的点u, 然后将于此点存在边的点v入度-1. 直到所有点都在序列中.
*dfs按照字母升序搜索, 即满足题目顺序要求.
*构图统计每个点u入度时注意判重, 存在多个点满足条件.

theme[DP], O(N^2)
f[i][j] = max{f[i+1][j+1]}(A[i+1]-A[i] == A[j+1]-A[j]) + 1
f[i][j]表示以A[i]和A[j]为起点的序列的最大长度, 以j-i为阶段, 注意f[i][j]<=j-i. 注意到状态之间存在依赖性, 各阶段间不存在依赖性, 只需保存当前状态. 不断更新答案即可.
*不能直接二分, 答案可能小于j-i, 无法写判定函数 -> 如果对于每个j-i的长度序列单调不下降的话还是可以二分.

8.17

starry[floodfill+模拟], 4h
读入图, 对每个点进行floodfill; 如果存在星座, 那么和之前的星座进行判重; 不重复的话, 利用数组st0记录当前星座. 否则改变标号.
判重首先判断 长度 和 星体个数(只利用这两点可以过4个点), 然后直接模拟即可. 在floodfill过程中记录坐标极值, 然后提取矩形, 和st0中星座比较.
比较需要用到顺时针向右转90度和水平翻转, 坐标变换分别是(tx-x, y)和(y, tx-x), 可以画图观察.
*一开始没有考虑如何判重, 想了1h
*没有考虑同一矩形内存在多个相同星座, 浪费0.5h

fc[凸包(Graham-Scan, 水平序实现)], 1h, 参考黑书
1.以纵坐标为第一关键字, 横坐标为第二关键字, 对坐标升序排序.
2.左链扫描, 从1到n. 如果栈内存在超过两个元素, 那么叉积判断是否>180°(即cross<=0), 满足的话弹出栈顶元素(利用while). 将当前点加入栈.
3.右链扫描, 从n-1到1. 判断同上.
4.计算周长. 加入初始点和末端点距离, 依次加入栈中元素.
*利用栈表示凸包序列

snail[DFS], 50min
读入路障坐标(x,y)标记为-1, 其他值为1; DFS过程中检查下一格是否可行, 若不可行, 如果是边界或路障可以转向. 记录最大值.
*注意当前标记在DFS后清除, 已路过格不可转向; 障碍纵坐标可能不是一位, 读入横坐标后标记该为为'0', 利用sscanf读入即可.
*想起了去年NOIp第四题, 只有半个小时, 但是写了floodfill却调不出来. 心里没底, 仿佛这是看RP的事情, 今天半个小时的时候发生了同样的事情, 务必加长算法设计时间.

wissqu[DFS] -> cheat
题目给出了每种牛的个数, 实质上就是带限制的全排列, 可行性剪枝很多, 代码大概要100+行.
*不过这题只有一个测试数据, 就是样例 -_-

8.18

fence3[局部搜索], 1h
标准做法是模拟退火, 或者随机化搜索. 基本思想是逐渐加精度(官方题解也这么写).
首先搜索所有整数坐标, 记录最小距离和当时坐标; 然后在此坐标±1范围内搜索最小值, 注意增量dx/dy要初始化为0(这时不会更新最小值).

bigbrn[DP], 30min
f[i][j]表示以(i, j)为右下方顶点的正方形的最大边长
f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1
初始化 f[i][j] = 1; 若(i, j)有障碍, 则f[i][j] = 0, 且该点不进行dp

window[链表(字符串实现) + 矩形切割(10行)], 3h
对于操作w/t/b/d, 维护操作序列order, 利用<string>实现. 注意string str(&a[i], &a[j])对应区间为[i, j). 构造小数据调试即可.
对于操作s, 利用矩形切割, 逆序添加操作序列order中矩形(可以同时维护面积). 实现非常简单, 首先对判断是否被已有矩形覆盖(x2 < x1), 然后分成四部分添加未被覆盖部分.
注意到数据中s操作可以连续, 不妨利用char记录上一操作, 可以避免一些矩形切割.
*这题想想会觉得头疼, 但是实现非常简单(ctypcow实现非常麻烦). 题目并不难, 很明显下午看题的时候高估了实现难度. 不要给自己制造"难题".
*提交程序中对stdout输出过多同样会造成崩溃

8.19

milk4[DFS-ID + DP], 45min
利用DFS-ID枚举桶(即枚举r-组合), 然后DP判断能否装满.
f[j] |= f[j-ans[i]](完全背包, 不考虑背包数)
初始化f[0] = 1, 其他为0; f[i]表示可以量出i夸脱的牛奶
*打错变量(DFS/DP), 应该首先静态差错, 而不是上数据.
*有纯dp做法, 记录方案很繁琐.

schlnet[强连通分量(Tarjan)], 1h
利用邻接表存储图, 利用Tarjan寻找强连通分量(BYVoid有个很好的教程, 主过程19行).
第一问是最小点基, 对求得的所有强连通分量进行缩点, 入度为0的点的个数即为答案.
第二问为min(入度为0的点的个数, 出度为0的点的个数), 需要注意只有一个点的时候需要特判.
[Tarjan]入栈\时间戳 -> 遍历相邻边 -> 未遍历点遍历 -> 更新LOW -> LOW是否等于DFN -> 出栈标记SCC

latin[DFS + 数学], 1h
注意第一行题目中已确定, 最后一行和最后一列同样可以推算, 因而只需枚举中间(n-1)*(n-2)方格即可. 可以规定第一列升序, 这样一来计算量只是原来的1/(n-1)!, 可以过六组. 第七组需要cheat, 运行时间大概1min左右(可能常数可以少一些). 标准做法是置换群.(std理解不能)

telecow[网络流], 按计划cheat

besty[DFS], 1h, N=7 15s
按照题意进行DFS, 有几个优化.
1.当点的可选择方向为2时, 用floodfill判断图内未填充点是否可以互相到达, 不能到达则剪枝.
2.如果经过点(1,n), 但填充顺序k不满足题意, 剪枝.
3.内层检查扩展节点是否符合题意(常数优化).
4.判断某点到(1,n)距离是否小于n*n-k(加了反而更慢).
*可以输出状态观察归纳不可解状态的共性, 然后剪枝. -> by dd_engi
*据说可以使用著名的cdqDP..
-> 参考黑书P184, 3h
1.图中必须没有孤立区域, 即上文优化1, 这里仅讨论■□■的情况.
2.搜索过程中, 除被搜索点和目标点外, 其他点至少有两个点与之相连. 可以利用数组link[i][j]记录(i, j)的连通情况.
3.如果移动方向上前一个点未被遍历, 左边点未被遍历, 且左前方点已被遍历时, 剪枝. 右侧同理.
利用剪枝1和2以及前文剪枝2, 在本地N=7需要2.3s, 加上剪枝3在本地需要1.9s, 在USACO卡时AC.
*一个技巧, 可以预先表示行列编号为0和n+1的点已读, 可以避免对越界的讨论.

tour[双进程DP/费用流/刷表法], 3h, O(N^3)
状态想对了, f[i][j]表示两个人分别从起点出发到达城市i\j所经过的城市数.
一开始认为方程是f[i][j] = max{f[i.prev][j], f[i][j.prev], f[i.prev][j.prev]+1}, 觉得不太对, 就去查题解.
北极天南星给出的方程是 f[i][j] = max{f[j][k], f[k][j]} + 1
规定对于任意状态f[i][j], i > j, 需要注意f[j][k]\f[k][j]必须计算过. 初始化f[1][1] = 1, 其余为0.
*利用strcmp比较字符串即可, memcmp似乎某些情况下会出错.
*这题和NOIp 08传纸条的主要区别: 这题是无向图, 而传纸条是矩阵. 因而转移方式不同.
[故事] by BYVoid
这是加拿大IOI93的一道原题。在WC2008中听吴教授说道，当时参加IOI的选手没有人了解动态规划，对这道题束手无策。选手们都用上了最复杂的搜索技巧，有人还写了双向搜索，可是都没有通过。回国后开始研究，最终提出了动态规划这一算法设计方法，于是动态规划变成了之后竞赛出题的热点。

8.20

hidden[字符串], 2.2h
最初的做法很猥琐, 按题意模拟, 记录最小字典序串的口令. 第8个点TLE了, 大概都要5s左右.
进一步的修正记录了每个字母每次出现的位置, alpha[i][0]表示出现次数, 类似邻接表. 只处理字典序最小出现次数非零的字母, 第10个点TLE了.
更进一步, 对于串中若干个连续的该字母, Count[j]表示alpha[i][j]开始, 由该字母组成的最长连续串. 只处理第一个, 一开始没有考虑环状, 第11个WA了.
*处理环状的必要条件是, alpha[i][alpha[i][0]] + 1 == n;
*对于复杂度估计不周, O(N)的常数太大所以挂了, 之后修正没有考虑环状情况, 卡了1h.
*秒杀做法包括最小表示法\后缀数组\类KMP\最小后缀, 有空应该学一下著名的KMP算法

cowxor[?]
很容易联想到最大连续和, 注意到异或运算满足结合律, 可以利用O(N^2)的时间枚举每个区间. 但是这题范围很大, 第6个点就TLE了.

8.21

charrec[DP + 统计 + 记录方案], 2.5h
注意到题目对于最优解的定义是损坏数据最少, 因而可以考虑DP.
f[i] = min{f[i + 19] + C[i][19], f[i + 20] + C[i][20], f[i + 21] + C[i][21]}
prev[i] = i + 19\20\21
prevk[i] = K(C[i][_]对应的字符)
f[i]表示从第i行到第n行的最少损坏(不同位数). C[i][j]表示从第i行开始连续匹配j行的最小损坏(不同位数), 这里需要返回所对应的字符, 实现时可以利用记忆化.
对于f数组, (n - 19, n]需要初始化为+∞
*可以利用d[i][j][k]表示第i个字符第j行和输入数据第k行不同位数
*需要注意数组大小, 以及题目中写出的font.in和给出的font.in不同.

picture[离散化+扫描线? / 离散化+线段树 / 离散化], 1h
1.无需离散化, 直接染色, 可以过8组数据. -> But, 第7组莫名奇妙的挂了.
[统计] 对于两线段交点, (G[i-1][j]^G[i+1][j]) && (G[i][j-1]^G[i][j+1])(即(i,j)左右\上下相邻点颜色不同).
  对于一般点, 水平方向上, 可以(G[i][j-1]^G[i][j+1]) && G[i-1][j] && G[i+1][j]. 竖直方向同理.
2.扫描线 + 离散化 by BYVoid
对于水平和竖直方向分别处理, 下面仅讨论水平情况, 竖直同理.
(1)对于每个矩形, 将其在水平方向上的边按照纵坐标的大小, 分为始边和终边.
(2)按照纵坐标升序扫描, 相同情况下始边优先(因为边重合的时不算入周长). -> 快排即可
(3)如果遇到始边, ++ level[i]; 如果遇到终边, -- level[i]; 如果出现level[i]从0到1的情况, ++ ans; 从1到0的情况相同, 不必考虑.
-> 对于这一题直接扫描每个点即可, 如果数据范围进一步扩大的话, 不妨使用线段切割.
答案即为ans*2;
*很像KOI10 Day2的某题, 当时貌似我直接模拟, 然后数组爆了. 其实用sizeof算一下内存即可.
*突然发现神牛的构造能力都很强. 比如说BYVoid的做法, 个人以为最重要的是level数组的构造.
*如果自己写计时函数并提交的话, 会发现USACO函数显示的时间比USACO给出的时间少得多, 原因不知.
*很奇葩的是, 以前一直用PROG, 然后USACO这次突然提示使用PROB -> 什么状况

twofive[Contor展开], ?h, 全仿std.
1.暴搜 -> 理论6组, 实际4组 -_-
2.类似kimbits, 可以使用康托展开(比较直观的解说参见白书第10章).
关键在于对于一个给定的串, 如何知道小于其前n位的串的方案数. 定义f[a][b][c][d][e]表示方案数. 对于每个字母ch, 如用过, 那么继续ch+1. 否则枚举已填位后所有位, 累计方案值.
(数学描述)
若ch未被使用, f[a][b][c][d][e] = f[a+1][b][c][d][e] + f[a][b+1][c][d][e] + f[a][b][c+1][d][e] + f[a][b][c][d+1][e] + f[a][b][c][d][e+1];
初始化f[5][5][5][5][5] = 1.
*[数组开小]
  > Run 1: Execution error: Your program had this runtime error:
        Illegal file open (/dev/tty). The program ran for 0.000 CPU
        seconds before the error.

rectbarn[DP], 1.5h
1.暴力, O(R^2*C^2*P), 可以过3个点
2.参考WC03王知昆论文, 非常好理解
悬线：上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线. 显然对于每个悬线扩展得到矩形一定包含答案. 我们可以利用O(RC)的时间得到所有悬线, 因而问题的关键在于利用O(1)的时间处理悬线. 这里可以使用DP.
H[i][j] = H[i-1][j] + 1   (G[i][j]未损坏)
    0      (G[i][j]损坏)
L[i][j] = min{l[j], L[i-1][j]} (G[i][j]未损坏)
    ∞      (G[i][j]未损坏)
R[i][j] = min{r[j], R[i-1][j]} (G[i][j]未损坏)
    ∞      (G[i][j]未损坏)
max{H[i][j]*(L[i][j] + R[i][j] - 1)}即为答案
*北极天南星 和 论文 似乎都有一个地方把 min 打成了 max.
*i和j不能随意交换, 需要注意所对应的下标范围.(#3 WA)

vans[DP / SCDP], 1h
奇葩的递推式, f[n] = 2*(f[n-1] + f[n-2] - f[n-3]) + f[n-4] (n >= 5)
初始化, f[1] = 0, f[2] = 2, f[3] = 4, f[4] = 5; f[50]之后需要高精度.
*推导方法待研究.
*求哈密顿回路个数, 可以使用基于连通性的SC.

cowxor[枚举 + 优化], 1h, 全仿std

posted @ 2011-08-23 12:17 Climber.pI 阅读(210) | 评论 (0) | 编辑 收藏

写在USACO通关之后

posted @ 2011-08-22 21:07 Climber.pI 阅读(752) | 评论 (0) | 编辑 收藏

Problem List (8.6 ~ 8.12)

posted @ 2011-08-18 12:31 Climber.pI 阅读(228) | 评论 (0) | 编辑 收藏

USACO Training 4.1.4 Cryptcowgraphy

USER: Yupan Liu [liuyupa1]
TASK: cryptcow
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3240 KB]
   Test 2: TEST OK [0.000 secs, 3240 KB]
   Test 3: TEST OK [0.000 secs, 3240 KB]
   Test 4: TEST OK [0.000 secs, 3240 KB]
   Test 5: TEST OK [0.000 secs, 3240 KB]
   Test 6: TEST OK [1.377 secs, 3240 KB]
   Test 7: TEST OK [0.054 secs, 3240 KB]
   Test 8: TEST OK [1.026 secs, 3240 KB]
   Test 9: TEST OK [1.782 secs, 3240 KB]
   Test 10: TEST OK [1.971 secs, 3240 KB]

All tests OK.
Your program ('cryptcow') produced all correct answers!  This is your
submission #37 for this problem.  Congratulations!

posted @ 2011-08-10 20:36 Climber.pI 阅读(230) | 评论 (0) | 编辑 收藏

Problem List (7.26 ~ 8.5)

7.26

最长公共子序列lcs, O(N^2)
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1(if A_i==B_j)}
初始化f[_][0] = f[0][_] = 0

7.27

编辑距离edit, O(N^2)
f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1, f[i-1][j-1] + !(A_i==A_j))
初始化f[i][0] = f[0][i] = i
*参考[这里]http://en.wikipedia.org/wiki/Levenshtein_distance
*状态转移过程中, 充分不一定最优, 必要才是最优; 事实上边界条件总有其具体意义
*[相关]http://www.matrix67.com/blog/archives/333

最短回文串palindrome[poj 1159], O(N^2)
1.套用lcs, O(N^2), 60
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1(if A_i==B_j)}
初始化f[_][0] = f[0][_] = 0, n - f[n][n]即为答案
*利用滚动数组优化, 空间复杂度O(N), 80
*关键语句k = 1 - k, 注意在内层循环外
2.套用edit, O(N^2), 30
f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1, f[i-1][j-1] + 2*!(A_i==A_j))、
初始化f[i][0] = f[0][i] = i, f[n][n]/2即为答案
3.O(N^2), 30
f[i,j]表示将Ai..Aj变为回文串的最小代价，则
f[i][j] = f[i+1][j-1] (若Ai=Aj)
    min(f[i+1][j],f[i][j-1])+1 （若Ai<>Aj）
4.利用位运算优化
http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/86.IPL.html

硬币找零coin[完全背包], O(N^2)
f[j] = min(f[j], f[j-c[i]]+1)
初始化f[0] = 0, f[1..T] = INT_MAX
*注意下标非零 和 INT_MAX的溢出

7.28

导弹拦截missile[LIS + 二分], O(NlogN)
(1)二分查找O(logn)
f[i] = max(f[j] + 1) (j < i)
d[i] = min(f[k]) (f[k] == i)
易知d[i]单调, 因而可以利用二分查找降低复杂度, i最大值即LIS长度为t, 那么
i)  f[i-1] < k <= f[i] (1 <= i <= t)
ii) 若k > 任意f[], 则f[t+1] = k;
iii) 若!k, 则f[1] = k;
*例子参见[这里]http://www.matrix67.com/blog/archives/112
[代码实现]
//情况ii和iii需要单独处理
x = 1; y = t;
while (x <= y){
 m = (x + y)/2;
 if (f[m-1] < k && k <= f[m]) break;//对于最长上升子序列和最长不下降子序列判定条件不明???
 //if (f[m-1] < k && k <= f[m]) return m;
 else if (k > f[m]) x = m + 1；
 else y = m - 1;
 //return x;
}
*利用注释, 可以避免对情况ii的单独处理LIS的方案, 记录方案需要使用pre数组, 范例不知???
*需要注意的是, f数组给出的并非是一个
(2)最少链划分 = 最长反链长度(关于偏序集, 参见《组合数学》P73)
[Dilworth定理]令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

最长不下降子序列lis[LIS + 二分], O(NlogN)
对[1..k-1][k+1..n]两个序列分别进行一次LIS即可.
*问题的关键之处在于第一次理解不彻底和浮躁, 以及对于困难程度的不合理估计.

7.29

加分二叉树tree[区间 + 记录方案], O(N^3), 20min
f[i][j] = max(f[i][k-1] * f[k+1][j] + A[k]) (i <= k <= j)
初始化f[i][i] = A[i], f[i+1][i] = 1
[记录方案]pa[i][j] = k, 递归即可, [边界]pa[i][j] == i 或者 j, 以及i == j的情况

整数划分separate[区间 + 记录方案], O(N^3), 2h
f[k][i]表示序列1..i分成k段的最大值
f[k][i] = max(f[k-1][j-1] * A[j][i])
pa[k][i] = j
初始化f[1][_] = A[1][_], 其他f[][] = -1
*注意等号情况同样需要更新
if (f[K][i] <= f[K-1][k-1] * A[k][i])
 f[K][i] = f[K-1][k-1] * A[k][i],
 pa[K][i] = k; //记录方案
*将[pa[k][i], i]加入答案, 递归[1, pa[k][i]-1], [边界] k == 0
*在Win下使用long long占位符为"%I64d", 在Linux下占位符为"%lld", 考试中利用<fstream>避开占位符问题

凸多边形的三角剖分division[区间]
f[i][j] = max{f[i][k] + f[k][j] + w(i, j, k)} (i < k < j)
初始化1<=i-j<=2的f只为0, 其他为-1
*表达式中同时出现long long和int的话, 会自动转换为int
*只过了6个点, 原因不知 -> 数据错误, 最后4个点output一样
*各种神牛们普遍指出没有考虑i>j的情况 -> 怎么写???

机器分配machine[区间], O(N^3)
f[i][j] = max(f[i-1][k] + A[i][j-k]) (0 <= k <= j)
初始化f[][] = 0, f[i][j] = max(f[i][j], A[i][j])
*注意读题"第i个公司分配j台机器的盈利", 不是分配第j台机器的盈利

装箱问题box[分组背包], O(N^2), 30min
f[i][j] = max{f[i-1][j], f[i-1][j-c[i][k]] + w[i][k]}
初始化f[][] = 0
*读题时注意变量的对应关系
*注意本题中背包不一定要装满

7.31

最长前缀prefix[判断性dp], O(kN), 70min
f[i] |= f[i - len[j]] & check(i - len[j] + 1, j) (1 <= i,j <= n)
初始化f[] = 0, check(x,y)表示主串[x,x+len[y]-1]和前缀y是否相同
*弄错j和len[j], 注意方程的字母指代, 以及实现中的字符指针位置, 注意静态查错[30min]
*[8.4优化]把check函数直接写在循环中, 如果f[i] == 1直接break -> 依旧超时三个点
*[8.5优化]i的上限为min(n, ans + 20), 更新f[i]的时候记录ans即可 -> AC
8.1

关键子工程project[DAG最长路], 70min
f[i] = max(f[j] + w[i]) (G[j][i] == 1)
初始化f[i] = w[i]
记录方案, 利用f[i] == w[i] + f[j] (G[j][i] == 1)
*利用定义求拓扑排序, 输出方案可以利用队列将递归转化为迭代, 无解情况用flag标记(inq数组表示是否在队列中)
*在纸上写出关键部分的代码, 两倍行距(比如递推或者记忆化函数, 输出方案的函数)

8.2

三角蛋糕trigon[坐标dp], 130min
[做法1](需保留空格)
f_[i][j]表示以(i, j)为顶点的Rt△的最大边长
对于倒三角形, 自右向左 f1[i][j] = min(f1[i+1][j], f1[i][j+1]) + 1
    自左向右 f2[i][j] = min(f2[i+1][j], f2[i][j-1]) + 1
对于正三角形, 自右向左 f1[i][j] = min(f1[i-1][j], f1[i][j+1]) + 1
    自左向右 f2[i][j] = min(f2[i-1][j], f2[i][j-1]) + 1
初始化, f[][] = 0(A[][] = '#'), f[][] = 1(A[][] = '-'); min(f1[i][j], f2[i][j])^2的最大值即为答案
[做法2](不需保留空格)
f[i][j]表示以(i, j)为顶点的△的最大高度
对于倒三角形, f[i][j] = min(f[i-1][j], f[i-1][j+1], f[i-1][j+2]) + 1
对于正三角形, f[i][j] = min(f[i+1][j], f[i+1][j-1], f[i+1][j-2]) + 1
初始化, f[][] = 0(A[][] = '#'), f[][] = 1(A[][] = '-'); min(f[i][j])^2即为答案
*输入需保留空格, 卡了30min(排除ASCII为10或13的字符即可)
*没有考虑正方向, 大约2h时对照std发现
*有两个点数据错误, 对照std后发现std仅当横坐标为奇数是考虑倒三角形, 横坐标为偶数时考虑正三角形, 而题目中无此限制
*学习利用批处理对拍的写法
@echo off
:again
gen
trigon
trigon_me
fc trigon.out trigon_me.out > nul
if not errorlevel 1 goto again

选课course[树形dp]
[做法1]多叉转二叉
f[i][j]表示以i为根节点的树中, 选择j门课
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-1] + i.v) (0<=k<j)
初始化f[][] = 0
*无法记录方案 -> gXX表示比较困难
[做法2]泛化物品
??? -> 想撞墙 -> 需要学习

通向自由的钥匙key[树形dp], 150min, zoj 2280
f[i][j]表示以i为根节点的数, 花费能量为j时可以拿到的最多的钥匙数
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-i.c] + i.v) (o<=k<=j-i.c)
初始化f[][] = -1, 边界处理f[i][j] = 0(i<=0 || j<0)
*记录各点邻接矩阵, 利用dfs构造树(注意处理后取消邻接), 并多叉转二叉 -> 30min
*对于f[i.r][j]不必在记忆化搜索函数中遍历所有兄弟, 只遍历最近的即可
*注意读题, 出发点为1, i.c和i.v非负 -> 1.5min
*注意静态查错, 如记忆化搜索中dp(i, j)打成f(i, j)的情况
*觉得比较晕的时候等一下再调题, 可以先干点别的, 这样可以减少时间的浪费

警卫安排security[树形dp], 100min
[状态]
f[i][0]表示以i为根节点, 并在i安排警卫的最小花费
f[i][1]表示以i为根节点, i的父节点已安排警卫的最小花费
f[i][2]表示以i为根节点, i的子节点已安排警卫的最小花费
[方程]
f[i][0] = Σmin(f[i.son][0], f[i.son][1], f[i.son][2]) + i.v
f[i][1] = Σmin{f[i.som][0], f[i.son][2]} (i不是树的根节点)
f[i][2] = min{Σmin{f[i.son][0], f[i.son][2]}(i.son != k) + f[k = i.son][0]}
[初始化]
对于叶节点, f[i][0] = i.v, f[i][1] = 0, f[i][2] = i.v
对于其他值, f[][] = -1
*对于根节点的寻找, 利用prev[i]记录i的前驱, 若!prev[i], 则i为树根
*结合批处理和makedata以及小范围暴力程序, 可以有效地避免各种错误及极端情况 -> 需要学习搜索
*对于这类题目, 思考的关键在于分类写出方程, 并注意方程的边界条件(类似:tyvj 没有上司的舞会)
*对于树形dp, 存在两种类型; 一种是对于加权路径长度限制, 另一种则是求加权最值

8.4

青蛙的烦恼frog[区间dp]
初看是最小生成树问题, 但是此题有几个特别的性质:
1.以1号荷叶为起点, 终点不定
2.遍历荷叶的最短路径是一条链
3.题目给出的坐标顺序是一个顺时针方向的多边形
4.最短路径不相交(画一个四边形, 利用三角形性质可以观察到)
根据性质1和2, 容易得出O(N^3)的方程, 很明显会超时
f[i][j] = min(f[k][j-1] + d[i][k]) (i!=k)
-f[i][j]表示以i为起点, 长度为j的最短路径, 初始化f[i][1] = 0
进而考虑性质3和4, 因而对于点1, 只能选择相邻的点2和n, 可以得到O(N^2)的方程
f[i][j][0] = min{f[i+1][j-1][0] + d[i][i+1], f[i+1][j-1][1] + d[i][i+j-1]}
f[i][j][1] = min{f[i][j-1][1] + d[i+j-1][i+j-2], f[i][j-1][1] + d[i+j-1][i]}
-f[i][j][0]表示以i为起点, 长度为j的最短路径, f[i][j][1]表示以i为终点, 长度为j的最短路径, 初始化f[][1][] = 0
-一个实现上的小优化, 保证d[i][j](i<j)
*注意静态查错, 区别变量名, 思考算法的过程应该长于调试的过程
*修正了测试点6

火车进站train[线性dp], 70min
1.M <= 3 -> 可以分类讨论
2.只存在一条轨道, M只能决定轨道的长度 -> 如果同时在轨道中, i在j前的必要条件是i.s<=j.s和i.t<=j.t
3.小站工作人员可以任意安排这些火车进站的先后排列 -> 记忆化搜索
4.小站允许几辆火车同时进站或出站 -> 所有条件都可取等号
M = 1, f[i] = max(f[j] + 1)    (i.t <= j.s)
M = 2, f[i][j] = max(f[j][k] + 1)  (i.t <= k.s)
M = 3, f[i][j][k] = max(f[j][k][l] + 1) (i.t <= l.s)
初始化f = 0, 利用vis记录是否计算过, 各下标互不相等
*枚举过程中注意剪枝, 利用i!=j和i.s<=j.s,i.t<=j.t逐层处理即可
*[读题]明确要求的是什么, 存在哪些条件, 写list
*[未验证]先对以进站时间为第一关键字, 出站时间为第二关键字进行快排, 然后直接递推, 下标满足i < j < k < l

快餐问题meal[资源分配(不妨认为是背包)dp + 贪心优化] -> 类似, usaco 3.4.4 rocker
f[k][i][j]表示k条生产线生产i个汉堡, j个薯条时生产饮料的最大值, p[k][i][j]表示第k条生产线, 其他同.
f[k][i][j] = max{f[k][i-ki][j-kj] + p[k][i][j]}
sum[i] = sum[i-1] + A[i]
初始化f[1][i][j] = p[1][i][j], f[2..n][i][j] = -1, 复杂度O(N*100^4)
几个优化
1.注意到每种物品总数小于100, 最大产量的上限是lim = min(100/a, 100/b, 100/c, sum[n]/(a*p1+b*p2+c*p3))
2.为了避免数组越界, i的上限是min(lim*a, sum[n]/p1), j的上限min(lim*b, (A[k] - i*p1)/p2);
ki的上限min(i, A[k]/p1), kj的上限min(j, (A[k] - ki*p1)/p2) -> 对于逗号右边, 其实就是ki*p1+kj*p2<=A[k]
3.将程序中的min/max用if语句替代
4.对于每一套生产线, 尽量成套生产
[反例]
1 1 1
2 3 7
3
15 16 17
贪心可得最大值为3, 实际上15 = 7 + 3 + 3 + 2, 16 = 7 + 3 + 2 + 2 + 2, 17 = 7 + 7 + 3, 最大值为4;
利用优化1和2可以过5个测试点, 优化3可以进一步优化时间常数, 利用优化4可以过9个测试点
AC程序参见[此文]http://hi.baidu.com/zijingningmeng/blog/item/2761617e2afe7ae32e73b3b3.html
*调试过程中的主要问题是边界溢出(没有区分是否计算过), 变量名写错
*网上有说法表示去掉每种物品的件数限制后, 题目变成网络流 -> gXX证伪
*比赛的话, 不妨小数据(n<5)DP, 大数据(n>=5)贪心, 这样应该可以得到超过一半的分数

卡车更新问题truck, O(N^2), 1h
f[i][k]表示第i年某车已使用了k年
f[i][k] = max{f(i+1, 1) + R[0] - U[0] - C[k], f(i+1, k+1) + R[k] - U[k]}
初始化f[][] = -1, 边界条件f[i][k] = 0(i>N,k>K), 利用记忆化搜索实现
记录方案利用bool型数组prev[i][j][k]记录是否购买新车, 递归即可
*尽可能不换新车
*利用样例构造树, 写出状态即可得到方程
*测试点1存在等价方案, 已修正数据(可能需要Special Judge)
*f[i][j][k]中i和k可以唯一确定状态, 因而可以去掉中间1维

选课course[树形dp + 记录方案], 多叉转二叉实现
f[i][j]表示以i为根节点的树中, 选择j门课
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-1] + i.v) (0<=k<j)
初始化f[][] = 0
[记录方案]
利用print(i, j)递归, vis[i][j]表示是否已遍历, [边界]i∈[1, m], j∈[1, n]
right[i][j]表示f[i][j]是否等于f[i.r][j]
prev[i][j] = k表示f[i][j]由f[i.l][k],f[i.r][j-k-1]推得, 这时需记录p[i] = 1
从1到n判断p[i]直接输出即可.

8.5

广场铺砖问题floor[状压dp], 2h
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即为答案
对于每个f[i-1][S']利用dfs(当前行i, 当前行状态s1, 下一行状态s2, 当前行指针k)寻找S
if(!(s2 & 1<<k) && !(s2 & 1<<(k+1)))
 dp(i, s1, s2, k + 2);//存在连续两个空位, 即横放
dp(i, s1, s2 ^ (1<<(k)), k + 1);//对当前位取反, 即竖放
利用int保存每一位的摆放方式, 1表示当前行被上一行占用, 0表示当前行未被占用
[边界]k = 0, 递归过程中k > w则退出

硬木地板floor2[状压dp]
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即为答案
*实现无能, 最终放弃 -> 我应该去学位运算优化BFS -_-
*鱼牛《状态压缩》理解不能, NOI导刊朱全民文章code不全.
*耗时最长的题目往往不是表面上的难题, 而是那些被简单估计的难题

posted @ 2011-08-05 20:51 Climber.pI 阅读(538) | 评论 (0) | 编辑 收藏

Problem List (7.13 ~ 7.20)

posted @ 2011-07-21 15:55 Climber.pI 阅读(285) | 评论 (0) | 编辑 收藏

LGOI 2011 初赛备考

记得去年在纸上写过一份这样的东西，迎来的是exhaustive fail.需要明确复习重点是数据结构和算法, 考场上要注意出题规律和草稿的清晰性. 简单复习大概用了6个番茄钟.

1.表达式树
[中缀] (a + b) * c + d * c
(((a + b) * c) + (d * c))
[前缀] +(*(+(a b) c) * (d c))
+ * + a b c * d c
[计算方法1] 压栈(前缀 -> 从后向前)
[计算方法2] 括号(opt后) -> 中缀

2.二分查找的平均次数 log(n+1)-1

3.heap的实现
[up] while(k > 1) 比较 交换(h[k], h[k/2])
[down] while(2 * k <= n) 比较 交换(h[k], h[2k + 1(小于n的话)])

4.排序算法的稳定性
[稳定]插入排序、冒泡排序、归并排序、分配排序(桶式、基数)
[不稳定的]直接选择排序、堆排序、shell排序、快速排序都是不稳定的排序算法。
[稳定排序]http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/chapter7/01/05.html
[排序原理]http://hi.baidu.com/cuifenghui/blog/item/0587932b039557f9e7cd4051.html

5.出栈序列
一个数列满足条件，当且仅当每一段单调递减数列要么不存在空缺（即为公差-1的等差数列），要么它的空缺在之前全部已经出现。

[充要条件]若出栈序列合法，则一定不存在1<=i<j<k<=n，使s[j]<s[k]<s[i]

6.邻接表的插入操作(链表的插入)
next[e] = first[u[e]]; first[u[e]] = e;

7.逻辑表达式恒值
注意符号, 转化为分情况表示的函数

8.叉积的计算(特别注意第二个负号)
|i j k|
|a1 a2 a3|=i|a2 a3|-j|a1 a3|+k|a1 a2|
|b1 b2 b3|  |b2 b3|  |b1 b3|  |b1 b2|

9.阅读程序注意意图, 草稿的清晰度(减少乱划)

[RAM]http://baike.baidu.com/view/3558.htm
随机存储: 访问时间与位置无关
[Hash]http://www.nocow.cn/index.php/%E6%95%A3%E5%88%97%E8%A1%A8
[拓扑排序(DAG)]http://zh.wikipedia.org/wiki/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F\

posted @ 2011-05-14 19:21 Climber.pI 阅读(4691) | 评论 (0) | 编辑 收藏