UOJ Logo WrongAnswer的博客

博客

APIO2016酱油记

2016-05-09 17:48:41 By WrongAnswer

一直听说APIO是个神奇的比赛【以前似乎有CTSC Au的神犇挂APIO?】于是更加紧张了233

事实证明我实力还是不足最后200都没上

——————————

5月5日。

APIO前有个练习赛,在网上进行。练习赛有两道题,一道是交互题network,一道是传统题sequence。

今年APIO有交互题!然而我交互题巨弱无比怎么办?

其他同学都A了一题我才登进网站去做- -第一题network看起来似乎挺可做的?

第一题network,题目给一个无向无权图 $G=(V,E)$ 以及两点 $s,t\in V$,要求给出从 $s$ 到 $t$ 的任意一条最短路,其中可以调用 ping(i, j) 询问 $i$ 到 $j$ 的最短路长度。不管先敲了个 $O(n^2)$ 的大暴力再说,25分……一看怎么里面的点有的AC有的WA?

子任务制就是好(sang)啊!可以在一个子任务里塞一大堆点,然后卡各种方面的细节,只要有一点小问题就可以卡到0分。

后来强行优化并逐个通过了这些子任务(一共交了4次)。这题被大神犇 @lightning 吐槽为大水题(@lightning:原来是这么水的APIO!@immortalCO:XXX嫌APIO题水啊!后来@lightning在APIO的时候真的A了交互题,巨强)

第二题sequence是个算(xi)法(jie)好(keng)题,给一个长度为 $K$ 的十进制数字序列 $a_0,a_1,...,a_{K-1}$ ,求最小的 $N$ 使得对任意整数 $0\le i< K$,$N+i$ 的十进制表示包含数字 $a_i$。

这题 @immortalCO、@y0rkl1u、@dick32165401 等大神交流了一段时间以后都想出了AC做法,就我还傻呆呆地不会。

一开始完全没思路。想了很久发现问题具有递归性质?枚举 $N$ 的个位就可以得到一个规模为原来 $\frac{1}{10}$ 的子问题,问题缩小到 $K\le 2$ 就可以贪心了。但是细节很多,要判0什么的,推导了很久,最后还WA了一发因为预处理 $10^i$ 没处理满第二次才AC。【那时候是5月5日22点,第二天练习赛就关闭了,还好我及时

另外APIO能多次提交确实是个好东西不然就爆0了

然后刷了点别的题练手,@immortalCO把UR10的世界线A了,而我一直调不出来了,完蛋了我交互题真的要狗带了

——————————

5月6日。

第一天培训。讲的比我想象中的有意思。

阅读更多……

CTSC2016提答记

2016-05-05 10:23:47 By WrongAnswer

神犇的CTSC:怒A数据结构题,狂虐DP题,吓傻出题人。

蒟蒻的CTSC:捞点部分分,磕提交答案题,依赖出题人的良心。

我就是蒟蒻啊- -两天CTSC得分最多的题都是提交答案题……

先祝贺一下咱们学校的神犇 @kfdong 过关斩将进了IOI!神犇 @immortalCO A掉第1天第1题,直冲rank8!

——————————

Day 0。

5月1日,早早地赶上了到北京的飞机。(心想还有好多题不会,真是无比虚啊)

和 @immortalCO 交流了一些算法。

由于比较早,比较困,所以大多数时间都在休息【老师:今天的主要任务是休息

我依旧处于颓废状态于是晚上也没刷什么题不到22点就去睡觉了233333(另外宾馆不错)

——————————

Day 1。

设了6:30的闹铃但事实上不到6:30就醒了,然后开始紧张上午的比赛(Day 1就那么紧张干吗)

吃完早饭进考场脑子一片空白,盯着时间看,8:25,8:26,8:27,8:28,8:29,8:29:30,……

开始了。

(由于我比较逗比先看到的不是试卷上的题目而是文件夹)

travel,suffix,noip。

前两个看样子是传统题,第三题noip就比较有亮点了(我猜它一定叫“NOIP十合一”),看样子是一道有趣的提交答案题。

看题。

第一题好长,似乎是一道码农数据结构题,先写个暴力吧,等下……

第二题不长,但一看就完全没有思路,似乎是一道巨丧的DP题,先写个暴力吧,等下……

第三题果然名称叫“NOIP十合一”,似乎比前两题都可搞。先开始做这题吧!

阅读更多……

APIO2013 TASKSAUTHOR 题解

2016-04-26 10:56:11 By WrongAnswer

题目描述

http://uoj.ac/problem/109

解法分析

要区分两个程序 $A$ 和 $B$,就要知道 $A$ 和 $B$ 各自的优缺点.

1. SSSP

FloydWarshall 的运行效率取决于点数 $V$,通过代码可以发现 $\mathrm{counter}=V^3$,与询问数 $Q$ 无关.

OptimizedBellmanFord 通过多轮松弛求出最短路,从代码中可以看出,每轮按照边在输入文件中的顺序松弛,当 $s$ 出发的最短路恰好沿着输入边的顺序时,一轮松弛就能求出最短路,但如果恰好逆着这个顺序,则要松弛 $V-1$ 次才能求出最短路.

ModifiedDijkstra 当边权均为正时就是复杂度有保证的 Dijkstra 算法,而当有负边权时类似贪心的 SPFA. 不难发现当从 $s$ 出发的最短路第一条边不是 $s$ 边权最小的出边时,可能有大量无用的松弛操作.

2. Mystery

Gamble 为题目设计所用,不考虑.

RecursiveBacktracking 为暴力迭代深搜求解图的色数的程序,复杂度指数级,随便的图就能使其 TLE,要使其不 TLE 就要构造答案接近于程序的枚举顺序的图.

详细题解

测试点1

问题为 SSSP,$A$ 为 ModifiedDijkstra,$B$ 为 FloydWarshall,$T=107$.

要使 FloydWarshall 程序 TLE,只需令 $\mathrm{counter}=V^3>10^6$,即 $V>100$. 由于输入文件不能包含超过 $107$ 个数,只要生成 $V=101$ 的空图(没有边)以及任意 $1$ 组询问即可.

阅读更多……

APIO2014 Beads and wires 分值似乎有误?

2016-04-25 16:11:18 By WrongAnswer

刚刚研究APIO2014的Beads and wires,写了个$O(n^2)$做法。

看了下子任务能拿$28$分。

交上去,发现只有$26$分。

点进去看,发现第一个子任务本来是$13$分,结果只有$11$分。

然而根据页面里面的得分,$11+15+29+43=98$,不到$100$分。

是BUG吗?

链接:http://uoj.ac/submission/65761 点进去就会看到100分程序的四个子任务加起来不到100分

无比玄学的事情

2016-04-21 19:45:35 By WrongAnswer

今天为了学斜率优化,去做了下APIO2014的Split the Sequence。

写的时候发现凸包里面的点,x是int级别的,y是long long级别的,叉积似乎会爆long long?

于是手写了大整数乘法,然后交上去TLE了。

(一开始T是因为用了二分复杂度差,改成不二分以后还是TLE)

强行用一些黑科技卡常数卡过去了。

由于跑得太慢垫底了,于是想了解如何优化程序效率。

看到有人直接整数除法下取整,过了。

然而斜率不一定是整数,到底对不对?我构不出数据卡这个做法- -(那么这个做法是不是对的?)感觉略玄学。

还有人直接long long叉积也过了,我试了下

100000 200

10000 10000 10000 10000 10000 ...

的数据,确实A了。

依旧比较好奇为什么不会爆- -理论上叉积是10^27级别的啊?有些玄学。

然而我把程序改完以后跑的时间仍然是rank1的5倍,百思不得其解。

用了个计数器counter计数,都是3×10^7~4×10^7,然而为何我的程序慢那么多?

各种调试……

最后脑洞大开,原本我的DP数组是

f[100010][210], g[100010][210]

改成:

f[210][100010], g[210][100010]

跑的时间就是原来的1/4了!进第一页了!UPD:现在又不是第一页了

阅读更多……

论“大胆猜想,不用证明”思想的危害性

2016-04-11 14:23:24 By WrongAnswer

昨天UR13本渣又参加了。A题看起来挺可做的。

经过我的推导,发现最优解可以从小到大删数构造。(一开始不太放心是不是对的于是假设了下交换顺序反证了一下发现是对的,再对样例验证了下没问题)。

正要想用单调栈什么东西乱搞。

@immortalCO 大神提出说似乎答案只和最大的数有关,我居然SB地就信了。(然后让我测下样例居然也过了)

“大胆猜想,不用证明!”

于是你们就看到了我第一发通过Pretest。

直到快要比赛结束,我才感受到了出题人的良(e)心(yi)。回头想第一题卧槽我构出了一组数据卡掉了这个错误算法!

然而并没有什么卵用……没时间改了……

最后的结果是极惨的——

爆10分。

接着的结果不忍直视——rank掉到76,rating掉了54。

总结:在猜结论的同时,一定要证明正确性,否则被错误结论误导损失惨重。一定要相信自己的推理,而不要相信奇怪的言论。

FJOI2016爆炸记

2016-04-10 17:28:54 By WrongAnswer

今天福建省选二试。果然,还是我太弱了,完美爆炸。

[以下是废话部分]

早上起床迟了,7点才起来,然后由于自己作死把手机掉床缝里面去了找了好久才找到(还好找到了)。

@Paladin100100 进宿舍催感觉很急于是匆忙吃了个早饭检查了下证就出发了,车上一直看考生须知,感觉就怕哪里看错了- -

来的时候和 @immortalCO 大神交流了一些算法(呸只是聊一聊啥都没交流)接着就入场了。

各种紧张。

[以下是正题]

“估计今天的题会很丧。”我想。

7点55分,电脑右下角时间居然是7:50,卧槽居然不能调?(接着监考老师叫我们把手表摘了于是考试的时候只能把时间加5来推算了2333)

发卷。

一看到题,本人立马傻掉了。

第一题“树的平均路长问题”,题目一开始就是个带sigma的公式,感觉相当不可做,再看后面,靠,居然是红黑树,一堆定义看得好晕。

总之第一题看完就先跳过了- -

第二题“所有最长公共上升子序列问题”,是求两个序列有多少个最长公共上升子序列,这不是和一试的题类似吗?再看数据范围,卧槽,序列长度n,m<=5200,元素范围20000,似乎套不了一试的那种做法,先放弃- -

第三题“n点游戏问题”,等等这是大爆搜的节奏吗?跑了下n<=6都跑不出于是直接弃疗。

第四题“密码破解问题”,树的路径计数,这……点分治应该能过吧。

感觉第一题输入一个数输出两个数而且输入的n<=5000似乎可以打表。试试?

噫……总算看明白了题意,求的是n个节点的红黑树所有点的深度之和的最小值和最大值,推了个O(n^3)的式子,写了一发试了下样例过了!那就打表吧,要求最大值和最小值,那就先打最大值吧,开打……

接着……该写哪题呢?

阅读更多……

UOJ 59 小Q运动季 checker和评分标准和原题不一样?

2016-03-13 14:54:01 By WrongAnswer

前段时间做WC2013的小Q运动季(直接说同余方程组不就好了嘛=-=)

上网找东西的时候无意间找到了这个:http://www.doc88.com/p-2708100547886.html

然后看了下同余方程组(小Q运动季),发现:原题当中,得2分的条件是

$w_u>0$

而UOJ上是

$w_u\ge 0$(也就是和得1分的条件一样)

另外checker的格式也不一样……我用的时候并不是显示 Correct! x / m。

【以及前2题似乎也有不一样的地方:前2题的原题时限分别是5s和10s,UOJ上都缩短了。因为UOJ评测机快?】

求解答。

共 38 篇博客