[GZOI2019&GXOI2019]省选GG记

GZOI=贵州OI

题目 ecr1欢迎AK）题解 4hac

Update:我省的题终于上OJ了好感动

Luogu P5300 [GXOI/GZOI2019]与或和

Luogu P5301 [GXOI/GZOI2019]宝牌一大堆

Luogu P5302 [GXOI/GZOI2019]特技飞行

Luogu P5303 [GXOI/GZOI2019]逼死强迫症

Luogu P5304 [GXOI/GZOI2019]旅行者

Luogu P5305 [GXOI/GZOI2019]旧词

$DAY0$

上一次的普及难度成功地让我体验到了省选500+的快感。

然后今年又来混2天半的假期（

然后就被两套省选模拟搞到自闭

坐了大半天的车，难受得要死，去试机，敲了3k(FTT,NTT,平衡树-树状数组版)的模板就溜了。。

到宾馆就开始打Arcaea，完全不想复习QWQ

Arc真好玩，我推荐你们都去玩一玩

$DAY1$

早上差点睡过头。。

赶往考场，然后发了密码

for i := 1 to n do

这一股浓浓的pascal风格是怎么回事。。

然后就锅了（

很多人都解不开压缩包，好像在Windows上面用了什么奇怪的压缩软件

结果变成工作人员手动发数据

幸好我靠前（雾

按照惯例，先开$T1$

大意是给一个$NN$的矩阵，求所有子矩阵的$and$和$or$值之和

$N$

一眼按位处理，然后就是求多少个矩阵全为$1$

我：瞎JBDP一下不就好了

$1h$敲完，然后成功手动Hack

？？？

我开始慌了

然后想了半小时，又想到一个$N^2$(？)的算法，确定没问题之后就开始敲，拍完后总共过去了$2h$

赶紧开$T2$，然后。。。

麻将？？？

wori怎么是个比赛都要打牌的啊？

z?出来挨打（指出题人

看题花了半个小时，然后开始大暴力，瞎敲了$600+$行

g++ test.cpp -o test -Wall -O2

TLE+WA

我 打 O I 像 蔡 徐 坤

写了个连样例都过不去的贪心交了，放弃治疗

此时只剩$1h$了，赶紧看$T3$

这是什么题.jpg

计 算 几 何

暴 力 不 能

输 出 样 例

爆 零 放 弃

想了半小时没有思路，回去看了看$T1$，突然发现$T1$应该写了个$N^3$（还有一个60的常数）

我真的慌了，只剩$20$分钟，疯狂卡常，可以过随机数据

可能全世界就我不会$T1$了⑧

思考人生中，然后收程序时又出锅（你们是C*F总部来的吗（

$D1$咕分：$50+0+0$

不知道$D2$能不能翻盘。。

出来问了一下，$T2T3$应该没几个人做，不知道$T1$有几个人A？

$DAY2$

天气突然变冷QAQ

暗示我要凉？

进考场，试密码，依旧试不出来

今天的密码：public static void AC

这是什么语言啊QAQ

开题，杠T1：

$T$组数据，你有$n$块$1<em>2$的地砖，其中一块碎成了两个$1</em>1$的，问有多少种方法组成$2*n$的道路（两个碎片没有公共边）

$n2e9,T$

看到范围，瞎猜是根号算法（Flag

先推公式，发现如果确定两个碎片在哪一列，那么两碎片中间的部分方法就唯一。

然后旁边两部分的方法就很简单了（若一边有$x$个剩余的空位，方案数就是$Fib_x$）

那么就推个公式：$<em>{i=3}^n</em>{j=0}^{n-i}2Fib_jFib_{n-i-j}$

枚举"中间"部分长度$i$，左边长度$j$

（中间两个碎片的部分可以上下翻转）

为了方便，先让$n=n-3$，就变成$<em>{i=0}^n</em>{j=0}^{n-i}2Fib_jFib_{n-i-j}$

然后拆开化一下，就是$2*<em>{i=0}^nFib_i</em>{j=0}^{n-i}Fib_j$

预处理前缀和，写了个$O(Tn)$的50pts暴力放着

此时过去40min，感觉良好（？

开T2

给一个有向图，$n$点$m$边，求$k$点之间两两最短距离最小值

$2kn^5,m5$

为什么总感觉见过这个题？？

先写$n,m$的暴力，大力Dijkstra+剪枝

然后有30pts的有向无环图，写了个$DP$，手动跑了几组小数据，感觉没有问题

然后呢？？这题怎么做？？？

2分钟想了个算法：建原点向所有要求的点连边，长度为0，每个点拆成2个，一个点若有边，则向指向的点的两个拆点都连边，最后所有点的第二个向汇点连边，跑一边最短路

好像很珂学的样子？

然而还没2分钟就觉得fake至极

www感觉只会暴力了啊

还剩两个小时，不管了先开T3：

一颗树，$1$为根，$Q$次询问，给定$x,y$，求

$_{i=1}^{xDepth(LCA(i,y))}k$

$k$为常数

$n,Q,k^9$

awsl

写了个$20$暴力，走了走了

滚回去看$T1$，试着推了推$DP$式，发现这不就一sb矩阵乘法吗

吓得我先写了个$7<em>7$的转移矩阵压压惊（问了问其他人33矩阵吊打我Orz

中间连着推错4次矩阵

然后就只剩$20$分钟了，卡了卡常，万一有奇迹出现呢（

走出门外，听见了大量神仙发言：

“T1找规律啊，特简单”

“T1不就一矩阵乘法吗。。”

“T3写了个90分”

好像还有初一神仙A T2

全世界就我不会找规律

$D2$咕分：$100+50+20$

回宾馆躺着打Galgame等死了

A few minutes later

下午出成绩了QWQ

$100+0+0+100+100+20$

？？？

为什么暴力可以过2个题啊。。

这什么垃圾数据，点赞了

然后就蜜汁rk1了？？弱省真好

溜了溜了，回去学文化课了（自闭了