11.19
poj 1258[Kruskal]
和training的那题一样, 注意有多组数据
*数组开错, 没有区分MAXn/MAXedge
11.21
poj 1944[DP], unAC
没看出来是DP.
网上有两种做法:
(1) 三维DP
(2) 两个二维DP
快速读入 by gXX
int getInt() {
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
int ret = 0;
while ('0' <= ch && ch <= '9') {
ret = ret * 10 + ch - '0';
ch = getchar();
}
return ret;
}
qc #20:
getInt(), 0.06s
fscanf(), 0.2s
fstream, 0.35s
11.28
马走日问题[回溯], 1h
*lrp问了, 昨晚随便敲了一下, 发现想得乱七八糟, 果然要想清楚问题再敲.
求(1, 1)到(m, n)的路径数, 注意回溯边界即可.
NOIp2011P, 统计单词数[字符串], 1h
读入文章中的每个单词, 转换大小写后, 和已知目标单词比较. 记录相同单词数, 及每个单词的首字母在文章中位置即可.
*trick:
(1)文章中单词间可能存在多个空格, 因而需要读入每个字符
-> 需要注意的是, 需要删除pdf样例中多余的空格
(2) 文章中的单词长度可能远大于目标单词长度
*很像叉姐第一次模拟题的第一题
NOIp2011P, 瑞士轮[双关键字排序], 60, 40min
*样例说明很详细
需要注意双关键字排序和间接排序的区别:
(score[i] < score[j] || (score[i] == score[j] && i > j))
这里直接比较i和j, 而非id[i]和id[j].
*我觉得我这么废都能一等就是一个奇迹.. >_<
11.30
NOIp2011T, 选择客栈[数学], 2h
(1) 注意到各颜色间相互独立, 不妨单独处理
(2) 题目要求找到区间中存在任意满足条件点的区间个数, 即所有子区间的个数减去连续不满足条件的区间个数
*边界各种挂, 调试无能
12.5
NOIp2011P, 瑞士轮, 1h
*非常心不在焉
*注意静态查错 -> 如果出现循环, 大部分正确, 最后出现错误的情况, 极有可能是打错变量.
*注意数组的实际意义, 如存储标号还是值
(1) 以force[]为第一关键字降序, id[]为第二关键字升序排序
(2) 注意到过程中只有N个元素+1, 其余N个元素不变, 且对于变化或者不变的元素, score[]单调递减
故而对于每组选手(i, j), 利用队列A[]存储胜利选手, 队列B[]存储失败选手
(3) 按照双关键字合并队列A[]和B[]
(4) 将(2)(3)进行R轮, 输出id[Q]即可
NOIp2011T, 选择客栈, 1h
(1) 利用邻接表(数组实现), 按颜色存储客栈; 利用前缀和sum[i]表示1..i中cost_i <= p的客栈个数
(2) 对于每种颜色的每个区间预处理part[], 表示该区间是否符合条件
(3) 利用补集思想, 计算连续的不符合条件区间, C(2,N) - ∑C(2,N_i);
初始化pos = 1; 对于当前指针k, 若part[k] == 1, 则ans -= C(2, k-pos+1), pos = k+1; //pos记录当前第一个不符合条件区间的标号
*边界比较麻烦, 实现之前应该计算好
*尽可能分开不同步骤, 降低思维难度
12.12
NOIp 2011P, 表达式的值[表达式树], 1.5h, 80
*实际上50min就写完了, 查错查了很久
(1) 建树(左闭右开区间)
1) 找到括号外第一个+或*(即结合性反方向在括号外第一个运算符, 利用p记录是否在括号中)
2) 若不存在+, 令posO=posA
3) 递归build_tree(L, posO), build_tree(posO+1, R)
若不存在*, 则递归build_tree(L+1, R-1)
*[优化] 每次过程执行前, 脱去所有括号, 需要记录括号位置; 如果直接判断端点, 可能会出现(*)+(*)的情况, 导致WA
(2) treedp(其实就是简单统计)
1) op[i] == '*'
f[i][0] = (f[i.l][0] + f[i.l][1])*(f[i.r][0] + f[i.r][1]) - f[i.l,1]*f[i.r,1]
f[i][1] = f[i.l][1] * f[i.r][1]
2) op[i] == '+'
f[i][0] = f[i.l][0] * f[i.r][0]
f[i][1] = (f[i.l][0] + f[i.l][1])*(f[i.r][0] + f[i.r][1]) - f[i.l,0]*f[i.r,0]
*如果左子树或右子树不存在, 则f[i.k][0] = f[i.k][0] = 1(特判, 直接赋值引起错误)
*朴素的表达式树是O(N^2)的, 常数较小, 可以利用两个奇怪的栈做到O(N). by gXX
12.19
NOIp 2011T, 观光公交, 研究题解.[*待实现]
*真是每周一题我擦...
(1) 初步的分析包括不使用加速器时的时间计算, 以及对加速器对时间影响的简要分析. => 一个比较关键的结论是, 加速器对时间的影响一定是一个连续段
(2) clj题解给出了一种非常高效的O(M+NlgN)做法, 实质上利用堆处理了取最大值的问题.
(3) O(kN)的做法比较好理解, 实质是利用g(i)数组表示d[i]-1可以影响[i, g(i)]的时间值, 对于每个加速器找最大值即可. 看起来时间可能比较尴尬, 不过实测效果很好.
12.26
NOIp 2011T, 观光公交[贪心+递推], AC
[1] 10% 做法, O(N)
每个景点的最晚出发时间
time[i] = max{T_j} (A_j = i)
每个景点的到达时间
enter[i] = max{time(i-1), enter(i-1)} + D[i-1]
景点1..i的游客数为sum[i]
ans = Σ(enter[B[i]] - T_i) (1 <= i <= M)
[2] 20% 做法, O(N^2)
仅考虑一个加速器, 尝试将其用于任意两个连续景点间, 记录最小值.
[3] 60%做法, O(kN^2)
可用反证法证明, 当前加速器在最优位置时, 前一个加速器必然在最优位置. 符合贪心选择性质.
因而, 对于每个加速器, 重复20%做法即可, 非常易于编写.
[4] AC做法, O(kN)
分析易知, 若对景点i到景点i+1应用一个加速器, 景点i之前的距离不受影响, 景点i之后仅当enter[i]-1 >= time[i]有影响, 因而受影响的若干个景点必为一连续线段.
g[i]表示在景点i到景点i+1应用一个加速器, 连续段[i, g(i)]受到影响, 可得
[方程]g[i] = g[i+1] (enter[i] > time[i])
i+1 (enter[i] <= time[i])
[边界]g[N-1] = g[N]
(1) 初始化数组
(2) 对于D[i] > 0的段, 计算max{sum[g[i]] - sum[i]}, 应用加速器
(3) 对于[i, min(g(i), N-2)]更新enter[]和g[]
(4) (2)(3)重复k次
*60分做法的只有50行, AC做法也不过70行. 60分做法只要对题意理解清楚不难实现, 10+min可以写完. AC做法发现了连续性质, 利用递推将寻找最优位置的耗时从O(N^2)变为O(N^2), 有一定思维难度, 但是和Day2P2的难度相差无几.
[5] AC做法, O(M + NlogN)
基本同上, 无需使用g[]数组, 对于每个路径一次应用多个加速器, 利用堆求得最大值.
未实现, 参考clj题解.