UOJ Logo WrongAnswer的博客

博客

做TopCoder题的一些总结

2017-01-25 10:17:36 By WrongAnswer

集训队第一次作业结束了。作业是TopCoder的156题(我完成了154题,理论上8分完成分我可以得到7.8分)。虽然我在提交的时候出了各种问题,感觉作业分会爆炸。然而我并不想退役QAQ

以下是我做TopCoder的一些总结。


1、题目形式

TopCoder和大多数OJ的题不太一样,大多数OJ都是使用用标准输入输出,而TopCoder只需实现一个关键的类(class)中的一个函数即可。函数传入的参数和返回值取代了标准输入输出。

TC的输入输出规模比较小,大多数题的数据范围都在 $50$ 以内,这是因为太大的数据点超出了Arena的容纳范围。事实上数据范围只有 $50$ 的题仍然颇有难度,这一点在之后会提到。

大多数的题目和日常做的OI题还是很类似的,但侧重点不一样。TC的组合计数以及组合优化类问题比较多,大多数题的主要难点在于思维上(当然也不乏代码题),很多题都是“暴力是指数级复杂度,难点在于想出一个多项式算法”,例如SRM 577的500,只要想到DP状态如何设计,很高的复杂度都能通过。当然也有一些 $O(n^3)$ 卡 $O(n^4)$ 之类的题,通常需要用特殊的方式进行输入(如输入字符串解密数字,输入随机数种子递推出随机数)。

2、解题遇到的困难

TC题比较难(当然是对我而言,对于C_SUNSHINE、matthew99、immortalCO等神犇来说应该是比较容易的?),我在做的时候遇到了不少的困难。

有一类问题,一开始看到的时候毫无思路,经过长时间多种方向的尝试最后才解决。

SRM 562的1000是一道有结论的树形DP问题,这题我研究了很久,终于推出了两种不同情况下的结论。其中一种情况是:$2k > n$ 时,排列 $p_0,p_1,...,p_{n-1}$ 合法当且仅当:①$p_{n-k},p_{n-k+1},...,p_{k-1}$ 这 $2k-n$ 个点构成一个连通块;②将该连通块删掉后,如果 $p_i,p_j$ 位于同一连通块,那么或者 $i,j < n-k$,或者 $i,j\ge k$;③对任意 $i < n-k$,$p_i,p_{i+1},...,p_{n-k-1}$ 构成连通块,以及对任意 $i\ge k$,$p_k,p_{k+1},...,p_{i-1}$ 构成连通块。想到这个结论以后我开始尝试用树形DP求出有多少个连通块大小恰为 $2k-n$,用树形背包的经典算法容易把满足③的排列个数也算进来,但是,对于每种选连通块的方案,贡献为满足②的把点分成 $i < n-k$ 和 $i\ge k$ 两类的方案数,这个我并不会统计。绕了不少弯路才发现其实是不从“对每个 $[n-k,k)$ 求有多少个 $[0,n-k)$ 和 $[k,n)$ 以及它们的排列方案数”考虑而是从“对每个 $[0,n-k)$、$[n-k,k)$、$[k,n)$ 求有多少个排列方案数”,也就是DP时把位于中间和位于两边的点数都计入状态。这样问题就得以解决了。事实证明这样的求和的问题转化思路是相当有趣的,以后可以出这类的题。

阅读更多……

失败的FJWC2017&FJOI2017

2017-01-19 19:21:56 By WrongAnswer

高二第二次参加省冬令营以及省选。退役前的倒数第二次冬令营。

并不希望得到多么好的成绩,只希望不要挂得太惨。


1月18日

报到。由于是外地生,和Paladin100100住进了宾馆。宾馆的质量不想吐槽。

晚上刷TC。一个晚上才刚出一道SRM 594的550网络流,1000想了个DP感觉可以优化然而没做出来,SRM 595的900调细节调了好久没调出来。我好菜啊。


1月19日

省冬第一天。

上午讲了一些偏基础的图论建模技巧,包括网络流建模技巧。有几道题还是蛮有趣的。

中午吃完饭发现手机屏幕又坏了,不明原因。有点郁闷。

下午训练。只有三个小时,手速赛差评。

第一题:给定 $h\times w$ 的矩阵,常数 $m$ 以及 $n$ 个子矩形,每个子矩形可以用 $x_1,y_1,x_2,y_2,v$ 描述,表示从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的子矩形最大值为 $v$。问有多少个矩阵满足每个数都是 $1$ 到 $m$ 的整数,且满足子矩形要求。$h,w,m\le 10^4$,$n\le 10$,$1\le x_1\le x_2\le h$,$1\le y_1\le y_2\le w$,$v\le m$。

看到 $n\le 10$ 想了想就是个容斥裸题。花了十几分钟写了个离散化+容斥过了样例就不管了。

第二题:题意比较复杂,简单的说就是给定有向图 $G=(V,E)$ 和 $s\in V$,求所有点对 $(u,v)$ 满足存在两条点不相交的路径 $s\rightarrow u$ 和 $s\rightarrow v$。$|V|\le 10^3$,$|E|\le 10^4$。

理解了很久的题意,感觉是支配树?因为如果 $s$ 到 $u,v$ 有同一个必经点就挂了,否则……好像都能构造出两条路径……可是我不会写支配树QAQ

第三题:给定字符串 $s$ 和常数 $K$,支持两种操作,一种是给定 $l,r,c$,对所有 $l\le i\le r$ 修改 $s_i$ 为 $c$,另一种是给定 $l,r$,求有多少对 $l\le l'\le r'\le r$ 且 $r'-l'+1 \le K$ 使得 $s[l..r]$ 是回文串。

看起来挺可做的啊……我来推一下。如果建个线段树,那么信息怎么合并?好像合并是 $O(K)$ 的于是单次 $O(K\log|s|)$ 不是很优秀啊。不太会。那就分块试试?以 $B>50$ 为块大小,记录下块内和块间的长度不超过 $K$ 的回文串个数,修改和查询时枚举整个的块,不满的用 manacher 暴力统计即可,就可以做到修改和查询复杂度均为 $O(B+\frac{|s|}{B}+K)$ 了?然而细节很多的样子……先是推导过程已经让我挺烦的,然后觉得这题如果不做出来应该没什么救,就刚了2个小时……写完分块准备敲 manacher 发现并不熟练QAQ

决定回去做第二题。数据规模这么小,能否不写支配树?那就是枚举两个点,把非源的必经点集合求个交,如果为空说明可行。$O(|V||E|+\frac{|V|^3}{w})$ 不知道能不能A。

第三题写了个暴力,分块写完 manacher 还没写,发现似乎有问题,然而没剩多少时间了,决定交暴力。

感觉今天正常应该有100+100+20=220吧?

出了考场,突然意识到一个问题——我离散化没检查,似乎写错了!样例里面的相邻矩形边界相差都是 $1$,发现不了这个问题!!

卧槽!!!

阅读更多……

关于UOJ#219的时限 & UOJ#264的样例

2016-12-16 16:57:50 By WrongAnswer

无聊在UOJ上乱逛发现两个问题

UOJ#219

http://uoj.ac/problem/219

这题时限是1.5s

然而我测了一下,怀疑时限是1s

http://uoj.ac/submission/114145 卡时1.3~1.7s,全部TLE

http://uoj.ac/submission/114147 卡时0.8~1.2s,部分测试点TLE,且没有TLE的点运行时间都在1s内

UOJ#264

http://uoj.ac/problem/264

这题原题第3个样例第一行有一个空行

并且样例说明里也说了第一行需要输出一个空行

但是UOJ上样例并没有空行

http://uoj.ac/submission/114149 另外经过测试,不输出空行也是对的

WAer的THU集训

2016-12-04 13:35:37 By WrongAnswer

这里是老是写挂题的WrongAnswer弱渣= =

作为一位无实力选手,当然要直播THU集训是怎么揭露本渣的辣鸡实力的2333


Day 0

很早起来赶飞机,到了以后赶去hotel,最后由于塞车等缘故还是没在报到结束前赶到hotel,啊好惨

尼玛,immortalCO整天都在说我是猫,啊我不是猫啊啊啊


Day 1

上午8:10开考。看了看题。

第一题,居然是TopCoder SRM 561的第二题,我的集训队作业啊= =然而原题数据范围是 $N\le 50$,这题是 $\sum N\le 200000$……

有啥好的性质吗?想了想并没有什么好的思路,敲了个60分暴力去写第二题。

第二题是个题面题……看了好久的题面才知道意思是啥……

发现题目是把 $b$ 求了个 $m$ 维前缀和,直接倒过来对 $c$ 做个差分就做完了,代码好短,让我一度怀疑做法是不是对的。

开始看第三题,怎么有种HNOI的既视感QAQ然而丧多了2333

没思路啊,只会暴力,连只有插入都不会做。那好吧还是写30分暴力,写完了交上去。

这时候10:00,开始研究第一题,准备打表找找规律,手动出了几组数据发现Grundy函数怎么有点奇怪??才发现有个地方vis标记忘了打……

还好查出来了。接着又猜了几个结论都是错的。弃。去检查第二题。

写了个checker对拍,拍了数十组WA了一组,发现有个细节没处理好,及时改对。

想了想我到底该搞第一题呢还是第三题呢,第三题没思路,还是弃第三题搞第一题吧……既然没有啥性质难道就是暴力用个数据结构维护?看到时限2s空间1G似乎明白了什么。

剩1h,开始写Trie合并。

最后10min写完了,结果样例没过不知道哪里狗了……尝试最后几分钟debug出来然而失败了……

出考场估分60+100+30=190。

10分钟后进考场看结果,60+100+0=160。

阅读更多……

一道原创题,欢迎大家来AC

2016-10-31 08:49:13 By WrongAnswer

这题的出题思路……来源于CTSC的NOIP十合一以及matthew99大爷的UOIP十合一……

这题是本人出给校内娱乐赛的一道题(并且被AC了),感觉蛮有意思的就放到了blog上。

另外为什么checker这么慢?因为要防止随便乱试啊2333

下面是正题。

子集计数问题


题目描述

给定无向图 $G=(V,E)$,$|V|=n$,$|E|=m$,$V$ 中的点编号为 $1,2,...,n$。求有多少个子集 $V'\subseteq V$ 满足 $|V'|=k$ 且 $\forall (u,v)\in E,u\not\in V'\lor v\not\in V'$。由于答案可能很大,只需输出答案对 $p$ 取模的结果。

输入格式

本题为提交答案题。所有输入数据 subset1.in ~ subset10.in 见输入数据下载。

输入第 $1$ 行包含 $4$ 个用空格分隔的正整数 $n$,$m$,$k$,$p$,分别表示 $|V|$,$|E|$,要求的 $|V'|$ 的大小以及模数。

随后 $m$ 行,每行包含 $2$ 个用空格分隔的正整数 $a_i$,$b_i$,描述 $G$ 中的边 $(a_i,b_i)\in E$。

输出格式

针对给定的 $10$ 个输入文件 subset1.in ~ subset10.in,你需要分别提交你的输出文件 subset1.out ~ subset10.out。

输出文件共 $1$ 行,包含 $1$ 个整数,表示子集 $V'$ 的个数对 $p$ 取模的值。

阅读更多……

模意义下的有理数运算模板,求hack

2016-10-12 16:03:16 By WrongAnswer

由于要在学校出校内训练,以后要出些卡操作次数的交互题什么的,于是最近就开始做准备

首先是仿照NOI2016国王饮水记写了个有理数类 Rational,可以支持模意义下的有理数运算 +-*/,比较运算 ==!=

可以指定模数

由于是模意义下的,不能比较两个数的大小

这样就可以出一些卡运算次数和精度的题了(比如计算概率和期望之类的题,或者某些数据结构题)

然而不知道有没写错,如果有错的话求hack

阅读更多……

NOI2016游记

2016-07-22 18:58:48 By WrongAnswer

NOI2016,最终我以一道水题不会做没到平均分滚粗了运气好进了前50。

7月21日

就要NOI了。紧张。

然而我连矩形面积并都不会写显然是要挂的

突然想起不会 $O(n^2)$ 的LCIS和石子合并,赶快去看

和immortalCO交流了一道模板题,给他看题以后几分钟就催我要数据(秒题真快),给他数据以后他又说我出的数据太弱可以水过2333

果然我是既不会乱搞也不会卡乱搞的蒟蒻

iCat%%%

无聊把果冻运输剩下两个点跑出来A了

7月22日

早上很早起来出发。

在机场和immortalCO交流算法。

在飞机上和immortalCO交流算法。

到了以后继续和immortalCO交流算法。

(1)

WAer蒟蒻:我发现DP的决策单调性我完全做不动

immortalCO:决策单调性就是找规律

WAer蒟蒻:……

UPDATE:NOI Day2的第2题我确实找了规律,然而没调出来= =

(2)

WAer蒟蒻:NOI2012的题我很多不会。

immortalCO:说谎!

WAer蒟蒻:魔幻棋盘我就不会做。想到了和关键点有关,考虑了差分,但还是不会。

immortalCO:你都想到维护差分了为什么不会?

WAer蒟蒻:……

(3)

WAer蒟蒻:CTSC2014的手写识别好丧,要我的话肯定只能搞十几二十分。

immortalCO:AKF这题分数很高。

阅读更多……

NOI2016考前刷题记(下)

2016-07-20 09:48:15 By WrongAnswer

由于NOI2016考前刷题记(上)写太多了,重新开了个blog。


UNR1滚粗记

就要NOI了,在挂NOI之前先挂一场模拟赛以作心理准备。

7月16日

晚上笔试。

由于之前没背笔试,于是喜闻乐见地爆成了97分……

看了下名次,居然掉出了前100名。这是Fe滚粗的节奏啊……

就这么挂了。坐等UNR考跪。

7月17日

早上以为是8:00开始比赛后来看了一下是8:30……于是去BZOJ上研究了一些题【然而并没有研究出来

8:30。

开场看第1题,一眼这不就是笛卡尔树吗= =(前两天在学校还讲过笛卡尔树的线性构造)

然后迅速写完一查样例1,WA

发现题目理解错了2333

改了一下终于过了样例1

一交,样例全过了【也许样例弱?不知道反正我不管了

这时候9点多了。

看第二题看了好久才明白,然后没思路!0=0!

把期望转成概率来算?然而是个无穷级数而题目要求精确值我就放弃了。【我真是SB

$n=m$ 貌似可以直接算?

写了下发现不对

阅读更多……

NOI2016考前刷题记(上)

2016-07-12 15:56:48 By WrongAnswer

先挖个坑。

以下是吐槽时间

原以为自己实力还行,结果省队集训3次考挂让我明白了什么- -

说白了还是自己太弱了2333 既然弱那NOI当然是滚粗咯

[UPDATE 7/12 16:00] 12号校内训练又被immortalCO和lightning虐成垫底了,一道CF的图象识别题居然不知道有给样例,完全不会搞,最后高二神犇immortalCO、lightning,高一神犇dick32165401都A了这题,我高一蒟蒻WAer(我真的除了WA不会别的了)WA了59个点。。。被暴踩。。。【手动垫底去了】(对着样例随便调下参就A了,日了狗了)整场研究第2题,然而第1题是个std才200b的水题。。。居然没时间想了。。。我好弱啊。。。

要是在NOI可能连Ag都没有了

[UPDATE 7/12 16:50] 刚去推了下第一题……卧槽真的比第二题简单不知道多少倍,半个小时就推出来了,而且确实好写不用拍交到CF上直接A了……我干嘛自己作死不想第一题啊!【我是sb


CF690A2口胡

http://www.codeforces.com/problemset/problem/690/A2

考试的时候脑补了下 $n=1,2,3,4$ 没啥规律,以为是道不可做题就扔了= =事实证明这题相当简单

假设有 $k$ 个物品分给 $n$ 个人,显然 $n\le 2$ 时第 $n$ 个人自己同意就能获得全部 $k$ 个,$n=3$ 时要让一个人同意就得给 $1$ 一个,$n=4$ 时要让一个人同意就给给 $2$ 一个(如果要给 $1$ 就得给两个,不划算),类推得到 $n=3,5,...,2k+1$ 时要给 $1,3,...,n-2$ 各一个,$n=4,6,...,2k+2$ 时要给 $2,4,...,n-2$ 各一个。

其实是我考试的时候手工列完表然后瞎以为答案是 $\frac{n}{2}$ 后来被自己叉了就觉得答案很复杂不可做

事实告诉我们要坚持下去啊!【要从被坑的经历中吸取教训

阅读更多……

直播FJ省队集训大爆炸

2016-07-04 21:15:37 By WrongAnswer

话说省队集训居然开放所有人参加,于是参加的人远远不止15个……

作为高一参加省队集训的蒟蒻WAer……

自然是被神犇们爆虐咯……


Day1

计算几何。

居然有两道省冬原题,所以今天训练并没有什么卵用。

一堆人高分。

然后我有一道原题被卡精度,WA了50分。

坐等本WAer明天继续爆炸= =


Day2

计算几何。完全写不动的东西。

上午讲了各种凸包、半平面交、旋转卡壳之类的东西,由于我是口胡选手所以自然以为都会了2333

然而下午的测试让我明白了我是多么的naive。

第一题:给 $n$ 个平面 $xOy$ 上的动点(保证不存在始终重合的),时刻 $t$ 第 $i$ 个动点位置 $(kx_i\cdot t+bx_i,ky_i\cdot t+by_i)$,$i$,$j$ 连一条边当且仅当存在 $t\in(-\infty,+\infty)$,求图的最大团。

一眼看没什么思路,先敲了个 $O(2^nn)$ 暴力。

第二题,平面上有两个点集 $A$,$B$,$A\cup B$ 内没有三点共线,每个 $B$ 中的点 $i$ 有 $p_i$ 概率选,$1-p_i$ 概率不选,求选出的点的凸包内 $A$ 中的点个数期望值。

想了下不知道能不能用期望的性质搞,但很快被我叉掉了。

算了先弃这一题。

第三题,给两个点集 $A$,$B$,求顶点都在 $A$ 中的最大凸多边形使得其内部没有 $B$ 中的点。输出方案。

……这不是原题吗?虽然我当时也没做出来不过我会做,哈哈。

不过似乎挺难写?算了回去看第一题。

第一题研究了挺久,推了个式子 $\frac{ky_i-ky_j}{kx_i-kx_j}=\frac{by_i-by_j}{bx_i-bx_j}$ 但并没有什么卵用。

想了想决定加个垂直于 $xOy$ 平面的 $t$ 轴,于是变成三维空间求两两相交的直线集。

看样子这些线共面,于是枚举两条线确定平面然后统计平面上的线,呼……终于写完了……

接着开始搞第三题。

排序以后可以DP,开始写各种情况。

一写两三个小时过去了……

终于写完,样例过不了,又调了好久才过样例。我代码能力该是有多弱啊= =

由于省队集训名义上比赛时间是5h,实际上只有4.5h,只剩下半个小时左右了。

赶紧敲第二题暴力。

敲完了。

第一题对拍没问题。然而这题随机数据几乎答案都是1和2,对拍并没有什么卵用。

结果意识到一个问题——

不仅可能所有线共面,还有可能所有线不共面但共点!

觉得要改很麻烦,没时间改了。再说也许数据弱呢

第三题出了一组数据WA了,又改了几个地方才过。要结束了,没时间对拍了。感觉这下没问题了

完了似乎要跪了。。。

开始评测,结果……

阅读更多……

共 40 篇博客