UOJ Logo Scape的博客

博客

标签
暂无

JOI计划

2018-02-22 22:43:32 By Scape

大概是。。发现自己太颓了。。每天稳定$\ge 5h$遗迹暖暖dota2没啥救了。。所以给自己开个坑来让自己不那么自爆。。。

感觉JOI的题还不错,所以就切点JOI来压压惊。

发现没有地方评测。所以做一题之前就先上传到uoj上。

因为是在打dota2,看番,水知乎中抽出时间来做JOI。所以可能要慢慢做。。切得慢了请各位观众老爷轻喷。

我比较懒,所以val.cpp懒得写了暂时先坑着。等有空了或者有好心人再填上。

因为是我一个人在加题(而且只有我和fsf在翻译)所以可能题面数据啥的会出锅。大家发现问题可以和我直接联系。

JOI2017春季合宿 Day1T1 Cultivation

首先易知和顺序无关,只要确定上下左右的天数就可以了。

先考虑下一维的情况。大概就是$\max(x[i]-x[i-1],x[1]+w-x[n])$之类的。

考虑如果把向左和向右的确定了,那么向上和向下的你一列一列去确定就算完了。

考虑一下这样一个事情,如果一个$l,r,u,d$是合法的,且$l$不等于某个$x_i-1$,那么$l-1,r+1,u,d$一定也是合法的,所以可能的$l$只有$O(n)$种。

考虑完$l$后,考虑一下$r$,可能的$r$显然也只有$O(n^2)$中,就是$x_i-x_j-l-1$之类的。然后从小到大枚举一下$r$维护一下每一段大概能做到$O(n^3logn)$

但是感觉不太能过。。然后又注意$u,d$本质不同的答案只有$O(n^2)$个,且随着$r$的增大$u,d$只会变小,所以大概把答案预处理下然后用数组来维护。应该能做到$O(n^3)$..(只是嘴巴bb没写过。。

有个更好些的写法是先枚举$r$,然后$l$可以用单调队列扫一遍。。这样也是$O(n^3)$的。。。

JOI2017春季合宿 Day1T2 Port Facility

显然是把图建出来之后判断是否是二分图。如果是二分图答案就是$2^{联通块个数}$。

考虑一下先把三元环给判掉。判完之后考虑一下,令$fa_i$为最短的包含第$i$个的线段,并建树后发现那么连边就是一个点向树上的一条链连边。

然后就用并查集维护下把树上相同颜色的点缩一起然后BFS染色一下就可以了。。

JOI2017春季合宿 Day1T3 Sparklers

退役记&&NOI游记

2016-07-31 01:08:02 By Scape

滚粗狗的高一OI历程。。。。。


NOIP2015:

考前停了两周课。。。

Day 1的时候。。。。写完了T1,T2,T3....

最后检查有没有CE的时候。。。。

    g++ landlords.cpp -o landlords.cpp  -lm

我看了眼右下角时间 11:59.....

当时就懵逼了。。。。当时举手求助监考老师。。。希望能不能复原源代码。。。

“你还有明年”。。。。

然后心态就爆炸了。。。。Day 2的时候也是一团糟。。。。回来后躲在机房里哭。。。。。最后只能回去准备文化课。。。

出结果。。。450。。。。居然压线1=.。。。。真是感动。。。。


WC 2016

wc前被某秦心拉进了一个群。。。。从此决定了NOI滚粗的命运

从2016.1.1开始坚持每天一道TC Easy。。。。被虐的死去活来。。。。。

wc的时候靠着打打暴力居然Au了。。。。

记得wc的时候一直在和dwj,wyy,fsf打鬼畜天线宝宝。挺好的游戏,推荐给大家(大雾

寒假的时候和某群的人一起搞了个CMC。。现在看了眼居然觉得当时题目质量还不错。。。虽然最后大家都在鸽鸽鸽


ZJOI Day 1

听课的时候和cdz坐一起。。看cdz切题感觉非常仰慕。。mzl怎么总是拿着我的手机[哔-------]

考试前夜吃了XJ旁边的辣鸡套餐。。。当天晚上肚子爆炸。。。折腾到2点才睡(似乎从此之后我每次考试肚子都会爆炸

考试先开T3.。。。。写了个玄学暴力。。。。。试了下极限数据居然能1s过。。。。。然后发现似乎可以fwt一波。。。。。然而感觉非常自信就没有fwt。。。

然后去干T1.。。。。瞎抓了点东西判判。。。。T2没怎么想写了暴力。。。

出来之后觉得自己还是挺稳的。。。。

结果发现T1我没读数据是第几组的。。。我大样例自己没测。。用的是自己造的数据。。。。。然后就biubiu了。。。。

T3怎么被卡成70了啊。。。

于是我就滚了。。。感觉有点感动。。。全省#30左右。。。。掰了下手指算了下。。。如果noip没炸似乎还有点希望。。。gg。。。。

Day 1之后似乎就跑到处各地。。。

先是去了AHSDFZ....每天和wyy正面战斗。。。wyy每天都虐我呜呜呜

然后似乎又去了JSOI玩了一圈。。。

Day 1是我第一次在考场上写了模拟退火神TM jsoi那题标算似乎就是退火。。。感谢lyx大爷对我日复一日的退火洗脑让我在考场上成功yy出模拟退火(大雾

Day 2我三题都写了正解。。。然后三题以三种方式花样狗带。。。挂成了130.。。然而三题我都拍过(捂脸。。。。。


ZJOI Day 2

Day 2感觉以浪为主啊。。。

第一天白天打了个CC的RNG。。。。

晚上和某群的人在yyhs旁边的万达浪。。。找了半天在一个鬼畜的地方找到一家密室。。。。。。。。

第二天的时候又出去浪。。。晚上在万达某家牛排店吃饭。。。。担心肚子爆炸点了11分熟(大雾。。。结果最后还是爆炸了。。。。。

考试的时候选择了放弃梦想。。。轻易地开始打暴力。。

然后神奇的事情发生了。。。。。Day 1前在我前面的看错题的看错题。。省队杀的省队杀。。。。然后我就卡线进队了。。。

人呐真是不可预料。。。你说我一个滚粗狗。。。怎么就进队了呢。。。


CTSC && APIO

CTSC之前先和wyy,fsf打了场THU校赛。。。最后#7似乎。。。

唯一的欣慰似乎就是某让我noip狗带的出题人#8(捂脸逃。。。

CTSC抱着练习提答的态度全场玩提答。。

最后似乎我是Day2提答最高分。。。。?

CTSC结束那天晚上某群聚会。。。成功让洲阁大放血。。。第一次看到用一个辣么大的箱子送来的M。。。。

感觉那次聚会大概是某群聚人数的巅峰了。。?(从此之后就一个个退役了呢。。sigh......

作为一个noip滚粗狗并没能参加APIO(蛤蛤蛤你看这就是ZJ省队的实力。。。

场外看了下题感觉T1T3还是不难的嘛(大雾

然后去打PKU校赛。。。被一道鬼畜结论题和一道字母识别题玩炸了。。。。#10+。。。。赶紧捂脸跑了。。


NOI

noi前去了叉姐的OICamp。。。。每天和kpm正面战斗。。。。kpm每天都虐我呜呜呜

心痒难耐在NOI前选择了给TC渡劫。。感觉对TC还是有点执念的。。。成功红名。。。。

于是大概在去noi之前是CF黄。。TC红的状态。。。

Day 1前辗转反侧。。。彻夜未眠。。。。感觉心态有点爆炸。。。

先看T1。。。。暴力有95那我就95吧。。。

看了眼T2。。。。。第一眼反应是答案最大是4.。。

然后冷静了下。。。发现答案最大是3.。。。。

又冷静了下发现答案最大只有2(捂脸。。

思考了下怎么判答案是否为0.。。。最开始以为只要判它们是否有环

然后发现实心我会狗带。。想了想我感觉似乎只要把每个障碍附近8个块都点亮这样似乎就能代表它们的连通性了。。

自己造了个反例。。。思考了下。。把每个障碍附近24个块都点亮了看起来就很对了。。然后就写写写过了大样例。。。

这时候cxm提醒了注意边界情况。。吓得我赶紧拍了下n=1的数据。。又检查了下自己在非障碍点很少的时候的情况。。发现没问题就不管了。。。

看了眼T3。。。。觉得不如先打暴力。。。于是打了个$O(m^2)$的暴力。。。

当时时间只剩下1h了。。。。感觉有点怂。。我猜大家都不会T3。。而且我平时模拟赛的习惯也都是两道正解+一道低分暴力。。于是我就跑回去检查T1T2了。。。

出考场之后遇到了松松松。。发现他的T2做法和我考场上yy的一样。。。感觉自己有点稳。。。

结果大家T3怎么分都这么高啊。。。。。早知道剩下1h淦T3了(泪目

看分的时候发现自己n=1没挂。。。m=1挂了(捂脸。。。挂成了60分。。。。感觉有点gg。。。。

fsf似乎95+100+85挂成了95+60+40。。。。感觉有点惨。。。。

dwj,wyy似乎挂的比我还惨。。。。

据说金牌线190+.。。。。感觉有点救。。。。

Day 2前又是辗转反侧睡不着。。。折腾到3点才睡。。。感觉要gg。。。

我坐在myh旁边。。。。成为了站在铁轨上的男人(大雾。。。。。。

开场看T1..怎么看起来数据结构啊。。我猜是松松松出的。。。。想了0.5h不会。。。。。感觉自己药丸。。。

然后看T2...一眼$O(n^3P)$dp..我赌五毛它有决策单调!拍了下发现果然有。。于是写了个$O(n^2lognP)$就不管了。。。

看了眼T1发现我会$O(log^2)$!。。。。感觉松松松总是能莫名其妙少个log。。于是我就自信大家都是$O(log^2)$。。。。

然后去玩T3。。。。好像我不太会怎么拆二进制啊。。就只玩了50出来。。。

最后1h全在检查。。。

出考场发现T1怎么是zz题啊。。那我不是要滚了。。。

没心情吃饭。。。。回到宿舍。。。。大概两点 的时候得知两天加起来#50是408。。。。发现自己不挂题也要滚。。。感觉非常绝望。。。。

大家怎么都这么劲啊。。。。

到了考场发现自己没挂题。。。然而也没用了。。。最终还是滚了。。。

某群高一除了bx2k之外。。。wyy,dwj,fsf,rxd好像都滚了。。。

高二的kpm,ioi,gwy也都滚了。。。。。

13岁的秦心也滚了

考前互奶太狠了沉群了啊。。。

感觉心态有点爆炸。。然而作为Loser感觉也没什么理由喷什么。。。。

本来想取消逗比Star和计蒜客的行程直接滚回去文化课。。。。。。后来想想不太好。。选择了和dwj和wyy一起去成都玩。。。。

三个Ag狗游成都。。后来把yjq叫了出来。。。在成都某个地方打电玩。。。。感受wyy展现高超开车技巧

突然出现了王队长一行。。。然后yjq和王队长身旁就各有了一个妹子。。。。kpm突然在某群虐狗。。。。刚退役就有2,3个妹子表白。。。。你们怎么都这么人赢。。。。


写在最后

大概高一赛季就结束了。。。感觉还是挺痛苦的。。也许高二不打了。。。。和wyy一起推妹子去了。。。

“有谁知道史地政怎么快速预习嘛,在线等,挺急的。”

共 2 篇博客