Codeforces April Fools Day Contest 2020

愚人节专场,打一乐。官方tutorial

A. Is it rated?

puts("no");

B. Limericks

看样例35->57, 57->319, 391->1723,敏锐的觉察到可能是质因数分解。

for(int i=2;i<=x;i++){
        while(x%i==0){
            printf("%d",i);
            x/=i;
        }
    }

C. …And after happily lived ever they

数据范围是0~63感觉和二进制有关。

又听同学说标题对应的正确顺序是And They Lived Happily Ever After,于是感觉是个二进制位置的置换。

    // And after happily lived ever they
    // 0   1     2        3    4     5
    // And They Lived Happily Ever After
    // 0   5    3     2      4     1
    // 5   0    2     3      1     4
    // 
    //  2:  000010   000010
    //  5:  000101   011000
    // 35:  100011   110010
    int x;
    int trans[] ={4, 1, 3, 2, 0, 5};
    int y = 0;
    scanf("%d",&x);
    for(int i=0;i<6;i++){
        if(x>>(i) &1){
            y|=(1<<trans[i]);
        }
    }
    printf("%d\n",y);

D. Again?

乍看A+7位数字像oeis的序列id,但是考虑到评测机不能访问网络,所以其实只是最后一个数字的奇偶。

    scanf("%s",s);
    if((s[6] -'0' )%2) puts("1");
    else puts("0");

E. Jordan Smiley

face

这是一个64*64的图,问某个位置是在图形里面还是外面。

画图工具的填充工具对内部区域填充纯黑,之后用Python的Pillow库处理出黑色的位置,然后把表打给c++。

from PIL import Image
import numpy as np
I = Image.open('./untitled.png') 
I_array = np.array(I)
def pos( x):
    return x*15+7
s = 'int a[] = {'
for i in range(64):
    for j in range(64):
        if I_array[pos(i),pos(j), 0] == 255:
            s+='0,'
        else:
            s+='1,'
s += '}'
print(s)
int a[] = {0,0,0,0,...,0};
int main(){
    int x,y;
    scanf("%d%d",&x,&y);
    if(a[x*64+y] == 0) puts("OUT");
    else puts("IN");
    return 0;
}

F. Elementary!

没猜出来。

upd: 看了题解,原来是判断字符串是不是由元素缩写组成。

G. Lingua Romana

per nextum in unam tum XI conscribementis fac sic
    vestibulo perlegementum da varo.
    morde varo.
    seqis cumula varum.
cis

per nextum in unam tum XI conscribementis fac sic
    seqis decumulamenta da varo.
    varum privamentum fodementum da aresulto.
    varum tum III elevamentum tum V multiplicamentum da bresulto.
    aresultum tum bresultum addementum da resulto.

    si CD tum resultum non praestantiam fac sic
        dictum sic f(%d) = %.2f cis tum varum tum resultum egresso describe.
        novumversum egresso scribe.
    cis
    si CD tum resultum praestantiam fac sic
        dictum sic f(%d) = MAGNA NIMIS! cis tum varum egresso describe.
        novumversum egresso scribe.        
    cis
cis

sic, cis应该是begin,endvarum,resultum应该是变量,praestantiam应该是类似NaN的东西。

第一段代码可能是存在了一个数组里,然后倒序了。

观察到答案和x^3*5很接近,猜想varum tum III elevamentum tum V multiplicamentum da bresulto.是三次方乘5的意思。

upd: 看了题解,这程序原来真的是个语言的源码,演示的是TPK算法,这个算法大概就是用来demo语言的,算法内容是读11个数字、逆序、输出每个数字5*t^3+sqrt(fabs(t))

H. It’s showtime

Invocation failed [COMPILATION_ERROR]
Can't compile file:
WHAT THE FUCK DID I DO WRONG:
Invalid input 'R', expected Root (line 1, pos 1):
Root
^

=====
Used: 0 ms, 0 KB

这个UnknownX语言的第一个字符该是啥都没试出来。

upd: 看了题解原来是这个语言。ArnoldC, 第一行必须是IT'S SHOWTIME

后缀自动机(SAM) 可视化

又修了一次这个工具,因为要用。

Build!

用Python3写了个OJ

这个OJ以后可能搭在学校吧..(论造轮子的修养)

https://github.com/zrt/XOJ

主要为了练习下python和HTML。

分为web和judger两个部分。

web主要处理OJ非评测的部分,judger主要处理评测部分。

web:

使用了tornado框架。

前端用了bootstrap模板。

数据库用了MySQL。

judger:

web有评测任务时直接通过http发送评测内容给judger,judger也使用tornado监听评测指令,然后评测结束callback给web。

judger用Celery+RabbitMQ分配评测任务。

评测核心部分用Lo-runner

理论上可以支持许多judger。


基本功能写完,在sjzez.com:777不删档内测。


感谢Chenyao同学认真指导。

我的集训队作业

第一次作业

我的题目分别是Codechef Nov 2014的三道题 :

  • Chef and Churu https://www.codechef.com/problems/FNCS
  • Sereja and Order https://www.codechef.com/problems/SEAORD
  • The Spelling Problem https://www.codechef.com/problems/SPELL

福利内容?

自认为写的题解还不如官方题解。QAQ。
T1简要题解: 分块+树状数组。对函数分块,预处理每个位置在每一块里出现次数。
T2简要题解: 贪心+排序。证明答案一定等于max(max(ai+bi),max(sumA,sumB)),然后贪心或随机化。卡掉了几个不正确的贪心。
T3简要题解: hash或trie树。给字典中的单词赋一个权值。对于每个不在字典中的词,尝试所有的出错方法,取权值最高的那个词。

每题一组数据:
链接: http://pan.baidu.com/s/1hqyKkTY 密码: iqfz

第二次作业

进度:未知

NOI2015 行记

NOI2015这么快就到了呢。

作为弱省高一开始学OI的蒟蒻。

一辈子也就参加这一次NOI吧。

写写日记记录下吧。


感觉时间过的好快。

好像昨天才听说了OI,今天却已经到了国家赛的现场。

“陪你开始OI的人可能不能陪你走到最后,一次擦肩而过就可能再也见不到了。”

一路上,认识的人越来越多,校内的、省内的、省外的,一同的人却越来越少。


“支持你的,最初是兴趣,后来是梦想,最终是使命。”

最初不知是因为什么走进了竞赛班,最后可能是出于对电脑的热爱选择了OI。时间过得这么快,我也走到了竞赛的最后了吧。


“考好了买个吉他,考挂了当个学霸。”

来自某位神犇的说说。我们都需要一个好的心态去面对OI生涯中最后一场考试。大不了回去高考。

7.15

在坐了一晚上的火车后,在10点半到了杭州。

火车上的餐车味道还不错,就是价格稍微有点高。

在上车前遇到了一中的刘天怡与刘沛良。

邯郸站上来了薛欣磊。

路上听了一路音乐+玩手机。

火车上孙庆岩给我展示了修改BIOS后的笔记本的漏电usb口。可以实现充电宝功能,感觉很赞。

火车上感受了孙庆岩高超的手机游戏技巧,自愧不如。(雾。

火车站有人来接站。走了一截后上了一辆中巴车,二十多分钟就到了学军中学。

大概是因为冬令营时来过吧,看着学军比较熟悉。

然后就在行政楼一楼报道咯。登记下。然后发现和耿明灏、孙庆岩还有一中的刘沛良住一个房间。

领了个书包。有秩序册啥的。

然后志愿者把我们领到了宿舍。

感觉还不错。

4个人住8人间。

有空调,没插销。

貌似是女生宿舍。

我发现我的ThinkPad上也有一个黄色的usb口,于是研究了下怎么漏电。

貌似只能去图书馆充电。

(另,Google手机输入法不错哦。这篇文章大部分都是拿手机打的。

空调不给遥控器。我们有手机遥控器233。

感觉杭州似乎比石家庄更适合生活?也许吧。

(另。胸牌背面有一道修正带覆盖的痕迹。刮开后竟然是“冬令营日程”。真是6。

然后去吃了午饭。还不错,挺丰盛的。碰到几个认识的选手。

中午他们其他人小睡了一会。。

下午决定出去转转。然而冬令营已经去了两次西湖,不过鉴于耿明灏神犇还没有去过,于是打算去转转。

于是我们三个背着奇怪的单肩包(发的)出去了。

孙庆岩用滴滴打车叫了一个车来。。然而那辆车给堵半路上了。导致等了好久才上了车(貌似杭州还按时间限号?)。

到了湖边。感觉好热好热。然后上次没开的莲花开了。

在湖边转啊转转啊转。

耿明灏在写诗。孙庆岩在用ingress在各各景点入侵,完成任务“西湖十景”。

过了很久大家觉得没意思了。

就准备回去咯。

孙庆岩又叫了个滴滴。

这次蛮快的。

回来刚好晚餐。都带着餐券。于是直接去吃饭了。学军的饭一向不错。

吃饭时坐到了吉林众旁边。

吃饭过程中得知了晚上电子阅览室开门,决定去那上网。

到了图书馆二楼等了一会一个人来开门。说一共有70多个位置。然后许多人就没有位置了。

(阅览室的干什么的都有233。

PoPoQQQ貌似在做一些和谐的事。

过了一会电都充满了。决定回去。

到了宿舍,挂上了蚊帐。

听说一些人在群里撕逼。不明觉厉。

背背笔试玩玩手机听听音乐睡了。

7.16

早上6点40起床。

昨晚睡得还不错。

听说石家庄下大暴雨了。

上午大概是拍合影和开幕式。

吃完早饭去田径场。人大概多了起来。

由红色衣服的志愿者摆一个CCF NOI 2015造型。

然后等了好久好久还不开始。。

结果听说老师堵路上了。

等了好久老师才来。

于是一个省一个省的站上去。

发现我们的位置已经站上了别的省的人。于是我们站到了其他省的位置。

于是最后哪个省好像被无情拆散填补空隙了。。

拍的很快。手动全景照片。

于是由志愿者引导去会议中心看开幕式。

先是几个制作精良的宣传片。

学军中学的乐团还是蛮赞的。

然后各种领导讲话。

然后中间隔了一个节目。

然后尊敬的杜子德研究员讲话。中间还请了是搞deepin的王勇与我们交流。他说,现在都是上过大学的给没上大学的打工。

然后有一个意义不明的舞蹈节目《课堂畅想》233。

最后弄了个球启动。

感觉灯光挺亮瞎眼的。

杭州电视台的主持人不错。

然后宿舍休息去吃饭。

下午笔试。

外边排队等了好久。用手机又看了看笔试题。

然后进去。环境还不错。

都是蓝色的。

找到了自己的位置。

然后听王宏说了今年获奖政策。

貌似A类加5分然后大排队。

然后笔试。

中间试了一个题,然后点关闭没点准,把笔试题界面给关了。。T T。

再打开做的题都没了。

还好时间不紧,又做了一遍。检查了检查。

后来出分了发现是100。

中间看到了右边AH-01(吓。

之后试了试机子。就和孙庆岩出来了。

找了圈耿明灏并没有找到T T。

然后就是晚饭。

晚饭时碰到了dx神犇(美丽的邂逅啊)。

晚饭后就去电子阅览室咯。带着插线板有用啊。

依然干啥的都有= =。

看了看模板。刷了刷知乎。

明天NOI day1了,早点睡吧。

7.17

早上起来吃早饭,然后去体育馆前面等着入场。

然后大概8:10 开始的考试。

考试过程略。

还算顺利,中间看到吉利打贪吃蛇。

后来得知右边是alpq神犇,%%%。

然后出来没心情吃饭。

就回宿舍了。。

中间得知考了300。gmh好像差一点。

然后下午就没去自己机子查分。

大家二试都RP++吧。

听说Au线250?

晚上看电影。

看第二天才在中国上映的《模仿游戏》。

感觉我们这些人里再过n多年会不会走出一个图灵奖或者改变未来的人?也许吧。

人类就是在不断创新过程中前进的。

7.18

听说今天好好玩,二试能考好。

先去的Alibaba,sqy表示是JD用户。

肩上还贴个阿里的标志。

好像一个人在报告厅讲了些什么东西,什么淘宝图片加载很快啦,我们数据量很大,每天入口1PB,是厉害。

然后就去了西溪湿地。

“两年OI一场空,西溪挖宝变富翁。”

有人提前藏好了奖券。

而我们是最先到的几个省之一。

每个人收入都颇丰。

sqy好像刚开始弄到几个三等奖。

后来我们在终点碰到两个志愿者。

给我们看了一等奖的埋藏图片。

很普通的环境。

不太知道在哪里。

我们又翻回去找了一趟。

就在刚下船的位置,河边一个危险的位置,sqy机智的找到了一等奖。

“闷声发大财,这是最好的。”

后来下大雨了。。。

就提前回去了,学军还准备了姜汤。

后来能兑奖了,听说一共40个奖河北兑了10个?

果然先到是有优势啊。

我沾sqy光,弄了个三等奖。。(不过后来落在了学军宿舍。)

7.19

二试。

像一试一样。

考试过程略。

最后一道题写到死都没写完。。

码力不足。

后来得知我250分,稳了。

gmh,sqy都不太好。

最后好像全国第6。。

好像河北今年1金10铜?

感觉还没有签一本的时候激动。

后来高校宣讲也没认真听。。

之后就找THU换了个协议。

7.20

上午趣味运动会。

需要4个人,我们组了个路人组,分布:吉林、福建、海南还有我河北。

然后我们在JL-YGY的强大领导下,各个项目分工协作。

其中一位同学在一个项目里跳坏了裤子,于是又换了一条。

然后凭借着拼图项目的无比巨大的优势夺得运动会第一。

下午是闭幕式。

表演节目。

然后颁奖,上去了两次233,一次是运动会那个送了个智能插座,另一次是Au。

各种领导致辞。

之后

旅行开始了?

感谢老师、各地同学。

祝大家Good Luck~。

官方文:http://www.noi.cn/noi-news/noi/680-ccf-noi-2015

THUSC2015 行记

THUSC: Tsinghua University Summer Camp.

我参加的当然是OI营咯。

之前一直纠结是去P大夏令营还是T大夏令营。

经过与学长的交流还有自己的思考终于决定去THU的啦。

sqy去了P大的夏令营。

day0.

在西郊宾馆里报道,碰到了河北众和其他省的一些神犇。

和衡水的phx神犇住进了一个房间。

然后等了很久才拿到房卡。

又鼓捣了半天弄得能上网了。

不错~

然后看到phx神犇拿出了一台崭新的电脑,在看着些什么。

我说复习下模版题吧。

然后他让我做‘Attack’ 这个题,我突然想到好像是冬令营的时候他问过我这个题,可是我现在还不会。。

我看完题说可以拿kdtree水吧。

他说李超的数据,应该比较强。

我写了一发,结果T了几个点。。

去Tsinsen看了下当年的论文,发现原来是分块然后主席树一块走一走。

他让我今天晚上写,我写了一点就放弃了。

Pku的貌似比我们早一天。

day1

西郊宾馆的早饭还是不错的,还有一些外国人?

我们的到来显然拉低了他们早餐水平。

然后去THU拍合影。

拍完合影去阶梯教室看开营式。

吴文虎教授真是健康啊,好厉害。

看来多运动还是有必要的。

听起来今年政策还不错。

并且T校还说要坚持搞下去。

然后10:00 去东主楼试机。

试机题写错QAQ。

考试环境是一个内网的Tsinsen。

中午说不回宾馆了,让自己解决。

我于是去了THU边上的一家KFC。

有很多OIer呢。

要了份套餐开始吃。

吃着吃着,我左边的人可能看到我穿的‘信息夏令营’的衣服了,问我,你们编程用VB么?

我说我们一般用C++。

突然看到手机有个短信,发现在早上8点的时候流量爆炸了,于是我还津津有味的用了一上午流量。

速开流量包,速充话费。

后来要了杯咖啡喝了。

下午正式考试咯。

THU比较痛快,就考一次结束。

我想了下去年题的难度,吓了个半死。。

不过听说那些比较厉害的人都没来出题?

然后看到了题。

“异或运算”、“平方运算”、“解密运算”。

一个人出的?

我记着去年他们说出题人在考试前都不知道互相出的什么题啊。。

然后一读第一题,<=1000?,想到了昨天晚上那个思路,不就是Trie树上一块走一走么。

感觉今天考试不难。

第二题奇奇怪怪,给出这么多p难道要找规律?

然后看第三题,啊!我做过。

怎么做着来着?好像当时写了个暴力就A了。。。

后来想了下倍增,写了好久好像没问题了。

然后看第二题,好像循环节都在60以内?。。好像还不会。。

于是有几个循环节是1或者2特判了下,大概有20-30分?

然后发现TKD还有一些人在交A+B,可能是提交哪里有漏洞了吧。

然后考试就结束了,预估分数220-230吧。。

估计永远知道不了考了多少分了。。

PoPoQQQ出来说AK,然后突然发现键盘没拿回来然后跑去那键盘,最后拦车上车。

后来回来的车上TKD说,这A+B真tm难,怎么写都不对。。

晚上想了想怎么面试。。

感觉加上以前WC,APIO,CTSC的成绩应该能进面试。

day2

像昨天一样去吃早饭。

没有接到电话。

不过其他人好像也没有接到。

吃完了会宾馆等着的时候,8:12的时候,接到了一个电话,让我去一个会议室准备面试,准备2分钟自我介绍,面试持续10分钟。

然后和家长打了个电话就去会议室啦。

会议室家长不让进。。

面试大概有80人。

刚开始我们都在玩着手机,后来来了一个人说禁止用手机,看到了取消资格,我们是有差额的!

于是大家都收起来了。。

会议室等待的人越来越少,越来越少。。

貌似是按照拼音顺序来的,但是也不是严格的拼音顺序。。(后来发现是分成5组,每组拼音顺序。)

从9:00 到了11:40。

说好了面试12:00结束。

来了个老师说:“The last not the least.”

然后给了我一张纸,说可以打草稿。

等上一个人出来,我就进去了。

进去了先问好,发现没有想想当中的王宏等人。

好像都不认识。

然后把准备好的自我介绍说了,声音有点抖。

然后到了提问环节!

Q: 你为啥搞这方面?

A: 可能是小的时候相当黑客吧。。

Q: 黑客实践过么?

A: 好像有点法律问题,我只是更关心了互联网安全、漏洞什么的。
他说,嗯。

Q: 如果不从事计算机,那打算学什么呢?

A: 我说,金融吧,¥&(¥@#%。

Q: 你刚才说你会拉小提琴?考过级什么么。

A: 考过,x级(如实)。

Q: 我来考你个数学题啊,你可以拿笔算算。我们知道一条直线可以把平面分成两部分,两条直线可以分成4部分,那n条直线呢?

A:(这不是小学数奥题么。。我画了下。。)然后我说是$\frac{(1+n)n}{2}+1$。

Q: 你的答案是对的。说说过程?

A: 第n条直线会与前n-1条直线各有一个交点,也就是分隔了n个区域,也就是多出了n个区域,于是等差数列求和。

他说,很好,你的面试结束了。

我拿着草稿纸就走了。

感觉还不错!

中午吃不下饭。

下午2点开始院系介绍。。介绍到4点。

然后发协议。

说协议分三档,分别为无条件一本线,NOI前100一本线否则降60和NOI前100降60。

并且一本线人数比去年多。(去年大概是30个吧。。

然后好像是故意打乱了念的。

我领了之后发现没有数字。。嗯一本线。。稳了。

后来发现领错人的了又换了下。。还是没有数字。

好像大家都领到了满意的协议,那些没领到满意的协议的NOI加油吧-。

THUSC结束了。

HEOI2015 行记

陪你开始OI的人未必能陪你走到散场。一次擦肩而过之后可能就再也见不到了。

这几天过得好乱,也不知该说些什么。

Day 0

今年省选在河北师大,和去年noip一样。

听说dyf大爷要来,也不知道来干啥。

考试前一天去试机萌萌哒。

键盘软的不行不行的。

打了个SA,FFT?调了半天才对,反正估计考的可能性不大。

╮(╯▽╰)╭

然后高一的连试机都不来。(真是厉害。

Day 1

第一天好紧张啊好紧张,一想弄不好就滚粗了就害怕。

然后一切正常的进了考场。

看了第一题。发现只会三十分树形背包。

看了第二题。发现只会三十分暴力。

看了第三题。好像是乱搞题。

maya。。看了第一题数据范围那么大。

就去想跟m无关的算法了,后来想到贪心,和暴力拍的没问题。

一想“富贵险中求”,就决定交了贪心。

后来觉得第二题分块可搞,就写了,拍了,没问题,好像有点卡时。

然后第三题sb题,随便搞搞和暴力拍。

就结束了。

先去吃饭。

没食欲QAQ。

然后回去发现 100,0,100。觉得很费解。。第二题怎么爆零了。

然后得知某位神犇考挂了。。sad。。(可能是压力太大了吧。。

数据肯定是没问题的。

回家看了半天我的程序,发现我考场上竟然把$10^9$以内的数xor值还认为是$10^9$以内。于是挂掉。。爆零。

改了测了下。。100.。。Sad。。

然后第一题正解就是那个贪心,第二题正解就是那个分块,第三题正解就是那个乱搞。

这天不是rank1,但是听说有人的程序有问题?

貌似总分还是rank1.

Day 2

一想和rank2现在差50分,就放松了一点。(TAT

然后一切正常的进了考场。

看了眼第一题,开头是“在某一天,你有了一个女性朋友。”。。

→_→

期望啥的。暴力吧。

看了眼第二题,貌似生成树计数,让mod10^9

看第三题,字符串,子串,子序列啥的。

然后大部分时间都在搞第一题。

输出了下暴力的方案,发现都是单调不增的。

而且开始和最后都是最值连续的两端。

想了想好像可以根据这个性质搞。

然后枚举了下分界点。

和暴力拍。。好像没事。

然后去做第三题。

是一个4in1的题,好像有一个做不出来都是挂。

看了看1,2都好dp,3,4不太会。

想起了bzoj1194,好像有一个bfs的方法能判断两个自动机是否相同。

然后还能找出来最小的在A中出现不在B中出现串的长度。

嗯很有道理,子串是后缀自动机,子序列是。。子序列自动机?。

然后YY了下,写了两个自动机。

然后$n^2$bfs。四个问题都解决了。

不太会写暴力。0.0

爽。

然后去做第二题。

mod1e9好像可以拆成2^9和5^9分着做?

高斯消元每次找一个2或5次数最小的。然后CRT合并?。。

去写了。。不知道为啥莫名RE。

哎。。不想写了QAQ。

于是打算long double 试试?

然后就结束了考试。

后来出分 70 70 100.。

总分240,其他选手<=100?

感觉HE平均水平在降低。。

显然写的都不是正解。都是错的。。

能拿到分就不是我的问题了。。

就这么进了A队。貌似超了rank2,200分?。。


感谢GMH神犇陪伴学习生活。

感谢老师们的真挚教导。

感谢HE省内的同学交流。

感谢“弱”省神犇们的指导。

感谢强省神犇们细心解答问题。

NOI赛场见。(不对。更近的好像是CTSC、APIO?