UOJ Logo WrongAnswer的博客

博客

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了,又改了几个地方才过。要结束了,没时间对拍了。感觉这下没问题了

完了似乎要跪了。。。

开始评测,结果……

阅读更多……

UOIP十合一 口胡

2016-06-29 15:00:59 By WrongAnswer

上次来UOJ看发现UOJ多了俩题,而且好多人都A了一题,于是就准备也来A一题

一眼看起来是个模板题,DAG子图计数,然而并不会= =算了先看测试点吧

【以下是本蒟蒻自己闷声做大死的口胡做法,不保证是正解】

测试点1

$|V|=1000$,$|E|=100000$,好大,想弃疗。

不过既然是第一个点应该是个特殊点。

写了个程序验证,发现

$$\forall (u,v)\in E,u\le v$$

于是答案就是 $2^k$ 的形式,很快就搞出来了。

测试点2

一眼看出特殊图,每个点 $i$ 向 $[i-4,i+4]$ 内的点连边,即

$$\forall (u,v)\in E,|u-v|\le 4$$

也就是从左到右决定每条边选不选的时候,只有最近4个点的连通性影响状态。

状压4个点的传递闭包跑个DP,即设 $f(i,S)$ 为已确定点集 $\{1,2,...,i-1\}$ 内边的状态,且 $\{i-4,...,i-1\}$ 的传递闭包为 $S$,考虑边集 $E_i=\{(u,v)\in E|\begin{cases}u=i,\\v < i \end{cases}\lor\begin{cases}u < i,\\v=i\end{cases}\}$ 选不选,可以得到

阅读更多……

Hack界面里的Judging是怎么回事?

2016-06-08 17:02:46 By WrongAnswer

去看Hack页面。

结果发现除了绿色的Success和红色的Failed以外,还出现了一个蓝色的Judging。

然而它不可能在运行啊。

这是bug吗?

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日。

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

阅读更多……

共 37 篇博客