2.6
poj 3660[Floyd]
[题意]
给定n个点, m条有向边, 判断有多少个点的位置唯一确定.
[做法]
从对每个节点的度分析入手. 利用Floyd传递闭包, O(N^3)足矣, 统计所有 入度+出度 = 顶点数-1 的点的个数, 显然如果一个点x, 与其他n-1个点的关系确定, 那么这个点的位置可以确定.
*一开始从度的分析入手(这是对的, 但是要传递闭包), 之后认为是拓扑排序, 在这之后就没有思路了. 但事实上这时候不应该看题解, 至少应该进行30min的思考.
*传递闭包有O(N^2)的做法, 参见去年的shock, 大意是每增加一条边(x, y), 对于任意(a, x), 使得(a, y)连通; 对于y的处理同理.
*每周的训练时间大致是周一下午, 周三一节课.
2.8
poj 3661[DP]
比较奇怪的DP, 去年查阅各种题解后A了, 今年还是不会做 = =|||
[状态]f[i][j]表示第i秒后, 体力值为j时的可以到达的最大距离.
很自然的得到了第一个方程
f[i][j] = max{f[i-1][j-1] + d[i], f[i+j][0]}
很明显两个状态要求的规划方向矛盾.
于是自然的YY了一个错误的方程
f[i][j] = max{f[i+1][j+1] + d[i], f[i+j][0]}
但事实上应该这样考虑
f[i][j] = f[i-1][j-1] + d[i]
f[i][0] = max{f[i-1][0], f[i-j][j]} (i-j >= j && j <= m) => (j <= min(i/2, m))
即对不同的规划方向分别处理.
*本题的关键即对不同规划方向的处理, 其实想一想不见得想不出来
2.13
poj 3663[数学/二分/枚举], 1h
很简单的题目, 但是由于各种细节考虑不周, 连对拍在内写了1h = =|||
[1] 显然可以O(N^2)枚举, 然后随便排序一下, 就可以0.6s通过了.
[2] 我想到的一种很疼的O(N)做法
(1) Cnt[n]表示1..n的值的个数, 可以利用前缀和得到
(2) 对于每个L_i, 累加Cnt[S - L_i] - (2*L <= S), 需要讨论S - L_i >= Max{L_i} 和 S - L_I <= 0的情况
(3) 显然每对数都被计算两次, 输出ans/2即可
[3] 官方题解的O(NlogN)做法
(1) 排序
(2) 对于每个Lower, 计算满足题目的最小Higher, 累加Higher - Lower即为答案
poj 3664[排序]
利用qsort对A[]间接排序, 然后利用O(K)的时间循环检查最大值即可, 复杂度O(NlogN)
poj 3665[模拟]
很像是数据结构题的小范围写法 = =|||
按照题目模拟即可.
2.20
poj 3662[最短路+二分]
[题意]
给定N个点, P条双向带权边, 其中K条边的权可以为0, 求最大边权的最小值.
[做法]
根据描述很容易想到二分, 注意到题目对前K条边的具体情况没有要求. 用f(M)表示最大边权为M时是否可行, 把边权大于M的边赋值为1, 小于M的边赋值为0, 求最短路即可.
*这里并不能使用BFS求最短路, BFS仅在无全图中可求最短路.
*注意二分的写法, 可以打出f(M)的值观察条件
*注意无解和0的区别
3.5
MAR12 Silver[未实现]
P1
[Brief]
在1000*1000棋盘上从(x, y)到(1, 1), 给定N个定点, 最少通过N个定点中的几个点.
[Solution]dij+heap, O(ElogV)
对每个点u, 如果其周围有定点v则 w(u, v) = 1, 否则w(u, v) = 0. 易知|V| <= 4*1000^2, 直接求(x, y) 到 (1, 1) 的单源最短路即可.
P2
不会做...
P3
同上 > <
3.12
MAR12 Bronze[我堕落了...]
P1: std将17拆分为16+1, 从而避免了进制转换.
P2
[Brief]
从(0, 0)开始, 仅在N个顶点可以转弯(90或180), 求有多少序列可以仅经过一次所有点, 并回到原点.
[Solution]
O(N!)生成序列, 直接利用坐标判断是否合法即可.
P3
[Brief]
给出一个序列(L <= 10^5), 每个字符可能是三个操作符F/L/R其中之一, FJ打错了一个字符, 试统计可能到达多少种不同的终点.
[Solution]
(1) 扫描序列, 记录每个点的位置, 可以得到任意两点之间的向量.
(2) 枚举每个位置可能的错误字符, location(n-1) + (n -> dimension)即为答案.
(3) 记录每个可行终点, 利用排序去重.
总复杂度O(N+N+NlogN) = O(NlogN).
3.15
MAR12 Silver
flowerpot[Heap/二分+RMQ]
[Brief]
给定N个坐标, 满足|y_j - y_i| >= D, 求|x_i - x_j|的最小值, 若不存在最小值则输出-1.
*题目真心看不懂, 看了样例才懂了.
[Solution]
[1] O(N^2)暴力枚举每个坐标
[2] O(NlogN)
(1) 对x升序排序
(2) 求出y的区间最大/小值
(3) 二分|x_i - x_j|, 这里需要记录对于每个x_i, x_i+D的位置(可能不存在)
-> 这个思路非常麻烦, 不可行
[3] O(NlogN), 利用Heap
和我最初的想法一致.
(1) 对x升序排序
(2) 对于每个x_i, 找到最近的x_j, 满足|y_i - y_j| >= D
事实上(2)可以进一步强化为|max{y} - min{y}| >= D, 也即若区间[i, j]满足题意, 但|y_i - y_j|不满足题意, 则其中必有子区间满足|y_i - y_j| >= D
[译自官方题解]
我们首先对所有点的x进行排序, 然后利用一对竖直的扫描线, 从左至右遍历整个平面. 一对扫描线之间的点的y值, 利用一个能够快速查找最大/最小值的数据结构存储, 例如STL multiset(如我们在下文所使用), 或者一对堆. 每当最大和最小的y的差至少为D时, 我们检查此时是否得到目前位置的最优结果, 之后将左扫描线向前移动. 否则, 我们将右扫描线向前移动. 算法总的运行时间为O(NlogN).
*对(2)进行强化后, 可以避免大量冗余操作
*强化后, (2)可以直接使用Sparse Table在O(1)得到最值. 效率应略高于官方题解.
3.19
[利用qsort对结构体排序]
int cmp(const void *a, const void *b){
point *A = (point*)a, *B = (point*)b;
return (A->x > B->x) ? 1 : -1;
}
*A是一个指针, *A = (point*)a表示把无类型指针a转换为point型的指针
int cmp(const void *a, const void *b){
int i = *(int*)a, j = *(int*)b;
return (i > j) ? 1 : -1;
}
i = *(int*)a表示先把无类型指针a转换为int型的指针, 然后利用*得到指针所对应的值
flowerpot[区间扫描+RMQ(Sparse Table)], 40min
(1) 对x升序排序(由于之后需要得到区间最值, 直接对结构体排序, 而非间接排序)
(2) sprase_table
*f[i][j] = max{f[i][j-1], f[i + 2^(j-1)][j-1]}, 初始化f[i][0] = P[i].y
(3) 区间扫描, 初始区间[i = 1, j = 1]
i) 若区间[i, j]满足题意, 尝试更新答案, ++i
ii) 若区间[i, j]不满足题意, ++j
*对于操作i, 此时区间合法, 为了得到最短区间, 左指针右移.
landscape[DP, 编辑距离], 1h
[Brief]
给定一个长度为N(N<=100)的序列, 序列中的每个元素权重为a_i(Σa_i <= 1000), 对A_i加1需要付出代价X, 对a_i减1需要付出代价Y, 把1个单位从a_i移动到a_j需要代价(j-i)*Z, 求把序列a_i变换为序列b_i(Σb_i<=1000)的最小代价.
[Solution]
[1] 最初由N的范围猜测是DP, 用f[i][j]表示前i-1个元素已符合题意时, 第i个元素权重为j时的代价. 遂发现此时存在后效性, 无果而终. 进而猜测可能是网络流模型, 参看题解.
*和GDKOI 2012 Day1一样, 最初的想法是正确的, 略深入的想法是错误的, 但此时切换角度思考就能得到正确结果.
[2] 换一种角度, 我们考虑每个代价的位置序列A_i, 变换为B_i. 序列A_i和B_i单调不降. 考虑到题目中的三种操作, 套用"编辑距离"模型.
[状态] f[i][j]表示A_1..i和B_1..j符合题意时的最小代价
[方程] f[i][j] = min{f[i-1][j] + Y, f[i][j-1] + X, f[i-1][j-1] + Z*|A[i] - B[j]|}
[初值] f[i][0] = Y*i, f[0][j]= X*j
*对于确定大致方向的题目, 可以分别考虑题目中涉及的几个量, 进而得到解法.