#
其实是对最后一年NOIp的吐槽吧. 初赛后有若干个理由支持我去或不去, 有个理由是给Juda送书. 哦, 我应该伪装的高尚一点, 其实是去见证历史的乱象的, 最后一年保送的最后一门. 回来以后发现, 还有个理由, 自费旅游放松心情(好吧我是来观赛的…
虽然最想见的人都没去, 代码能力各种退化, 目测不写挂就二等, 不过怎么样就怎么样吧……
Day0
转车是种奇怪的事情, 不过深圳北站和广州南站都实在是很张狂的现代建筑, 空间非常宽广, 置身其中会深深的体味到自身的渺小.
似乎凡是带了"和谐号"的车, 似乎都是可以提前上车的. 听父亲讲, 像我这么大的时候, 买站票, 跟人去餐车蹭座位…制度尚未形成, 或者在变革途中的年代, 其实更容易产生丰富的人生经历, 倒是现在这样, 四平八稳, 更多的是平淡的味道. 轻轨这玩意明明就是城际地铁, 但是少了几分灵活, 出来之后摩的这个多……
雅居乐酒店我怎么觉得外墙有种欧式风格, 同房间的老师居然是四会的…然后发现5F几乎被深圳众占领了. 出去逛了一圈, 还有个大妈把她哭闹的孩子往我这边推, 说”我不要他了”, 当时我就____, 我长得这么像大叔么(
酒店外面的桂花很香, 不是有句话叫”金秋十月, 丹桂飘香”么, “回忆像一场艳丽烟火, 伴随着喜怒哀乐终究要散落”, 倒是隐隐约约记起去年自己一个人在纪中逛了一圈. 出门走了一段, 在某个路口突然觉得有些时空错位, 隐隐约约的觉得像是太原. 走了很久, 直到人困马乏, 在一条长长的河旁的堤岸边上散步. 印象最深的是一所小学, 进去有座门楼, 同样是校友捐赠, 满满的历史的痕迹, 背后漆喷上去的字实在是很不应景. 小学的门口是形形色色的文具店小吃店各种才艺培训, 接孩子的家长几乎都骑着摩托.
晚上和深圳众出去吃饭, 和chj师弟以及深外的yy去扯淡了, 对着某份一堆超纲知识点的大纲评头论足一番, 结果后来各种超纲. = =||| 给Juda神牛送书, 然后被涮了呜呜呜呜, 虽然Juda那么像初一的小盆友.(> <) 然后晚上就和知远兄谈理想谈人生谈爱情去了, 其实熟识的人都挺像的, 明明专心致志在别的地方, 结果文化课就莫名其妙的考好了, 除了文理, 其实两个人太像了. 或者说, 本来就不该区分文理, 希望他博雅杯能过吧. 最终晚上只复习了怎么写gen和对拍器.
Day1
一上车就看到卢牛以及身边的妹子, 不科学……
一进去就在写gen和对拍器, 然后写读入, 然后就开场了. 密码和实事结合很紧嘛. 读题很慢, 但是没有像去年一样, 写了满满一页的题目要点. P1是个很水的字符串, 不过据说两位省队跪掉了(>_)<). P2是<局部调整法在信息学竞赛中的应用>的例题, 只要想到贪心的话, 60%, 然后要写单精乘除. 当然, 作为低智商选手, 我花了40min最终YY出来二分+集合状态转移, 40%, 当然没写……P3的裸模拟50%, 预处理一下70%……Day1以100+20+50告终(要是写跪了呢 T_T)
下午在看某部很奇怪的电影…果然带了什么都不会干正事, 一直在刷机……其间拜读了clj的题解. 以及听prof.guo讲了半个小时, 包括复赛名额如何决定, GDOI/GDKOI可能的变化etc, 其间东莞的教研员由于邮箱查看不及时被点名批评”不做事”, 我大深圳就呵呵呵呵吧. BTW, 第一天实在各种热, 于是就把衣服留在401了, 还去麻烦了moreD大神……跟wx神牛各种短信若干, 其实他可以和cxq一样来观赛嘛 >_<
晚上继续颓废, 看完conan, 听知远兄给的*.wav, 听了一半被Juda拉下去面基, 然后被他们的小朋友膜拜…于是…于是…Day2果然就跪了(
Day2
进去以后继续敲gen和对拍器, 一看题就跪了. p1是扩展欧几里得, 当时一看是不定方程, 变形以后果断裴蜀定理, 易知a,b互质, 然后就不会了……可以知道x<=b, 虽然后面想到辗转相除, 但是没多想一步, 对于2的幂次观察到x为a%b或b-a%b, 对于a-b=1或2的情况得到了结论, 不过不能推广, 数学渣啊… = =||| p2 30%是二逼模拟O(NM), 想了10min就发现可以二分+BIT, O(NlogMlogN)不过只能70%, 但是BIT/zkw线段树都不会写了, YY了半天没YY出来. 好吧据说正解又是前缀和+二分, 作为去年A了那题的群众我哭了. P3一上来就想到LCA, 大概可以O(N^3)搞出任一点对距离, 但是军队实在不知道怎么移动……最终特判了0和-1, 希望数据比较科学两个点都有. Day2大概60 + 30 + 10(20?), 两天加起来270吧, 目测一等线300-330, 求二等 T_T
目测今年深圳两个一等的样子, 看他们写跪多少吧……
回来的路上终于看完TBBT, 艾米又在体现”女孩子好麻烦”了…路上看到zxk的感伤段子, 作为见证历史的观众, 我觉得大可不必如此悲观, 至少我还是相信历史的车轮会滚滚向前的.
一个人去, 一个人回, 孤独落寞的征途果然如此么.
10.22
P1326, SPFA.
最短路模板题
P2022, 模拟.
维护长度为N的序列即可, 对于每个操作注意细节.
P2017, 搜索
贪心上界, 累加下界, 中间暴搜. 昨天打漏了\sum C_i的初始化, 把C_i和A_i打混了.
*据说数据弱到直接交下界就A
*需要复习下gen怎么写了
P2021, 位运算+DP
and, 统计连续的1, 直接计算
or, 统计连续的0, 间接计算
10.27
Vijos Monthly Oct12
P1742, 模拟.
平均数 加权累加即可;
中位数 qsort排序, 按照奇偶分类输出;
众数 排序后累计不同的值和出现次数, 排序输出;
P1745, 贪心?
数据范围否定了DP, 但是作为贪心范围确实有点小. 按照切割的权w_i排序, 如果w_i相等, 则行/列多的先切. 排序后累加即可.
如果f[i][j]来dp的话, 大概是O(N^3)的时间, O(N^4)的空间...
-> 很好, 爆longlong了...T_T
P1746, 图论.
最短路变形, N = 300. 直接利用Floyd得到所有最短路, 对于一对u,v, 分别枚举N个节点, min{G[u][i] + G[i][v]}即为所求.
P1747, ?.
30%明显是搜索, 但是我实在不会暴力了, 连方向都不知道. 我想起来今天AIME那几个暴力算的圆...
*对于算法, 在实现前必须充分讨论细节. 在实现过程中修改细节及其浪费时间.
*对拍 & 特别小数据的构造需要复习, 正确率.
*各类算法模板的整理.
-> 150/300, 实现能力啊啊啊啊
http://www.vijos.org/Discuss_Show.asp?DisID=55613
10.28
Vijos T1062, 实在没动力写, 就YY了一下(...
P1, 十进制小数转二进制小数
不会...乘二取整法套不上
P2, ?
只会暴力做法, O(N!)生成序列, 然后根据约束条件剪枝, 譬如:
(1) 贺卡的时间顺序
(2) 每个人的时区互异性
(3) 时间范围
其实手算可容易了...(
P3, 模拟
[70%做法]
(1) O(N^2)把每个区域盖房子的权值预处理一遍
(2) 盖N次房子, 每次扫一遍找最小值, 然后标记相关区域不可用O(N^3)
*可能的房子数量上限好像是大于N的 ...
[AC做法]
(1) O(N^2)把每个区域盖房子的权值预处理一遍
(2) 把每个区域的权值升序排序, 依次选择, 对于选中的区域, 标记其周边区域不可用, 复杂度O(N^2)
10.12
NOIp 2011 初赛, 84; 注意读题, 思维盲点;
10.13
NOIp 2012 初赛, 71.5.
(T_T 2.5分到哪里去了...)
10.19
「Clover IX」杯HE两校联赛(Day1)
只写了1.5h, 看了题就果断敲暴力了, 自己没出数据, 没对拍, 没手感......
40 + 10 + 0...明晚回来看题解, 果然NOIp裸考挂定了...
P1[简单数学]
注意到序列里的U和D只要合法就可以移动, 所以对字符串st计算高度的变化dH, 分类讨论:
1) |h[0]+dH-h[N]| < N-len, 奇偶性相同则有解, 反之无解
2) |h[0]+dH-h[N]| = N-len, 有解, 且需满足h[0]+dH >= 0 || h[N]-dH >= 0
3) |h[0]+dH-h[N]| > N-len, 无解
*要用草稿纸!!!注意考虑各种情况!!!
P2[字符串]
<暴力做法1>
用数组记录每个beautiful words的长度和起止字母, 然后用O(N^4*M)来暴力枚举.
<暴力做法2>
对于每个beautiful words, 从头扫一遍记录前缀长度, 从后面扫一遍记录前缀长度, 然后记录长度大于该beautiful words的字符串数量, 累加即可. 复杂度O(N^2*M).
<AC做法>
同暴力做法而, 不同的是由于使用了KMP所以复杂度变成O(NM)
P3[_____]
根据样例, 如果一对元素A_i, A_j需要操作的话, 必然满足A_i ^ A_j > max{A_i, A_j}. 于是当任何一对A_i, A_j都不能被操作时, \sum_{A_i}最大,
然后由于还有15min了, 我就果断敲回溯暴力了...
AC做法是高斯消元然后乱搞...看不懂
10.20
鉴于是恢复状态的训练, 而且AC做法全都没学过, 出于给生活以情趣的目的......看了题解就算了......
10.21
P1, Preda's queue, 模拟
注意到最多有N次弹出操作, 所以保留N个元素就好了, 然后模拟即可.
*居然爆零了...这不科学
P2, signal, 位运算+DP统计
[O(N^3)做法] 直接O(N^2)得到所有区间
[O(N^2)做法] 可以利用heap/线段树在O(NlogN)的时间里得到所有区间的操作结果, O(N^2)枚举. 特别地, xor满足区间减法, 可以直接O(N^2).
[O(NlogN)做法 by Juda]
(1) and
对于元素A_i, f[i][j]表示A_1...A_i的第j个二进制位中连续为1的个数, 累加即得.
(2) or
对于元素A_i, g[i][j]表示A_1...A_i的第j个二进制位中1第一次出现的位置, 累加即得.
*上述做法可以统一描述为, 自右向左扫描, and/or需要记录第i个元素前的元素中第j位第一次为0/1的位置, 2^j * (i - f[i][j] + 1)即为所求
(3) xor
[xor运算性质] 对于A_1 xor A_2 xor ... xor A_n, 考虑第j位, 若有奇数个1则为0, 反之亦然.
对于元素A_i, f[i][j]表示A_1...A_i, A_2...A_i, .. , A_i的中有奇数个1的序列个个数, g[i][j]表示序列中有偶数个1的序列个数, 不断交换, \sum 2^j * f[i][j]即为所求.
*还是爆零了不科学...
P3, catclimb, DFS-ID
一开始读题以为是DP, 条件反射想到training里的rocker和GDKOI 2012 Day1P1. 被P2虐了一通之后, 发现其实是搜索, 智商这个拙计啊....
标程给的做法是DFS-ID. 直接\sum{A_i}\N上取整可以得到理论下界, 然后qsort一下{A_i}先取大的再取小的填一下可以得到上界, 直接O(N!)暴力枚举. 如果达到下界或超过上界马上剪枝.
*只过了一个点...这不科学!!!!!!!!
P4, communicate, LCA
只会SPFA...但是这个范围!!!一看就不是NOIp题(
*明天晚上抽2h调一下吧...还要写PS...
第四年参加NOIp, 大概是四年来压力最小的一次.
和CPhOp预赛地点一样, 不同之处在于NOIp初赛人很少, 教室只占了一层楼. 没有蜂拥而至的人群, 亦没有死守在楼梯口的保安, 连考务都是各校教练, 不知道可喜还是可悲. 就考前两天随手做了两套题, 也没复习什么东西. 给的成绩大概是71.5, 全市第二. 自己对了下答案, 大概是74, 有个很二的空填错了. 要是和CMOp预赛的分数换一下, 高中的竞赛生涯也算圆满了.
题目难度加大, 但是风格很好, 延续了10年以来的灵活. 选择题对知识量的要求依旧弱, 除了不记得P/NP/NPC的定义还真没别的识记问题. 问题求解很难, 第一题是数理逻辑背景, 看不懂题意. 第二题大概是类似tree dp的组合计数, 很久没碰了, 没做. 阅读不难, 第一题是去掉一个最低分去掉一个最高分算均值, 第二题是统计n的正因子个数, 第三题是n-n的二进制表示中1的个数, 第四题是给个先序和中序, 然后画出树来加权. 完善第一题是暴力搜索例题, 眼残了一个填空. 第二题有点意思, 但是由于很久没敲过题了, 果断只对了两个空. 大概一年前的水平是可以解出来此题的.
该干什么干什么吧.
上周四研究有多套系数的氧化还原反应方程式配平的时候, 遇到了多元线性方程组求解的问题, 不过似乎书上写挂了(应该写通解, 而书上只给出了一个特解). 另外一个可能遇到的应用,是, 在电路问题中, 结合欧姆定律和基尔霍夫定律暴力求解. 当然, 平时用的最多的是利用二阶行列式求解系数较为复杂的二元一次方程, 比如高考解析几何大题.
大概是对于wikipedia上概念, 结合个人认识的一些重述, 实在不是便于理解, 仅供复习:
[线性方程组的矩阵表示] A \times a = b. 矩阵乘法的一个应用是求解线性递推数列, 可以利用快速幂将复杂度降至O(logN).
[Rank(秩)] 线性无关的列的个数, 对于n元线性方程组, 仅当秩r = n时恰有一组解. r > n时无解, r < n时有无数组解.
[Gaussian Elimination(高斯消元法)] 通过不断消元, 使得方程组中每个方程的元的个数逐个递减, 等号左边呈三角形状, 自下而上代入消元即可. 具体操作时, 对于方程f_1(x_1, x_2, \cdots, x_n) = 0, f_2(x_1, x_2, \cdots, x_n) = 0, 令f_2(...) = f_1(...) + \lambda f_2(...). 手算的话, 消元方向很明确,
对于N元线性方程组, 时间复杂度为O(N^3). 更好的做法是共轭梯度法, 时间复杂度为O(N^2). NOIp 2004的虫食算的AC算法可以使用Gaussion Elimination.
[Cramer's Rule(克莱姆法则)] 二阶行列式解二元一次方程组的理论依据.
x_i = \frac{D_i}{D} (1 \leq i \leq n), D = det(A). D_i = det(A_i), 即把矩阵A的第i列换成矩阵b. 显然当D为0时线性方程组无解. 对于N元线性方程组, 时间复杂度为O(N!).
[Least Squares(最小二乘法)]参见选修2-3, 推导有一定技巧性, 但是我已经忘完了 >_<. 值得一提的是, 发现者是Gauss和Legendre, 存在发现先后的争论, Legendre的肖像居然和同名法国政治家的肖像混用了一个多世纪(参见维基), 不过发现者是如何的淡腾. = =|||
[Cross Product(叉积)] 可以通过向量矩阵和(i, j, k)的乘法计算, 通过右手定则判定方向. 比较简单的用途是计算立体几何中的法向量(口算), 以及安培力和洛伦磁力的方向确定.(不过高中教材中介绍左手定则判定方向, 分离了矢量的方向和大小).
考虑向量a, b, 存在|a \times b|^2 + |a \cdot b|^2 = |a|^2 \ cdot |b|^2, 这个结论被称作Lagrangian Identities(拉格朗日恒等式).
立体几何一个的应用在化学的晶体结构中, 比如正四面体CH_4, 键角为arccos{-1/3}. 如果尝试思考不同学科之间的联系, 会发现很多意想不到的结论, 往往可以通过其他学科浅显的结论, 来解释另一学科中难以求解的问题. 令人唏嘘的是, 一些原本浅显的联系并没有在高中教学中被体现. 也许可以尝试收集这样的联系, 何况生活原本是充满乐趣, 可我们却停留在了乏味而抽象的表层.
不管怎么说还有个三等, 退役了, 随意了. 只是深圳又从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之后就放弃了. 结局如此, 意料之外, 情理之中, 差强人意.
其实还是太弱了, 思维局限很严重, 训练方式同样存在盲点. 起步太晚同样是一方面, 结局如此, 也罢, 也罢.
退役了, 一段生活的结束, 也许是暂时的离开, 也许是永远的离开.
一局终了, 从开始到结束经历了三年, 挺长的.
高中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, 算法模板, 并准备若干测试数据, 以测试模板.
//大概在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) 乱七八糟的想法