Logic
向着梦想进发
Logic's Blog

【WriteUp】2024 甘肃省赛网络赛

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

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

B

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

A

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

C

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

$$
\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}C_{n}^{i}\times C_{n-i}^{j}
$$

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

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

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

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

E

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

D

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

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

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

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

$$
f_v=\sum_{(u,v)\in G}{(f_u+1)}\times 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
account_circle
email

Logic's Blog

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