3.19
MAR11 Bronze Division Analysis
charms 边读入边处理, 由于读题失误没有想到
pathfind -
spiral -
MAR11 Silver Division Analysis
meetplace[AC] O(N^2)的比较最早公共元素常数较小, 最大测试点0.019s
[算法1] O(N^2 + NM)
O(N^2)预处理, 枚举公共祖先j, 计算dist(a, j)+dist(b, j)的最小值; O(NM)针对每次询问取最小值.
[算法2] O(N + MN) 最大测试点0.03s
O(N)的预处理, 计算不同结点间距离, 设置表示变量; O(MN)的循环比较最小值.
packdel[-2] SPFA, INF值过小, 使用循环队列后[-1]
[std] Dijkstra + Heap, O(E lg V)
[实现]gXX指出, 此题卡SPFA
rotsym O(N^4), 暴力模拟
[std] O(N^2lgN) 生成任意两点的中点, 排序, 确定相同坐标区间长度j-i, 累加C(j-i, 2).
[实现]gXX曰:(1)数组开大 -> Error127 (2)long long输入使用%lld
3.21
fence6 研究sinya的质点系做法(Floyd求最小环)
3.22
ditch 23min AC 复习最大流增广路算法的邻接矩阵+BFS实现
fence6 AC 对拍sinya程序
3.23
ditch 11min AC 复习最大流增广路算法的邻接矩阵+BFS实现
fence6 22min AC 大量参考昨日程序
(1)质点边赋值错误
(2)循环取最小环G[k][rn[i][j]]打反
*机械记忆而非深入理解机理, 易忘
*Ctrl + click函数 -> 函数的实现代码
学习Floyd求最小环
for (k = 1; k <= n; k+=){
for (i = 1; i <= k-1; i++)
for (j = 1; j <= k=1; j++)
ans = min(ans, G[i][j] + G[i][k] + G[k][j]);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
3.28
fence6 40min AC 复习Floyd求最小环
[Linker error] undefined refetence to 'WinMain@16'
ld returned 1 exit status
-> main() 打反
3.29
fence8 40min
*fscanf 注意寻址&
3.30
buylow 高精度 & 判重无能
4.6
msquare 位运算判重, 未输出路径
4.7
msquare AC 位运算 35MB[MLE]
[4.10]位运算判冲实质与flag[][][][]..相同 -> MLE
4.11
如何估算答案长度
4.13
自动进行操作A, 原因不明.
如何避免颓废状态 ???
4.14
msquare AC
memcmp() 进行剪枝, 效率提升约60%;
*借鉴回溯思想, 枚举每种情况后应置换为原始状态.
[算法简述]
print() 输出路径, 注意方向.
encode() Contor展开编码判重.
trans() 置换表, 需要建立双方向表.
bfs() 队列使用state类型 -> 空间复杂度换编程复杂度
5.1
U S Open 2011 Silver Division
花了0.5h读题, 调了1.5h后第一题放弃了.
cornmaze
加了点花样的BFS最短路, 注意事项:
(1)瞬间移动用置换表解决, 需要注意新位置距离赋值
(2)(x,y)的代表关系
cowcheck
博弈问题, 没找到先手必败态, 简单分析的结果是初始状态在对角线附近的话先手必败
forgot
字串匹配, 似乎可以爆搜.
llang
原谅我找不到合适的模型描述