0%

An Easy Physics Problem

Tags: 几何

简单几何,不过好多人说会挂精度是怎么回事。。(不管反正我只会嘴炮

注意,两个点都在圆外,而且不在圆边上,这点非常重要!

Binary Tree

Tags: 构造

好吧。。这题本来想出成不给$K$的,但是考虑到缺中档偏简单的题而且不给$K$输出不好控制,就给了个这么奇怪的限制。。

对于所有的奇数我们可以用$1$, $2$, $4$, $\cdots$, $2^K$这条路径进行贪心构造。

对于所有偶数的情况,由于我们已经构造出了所有的奇数,偶数就是奇数加$1$啦,所以我们可以从$1$走到$2^{K-1}$然后走到$2^K+1$。

时间复杂度$O(K)$。

Colorful Tree

Tags: 数据结构

先上一个可能会 TLE 的做法。。把整个树根据DFS序展开成线性的,然后我们可以把整个问题转化为,修改一个区间颜色,查询区间不颜色的数量。这里,如果修改的单点的话,就可以用类似 这个破题 的思路来写了。这样时间复杂度是$O(N\lg^2N)$.

对于把区间更新转化成单点更新,可以考虑,由于我们每次都是更新的一整个子树,那么对于修改操作,我可以把根结点的颜色更新成我们要的颜色,对于剩下的点,我们直接暴力把它们删掉。对于删颜色的操作,最多只会有$N+M$次。

查询的时候,我们先看这个区间内的不同颜色数量,再考虑,如果根的颜色是空的话,我们要找到根真正的颜色,还要看这个颜色在不在区间内。不过这个好处理,直接维护一个线段树,表示每个点真正的颜色就可以了(对于更新一个子树的颜色,就等价于更新线段树里面一个区间的值)。

最后,我们考虑怎么把时间复杂度再降一点(现场前者做法如果常数不大其实是可以过的)。对于相同颜色的结点,我们把他们按DFS序排好序,我们维护一个树,树上每个结点的值,表示以这个结点为根的答案,那么我们直接考虑不转线性地去维护这些答案。我们会发现,对于每个点,它的颜色只会影响到它到它祖先里面深度最大的同颜色点下面的结点的答案。但是有可能一个结点下面会有多个同颜色的点,怎么办?我们假设同颜色的DFS序是$a$,$b$, $c$, $\cdots$,对于$a$我们只认为它影响到了$a$到$LCA(a, b)$路径上的答案,对于$b$来说,影响到的是$b$到$LCA(b, c)$上的答案。。。这样就可以把整个问题转化成了树上路径更新,单点查询的问题了。

最后,总体复杂度是$O((N + M) \lg N)$。

Discover Water Tank

Tags: 动态规划

将整个$h$数组抽象成一棵笛卡尔树,对于每一个挡板,我们从它最高点向左右划横线,直到遇到比它高的挡板停止,然后我们会发现这个图被分成了很多个长方形,这些长方形就是树的每个结点(自己画图QUQ)。然后我们就可以在这些结点上DP了。

定义状态
$$dp[u][s]$$
表示考虑到结点$u$,$s$表示有水还是没水,值是最多不冲突的条件的数量。然后直接树形DP转移就可以了。

这个树不一定要建出来,可以用并查集抽象化就可以(当然建树并不难写就是了)。

对于每个结点,我们需要把在内部的条件预先排好序(内部有可能冲突),所以最后时间复杂度是$O(M \lg M + N)$。

Expection of String

Tags: 动态规划

Solution I

直接DP每两个位置的期望,定义状态
$$dp[s][i][j][k]$$
表示现在还有$k$次交换机会,两个数位置在$i$和$j$,乘号在$k$,对最后答案的影响。转移可以通过求和来达到$O(1)$。

时间复杂度是$O(N^3 \cdot K)$。

Solution II

固定$C$我们用DP算$x \times y$的期望

定义状态
$$dp[A][B][C][K]$$
表示当前某三个位置$i < j < k$的值分别是$A$ $B$ $C$,还有$K$步要走时,
这三个位置的$x \times y$的期望,边界条件为
$$dp[A][B][C][0] = \begin{cases}A \times C & \mbox{if }B = *\\0 & \mbox{if }B \neq *\end{cases}$$

于是由于$A$ $B$ $C$分别只能是$0-9$以及 * 共$11$种 然后转移的时候也只与这$11$种的个数有关,因此可以做到$O(11)$的转移

最后答案是
$$\sum_{i < j < k}(dp[s_i][s_j][s_k][K] \times C(i, j, k))$$
其中$C(i, j, k) = 10 ^ {(j - i - 1) + (N - k - 1)}$

总体复杂度$O\left(11^4 \cdot K + N^3\right)$.

Friendship of Frog

Tags: 杂题

怎么写都可以。。数据范围$N \leq 1000$瞩目。

时间复杂度强行$O(N^2)$。

Game of Arrays

Tags: 博弈

  • 先计算出$A+B-C$,得到每一位需要操作的次数,若为正,即操作$A$或$B$,若为负,即操作$C$。
  • 如果初始状态等式成立,则先手赢。否则枚举先手第一步。
  • 对于每一位,判断初始时是否在等式永远不可能成立的状态,如果是,后手赢。
  • 否则判断其是否有一种方法(后手不断操作$A$/$B$,或者后手不断操作$C$),使其永远都不能成立。
    • 如果是,判断在这种情况下(后手不断操作$A$/$B$,或者后手不断操作$C$),先手能不能赢(即在这 一位等式永远不成立之前,先手把其他位都操作成等式)
    • 如果先手不能赢,那么后手就执行这种方法(后手不断操作$A$/$B$,或者后手不断操作$C$),后手赢。
    • 如果对于每一位,后手都不能将其操作为永远不可能成立的状态,那么先手赢。

Happiness of Frog

Tags: 动态规划

不会。。。

Infinity Point Sets

Tags: 几何 计数

其实这题需要画图强行猜个结论(不

最后满足条件的点集,只有一种,那就是一堆共线的点,加上两边最多各一个点(最多的意思是可以有一边没有点,或者两边都没有)。

但是这样不好统计,怎么办?把这个结论划分成下面几类:

  • 小于等于$4$个点,或者大于等于$5$个点并且它们共线。
  • 大于等于$4$个点共线,加上其中一侧有一个点。
  • 大于等于$3$个点共线,加上两侧各有一个点。

我们枚举一个点,把所有点极角排序,对于第2种情况可以直接算出来,对于第3种情况,我们假设这个枚举的点是四边形的中心,这样可以把四边形加上对角线交点这种会重复算的去掉。

时间复杂度$O(N^2 \lg N)$。

Journey of Taku

Tags: 图论 最短路

首先如果Taku使用了第二种魔法,那么有$K$步的移动是可以确定的,于是我们记录每条边走完后,通过第一种魔法下一步是哪条边,这样可以倍增算出K步后在哪儿,于是可以直接建图,求最短路即可。

重要的话一定要加粗说!答案会爆int,另外题意有毒!

时间复杂度$O(M \lg K)$。

Kingdom of Black and White

Tags: 杂题

直接枚举修改哪个点,我们可以先算出原来的答案,然后修改一个点只会影响到相邻的两个连续段,直接算修改后对答案的影响就可以了。

时间复杂度$O(N)$。

LCM Walk

Tags: 数论(假)

对于$(x, y)$走到$(x + z, y)$或者$(x, y + z)$。由于$z \geq x$且$z \geq y$。我们可以算出来$(e_x, e_y)$的前驱。实际上前驱是唯一确定的,所以直接模拟就可以。

时间复杂度$O(\lg\left(\max(e_x, e_y)\right))$。

Secrete Master Plan

Tags: 杂题

把输入的格子数字按顺时针或者逆时针顺序放到两个数组中,然后用for循环判断能不能通过shift来使得两个数组相同。

Build Towers

Tags: 启发式搜索

把状态进行hash,然后跑A*或者IDA*,一个简单的估价函数可以是

$$h(s) = size - 6$$

其中$s$是状态,$size$是当前状态中单独块的个数,比如说$0-1$算是$1$块,$0-1,3-5$算是$2$块。

一个比较好的优化是,把每个塔进行排序,行按照塔上木棍的数量从小到大,一样的时候,按字典序,这样可以把重复的状态减少。

The Battle of Chibi

Tags: 数据结构 动态规划 图论

定义状态$dp[i][j]$表示选了$i$个考虑到了前$j$个,这$i$个是严格递增的方法数,转移方程:

$$dp[i][j] = \sum_{a_k < a_j}(dp[i - 1][k])$$

这里的转移可以用树状数组进行优化,转移是$O(\lg N)$的,总体复杂度$O(N \cdot M \lg N)$。

Pick The Sticks

Tags: 动态规划

把金条按长度从大到小排序,定义状态$dp[i][j][k]$表示考虑到前$i$个金条,选了$j$个,它们的长度和是$k$,可以获得的最大价值,直接0-1背包就可以,其中$j$是0-2的,如果$j$是$0$或者$1$,那么新选择的金条有效长度减半,否则就用原长。由于这题说的是重心,为了方便处理,可以把所有的长度乘以$2$方便转移。

Ba Gua Zhen

Tags: 数学 图论

先构建一棵生成树,对于所有的非树边,求出对应的简单环的异或和,这样我们可以得到$M - N$个数,最后这题的问题就可以转化为给$M - N$个数,选出一些数出来,使得异或和最大。这个可以用类似高斯消元的思想在$O(60 \times (M - N))$时间内求得。

The Battle of Guandu

Tags: 图论

根据题意可以构建出一个不等式组,把这个不等式组,求个对偶形式,可以发现模型由一个单纯形的问题转化成了差分约束系统,可以建图跑最短路得到答案。

Ancient Go

Tags: 杂题

对于每个白子跑DFS或者BFS找气,只要气是(1)就说明下一步可以吃子。

Sudoku

Tags: 搜索 暴力

简单的搜索或者枚举就可以。枚举的话就直接枚举每一行的排列是什么然后判断,排列方式只有$24$种,最暴力的做法也就$O(24^4 \times N^2)$。

Mahjong

Tags: 动态规划 状态压缩

动态规划,定义$dp[i][j][s]$表示考虑到第$i$种牌,一共用了$j$个,$s$表示一个压缩的状态,这个状态记录的是一个三元组$(i,j,k)$,表示考虑到$i$,其中$i-2$剩下了$j$个,$i-1$剩下了$k$个,这样的状态定义可以比较方便处理重复的情况。其中对于每个状态,$s$的值是很少的,这里可以直接预处理出来合法的$s$。

Walk Around The Campsite

Tags: 几何 动态规划

对于每一个点,我们都要知道站在它位置上可以“看到”哪些点,这里将所有的线段拆分成三种事件,一种是一个发现了一个新的线段,一个是一个线段将要被删除,还有一个是查询一个点是不是能从中心点看到。由于所有的线段最多只会在端点相交,所以我们可以用平衡树维护线段的序,平衡树的key是沿当前角度上从中心点看,这个线段到中心点的距离,值是线段,这样对于查询点的事件,我们只要看它是不是在最近的线段上就可以了。

处理完有效的信息之后就是一个很简单的转移(卧槽为毛这么多dp):

$$dp[i] = max(dp[k] - dist(k, i) + v_i)$$

其中,从$k$可以看到$i$。最后答案是$max(dp[i])$。

Game Rooms

Tags: 动态规划

再吐槽下为毛这么多dp(不

定义状态$dp[i][j][k]$表示考虑到第$i$层,上次和这一层一样的活动室是在$j$层,当前楼层放$k(0, 1)$这个活动室的最小代价。转移的时候可以处理出$\sum{a_i}$和$i \times a_i$然后在$O(1)$时间内转移。

Huatuo’s Medicine

Tags: 杂题

签到0.0

1
2
3
4
5
#! /usr/bin/env python2

T = int(raw_input())
for cas in xrange(0, T):
print "Case #%d: %d" % (cas + 1, 2 * int(raw_input()) - 1)

这几个晚上在倒腾CDOJ的git repository,在家试着 git clone 了一把,第一感觉是

1
坑爹啊,这是什么鬼,为什么会有100多MB的history。

国内的情况你们懂的,花了10来分钟才把repo下下来,想了下原因,大致上是:昀大爷年轻的时候把 MathJaxFont 之类的前端module给push上去了,还不时地移了几次位置,更新了几次版本,就这样把几百MB的东西加到历史里去了。。。

那么问题来了,怎么要才能把这些“没有必要存在”的文件从git history里面给干掉呢?这里推荐一个相对简单的办法(更简单的办法是用 bfg ,然而家里的网络直接装都装不上,我放弃了)。

想起来你要删的文件是什么

在这里我们用 MathJax.zip 做例子。

用git filter-branch去看下有多少commits和你选择的文件相关。

1
$ git log --stat | grep -B 10 -A 10 MathJax\\.zip

在这里, grep 的A和B参数表示的是after和before,这样可以大致上看到一个commit的context。

把你所不关心的文件从历史记录中删掉

1
2
3
$ git filter-branch --force --index-filter \
'git rm --cache --ignore-unmatch MathJax.zip' \
--prune-empty --tag-name-filter cat -- --all

清理下你的本地git repo

1
2
3
$ git for-each-ref --format='delete %(refname)' refs/original | git update-ref --stdin
$ git reflog expire --expire=now --all
$ git gc --prune=now --aggressive

强制刷新remote repo的内容

1
2
$ git push origin --force --all
$ git push origin --force --tags

Jekyll有两个比较重要的依赖,一个是 Ruby ,一个是 libffi ,一般来说我们可以用 Homebrew 直接搞定它们

1
2
$ brew install ruby libffi
$ ruby -v

然后就在安装 jekyll 的时候,指定好include path了,注意这里不能用

1
2
$ export CPATH=~/homebrew/Cellar/libffi/<ffi-version>/lib/libffi-<ffi-version>/include/
$ gem install jekyll

因为 brew install 会新打开一个 shell 进程,我们可以用

1
$ CPATH=~/homebrew/Cellar/libffi/<ffi-version>/lib/libffi-<ffi-version>/include/ gem install jekyll

这样可以安装成功

这段时间老是有许多新人向我问到ACM相关的问题。比如它与工作的关系,对我以后的工作到底有没有帮助?还比如说第二年的训练计划应该是什么样的?还有的孩子问到,我寒假玩儿的一个寒假,又该怎么办?

看到这些问题,我自己也感慨万千,一眨眼自己在这方面也涉猎了两年多了,经过那一段时间的纠结,最终还是决定第三年继续。大家选择ACM的理由的很多很多,为了以后方便找工作?充实生活?巩固学科基础?不管是为了功利心理也好,还是纯粹的兴趣也罢,最后共同的结果就是我们选择了ACM作为自己大学生活的一部分。

我们可以从ACM中学到什么?

首先,作为一个团队活动,我们可以从中感受到团队合作的魅力,只可以感受团队合作给我们带来有那种不一样的感觉,当然,也可以从中认识更多的志同道合的朋友。

其次,ACM是一个学习的过程,对我来说,在这两年里,我自己学到了许多上课不会涉及的东西,自己吸收其它方面知识变得更快了,对于即将从事IT产业的我们来说,学习能力是一个非常重要的能力。

最后,要取得好的成绩,我们要掌握许许多多的知识,而大部分的知识,都是计算机学科、数学学科的基础,比如说微积分、线性代数、概率论、数据结构等等。

ACM需要的是坚持而不是三分钟热度

大一开班会的时候提及到过大学四年的规划,记得当时选这个的人挺多的,坚持半年的也很多,但是到了大一下学期,一个寒假回来,坚持下来的就没有几个了,而到了最后参加讲座的就更少了。这说明的什么?可能是没有兴趣吧,ACM是一个需要坚持的竞赛活动,不是简简单单的混个三、四个月就可以有成绩的,只因为付出了,才会有后来的回报。

很久以前就听学长们说了一句话

ACM ICPC不应该成为大学生活的全部,但是我们却时常后悔没有把我们的全部投入进去。

很多人常常在失败的时候抱怨自己的队友,把失败归咎于自己的团队,当然也有人把所有的责任推到自己的身上。我们要记住,ACM是三个人的活动,不是你一个人的,更不是你队友的。三个人坚持下来了,我们要的不一定是得到辉煌的成就,最主要的还是那深厚的友谊加上和朋友们一起奋斗的过程。

关于ACM的种种小事

交流是重中之重

成为集训队的成员已经有两年的时光了,在每年新的一轮训练开始时,最经常见到的就是一个新人的队伍,甚至是有一定配合的老队伍的三个人,各自做各自的,从始至终都没有什么交流,说的最多的就是这题过了,这题挂了,或者是你先下来,我先写另外一道,等等。切记一点,ACM是三个人的活动,并不是1+1+1那么简单的,如果三个人各自为战,这和个人活动有什么区别?1+1+1<1是常常遇到的事儿,出现这类问题最主要的原因就是各自为战。

做事要有一个整体规划

到现在,我见到的最多的解题策略,包括我自己曾经用的,都是reading-thinking-coding-thinking-coding-debug-thinking-debug-submit。对于一个中档题来说,这个过程可能需要30到50分钟不等,往往很多人觉得50分钟和30分钟是没区别的。在过题之后估计整个过程,许多人会把实际上是50分钟的时间估计成半小时,然后就觉得时间充裕。不管是做ACM也好,平时做事也罢,有一个非常重要的环节,那就是Programming,这可不是Programmer相关的单词,而是Dynamic Programming中的Programming,它是规划的意思,相同的一个ACM问题,如果你在上机前多花5分钟规划,你可以在coding和debug阶段省下很多的时间。记住,理想的解题过程应该是reading-thinking-programming-coding-debug-submit,甚至对代码能力好的人来说,debug这个环节可以省略。

克服对新知识的抵触心理

第一年训练结束之后,队伍解散,我也开始新知识的储备,那时候对DP有着很大的抵触心理,后来在寒假逼着自己看了几篇DP优化相关的论文,结果虽说不上喜欢上了DP,至少对DP的抵触心理小了很多。世上不存在什么不可能学会的知识,我们要做的仅仅是培养兴趣而已。

代码越短越好 or 写的代码越长说明自己越牛?

我想一定的不少人觉得代码越短越好,或者代码越长说明自己越强。很明显这种想法并没有任何的科学性。coding是一门艺术,拿coding和写文章作对比,可谓大同小异,作为一个团队的成员,我们要做的是使自己的 文章 可读性更强,而不是刻意地去压缩、扩充自己的代码。解题的过程,个人能力差异最小的就是coding在过程,差异最大的是thking和debug的时间。代码比别人的长了点儿,coding多花了时间,但是debug的时候队友可以给自己更多的帮助不是么?

为什么我投入了这么多却没有得到回报?

很多人,包括我自己,都遇到过这类问题。当遇到这类问题的时候,有的人会选择退却,有的人会选择反思,当然也有人选择不管不问,使用以往的方式继续下去。遇到这类问题,我们要做的事就是找到问题的根源,我想最大的一个原因,就是不够专注。何谓专注?专注不是一整天只吃一顿饭,即使逃课也要训练,专注也不是花大量的时间,只学了本来一个小时就可以学会的知识。高中的时候,很多同学问我为什么做作业比他们快,其实高中的时候效率高的原因仅仅是不在做作业的时候听音乐而已(我发现自己没法做到那样的状态了,训练的时候没法做到原来那么专注,有点可惜)。在训练的时候,我习惯把电脑静音,拔去散热器的电源,我不希望散热底座风扇转动的声音影响自己的思考,虽然我的思维很慢。有的人(有时候我也有这样的毛病)喜欢在训练还没结束的时候就在群里得瑟,或者在训练一半的时候发现剩下的题目自己肯定没戏,就放弃了。我觉得这都不是一个好的习惯,养成好的习惯可以让你有更大的成就的。

谈谈ACM的学习氛围

我常见到很多人在群里抱怨题目看不懂,当然也不排除这些题目描述真的写得很渣的原因。如果一套题,特别是好题,你发现自己很多题都看不懂意思的话,那只能说你有点浮躁了。

虽然不愿意这么说,但这却是事实,做ACM最需要的是一个氛围,一个平常十分融洽,训练的时候却严肃的氛围。其实我不喜欢训练的时候开玩笑,以前不少老队员和我说:何老师,你的表情太呆板啦,和我们一样嘻嘻哈哈的多好。我可能习惯了,平时都不会嘻嘻哈哈的,但是我并不反对平时没有训练的时候大家活跃一点,毕竟大家是在一个集体之中,需要更多的沟通交流。我也不反对平时一起玩游戏、一起听音乐、杀人、三国杀,娱乐活动是生活不可缺少的一部分,这我还是知道的。但是在训练的时候得瑟、逛社交网络、在QQ空间里瞎逛就不可取了。

凡事都不会是绝对公平的,不管在什么情况下,不公平的事可谓是屡见不鲜了。copy他人的代码(或者自己以前写的代码),太过于 乐于助人 等等。我想很多人在前期会有想不出来马上就看题解的习惯,慢慢演变成了这样,当他意识到事情的严重性的时候,却很难改正了。甚至有人并没有意识到这里面对自己的危害有多深,而到了最后的赛场才后悔莫及。

SCL到底是好是坏?

SCL,大部分人称其为 模板 模块 标程 等,对很多人来说,可能是比赛场上必不可少的 武器 吧?不过我的观点是能不用就不用,大多数人使用SCL的原因是其中的代码并不是他自己实现的,有可能是google的,或者其他队员、学长实现的。我并不反对这种行为,但是比赛比的就是代码实现能力,至少,你要对这份代码相当熟悉才行。

之所以不推荐用SCL,主要的原因是它会阻碍代码能力的提升,习惯用SCL之后,你会发现自己写代码越来越容易写挂,1Y率大幅度下降,随着自己学的东西越来越多,积累的SCL越多,代码能力就下降的越快。SCL仅仅是为了正式比赛心安的一个工具,而不是训练的工具。

ACM与大学生活

作为ACMer,我认为ACM给我带来最多的好处,那就是充实了我的大学生活,让我喜欢上了看课外书。看书不能囫囵吞枣,否则你可能连原理都掌握不了。此外,最重要的是实践,一个新的算法,要自己试着实现。当然,实现之前一定要理清步骤,另一方面,我们还需要通过和他人的交流,让自己对某方面的知识的理解更进一步。

还有一个和我们大学生活相关的话题,那就是GPA。很多人因为ACM把学业扔了而挂了很多科,这可以说他们把时间全花在ACM上了么?当然不能。曾经问过学长类似的问题,得到的答案就是GPA相比ACM来说,公司虽然看中能力,但是更看中基础课的掌握程度,而GPA就是表现这个的最方便的方式。GPA说明了一个人对待学习的态度,也表现了一个人的学习能力。总而言之,我的建议地能不挂科就不挂科,毕竟挂科后要花更多时间去折腾自己的学业。

最后,想提及一下作息时间的问题,大一大二作息时间一天比一天混乱,特别是周末或者课少的时候,本人熟悉的ACMer中,有90%的是夜猫子,每天2、3点睡觉都是常事,而这样的作息时间导致了白天精神萎靡的情况。最近一直11点睡7点起,上课没有犯困过,感觉良好。

不管怎么说,既然要把ACM作为自己大学生活的全部,那么就认真地投入吧,好好享受这个过程才是最关键的不是么?