玉米投手 × 黄油投手 √

玉米投手 × 黄油投手 √

四带恶人

NOI 2020 同步赛划水记

posted on 2020-08-18 07:33:14 | under 穴 树 |

在想要不要用这个来当暑假作业(

1500字太难凑了放弃( 说不定就凑到了呢(

顺手来宣传一波自己的回答


Day1

早上8:20已经在机房准备好了,结果CCF服务器(不出意外)炸了。等到8:40(离原定时间已经过去十分钟了)终于是能够打开登录了。

结果题面没了。

差不多8:45的时候我去刷新了一遍页面,然后终于是有题面文件了。

T1

给定一张有向图( $n$个点, $m$条边,可能有重边)。每条边有一个边权 $w_i$,表示经过这条边所需要的时长。每个点有一个价值 $c_i(1\leq i\leq n)$,每次经过这个点你都会获得价值 $c_i$。
除此之外,有 $k$个特殊时刻,如果你在第 $t_i(1\leq i\leq k)$个时刻位于第 $x_i$个点,你可以额外获得价值 $y_i$。
你在第 $0$个时刻从 $1$号点出发,要求你在第 $T$个时刻回到 $1$号点,并且中间不在某个点停留。求出你能够获得的最大的价值和。
$\begin{aligned}&1\leq n\leq 50,1\leq m\leq 501,1\leq w_i\leq 5,1\leq c_i\leq 52501,\\& 0\leq k\leq 200,1\leq t_i\leq T\leq 10^9,1\leq y_i\leq 10^9\end{aligned}$

看到 $1\leq T\leq 10^9$基本上能猜到这是一道矩阵乘法的题目了,再加上 $1\leq w_i\leq 5$这个条件就已经能确定了。

花了大概一个小时确认了一遍中间的细节(比如矩阵转移时储存的内容),差不多了之后准备开始码代码。

码到一半准备再次确认时被旁边@w6666 和@洛谷最菜红名 的讨论影响了(主要是这个时候w6666说了一句 $\operatorname{lcm}$导致我以为跟这题这题相似),以为自己原思路有误于是按新思路码了一遍。

码完以后测试样例,测到第二个时发现有错,然后就去调试了一番,发现是新思路错了,原思路是对的,就又转回去码原来的思路。

大概到10:30-11:00的时候算是码完了,然后再一番调试把样例全部过掉了(此时我大样例跑了0.5秒)。

又算了遍整个的复杂度,发现是 $O(125N^3K\log T)$的,过不去,仔细想了下发现可以用之前这题类似的优化做到 $O(25N^2\log T(5N+K))$的复杂度。

码完测样例没有错误,但大样例跑了1.4秒,以为自己优化用错了再加上复杂度算出来以为过不了,但又不想改于是就没再管了(实际上这是能过的)。

这时已经11:30了,就先不管比赛去吃饭了,大概11:55的时候回到机房打剩下两题。

T2

给定一棵 $n$个点的树(以 $1$为根)和 $m$条路径 $(u,v)$( $u$是 $v$的祖先),要求给每条边赋值( $0$或 $1$),使得所有路径中至少包含一条值为 $1$的边,求有多少种赋值方案,对 $998244353$取模。
$1\leq n,m\leq 5\times10^5$

先是想到最暴力的 $O(2^nmn)$做法,之后想了下容斥+树剖(其实这个在去吃饭的路上就想到了),发现可以做到 $O(2^mm\log^2 n)$,就先把这个做法打出来交了。交完差不多12:20。

T3

给出一个 $n\times n$的棋盘,上面有 $n$个棋子(所有棋子两两之间位于不同行不同列)。定义一颗位于第 $x$行第 $y$列的棋子坐标为 $(x,y)$,第 $i$颗棋子的坐标为 $(x_i,y_i)$。
定义 $(a,b)\leq(c,d)$,当且仅当 $a\leq c$,且 $b\leq d$
给出 $m$次询问,每次询问有四个参数 $r_1,r_2,c_1,c_2(1\leq r_1\leq r_2\leq n,1\leq c_1\leq c_2\leq n)$,要求求出二元组 $(i,j)$的对数,满足 $(r_1,c_1)\leq(x_i,y_i)\leq(r_2,c_2),(r_1,c_1)\leq(x_j,y_j)\leq(r_2,c_2)$,且 $(x_i,y_i)\leq(x_j,y_j)$。
$1\leq n\leq 10^5,1\leq m\leq 2\times10^5$

一眼直接先写了 $O(nm\log n)$的暴力树状数组做法,这时差不多是12:30-12:40。

转回去想T2跟T3其他部分分的做法,发现不会做就放弃看别人写了。

13:30的时候才发现比赛结束时间从原来的的13:30延时到13:45了。

比赛结束后洛谷自测,发现有 $100+32+32=164$分,还算说的过去。

T1没想到这种做法的确能过,因为我自己算出来跑的时间大很多,可能是因为加了一些剪枝所以会比正常快一些。

希望明天也能尽力吧。

好消息:Day1已经一千字了(

Day2

CCF终于准时了。

T1

有 $n$个种类的物品,每种物品有 $d_i$个物品,一共有 $m\times k$个物品,要求将这些物品分成 $m$组,每组 $k$个物品,且每组物品的种类数不超过 $2$,输出方案(无解输出 $-1$)。有多组数据。
$\begin{aligned}&1\leq n\leq 500,1\leq m\leq 5000,n-2\leq m\\&1\leq k\leq 5000,\sum\limits_{i=1}^nd_i=m\times k\end{aligned}$

没啥思路,感觉不可做就直接跳过了。

T2

题面太长了实在简化不了。

有一点模糊的想法,不清楚怎么做就跳过看T3了。

T3

给定一张 $n$个点 $m$条边的带权无向图(保证原图联通,图中无重边和自环)。这张图有以下性质:

  • 对于一条环路 $c_1\to c_2\to c_3\to\cdots\to c_k\to c_1$( $c_1,c_2,c_3,\cdots,c_k$互不相同,且对于 $\forall i\in[1,k-1]$, $c_i$与 $c_{i+1}$之间有边相连,并且 $c_k$与 $c_1$之间有边相连),如果 $k>3$,保证存在 $u,v$( $u\geq v,u-v\geq 2$,且 $u,v$不同时为 $k$和 $1$),使得 $c_u$和 $c_v$之间有边相连

给定 $s,t(s\neq t)$,要求找出一条从 $s$到 $t$的路径,使得从原图中删去这条路径上的所有之后所有点依旧联通,求出这条路径最小的边权和。无解输出 $-1$。
$2\leq n\leq 5\times 10^5,2\leq m\leq 10^6$

(今年NOI day1题目挺正常的你day2题目咋这么毒瘤呢。出题人呢?快出来!保证不打死你!)

(以上内容不放入作文)

一开始把题目看错了,以为是 对于任意 $u,v$,想着这玩意直接求边双联通分量然后求最短路就行了,一直到差不多10:30的时候才发现自己题目看错了。

按题目意思大致分析发现对于一条长度为 $k$的环路,会不断有一条边把它分成两个长度更短的环路,直到环路长度 $\leq 3$。(据说这玩意叫弦图?)

画了很多图形还是不清楚怎么处理,于是直接输出 $-1$去吃饭了。

吃饭的路上想了一下T2,以为在上面相同,下面分别为父亲+左儿子(叶子)父亲+右儿子(叶子)父亲+左儿子(叶子)+右儿子(叶子)的三棵树可以直接合并成上面相同,下面一个叶子的树,于是吃完饭后就回来敲代码了。

敲完差不多是12:20,测试样例到第四个时发现出错了,仔细检查了一下发现这个思路还有很多漏洞,并不能这么做,但又一直想不出其他做法于是就先交上去了。

后面时间也对其他题目一直没有思路就没有继续打了。

唉,感觉day2比day1难好多,自己的实力还是不够。

洛谷上还没有数据,没办法测分数。

PS:听说现场赛好多人Day2心态崩了也考炸了?

Day3

洛谷上还是没有数据。

Day4

CCF官方成绩出了,Day2 成绩也知道了, $0+40+5=45$,两天一共 $209$。

D2T2 错误做法能骗 $40$就有、离谱。

勉强说得过去吧。

总结

D1T1因为之前类似的有做过所以比较容易想到做法,于是做的还算可以,而且没有挂分还不错。

D1T2和D1T3纯粹是自己水平不够没有练过类似的题目。

D2T1本质其实就是一个简单的贪心+构造,想复杂了所以没能做出来,比较可惜。

D2T2虽然是错误做法但还是能拿到 $40$分,说明有时候有些做法还是要写的,这样才能拿到尽可能多的分数。

D2T3浪费太多时间了,而且最后也只有 $5$分,说明时间分配还是得再合理分配的。


最后来扯句貌似这篇游记已经2000字了(

这篇要当作文所以写的比较正经(