日记 - 伊埃斯的博客站

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

T1

题意：有一个长度为 $n$ 的数组 $a$ ，其中对于 $\forall i,j \in [1,n]$ ，如果 $i < j$ 且 $\gcd(a_i,a_j) > 1$ 那么就在 $i \to j$ 建一条单向边。有 $q$ 次查询，每次查询 $x,y$ 问 $x$ 能否到达 $y$ 。

你说我写个 dfs 不好吗非得写那个 Floyd！！！挂了 tmd $60$ 分。

正解：维护 $dp_{i,j}$ 表示从 $i$ 出发能走到的最靠前的有 $pr_j$ 这个质因子的位置。维护方法如下：

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

这就是代码的核心之处。查询时遍历 $a_y$ 的每个因子 $pr_j$ ，看看有没有 $dp_{x,j} \le y$ 。有就是 Shi，没有就是 Fou。

T2

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

我也是个人物。

T3

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