#
9.5
Tyvj 1049 最长不下降子序列
f[j] = max(f[i]) + 1 (A[j] < A[i], 0 < j < i)
9.15
NOIp 2004 chorus
双向最长不下降子序列
9.16
NOIp 2003 network[UNAC]
拓扑排序
9.23
UVa 10305
拓扑排序[裸] -> 贪心实现
10.2
NOIp 2000 方格取数 O(N^4)
f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][j][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])
+ G[i][j] + G[k][l]
NOIp 2008 message O(N^3)
DP, 寻找各维数值关系, 计算确定第四维.
10.3
NOIp 2003 matches
建立数字表(对应match数), 枚举
10.5
NOIp 2006 budget 分组背包
预处理取消分组(生成各种情况), 01背包
NOIp 2003 tree 树形+统计DP
f[i][j] = max{f[i][k-1] * f[k+1][j] + a[k]} (i < k < i + l - 1)
10.8
NOIp 2005 river
线性DP+路径压缩(利用裴蜀定理)
10.12
NOIp 2004 fruit 小根堆
*复习堆的写法
10.19
nuggests 裴蜀定理 + 完全背包
10.26
(1)学习Union-set
(2)复习各种排序(qsort, bouble sort, merge)
10.28
1411 学习Prim
11.1
1386 枚举
11.2
1495 复习Flood fill
11.4
1451 复习DFS
11.10
NOV10 Bronze(daisy, marathon, mathprac)
11.11
water 枚举
11.14 NOIp 2007 Prob
count qsort + 统计
expand 模拟
game DP(高精度)[30]
11.15
NOIp 2007 game -> 高精度无能, longlong 无能[30]
11.18
NOIp 2004 alpha 暴力枚举 30
11.19
复习heap, dijkstra, SPFA, Krusal.
11.28 - 11.29
lrj第一次提供题目
12.1
UVa 11374 SPFA+记录路径[UNAC]
12.5
DEC10 Bronze(badrand, commas, boolclub)
12.6
1115
12.7 & 12.15
UVa 11374 SPFA+记录路径[UNAC]
求教gXX神牛, 对拍无能.
12.18
lrj第二次提供题目(至今未完成)
5.7
p1004 滑雪[2d最长下降子序列]
无思路.
p1005 采药[简单01背包], 调了1.5h
[spec,1d] f[j] = max{f[j], f[j - c[i]] + w[i]}, 能够有效避免f[i][j]中i的指代问题
*2d写法须注意f[i][j] = f[i-1][j]的值传递
for (i = 1; i <= n; i++)
for (j = T; j >= 1; j--)
if (j >= t[i])
f[i][j] = max(f[i - 1][j], f[i - 1][j - t[i]] + w[i]);
else f[i][j] = f[i - 1][j];
p1003 找啊找啊找GF[加强版01背包], 调了1h
读题分析后发现是0/1背包模型, 时间需要单独处理.(一开始认为要记录路径, 其实不用这么麻烦)
f[m][r] = max{f[m][r], f[m - rmb[i]][r - rp[i]] + 1}
t[m][r] = max{t[m][r], f[m - rmb[i]][r - rp[i]] + time[i]}, 如果f[m]..和f[m-rmb[i]]..相等,注意更新t[m][r]
[补]写rocker的时候想到一种方法，对于dp，维度往往是需要表示的量数-1，所以关于方程状态的表示可以从时间复杂度、空间复杂度、需要表示的量数综合考虑.此题中加上time的话，显然爆时间，然后从这个方向思考方程.
p1015 公路乘车[线性dp]
f[i] = max{f[i - k] + A[k]} (1 <= k <= 10)
p1011 传纸条[双线程dp + 时间降维]
注意读题, 题目中的来回等价为两次同时的单向过程
f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2], f[x1-1][y1][x2][y2-1], f[x1][y1-1][x2][y2-1], f[x1][y1-1][x2-1][y2]}+A[x1][y1]+A[x2][y2]
注意每个数if and only if取一次, f[x1][y1][x2][y2] -= A[x1][y1](x1=x2&&y1=y2)
p1014 乘法游戏[区间dp]
无思路
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
原谅我找不到合适的模型描述
3.12
MAR11 Bronze Division [AK]
[战术]先通读试题，想到大概算法，然后具体实施.测试了极限数据.
[注意]题目描述细节; 字母打错;
读题时间 27min
charms 69in
[大意]题目中给出一条链子，然后从中间吊起. 链子上还挂有链子，求每个链子在重力作用下的末端值.
[算法]O(N),做一个数组映射吊起后链子的位置，逐个链子计算，输出.
pathfind 110min
[大意]给出一个邻接矩阵和起点，算最短路.
[算法]O(N^2), bfs求最短路. 输出时利用flag变量, flag=0时输空格, 反之不输出.
spiral 53min
[大意]蛇形数阵
[算法]O(N^2), 若当前方向可前进, 继续填充; 反之，按照 右->下->左->上的顺序换方向.
3.13
USACO Contest get to Silver Division Success!
MAR11 Silver Division
[战术]通读题目，没有设计进一步的数据.
读题时间 22min
meetplace 90min
[大意]寻找树上任意两节点的最近公共祖先.
[算法]O(M*N^2), 期望得分30~50.
利用数组模拟链表存储树，对于每次询问用O(N^2)的时间用数组循环查找最近公共祖先.
[进一步的改进]把循环查找公共祖先的时间降到O(NlogN), 总复杂度O(N^2logN), 可以AC. 具体方式不明
packdel 44min
[大意]稀疏的无向图最短路
[算法]O(2N), 期望得分100, 裸的SPFA, 利用临界表存储.
spiral 63min
[大意]给出N个坐标，判断任意四点可成平行四边形的个数(包括重合情况).
[算法]O(N^4), 期望得分10~30, 操作数为C(4,N), 考虑常数的话N上限为200
利用四重循环生成子集(元素个数为4), 坐标判断(讨论AB, AC, AD为对角线的情况, A.x + B.x == C.x + D.x, y同理), 计数输出.
[进一步的改进]无
3.14
fence6 unAC
质心法，研究样例，发现缺少判断条件
3.15
ditch AC 学习最大流增广路算法的邻接矩阵实现，基本照抄lrj白书
*两点多边处理方法：合并
？如何用邻接表实现
3.16
ditch 30min AC 复习最大流增广路算法的邻接矩阵+BFS实现
*使用memset清空数组, 应在任何操作之前
*文件名(潜在问题)
stall4 38min AC 二分图最大匹配的网络流实现[参照Section 4.2.0 Text]
*起点和终点到对应点的流量限制是1而不是无限大, 因为流量限制对边而言
*注意两个集合的点的标号
3.17
ditch 15min AC 复习最大流增广路算法的邻接矩阵+BFS实现
*边权回溯修改错误
job 40min -
Welcome to the USACO submission gateway for the Elite 2011 March Competition contest.
You can submit SILVER solutions for three hours (or until the contest ends). The timeclock starts as soon as you read the problems!
仅此庆祝成功晋级的喜悦.
[题外话]因为party正在召开meeting于是非工作时间断网, 前一周腹痛, Training基本瘫痪.
2.28
camelot 50min UNAC
3.1
camelot
*队列尾指针r与行宽R重复定义 -> 常量应使用大写字母
*枚举坐标打漏
3.7
camelot 45min 16/19
解决输入问题
3.8
camelot 1h
样例未过，对拍无问题
3.9
fence4 0.5h 思路混乱
fence8 unAC 无向图最小环
利用质点系化边为点，然后用SPFA取最短路.
2.21
butter 17min 1WA
*数组开小
fence 70min 1WA 复习欧拉回路
[充要条件]每个点的度数均为偶数,或只有2点度数为奇数.
写了1h 70+行的DFS-ID不知哪里错了，标程十分简洁.
2.22
fence 10min 1Y 复习欧拉回路
rockers 9WA
*我的方程 f[i][j][k] = max{f[l][j][k-c[i]]+1, f[l][j-1][t-c[i]]+1} (0 < l < i))，O(N^4) -> 没有考虑不录的情况
参考了leokan程序 f[i][j][k] = max(f[i-1][j][k], f[i-1][j][k-c[i]]+1, f[i-1][j-1][t-c[i]]+1), O(N^3)
似乎是基于0/1背包问题
*改善状态转移从而避免求f[l][][]的最值
2.23
fence 13min 1WA
*深搜过程中不必使用break
*记录路径为p[++t] = k
rockers 7min 1Y
*状态转移与 待选择状态 顺序无关
heritage 15min 1Y -> 另:通过指针重建树,进行遍历
基本照抄lrj白书
*利用字符指针替代字符串传递(长度\起始地址)
kimbits 35min 1WA NAC -> 基本思想正确
2.24
heritage 8min 1Y 复习字符串指针写法
kimbits 22min 1WA
[分析]类似康托展开的思想，定义F(n,m)表示 ∑C(n,i)(0<=i<=m),显然若首位为1，则序号i必大于F(n-1,m),反之为0.
根据组合恒等式C(n,m) = C(n-1,m) + C(n-1,m-1),有F(n,m) = F(n,m-1) + C(n,m).
*因i越界，故使用double
msquare 30min 未完成
2.25
找Ylen要KOI题目,惊闻她一等.
http://u.youku.com/user_playlist/id_UMjIzOTYyODUy.html 题解视频
2.26
fence9 50min 4WA
复习 辗转相除法 Pick公式 某个几何结论
2.14
agrinet 29min 1Y
- 使用qsort进行结构体排序
int cmp(const int* a, const int* b){
edge* pa = (edge*)a, pb = (edge*)b;
return (pa->w > pb->w) ? 1 : 0;
}
couducters UNAC
butter UNAC
2.15
agrinet 15min 1WA
- 复习结构体排序.
butter 30min+? 3WA
*错误的变量名
*内存过小 -> 严格按照题目
2.16
butter 19min 2WA
*错误操作 -> 队列的进出
*错误的文件读入
=> 如何进行肉眼查错
URAL 1011 conductors
- 边界处理问题，需要注意，题目中区间的开闭.
-> *100 避免浮点误差，强制类型转换可能造成浮点误差!!
2.17
range 15min 1Y DP
- f[i][j] = min{f[i-1][j], f[i][j-1], f[i-1][j-1]} + f[i][j];
- f[i][j]表示以其为右下角的最大正方形边长
*变量打错count
game1 39min 1Y DP
- f[i][j] = sum[i][j] - min{f[i+1][j], f[i][j-1]};
- f[i][j]表示从i开始连续n个数先手取的最大值
*方程20min没想出来
*循环求值过程中，长度优先
2.18
[精度处理问题 by gXX]
#define EPS 1e-7
e.g. int(99.98*100)的正确写法int(99.98*100 + EPS)
2.19
GDKOI 2011 Day1[YY] -> Thk for Ylen.
第一题，暴力，觉得能A.
第二题，30%暴力；50%离散化，估计现场写不出来.
第三题，30%暴力，只会用Floyd求强连通分量.
第四题，似乎是生成某种子集，然后最小生成树，也许30%能过
理论估计最高值76，实际不出大错40+无压力.
2011.2.7
USACO Monthly Feb 2011
[读题模式]边读边做 -> 第一题读题出错 -> 浪费40min => 在不确定梯度的考试,通读全卷异常重要
40min时,开始崩溃状态.80min,崩溃状态结束.
最后超时1min -> 变量少了一个初始化 -> 写完后的静态调试非常重要
读题顺序 1 -> 2 -> 3. 解答顺序 1 -> 3 -> 1 -> 2
[dance2] 70min -> 30line
括号匹配,弄一个run变量记录'>'个数,出现'<'run-1.输出的情况:
1)illegal ->(1)途中run < 0 (2)最后run != 0
2)legal -> run == 0
[treats] 45min {读题} -> 77line
模拟,读题有难度.
题目中给出了一种启发式搜索(A*),要把最大值通过line row交换转换到(1,1).之后值同理,但不能交换已确定的row line.
定义check()函数检查row line是否交换,swap交换row line.利用check()循环求解即可.
[hexgon] 45min {坐标的意义} -> 42line
模拟:1)按题意填充矩阵;2)坐标判断可能值,加入队列;3)升序排序队列,输出;
butter 25min [未完成] SPFA
2011.2.8
humble 19min 1Y
butter 2h 2WA[SPFA]
(0)读题 -> 每个牧场可能有多个牛
(1)初始化 -> first[*] = -1 无从*点开始的边
-> d[*] = INF (* != k)
(2)SPFA -> 三角不等式d[v[e]] > d[u[e]] + w[e]
=> 若v[e]不在队列,(1)加入队列(2)更新距离d[v[e]] *
fence9 40min 9/12->TLE
利用行列式求面积判定点是否在三角形内,枚举
->皮克公式忘记
heritage 40min [UNAC]
使用<string>,无法编译
2011.2.9
USACO Monthly Feb 2011 [杯具的被封号了T^T]
**Cena -> 15/36
[dance2] AC.
fprintf (fout, "%slegal\n", bad || nesting > 0 ? "il" : ""
标程的 ?: 用的恰到好处
[treats] 调试未完
和标程思路基本一致，除了标程逐个元素判断，我用行列判断.
-> 行列判断如果出单行或单列数据就杯具了
butter 40min 1Y -> spfa主程序压缩至11行
重复定义变量;
看来寒假只能写完Chapter3,然后做相当于1-2个Section的Chapter4. -> 只能说稳定性有了提升,这应该就是重复做题的效果.
2011.1.30
rect1 90min 1WA.
逆序进行矩形切割:使用递归方式的矩形切割,实际上就是一种分治算法
(1)比对新添加矩形和已添加矩形
(2-1)若未覆盖，计算颜色面积
(2-2)若覆盖，删除新矩形，矩形切割(坐标比对)
[关于顺序]
矩形切割是一种平面上矩形的动态统计手段，因而统计和切割是同步进行的，所以必须逆序统计.若顺序统计，则必须把统计过程放在最后.
2011.1.31
NOI 1997 卫星覆盖 3/20
2011.2.1
stamps 15min 1Y.
rect1 42min 1Y.
[过程] 逆序添加矩形 -> 动态统计.
add-
1.添加矩形
2.判断覆盖 -> 补集思想,坐标必须使用闭区间.[卡了25min]
3-1 无覆盖则统计颜色
3-2 设置标准变量,切割矩形(4)
NOI '97 矩形覆盖 2h 19/20->{0.47s,352KB} [逆序切割] => 难度过大,最终放弃
[注意]判断覆盖利用了补集思想，所以必须是闭区间.
基本思想和算法 同 rect1.
[关于标程]Bvoid标程利用递归直接统计,0.28sAC. -> 差距
spin 40min 1Y 模拟
样例理解不能 -> 未读题[20min] => 不要臆断!!!
ratios 11min 1Y 枚举
2011.2.5
agrinet 11min 1Y.
hmuble 29min 1Y.
*思路错误,忽视异分子相乘的情况
(1)记录丑数，及每个因子所乘最大丑数
(2)去重,若新丑数等于上一丑数则不记录,记录因子所乘最大丑数
rect1 25min 1Y 注意输入
contact 2h 12WA
(1)以a,b分段读入字串 -> 利用二进制直接编码,在首添一,记录0开始情况;
(2)[qsort] qsort(set + 1, Max, sizeof(int), cmp);
int cmp(const void *a, const void *b){
if (flag[*(int*)a] == flag[*(int*)b])
return *(int*)a - *(int*)b;
return flag[*(int*)b] - flag[*(int*)a];
}
(3)输出:每6个换行,换行后无空格 -> 40min
kimbits 70min 2WA+1RE [UNAC]
利用组合恒等式C[k,n] = C[k,n-1] + C[k-1,n-1];
求值思想类似逆康拓展开.
2011.2.6
shopping 43min 1Y[DP]
SB做法:f[a][b][c][d][e] = min{f[a-1][b][c][d][e]+cost[a],..,优惠组s}
[min] 特殊处理0和INT_MAX -> 15min
-> f[a][b][c][d][e] = min{cost,优惠组};
-> 注意思考问题实质
game1 38min [UNAC]
轮流取数,状态设置错误:f[i][j] = max{f[i+1][j]+A[i], f[i][j-1]+A[j]};
range 40min [TLE 1点+MLE]
f[i][j][k] DP. O(n^3)
job 25min [未完]