Processing math: 100%
Logic
向着梦想进发

【WriteUp】2024 甘肃省赛网络赛

谁的生活不迷茫,谁的人生不迷惑。每个人都希望未卜先知,都希望掌控自己命运的罗盘,可变换莫测的世界总让我们感到失望,其实,我们的困惑并不在身外,而在我们的内心深处。我们总是希望心灵的疑惑得带一个真诚的回应,即便这个回应只是简单的“是”或“否”。——《答案之书》

引言与比赛无关,只是最近看到一段有意思的文字。

B

签到题,我要是少两发罚时,手速再快一点就好了。

A

签到题,手速还是不够快。

C

第一反应是一个组合数学,根据题意很容易写出答案就是:

n1i=1nij=1Cin×Cjni

尝试化简这个式子,发现无从下手。于是乎转换思路,考虑递推。

对于 f(n) 来说,考虑前一项如何转移。假设先选 n1 个数字,那么对于每一个可能的 (A,B)n 这个数字可能放入 A,也可能放入 B,也可能都不放入,这样就产生了 3×f(n1) 的贡献。对于一个子集单独为 {n} 的情况,显然另一个子集需要在 n1 个数里选,那么就有 2n11 种选法,考虑到有序对,故乘 2。所以递推式为 f(n)=3f(n1)+2n2,起点为 f(1)=0

那么现在需要求通项公式,这里我就不会了,还是靠我队友算的。反正凑配一下就可以发现通项公式就是 f(n)=3n2n+1+1,那么打一个快速幂就可以了。

一开始我以为这题可能是一道矩阵快速幂的题目,不过没想到直接就把通项公式求出来了。

E

看到群里的描述或许这题是被我卡常过的。我的思路是枚举 j,k,对于每一个 a[j] XOR a[k] 用 trie 树查找最优的 a[i]。实际上当时超时了,把 std::vector 换成数组,然后用快读才过了。不太清楚正解是啥。

D

一眼看到这题感觉是一道非常 DP 的题目,但是一时间没有很快想到思路。赛时的时候 T 了两发 E 题,然后换队友做这题,但是队友 WA 了,于是换我来写 E,结果没想到就改了常数就过了。然后开始思考这题。

我们可以考虑 fi 表示有多少点可以到达 i 点,gi 表示从 i 点出发能到达多少点。那么路径可以分成三类。以 i 为起点,终点和中间点。那么答案应该就是 ansi=fi×gi+fi+gi+1。(至于为什么要+1,其实我还没想明白,反正加了就对了)

考虑如何计算 fi、实际上 fi,gi 的计算方式是一致的,只不过后者是在反图上求。这里就是做一下 DP,容易看出 fv=(u,v)G(fu+1)。DP 的话要保证合法的顺序,所以先做一遍拓扑排序。

实际上我们需要考虑重边的情况。容易想到有几条重边,走法就会多几倍。所以只需要记录一下边出现的次数即可,最后的答案为:

fv=(u,v)G(fu+1)×cnt(u,v)

F

其实我没啥思路,%一下队里 AK 的佬,我自己确实还是得训。

赞赏
本文作者: Logic
本文链接: https://i.needwe.top/2024-gansu-province-race-network-race/
本文采用 CC BY-NC-SA 4.0 Unported 协议进行许可
#
首页      coding      【WriteUp】2024 甘肃省赛网络赛

发表回复

textsms

永恒幻想 Eternal Fanta5y

【WriteUp】2024 甘肃省赛网络赛
谁的生活不迷茫,谁的人生不迷惑。每个人都希望未卜先知,都希望掌控自己命运的罗盘,可变换莫测的世界总让我们感到失望,其实,我们的困惑并不在身外,而在我们的内心深处。我们总是希望…
扫描二维码继续阅读
19
2024/05