看来寒假只能写完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 [未完]