日记

日记

Wed Mar 26 2025
4 分钟

这个喷不了,这个是纯糖。

T1 Link to T1

题意:有一个长度为 nn 的数组 aa,其中对于 i,j[1,n]\forall i,j \in [1,n],如果 i<ji < jgcd(ai,aj)>1\gcd(a_i,a_j) > 1 那么就在 iji \to j 建一条单向边。有 qq 次查询,每次查询 x,yx,yxx 能否到达 yy

你说我写个 dfs 不好吗非得写那个 Floyd!!!挂了 tmd 6060 分。

正解:维护 dpi,jdp_{i,j} 表示从 ii 出发能走到的最靠前的有 prjpr_j 这个质因子的位置。维护方法如下:

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// f[j] 表示在 i 后面最靠前的有 pr[j] 这个质因子的位置
fill(f,f + pr.size(),n + 1);
for (int i = n; i >= 1; i--)
{
    if (!a[i])
    {
        fill(f,f + pr.size(),i);
        fill(dp[i],dp[i] + pr.size(),i);
    }
    else
    {
        fill(dp[i],dp[i] + pr.size(),n + 1);
        for (auto j : fac[i])
        {
            if (f[j] != n + 1)
                for (int k = 0; k < pr.size(); k++)
                    dp[i][k] = min(dp[i][k],dp[f[j]][k]);
            dp[i][j] = f[j] = i;
        }
    }
}

这就是代码的核心之处。查询时遍历 aya_y 的每个因子 prjpr_j,看看有没有 dpx,jydp_{x,j} \le y。有就是 Shi,没有就是 Fou

T2 Link to T2

赛时思路正确,但是码力实在是太过于高强导致硬挂 80\huge\color{ff0000}80 分。

我也是个人物。

T3 Link to T3

矩阵优化状压 dp。我们看到 m6m \le 6,直接想到状压。然后我们看到 len3000len \le 3000,这只能矩阵优化。如果 262^6 的状态直接上还带一个 90009000,这不 T 才怪呢。我们发现真正合法的状态只有 2020 种,203×90000=7.2×10720^3 \times 90000 = 7.2 \times 10^7,有点极限但是问题不大,反正它跑过了。

后日谈 Link to 后日谈

写完了 T1,自信的没有打对拍,于是直接硬挂 60\huge\color{ff0000}60 分。T2 码力高超硬挂 80\huge\color{ff0000}80。T3 如果打完 T2 不颓废似乎是可以想出来的。

其实 T2 并不算是全错,但是求最优解的地方有点问题。

总而言之,这次考试纯

考差了就得用下面的考试来补,这么简单(并非)的考试以后可不多见了啊

感觉心脏有点问题啊,要不要说一声呢?

我要进省队!\tiny \textcolor{ffffff}{我要进省队!}