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