
日记
这个喷不了,这个是纯糖。
T1 Link to T1
题意:有一个长度为 的数组 ,其中对于 ,如果 且 那么就在 建一条单向边。有 次查询,每次查询 问 能否到达 。
你说我写个 dfs 不好吗非得写那个 Floyd!!!挂了 tmd 分。
正解:维护 表示从 出发能走到的最靠前的有 这个质因子的位置。维护方法如下:
CPP
123456789101112131415161718192021
// 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;
}
}
}
这就是代码的核心之处。查询时遍历 的每个因子 ,看看有没有 。有就是 Shi
,没有就是 Fou
。
T2 Link to T2
赛时思路正确,但是码力实在是太过于高强导致硬挂 分。
我也是个人物。
T3 Link to T3
矩阵优化状压 dp。我们看到 ,直接想到状压。然后我们看到 ,这只能矩阵优化。如果 的状态直接上还带一个 ,这不 T 才怪呢。我们发现真正合法的状态只有 种,,有点极限但是问题不大,反正它跑过了。
后日谈 Link to 后日谈
写完了 T1,自信的没有打对拍,于是直接硬挂 分。T2 码力高超硬挂 。T3 如果打完 T2 不颓废似乎是可以想出来的。
其实 T2 并不算是全错,但是求最优解的地方有点问题。
总而言之,这次考试纯 唐
考差了就得用下面的考试来补,这么简单(并非)的考试以后可不多见了啊
感觉心脏有点问题啊,要不要说一声呢?
日记
© 伊埃斯 | CC BY-NC-SA 4.0