WC2019游记

day 1

THUWC D2挂惨之后,终于有时间能好好放松一下了qwq。

上午去报到,顺便在墙上留了点纪念:

然后去寝室放了下东西。

广二高中部的寝室感觉比初中部高到不知道哪里去了。陈设差不多,不过床不会一动就嘎吱嘎吱响,而且整体感觉新很多,干净很多。不过我为什么又双叒叕被分到了最顶楼!!!

又要整天爬楼了。

整理完东西,回酒店吃了午饭,然后和ftq一起进学校。

下午什么事都没有,在校园里转了一大圈。然后跑到报告厅去蹭了一会儿网,顺便和ftq还有yj打了几盘斗地主,被吊打

晚饭和ftq还有yj一起溜到外面去吃,差点没赶上开幕式。

开幕式上说这次会有一道传统,一道交互,一道提答?瑟瑟发抖。

就酱。

day 2

上午听了松松松讲评测系统,因为懒得开电脑痛失小黄鸭一只。。。

下午第一课堂好像要讲量子blah blah。

不是很感兴趣,就去第二课堂听LJ讲课了233。

LJ讲得有意思多了

晚上去试机。

WC的系统也太烂了吧!!!

第一次感受到了使用NOI Linux的无力,无比怀念THUWC的Ubuntu18.04。

编辑器只有anjuta,emacs,Vim和guide。。。

guide。。。

你让我一个刚适应sublime和VSC的人怎么办啊!!

最后试了一下,好像anjuta和我的习惯还勉强吻合,就它了。

不要跟我说什么配置Vim!!!不会!!!

day 3

主要在划水。

斗地主水平有提高

day 4

主要在划水。

晚上试机赛,感觉题目还可以?就是提答我真的是一窍不通。

day 5

主要在划水。

明天就要比赛了,不知道会怎么样呢。。。

THUWC2019游记

day -2

非常紧张,不知道该说什么好。

今天的模拟赛考的还行,T2一个能被卡成$O(n^2)$的分块算法竟然被放过去了,开心。可惜T3的35分最后没写出来,被各路神仙爆踩。

考完以后,慌得一比的我到校园里去逛了一大圈冷静了一下,感觉好多了。


下午写了道SAM题,基本是秒切。感觉心里有底了一点点。

下午去打了会儿篮球,然后玩了几局狼人杀,感觉轻松了一点。只可惜最后我居然忘记了是屠边,居然还想着把所有人杀光。。。

还吃了梦寐以求的泡椒风爪!!!爽得要命

晚上复习了一下二项式反演和Min-Max容斥,心里还是很没底。不过THUWC应该不会考这种概率DP题吧?不管怎么说,还是准备一下好。

THUWC的时候,只要我把能拿到的暴力分搞定,再刚出至少一道题的正解,应该就差不多了吧?现在我要做的就是冷静下来,不要自己吓自己,成绩应该不会太差。

话说回来,只要能尽自己的力做到最好,不管结果怎么样,应该都可以释然了吧。

luoguP4102 [HEOI2014]林中路径

原题传送门:>Here<

当路径长度$=L$,且只要求路径条数时,我们是很容易做的,只要用邻接矩阵乘一下就好了。

然而此题需要路径长度$\le L$的路径的长度平方和,感觉些微复杂。

我们先考虑$\le L$怎么做。

CF1100F. Ivan and Burgers

原题传送门:>Here<

我们发现一个询问$l,r$相当于把$[l,r]$里的所有数丢进线性基里,然后查询最大异或和。

用线段树维护线性基复杂度是$O(nlog^3n)$。我们考虑优秀一点的做法。

考虑分治。假设当前分治到$(l,r)$,中点为$mid$。

我们分别预处理出从$mid$往左右连续的线性基。

也就是对于$num_i$,当$i<mid$时,$num_i$为$[i,mid]$的线性基;否则就是$[mid,i]$的线性基。

这样对于一个跨越$mid$的询问,我们可以$O(log^2n)$合并线性基并$O(logn)$计算。对于一个只在左边/只在右边的询问,我们继续递归下去。

总复杂度$O(nlog^2n)$。

1220模拟赛 区间积

题目大意:

给一个序列和一些限制$l,r,ans$表示需要使得

询问满足条件的序列个数。序列中每个数$0\le a_i< 10$。

我们发现$10$不是个素数,很难处理,所以我们把$10$拆成$2$和$5$,分别处理。

对于每个素数,我们考虑判断每个区间中有没有$0$。

设$g_{l,r}$为区间$[l,r]$中可以有$0$时的方案数,$f_{l,r}$为没有$0$时的方案数。

loj#2289. 「THUWC 2017」在美妙的数学王国中畅游

原题传送门:>Here<

这道题乍一看很高端,其实只要瞎JB泰勒展开一下再维护一下前几项的值就好了。。。

我们考虑对三个函数泰勒展开:

接下来就是基本$LCT$处理了。

loj#6508. 「雅礼集训 2018 Day7」B

原题传送门:>Here<

我们发现有性质$(a,n)=1$,也就是说,$a\cdot i+b \mod n$的取值不会重复。

我们考虑对$S[0\cdots m-1]$建线段树,线段树下标为$a\cdot i + b\mod n$,存储的值是当前区间内$T$上对应位置为$1$的数的个数。

这样说可能有点抽象,我详细说明一下。

以样例为例:

1
2
3
9 5 6 4 3
101
...

构成的$S$的$a\cdot i+b\mod n$数组的前$m$项为

luoguP4385 [COCI2009]Dvapravca

原题传送门:>Here<

我们考虑随机选两个点,然后连一条经过这两个点的直线,并向两边扩展。做10000组就可以AC了。

以上是乱搞做法。

我们考虑当平行线平行于$x$轴时怎么办。

在这种情况下,我们只要把点投影到$y$轴上,然后查询最长连续红点就可以了。

其实绝对位置不重要,所以我们只要把点对纵坐标排序就行了。

现在我们考虑旋转平行线。

每次我们只需要把点投影到与平行线垂直的直线上,然后查询最长连续红点。

我们发现旋转平行线时,当两个点构成的直线与平行线平行时,也就说明这两个点的投影重合。那么在旋转前后,两个点的位置会进行交换。

这可以用线段树来维护。

luoguP5072 [Ynoi2015]盼君勿忘

原题传送门:>Here<

本来是不会去做Ynoi的毒瘤题的。。。

但是为了珂朵莉怎么都要做一下!!!

不过谁让我水平太差。。。其他的那些神仙题都不会,只能做这道了。

loj#6132. 「2017 山东三轮集训 Day1」Flair

原题传送门:>Here<

做过家喻户晓的小凯的疑惑的人应该会熟悉一个性质,即两种互质钱币最大不能表示的数为$ab-a-b​$。

而我们发现一个非常好的性质:$c_ic_j\le 10000(i\ne j)$

设$v=gcd(c_1,c_2,\cdots,c_m)$,则所有$\ge 10000$的$v​$的倍数都可以被表示。

这时我们只需要考虑选出的菜的数量$\%v=i​$的方案数。

设$f=(100-p)+px$,我们对这个多项式做循环卷积,得到$f^n$,$f^n_i$表示的就是在$n$道菜中随机选,选出菜的数量$\%v=i​$的方案数。

这样答案就是$\sum_{i=1}^{v-1}f^n_i(v-i)$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×