9.7
NOIp03 network[拓扑排序+模拟], 2h
注意读题, 题目中给出公式C[i] = Σ(W[j][i]*C[j]) - U[i](C[j] > 0), 特别注意成立条件.
把题目中给出的DAG反向, 对于C[i], 计算所有i的后继即可. 仅按照编号顺序输出大于零的神经元, 题目描述有误.
*注意分析题目, 不要急于敲程序.
*对于DAG上的拓扑排序问题, 一类如本题和project, 直接利用图; 另一类如frameup, 要输出完整路径, 需要按照定义消去点.
9.8
NOIp01 Car的旅行路线[预处理+最短路], 2h
1.构造矩形, 利用点积判断垂直, 利用平行四边形坐标关系求第四点坐标
2.构造图, 分别处理矩形内 和 不同矩形的情况
3.Floyd最短路, 对始末矩形判断最小值(此处假设始末矩形不同)
*需要特判始末矩形相同的情况
*注意double的强制转换
9.10
Tyvj Sept月赛(2.5h)
badgers, 0/1背包, 预计AC.
tree, 排序+乱搞, 看错题.
没有考虑深度>2的树, 似乎需要用到并查集.
number, 模拟, 预计30
显然top>=2^(n-1)
register, 没写, 只会30.
估计150. -> 50;
9.14
badgers, 二分+贪心, 40min, 1Y
对于n只badgers, 需要的食物总量tot = Σ(H[i] + (n-1)*G[i]), 二分求解即可.
*读题!
*写出关键函数
tree, kruskal变形
利用和kruskal一样的思想.
1. 对于每个点A分别属于各自的集合
2. 对边排序
3. 按顺序合并集合, ans += (num[i]*num[j]-1)(c[i]+1)+c[i];
9.26
NOIp10 关押罪犯[二分+BFS判重], 3h
1. 用邻接表存储边, 可以抽象为addEdge函数
2. 二分最大值
3. check函数用BFS染色判重, 枚举每一个点进行BFS.
*判重可以将数组初始化为-1, 然后判断队列中每个点的颜色是否为-1, 可以避免使用vis数组.
[注意事项]
1. 题目中仅给出无向边
2. 标记节点是否已读 -> 利用color即可
3. 遍历所有连通分量 -> 枚举每个点即可, 不必记录所有满足条件的边上的端点
9.27
NOIp10 关押罪犯, 30min, AC
1. 邻接表不熟
2. 二分打错
3. 不理解gXX程序判重原理
[原理]和我的做法一样, 不同的是gXX程序避免了对每个点重复染相同颜色, 因而需要进行染色的点必然未访问.
9.28
NOIp10 关押罪犯, 10min, AC
1. 邻接表first没有初始化
2. 边界打错
NOIp10 乌龟棋[DP], 20min, AC
注意到已通过路径可以用a+2*b+3*c+4*d表示, 因而设置状态为f[a][b][c][d];
f[a][b][c][d] = max{f[a-1][b][c][d], f[a][b-1][c][d], f[a][b][c-1][d], f[a][b][c][d-1]} + A[a+2*b+3*c+4*d];
*注意从第一个格子开始, 故A[0..n-1], f[0][0][0][0] = A[0], 注意下标实际意义.
*去年写错方程主要是没有考虑下标间练习, 直接套用NOIp05过河方程. 对于相似的题目, 最重要的是找到不同的部分.
9.29
NOIp08 双栈排序[DFS+剪枝], 50min, 30
1. dfs状态: (操作序列长度, 已输入序列长度, 已输出序列长度, 栈1深度, 栈2深度)
2. 可行性剪枝:
(1) 优先弹出符合条件元素(即等于 已输入序列长度+1)
(2) 找到解后立即退出
*标准做法的构造非常神奇, 解释动机无能. -> 观点来自gXX