UOJ Logo matthew99的博客

博客

HNOI D1T1 hunt

2018-04-15 13:32:46 By matthew99

第一次给HNOI出题(其实也是第一次给NOI赛事出题)。

题目链接

稍微了解一点MIT的人(比如知道Infinite Corridor不是真的无限长)可能看完题就知道出题人是谁了(然而好像因为奇怪的原因不能把学校名写在题目里,不过大家看到“某大学”,而不是“T大”或者“P大”可能也知道是怎么回事了?)。

简易题解:

如果第i个数之前的运算符是and,则这一位设为1,否则为0,得到的二进制数记为$x$。

对每一位分别考虑,对于第i位,如果第j个数是1,那么这一位设为1,否则为0,得到的二进制数记为$b_i$。

以左边为最低位,按前缀归纳容易证明,第i位的结果为1,当且仅当$x < b_i$。

我们将b从大到小排序,结果设为c,那么答案不为零仅当在c的顺序下,r中没有任何0在1的前面。找到r中第一个0的位置,假设是k,那么解x要满足$c_k \le x < c_{k – 1}$,于是答案是$c_{k – 1} – c_k$。

题外话:

当时出题的时候很紧张,是真的紧张,因为觉得实在是太水了。我当时的70分做法是猜结论,大概就是猜到有用的DP状态有$O(nm)$个再bitset。然后觉得这实在好猜了,其实根本不用猜,只要你注意到DP状态可能不满这个事实,然后直接记录有用状态就行了。

我当时很怕结果出来十几个AC,全场70。然后就再也没人找我出题了。

当时就不停的想HNOI有什么水题,是不是比我这个更水来安慰自己。

后面想想给大家送送分也好,至少这个题不是原题或者错题,能让自己成为大众喜闻乐见的出题人也不错。

结果分数分布大家都懂的。我至今不知道拿50分的是怎么回事($n$只开了$500$?拿50分的人能不能在下面评论区说一下怎么拿的)。于是我的顾虑成了多余的。

不过这也不错,一来我的题终于不是HNOI最水的题了,二来我的题很可能送人进队(比如你A了或者高分暴力),不太可能送人退役(最多就是你30分暴力分挂成10分或者0分)。Still,如果有人因为我的题暴力写错退役我只能抱歉了,对不起我给了30分暴力分

至于重测,那是因为我在Windows下造的数据,然后由于跨操作系统,换行符出了点问题-.-

考场上被各种倒推做法虐了。

其实倒推本质就是动态维护字典序。我很高兴大家因为我的题发明了一种新的排序算法。我可以把这个题改成每次模一个不同的数,然而似乎还是有基于倒推的奇技淫巧可以做。我也可以出成二进制高精度什么的,但是感觉它们还是可以过,也就是说在不懂正解只会倒推的(也就是大多数)人眼里,我把这个题目弄得更毒瘤而不是更神了。

说起来$O(\frac{nmq}{w})$可能是能过的(UOJ上能过TAT),解决方法大概是把$q$弄大,比如$10,000$。但是读入就很tricky了,可以压字符读入但是这样也很毒瘤。

所以大概这个题也只能放了吧,虽然不得不说我不是很喜欢这种倒推的做法,太直接了,个人感觉和标算没法比。但是也没办法,就像一个优美的题,结论就是输出a+b,也会有不明真相的群众写出一种和按位模拟加法等价的做法,你还没什么办法卡。

评论

vfleeking
orz myy
vfIeaking
orz myy
dlzzq2002
orz myy
kczno1
正解好简洁
514flowey
Day1T1 50分选手(之一)在此。 因为自己太菜写的nmq/32的倒推做法,其中m是bitset的大小(我开的1000)。n达到1000的时候会被卡常数,所以没有拿中间的20分 (这种时候应该多开一个namespace) 其实还有bitset开到5000的梦想选手被卡成10分。
Demerzel
我就是把bitset开到了5000大小然后爆10的梦想选手(大雾 考试的时候没想那么多= =
wearry
考场想到了正解思路, 但是没有意识到这个东西排序后是连续的, 所以强行算出两两串之间的最长公共后缀, 预处理出了所有可能的询问串的答案, 最后O(m^2)算法被卡常(虽然现在也不知道怎么卡进去), 成功获得70分
liu_cheng_ao
本蒟蒻是用倒推做法建字典树推出排序做的……

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。