2012年5月4日
#
不管怎么说还有个三等, 退役了, 随意了. 只是深圳又从B类市掉到C类市, 大概是对不起是后人了. 看着wx神牛最后一年挂了, 叹息而已.
[Day0]
发现宿舍比较坑爹. 晚上看tree dp无能, 翻了一下前几天的problist和白书, 找wx神牛要了SCC模板, 结果瞬间理解了. 只是没学习BCC, 机缘巧合? 教ylt SPFA的数组模拟链表实现. 和深中众去逛二中, 发现二中各种花前月下, 各种幽静之处. 没延续NOIp和GDKOI Day0乱逛的习惯. 真是些语无伦次的描述.
[Day1]
今天题目描述异常简洁, 于是读题的过程同样非常迅速, 但是几乎没有题目进行了深入的思考. P1一看就是暴搜, 一开始却算错状态, 以为是O(3^N), 于是认为GDOI难得出了一次送分题. 后面越看越水, P2暴力30, 似乎可以用tire. P3 无思路, 似乎是双连通分量, 但是考前复习的时候排除了. P4是数学题, 直观的想法是打表找规律. P5题目描述很长, 开始没看.
P1的DFS打错了多次, P2的字符串排序也打错了多次, 而且由于rank数组写错, 直接爆零. 很明显应该看清题目, 此次的样例调试性较好, 若调试性较差可能引起更大的问题. P4先打了暴力生成, 然后发现30%的速度非常快, 只是单独考虑各个位, 想通过某个特征数字确定答案. 事实上应该求和, 所的序列单调增, 然后可以通过二分得到答案, 于是可以过50%. P3想了20min, 结合数据范围用Floyd YY了一个错误的贪心, 骗了25分, 大概是改成等权图, 对于度为1的点, 成对连接距离最大的两个. P5可以看出要使用状态压缩, 但是实在想不出方程. 之后在P5的暴力, 死磕P1, P4之间犹豫. 最终选择死磕P1, 利用直角三角形的性质，枚举不妨或放在任意两边. 可以利用背包判断第三条边是否存在，复杂度$O(3^N \cdot N^2)$, 但是之后复评发现是错的. 做法完全正确只是DFS多写了一行. 这大概是我参加了三次GD字头的比赛，为数不多的在现场想出AC做法的题目. 由于第二题对于样例的大意, 丢了30%.
最终结果: 135 = 70 + 0 + 35 + 30 + 0
中午由于wx打算讲题, 于是又萌生了录像的想法. 下午还上去酱油了一下, 尽管讲错了.某天晚上脑子一抽，发现做法其实是对的，但是我手贱把$O(3^N)$写成了$O(4^N)$. 复评的时候有幸见到了wqc同学. 晚上除了整理视频就是各种颓废, 大概和神牛看了一集新的TBBT.
[Day2]
前一天晚上心情低落, 一直延续到今天. P1是数据结构, 目测可做. P2数据结构. P3 DP. P4 搜索. P5 博弈论. 写了P1的60%, 很显然的数组模拟, 数据范围比较厚道. 但是想AC算法一直想利用vector和维护坐标偏移, 思路完全南辕北辙, 实际上对于每种颜色应该分开考虑, 用0/1表示该点是否存在, 利用BIT维护区间和. 或者进行离线处理. 也不见得想不出来, 考前几乎没有进行BIT的模型识别, 结果如此也是可以预料到的. P2在最后1.5h写了O(N^4 \cdot M)的暴力查询, 用二维BIT查询矩阵和, 大概能过若干个测试点, 结果全崩溃了, 原因不知. 正解大概是转化成线段树, 前几年有个类似的题目. P3对于30%算法写了SCDP, 但是没调出来, 原因未知. 正解大概是对于条件进行简单的分析后, 转化为背包模型, 可以通过50%. 然后利用偏序关系优化. P4 20%可以一遍BFS得出结果, 但是没写; AC做法大概是状态压缩BFS. P5 20%可以记忆化搜索, AC算法思维难度极大, 现场只有卢神A了.
最终结果: 60 = 60 + 0 + 0 + 0 + 0
中午和tzz聊了聊, 觉得深圳14er的OI还是挺有希望的…只是下午就被撵回家了, 草草开局, 草草收尾, 如此而已.
考前问段神如何准备, 段神说”我是反面教材”, 令人唏嘘的是, 我大概成了反面教材2.0. 考前速成STL和数据结构, STL用了<pair>, BIT学的比较多, 但是最终没搞出模型. GDOI和GDKOI一样, 几乎看不出任何非显然的东西, Day1的状态有点莫名其妙, 策略比较正常, Day2异常低落, 使用了很奇怪的策略, 于是装13装过头了, 数据结构磕傻了, 集合状态DP从未写过却在考场上YY. 其实是新一轮的瓶颈期, 思维能力不适应知识量, 代码能力差强人意. 反正NOIp之后就放弃了. 结局如此, 意料之外, 情理之中, 差强人意.
其实还是太弱了, 思维局限很严重, 训练方式同样存在盲点. 起步太晚同样是一方面, 结局如此, 也罢, 也罢.
退役了, 一段生活的结束, 也许是暂时的离开, 也许是永远的离开.
一局终了, 从开始到结束经历了三年, 挺长的.
2012年5月1日
#
高中OI生涯结束. 可能是暂时的离开, 或是永远的离开. 也许会写一篇东西纪念.
大概是初三以来的代码, 按照日期整理, 可以对照Problem List. 题目的话, 参看Problem List上的来源吧:
/Files/Climber-pI/code.7z就这样了. 保送生考试, CMOp 2012.
等待着尘埃落定.
3.31
(1) 如何确定对那些题目进行深入思考
(2) 即使全打暴力不见得打得完
(3) 数论?
(4) SC DP?
GDOI 2011 Day1分析[未实现]
P1, 直接模拟, AC.
P2, 生成子集+高精变形, 8
P3, 暴力模拟, ?
P4, 快排, 4
P5, 暴搜, 12
大概是40 + 8 + ? + 4+ 12 = 64.
4.7
US Open Silver Division, 2h, 未实现
P1_unlock[DFS-ID + 二分]
[Brief]
在10*10的方格中, 有三个连通块, 对于每个连通块可以向四个方向移动, 求使得三个连通块互不相邻所需的最小移动次数.
[Solution]
---------|
-++++++++|
--------+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|||
分析:
(1) 大概最小移动次数的最大值不会超过20, 如上图. 移动次数的上限大概略大于 相连的边数/2.
(2) 可以发现, 每次的决策必然小于3*4 = 12种, 可以利用一次Floodfill得到不同连通块之间的相接关系, 显然只有相对方向有一方相连, 或者均不相连的部分可以移动.
可能的优化:
(1) 两个相连的连通块, 向相反方向移动是互相等价的.
(2) 若在某个方向能够移动的话, 一次移动到位.
*复杂度很难分析, 应该能通过大部分测试数据.
P2_bookshelf[DP]
[Brief]
给定N个长为W_i, 宽为H_i的书, 书的放置必须按照给定顺序, 每层的长度限制为L, 试求书柜高度最小值.
[Solution]
很明显是O(N^2)的动态规划, 但是我只想到了O(N^2*L)的, 似乎是有限制的背包问题.
[状态] f[i][j][k]表示放了i本书, 在第j层, 该层剩余宽度为k的最小值
[方程] 略, 讨论第i-1本书放在哪层即可.
*正解可能通过单调队列或是别的手段降维, 也可能是重新设计状态.
P3_running[数据结构]
[Brief]
N头牛, 跑L圈, 圈长C. 给出每头牛的速度v_i, 求跑的最快的牛到达终点是, 牛群中超车了多少次.
[Solution]
正解复杂度大概是O(NlogN).
可以知道T = C*L / max{v_i}, 然后对于每头牛i跑了C_i = T*v_i/C圈, Σ[C_i-C_j]即为答案. 复杂度O(N^2).
大概可以总结几点:
(1) 对题目的分析能力显著下降
(2) 实现能力是个问题
(3) 如何恰当的对拍, 减少时间成本, 又不损失正确率
4.9
GDOI 2011 Day2 分析[未实现]
P1, 读题无能, 完全不能找到"瞬移水只能作用于到过的点的描述". 做法是prim+heap或kruskal
P2, 时间常数比较大, 很难写, 不一定能AC
(1) 读入每部小说后, 对小说中每个单词进行排序(字典序), 注意不区分大小写, O(n*NlogN)
(2) 将排序后的单词按照顺序插入动态数组(指针/数组模拟链表/vector实现), O(N)
(3) 按照时髦值对小说进行间接排序, O(NlogN)
(4) 对于每个询问, 在每部小说中进行二分查找, O(QlogN)
总复杂度是O(n*NlogN), n = 1000, N <= 20000, 预计能通过大部分测试数据
P3, 数论题, AC做法需要用到中国剩余定理, 下面是50%的做法
(1) 构造素因子表判断A的合法性
(2) 对每个1..N除去因子后, 求乘积末位
(3) 记录构成K的因子的次数, 计算多余部分乘积末尾
(4) 输出结果
复杂度是O(QN)
P4, 计算几何, 这种做法大概能通过大部分数据
对于每个方案, 计算每个点和其中相连两点构成三角形面积之和(利用行列式), 并检测点是否在五边形上, 复杂度是O(5MN)
P5, treeDP, 看不出来...比较容易想到O(N!)的暴搜
(1) 利用儿子兄弟表示法建树
(2) 生成N!种顺序, 判断其合法性(利用树的层次关系?)
(3) 维护最小值
可能的分数大概是40? + 40- + 20 + 40- + 12?
考虑实际情况, 可能是0 + 32 + 20 + 24 + 0 = 76.
于是综合考虑两天, 大概是64 + 76 = 140, 差不多二等了. 可能的预计是, 题目方向变化, 难度提升.
4.15 ~ 4.28
用CTex写的, 虽然只是徒劳的努力, 不过也有些初窥门径的味道. 结局意料之外情理之中, 倒也罢了. 段神说他是反面教材, 我是反面教材2.0
省赛备战实录.pdf
4.28
一个idea, 算法模板, 并准备若干测试数据, 以测试模板.
2012年3月19日
#
//大概在5周前就写完忘记发了, (2)和(3)大概胎死腹中了.
Climber.pI按: 时隔两年, 故地重游, 大概是高中OI生涯的第二次GDKOI, 也是最后一次GDKOI, 倒数第三场正式比赛了. 结果差强人意, 却也是意料之中. 也就形式化一把, 随记二三.
(1) 关于赛场
大概是前一天晚上一个人逛中大, 结果还没找错了讲评的地方 = =|||
Day0
大概就是各种聊天, 各种扯淡…没敲一行代码, 所以第二天就NC了
Day1
感觉组织工作比NOIp差很多, 比如进去都半个小时了才有水喝.
P1是个DP, 一开始根据数据范围准备的判断了复杂度, 但是后来鉴于题目的背景, 没有进一步的分析题意. 相反, 联想到了USACO Training的job, 二分+贪心经典题, 于是YY了一个贪心. 大概是把所有任务排序, 然后先选大的, 不能再装的时候就选小的, 居然还过了样例.
但当时对贪心的正确性毫无把握, 于是又写了O(a^N)的暴搜, 然后对拍. 大概是手生的缘故, 一个半小时才全部折腾完, 最终的结果是贪心错误. 于是有改写了一个小范围暴搜, 大范围贪心的程序. 当天中午重新看题的时候, 瞬间发现题目实际上是个变形的背包. 一旦在现场思维走偏, 总是难以挽回, 比如去年初赛, 比如去年Day1P2.
这时候有种奇怪的感觉, 时时刻刻想着放弃却又不敢放弃, 完全不能控制比赛进程, 只能顺着身体的惯性写题. 很像初中的时候跑1500的感觉, 带着种无法预知的恐惧.
P2是最短路, 由于边的权值为{1, 2, 3}其中一个数, 所以可以拆成若干边权为1的边, 从而用O(3n)的BFS AC.
当时读题之后认为dij+heap可以A, 但是几乎不记得怎么写了. 大致估计了一下, 认为SPFA可以过80%, 又担心SPFA敲挂, 又多敲了一个Floyd. 敲完折腾完对拍基本上过了3h了, 结果一直不同, 最后手工算了一组数据发现是Floyd挂了, 原因不知. 当然, 由于只开了80%的范围, 也无缘享受4s时限优惠了.
P3是个数学题, 当时只有40+min, 果断放弃. 但事实上30%的做法可以直接手算打表, 50%的做法可以利用DP, 甚至可以通过记忆化搜索打表AC.
P4是字符串, 由于不记得C++的I/O, 只能用字符数组敲. 虽然原理绝对正确, 但是最后还是没调出来.
于是Day1就结束了, 41算是意料之中, 值得庆幸的是SPFA没有写挂. 和NOIp一样, 依旧是全市第二, 尽管wx神牛这次102是我的若干倍.
Day2
大概是被Day1吓到了, Day2晚上回来还是敲了一会儿代码. 第二天的组织工作好了很多.
P1是数学题. 仔细读题之后很快发现了O(N)的做法, 联想到若干次被周期数列坑了, 果断找循环节, 发现前面一部分并不循环, 而循环节一定是N的倍数, 于是果断从后面找N. 考虑了50%的范围, 于是找了400N, 于是只过了60%的数据. 可以证明的是循环节长度不超过O(N^2), 但是我并不知道如何证明, 于是12分没了. 经过一番对拍, 时间已经过了近2h了.
P2的标准做法需要用到线段树/树状数组/平衡树等高级数据结构. 读题之后发现模拟十分好写, 但是由于当时考虑不周, 边写边调浪费了很多时间. 大概是利用一个数组记录某值是否存在, 然后利用数组模拟链表来实现. 终于调对了之后, 发现样例挂了, 特意问了评委30%的范围是否符合50%的要求, 得到肯定答复后. 遂放弃此题的进一步调试, 最终过了4个点.
当时还有70min左右, 在P3和P4犹豫了很久, 发现P4如果用Floyd的话还需要记录路径, 实在不好写, 遂放弃.
第三题是搜索, 可以利用DP预处理状态, 或者充分利用问题性质, 只枚举每个格子需要填否即可. 当时的做法是记录未填格子的位置, 逐个枚举, 如果某行全部枚举后进行可行性剪枝, 最后判断没列是否符合题意. 虽然思路绝对正确, 但是一直调不出来, 在最后几分钟突然发现是初始状态打成1了, 应该为0, 改了之后, 屏幕一闪, 样例过了. 最终过了6个点, 仅超时了两个点, 有两个WA的点多输出了一组解, 不知道哪里写挂了.
于是总分就是18 + 16 + 24 = 58, 又是全市第二, xh64第一, wx牛居然直接3分了…
至此, GDKOI的赛程结束, 在中大西苑一楼大堂看到一等和二等证书发完却不见深圳踪影, 怅然若失之感涌上心头, 差不多退役了.
(2) 一些人一些事
(3) 乱七八糟的想法
2.6
poj 3660[Floyd]
[题意]
给定n个点, m条有向边, 判断有多少个点的位置唯一确定.
[做法]
从对每个节点的度分析入手. 利用Floyd传递闭包, O(N^3)足矣, 统计所有 入度+出度 = 顶点数-1 的点的个数, 显然如果一个点x, 与其他n-1个点的关系确定, 那么这个点的位置可以确定.
*一开始从度的分析入手(这是对的, 但是要传递闭包), 之后认为是拓扑排序, 在这之后就没有思路了. 但事实上这时候不应该看题解, 至少应该进行30min的思考.
*传递闭包有O(N^2)的做法, 参见去年的shock, 大意是每增加一条边(x, y), 对于任意(a, x), 使得(a, y)连通; 对于y的处理同理.
*每周的训练时间大致是周一下午, 周三一节课.
2.8
poj 3661[DP]
比较奇怪的DP, 去年查阅各种题解后A了, 今年还是不会做 = =|||
[状态]f[i][j]表示第i秒后, 体力值为j时的可以到达的最大距离.
很自然的得到了第一个方程
f[i][j] = max{f[i-1][j-1] + d[i], f[i+j][0]}
很明显两个状态要求的规划方向矛盾.
于是自然的YY了一个错误的方程
f[i][j] = max{f[i+1][j+1] + d[i], f[i+j][0]}
但事实上应该这样考虑
f[i][j] = f[i-1][j-1] + d[i]
f[i][0] = max{f[i-1][0], f[i-j][j]} (i-j >= j && j <= m) => (j <= min(i/2, m))
即对不同的规划方向分别处理.
*本题的关键即对不同规划方向的处理, 其实想一想不见得想不出来
2.13
poj 3663[数学/二分/枚举], 1h
很简单的题目, 但是由于各种细节考虑不周, 连对拍在内写了1h = =|||
[1] 显然可以O(N^2)枚举, 然后随便排序一下, 就可以0.6s通过了.
[2] 我想到的一种很疼的O(N)做法
(1) Cnt[n]表示1..n的值的个数, 可以利用前缀和得到
(2) 对于每个L_i, 累加Cnt[S - L_i] - (2*L <= S), 需要讨论S - L_i >= Max{L_i} 和 S - L_I <= 0的情况
(3) 显然每对数都被计算两次, 输出ans/2即可
[3] 官方题解的O(NlogN)做法
(1) 排序
(2) 对于每个Lower, 计算满足题目的最小Higher, 累加Higher - Lower即为答案
poj 3664[排序]
利用qsort对A[]间接排序, 然后利用O(K)的时间循环检查最大值即可, 复杂度O(NlogN)
poj 3665[模拟]
很像是数据结构题的小范围写法 = =|||
按照题目模拟即可.
2.20
poj 3662[最短路+二分]
[题意]
给定N个点, P条双向带权边, 其中K条边的权可以为0, 求最大边权的最小值.
[做法]
根据描述很容易想到二分, 注意到题目对前K条边的具体情况没有要求. 用f(M)表示最大边权为M时是否可行, 把边权大于M的边赋值为1, 小于M的边赋值为0, 求最短路即可.
*这里并不能使用BFS求最短路, BFS仅在无全图中可求最短路.
*注意二分的写法, 可以打出f(M)的值观察条件
*注意无解和0的区别
3.5
MAR12 Silver[未实现]
P1
[Brief]
在1000*1000棋盘上从(x, y)到(1, 1), 给定N个定点, 最少通过N个定点中的几个点.
[Solution]dij+heap, O(ElogV)
对每个点u, 如果其周围有定点v则 w(u, v) = 1, 否则w(u, v) = 0. 易知|V| <= 4*1000^2, 直接求(x, y) 到 (1, 1) 的单源最短路即可.
P2
不会做...
P3
同上 > <
3.12
MAR12 Bronze[我堕落了...]
P1: std将17拆分为16+1, 从而避免了进制转换.
P2
[Brief]
从(0, 0)开始, 仅在N个顶点可以转弯(90或180), 求有多少序列可以仅经过一次所有点, 并回到原点.
[Solution]
O(N!)生成序列, 直接利用坐标判断是否合法即可.
P3
[Brief]
给出一个序列(L <= 10^5), 每个字符可能是三个操作符F/L/R其中之一, FJ打错了一个字符, 试统计可能到达多少种不同的终点.
[Solution]
(1) 扫描序列, 记录每个点的位置, 可以得到任意两点之间的向量.
(2) 枚举每个位置可能的错误字符, location(n-1) + (n -> dimension)即为答案.
(3) 记录每个可行终点, 利用排序去重.
总复杂度O(N+N+NlogN) = O(NlogN).
3.15
MAR12 Silver
flowerpot[Heap/二分+RMQ]
[Brief]
给定N个坐标, 满足|y_j - y_i| >= D, 求|x_i - x_j|的最小值, 若不存在最小值则输出-1.
*题目真心看不懂, 看了样例才懂了.
[Solution]
[1] O(N^2)暴力枚举每个坐标
[2] O(NlogN)
(1) 对x升序排序
(2) 求出y的区间最大/小值
(3) 二分|x_i - x_j|, 这里需要记录对于每个x_i, x_i+D的位置(可能不存在)
-> 这个思路非常麻烦, 不可行
[3] O(NlogN), 利用Heap
和我最初的想法一致.
(1) 对x升序排序
(2) 对于每个x_i, 找到最近的x_j, 满足|y_i - y_j| >= D
事实上(2)可以进一步强化为|max{y} - min{y}| >= D, 也即若区间[i, j]满足题意, 但|y_i - y_j|不满足题意, 则其中必有子区间满足|y_i - y_j| >= D
[译自官方题解]
我们首先对所有点的x进行排序, 然后利用一对竖直的扫描线, 从左至右遍历整个平面. 一对扫描线之间的点的y值, 利用一个能够快速查找最大/最小值的数据结构存储, 例如STL multiset(如我们在下文所使用), 或者一对堆. 每当最大和最小的y的差至少为D时, 我们检查此时是否得到目前位置的最优结果, 之后将左扫描线向前移动. 否则, 我们将右扫描线向前移动. 算法总的运行时间为O(NlogN).
*对(2)进行强化后, 可以避免大量冗余操作
*强化后, (2)可以直接使用Sparse Table在O(1)得到最值. 效率应略高于官方题解.
3.19
[利用qsort对结构体排序]
int cmp(const void *a, const void *b){
point *A = (point*)a, *B = (point*)b;
return (A->x > B->x) ? 1 : -1;
}
*A是一个指针, *A = (point*)a表示把无类型指针a转换为point型的指针
int cmp(const void *a, const void *b){
int i = *(int*)a, j = *(int*)b;
return (i > j) ? 1 : -1;
}
i = *(int*)a表示先把无类型指针a转换为int型的指针, 然后利用*得到指针所对应的值
flowerpot[区间扫描+RMQ(Sparse Table)], 40min
(1) 对x升序排序(由于之后需要得到区间最值, 直接对结构体排序, 而非间接排序)
(2) sprase_table
*f[i][j] = max{f[i][j-1], f[i + 2^(j-1)][j-1]}, 初始化f[i][0] = P[i].y
(3) 区间扫描, 初始区间[i = 1, j = 1]
i) 若区间[i, j]满足题意, 尝试更新答案, ++i
ii) 若区间[i, j]不满足题意, ++j
*对于操作i, 此时区间合法, 为了得到最短区间, 左指针右移.
landscape[DP, 编辑距离], 1h
[Brief]
给定一个长度为N(N<=100)的序列, 序列中的每个元素权重为a_i(Σa_i <= 1000), 对A_i加1需要付出代价X, 对a_i减1需要付出代价Y, 把1个单位从a_i移动到a_j需要代价(j-i)*Z, 求把序列a_i变换为序列b_i(Σb_i<=1000)的最小代价.
[Solution]
[1] 最初由N的范围猜测是DP, 用f[i][j]表示前i-1个元素已符合题意时, 第i个元素权重为j时的代价. 遂发现此时存在后效性, 无果而终. 进而猜测可能是网络流模型, 参看题解.
*和GDKOI 2012 Day1一样, 最初的想法是正确的, 略深入的想法是错误的, 但此时切换角度思考就能得到正确结果.
[2] 换一种角度, 我们考虑每个代价的位置序列A_i, 变换为B_i. 序列A_i和B_i单调不降. 考虑到题目中的三种操作, 套用"编辑距离"模型.
[状态] f[i][j]表示A_1..i和B_1..j符合题意时的最小代价
[方程] f[i][j] = min{f[i-1][j] + Y, f[i][j-1] + X, f[i-1][j-1] + Z*|A[i] - B[j]|}
[初值] f[i][0] = Y*i, f[0][j]= X*j
*对于确定大致方向的题目, 可以分别考虑题目中涉及的几个量, 进而得到解法.
//GDKOI 2012之前涉及的题目, 由此可见寒假真的什么都没做
1.25
air[二分图最大匹配 -> 最大流], 1h
[建图]
(1) 在飞行员u和外籍飞行员v间增加有向边(u,v), 同时增加源S到u的边(S,u), 以及v到汇T的边(v,T).
(2) 考虑到n<=100, 利用邻接矩阵存储, 上文增加边容量为1, 其余为0, S到T的最大流即为答案.
(3) 直接利用map记录u和v的对应关系
*数据的方案似乎不是最小字典序, 此外题目中未涉及方案的顺序问题, 暂不考虑.
path[最小路径覆盖 -> 二分图最大匹配 -> 最大流], 1h
注意到在路径覆盖中, 每个点只能被覆盖一次.
[建图]
将每个点拆分, 然后源S和汇T分别连边, 点间按照题目要求连边, 求最大流f即可.
显然如果要增加一个路径覆盖, 必须存在某点没有前驱(或后继), n-f即为所求.
[输出方案]
利用flow数组从1开始遍历, 用vis标记已访问点即可.
某题 by ftiasch
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.
http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
[O(log(n+m))做法]
你假设求第k大嘛, 肯定是这边来前i个, 那边来前j个. 然后二分i, 就有j了. 然后check一下合法否.
1.27
poj 2976[分数规划 -> 参数搜索]
[定义]一般地, 求max{a(x)/b(x)}, a(x) b(x)是实值函数, 且b(x)>0.
特别地, 如果max{a(x)/b(x)} ∈ (0,1), 称为0/1分数规划
[解法]
不妨设lambda即为所求.
显然满足 a(x)/b(x) >= lambda (注意大于等于号)
整理可得 a(x) - b(x)*lambda >= 0
显然存在任意x值满足lambda即可, 比如在这种情况下可以求函数最大值, 若最大值不满足, 那么显然这个lambda不会得到满足.
设g(lambda) = max{a(x) - lambda*b(x)}
分析可知:
g(λ) > 0 <=> λ' < λ
g(λ) = 0 <=> λ' = λ
g(λ) < 0 <=> λ' > λ
转换为0/1分数规划后, lambda ∈ (0, 1), 可以二分lambda, 注意a(x)和b(x)的求法因题目而异.
*比如最优比率生成树问题
*可以利用qsort直接对double排序, 写法和int一致, 需要注意排序时return x > 0 ? 1 : -1;不要返回0
*对于浮点误差, EPS = 1e-8, 越小越好(时间代价?)
1.31
GDKOI 2010分析[未验证]
30 + 20 + 12 + 12 = 74
30 + 40 + 20 + 12 = 102
考虑到实际情况, 以及对拍时间, 似乎150+并非不可能.
Day1
[1]load
AC, 改变松弛条件的最短路, 可以使用Floyd
[2]goodjob
30%, 裸DFS
AC, 状压DP
[3]pizza
30%-50% 乱搞, 利用最大m段和或者分数规划
AC 利用周期数列的性质?不明.
[4]plan
30% 暴搜?
AC 费用流
Day2
[1]collection
数学题, 通过简单的变形得到函数, 可以利用三分法或者Cauthy不等式求解
[2]cook
10% 暴搜, 生成全排列
AC 4维DP
[3]table
50% BFS
AC 双向BFS
[4]push
30% 模拟
AC 利用扫描线思想, 对坐标排序[具体不明...]
GDKOI 2011分析[未验证]
30 + 20 + 8 + 12 = 70
24 + 20 + 12 + 12 = 68
考虑到考场上可能的问题, 大概能保证100.
Day1
[1]sewer
DFS/BFS/...随便模拟
*小数据验证
[2]park
50% 对于每个长方形, 枚举每棵树是否在其上, O(NM)
AC 通过某种操作把验证某个树在某个矩形上, 由O(N)降至O(logN), 比如平衡树
*小数据验证, 如果构造AC算法必须对拍
[3]mission
20% 模拟
AC T_T我不会
[4]move
30% BFS
AC A*/状压DP
*小数据验证
Day2
[1]weight
30% DFS, O(3^N)
AC 分成两堆, 分别进行DFS, 然后对于每个砝码组合m, 在另外一堆里找n, 使得m+n满足题意即可.
*两种思路对拍
[2]ponytail
50% 简单分析之后利用整除性和打表暴力
AC 进一步的分析, 利用欧拉函数求解
根据题意
s >= x + y ...(1)
1/x + 1/y = 1/z ...(2)
由(2)可得, x+y | xy ...(*)
设(x, y) = d
可得x = d * x1, y = d * y1
代入(*)可得 x1+y1 | dx1y1
易证x, y分别和x+y互质
令d = t(x1 + y1), 代入即得
s = x + y = t(x1 + y1)^2
令n = x1 + y1, 显然满足题意的n的个数为欧拉函数φ(n), 满足题意的t的个数为[S/n]
综上可得, Σφ(n)*[S/n]即为所求.
[3]bright
30% 最大流
AC T_T我不会
[4]eight
30% DFS
AC 状压DP
=> 导出结论, 主要复习暴搜, 其次复习基本算法, 如图论若干, ST等.
2.1
rqnoj 70 八数码难题[BFS+hash], 2h
BFS实现, 利用hash判重(简单的取余法)
*移动步骤考虑不周, 可以直接利用数组存储, 四个方向分别为±1或3; 需要注意±1, 即左右移动后, 0必须在同一行
*hash写错
双向广搜, 扩展完一边的该层节点, 再扩展另一边的一层节点, 直到两边状态相遇.
http://longxiaozhi.is-programmer.com/posts/24858.html
实现无能, 遂放弃.
2012年2月11日
#
一周之前的此时, 我应该在广州的地铁上, 带着怅然若失.
41 + 58 = 99, 二等分数线102, 其实也没什么可说的, 寒假没干正事, 结局如此确是正常.
本来打算写点东西, 现在看最近几天完成这个难度有点大, 这个月抽时间写吧.
"心中随生一种风云际会但终将风流云散的感觉"
Day2结束的时候, 看着wx神牛的成绩单, 无比诧异, 虽然带着一大堆行李, 却也去复评了一吧. 反正没机会再以选手身份来了, 倒不如把流程都体验一遍.
这几天渐渐的开始筹划CMOp了, 其实也就半年而已, 我也不知道自己能走多远. 渐渐的回忆起了以前不长的MO生涯, 删了一下午文件, 删着删着又怅然若失了. 现在听轻音乐又和NOIp前一样, 又开始觉得一股绝望溢出胸口.
而我, 却不知道忧伤从何而来.
2012年1月3日
#
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题解.
2011年11月23日
#
好在一等了.
390 = 100 + 60 + 20 + 100 + 100 + 10, 省排62, 市排2.Day1 180, 省排152; Day2 210, 省排24.
主要是我AC了Day2P2, 那题全省的AC率只有10%左右.
和那天的密码一样, 真是Happy Ending.
-----------------------------------
但是, 身边的人的悲伤, 太多了
2011年11月14日
#
去年在纪中, 我看到成绩单直接傻了.
当年会写270, 结果DP写挂了, 数组开小, 应该30, 结果爆零;
第四题, 30min, floodfill没调出来
于是直接130, 所幸还有个三等
-------------------------------------
今年比去年淡定多了
Day0果断去逛纪中
Day1还是很紧张, 题目很简单, 30min想出算法, 题意抄了满满一页
被叉姐模拟赛的WA吓怕了, 第一题就开始对拍, 写完两个程序外加gen, 已经过了1h了
第二题写了四个版本的程序O(N^2) -> O(N^3) -> O(N^2) -> O(N^2)
一开始还看错题了, 还好查出来了.
担心时间不够, 没敢想O(N)的AC算法, 却用了10min敲了ST, 所幸敲对了
第三题果断写30分, 结果最后还是没调出来
Day2开始淡定了, 题目5min看完, 第一题瞬间想到AC算法, 二三题无思路
于是半个小时, 敲完了第一题, 看着旁边的人手足无措, 有些洋洋自得
接下来敲第二题的暴力敲了30min, 出去了一趟, 瞬间想到了二分+前缀和优化, 又是30+min, 敲了AC算法
纠结了一下二分, 然后开始看第三题
突然发现对拍器听了, 修正了一个边界问题, 和昨天相仿, 只剩下40+min了
很快的YY了一个40分的DP, 却对正确性和边界毫无把握
于是写了一个10分的, 然后想20分的时候, 突然找到bug, 修正了
交卷的时候, 瞬间想到20分写法, 但是没时间了
Day2的发挥还好, 看起来210. Day1看起来只有170, 不知道还会不会再出问题.
Ylen神牛貌似写了230 + 210, wx神牛可能500+, xh裸考看起来都和我成绩差不多....
看了WJMZBMR神牛的题解, 三题做法一样, 有些心安. 看了贴吧, 发现某题某种边界情况没有测试, 细想了一下好像没问题.
本来挺淡定的, 颓了一个下午又心慌了. 还有不少作业, 还是不能颓啊.