P8410 题解

前言

题目传送门！

更好的阅读体验？

本次比赛第二题，好像没有人抢题解，那我来一发。

思路还是挺巧妙的。

\texttt{10 pts} 思路

深搜求解即可。

最坏情况，时间复杂度 O(n!)。

#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned int UI;
typedef unsigned long long ULL;
inline UI get_next(UI &seed) //直接套用给出的随机数代码即可。
{
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}
UI n, seed;
UI a[105], fa[105];
ULL maxn = 0;
bool vis[105];
void dfs(int x, ULL sum, UI minn)
{
    if (x == n)
    {
        //cout<<"sum="<<sum<<'\n';
        maxn = max(maxn, sum);
        return;
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i] && vis[fa[i]]) //选过 fa[i] 且没选过 i 才可以。
        {
            vis[i] = true;
            dfs(x+1, sum + min(minn, (UI)a[i]), min(minn, (UI)a[i]));
            vis[i] = false; //回溯。
        }
}
int main()
{
    scanf("%u%u", &n, &seed);
    for (int i = 1; i <= n; i++) a[i] = get_next(seed);
    for (int i = 2; i <= n; i++) fa[i] = get_next(seed) % (i-1) + 1;
    vis[1] = true;
    dfs(1, (ULL)(a[1]), a[1]);
    printf("%llu", maxn);
    return 0;
}

\texttt{50 pts} 思路

前置知识点：拓扑排序。

没学过没关系，可以直接看正解。

观察本题，捕捉关键句，如下。

先完成 fa_i 才能完成 i。

求和的最大值。

这不就是拓扑排序吗？

容易看出，用优先队列求解，每次选当前队列里的最大值即可。

所以要重载一下。

时间复杂度是带 \log 的，可以卡过 50\% 的数据。

最后按照拓扑序计算和即可。

类似模版，没有什么需要特别理解的地方。

#include <iostream>
#include <cstdio>
#include <queue>
#define N 10000005
using namespace std;
typedef unsigned int UI;
typedef unsigned long long ULL;
inline UI get_next(UI &seed)
{
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}
UI n, seed;
UI a[N], fa[N];
struct Edge
{
    int now, nxt;
}e[N];
int head[N], cur;
void add(int x, int y)
{
    e[++cur].now = y;
    e[cur].nxt = head[x];
    head[x] = cur;
}
struct Node
{
    UI x;
    bool operator <(const Node &t) const
    {
        return a[x] < a[t.x];
    }
};
int in[N], topo[N], Cur;
void topo_sort()
{
    priority_queue <Node> Q;
    Q.push( (Node){1} );
    while (!Q.empty())
    {
        int topi = Q.top().x;
        topo[++Cur] = topi;
        Q.pop();
        for (int i = head[topi]; i; i = e[i].nxt)
        {
            int p = e[i].now;
            in[p]--;
            if (in[p] == 0) Q.push( (Node){p} );
        }
    }
}
int main()
{
    scanf("%u%u", &n, &seed);
    for (int i = 1; i <= n; i++) a[i] = get_next(seed);
    for (int i = 2; i <= n; i++) fa[i] = get_next(seed) % (i-1) + 1;
    for (int i = 2; i <= n; i++) add(fa[i], i), in[i]++;
    topo_sort();
    ULL sum = 0, minn = 1e18;
    for (int i = 1; i <= n; i++) minn = min(minn, (ULL)a[topo[i]]), sum += minn;
    printf("%llu", sum);
    return 0;
}

正解

讲完部分分，终于可以将正解了。

然而正解和部分分几乎没有关系。

正解的突破口在于：1 \leq fa_i < i。

换句话说，顺着扫一遍数组，必定先扫到 fa_i 再扫到 i。

进一步讲，顺着扫，等同于遵守了拓扑序。

这下，问题就很简单了，转移方程 f_i = min(a_i, f_{fa_i})。

注意到 a_i 在后面没有用了，所以可以直接用 a_i 代替f_i，节约空间。

另外，不存在 fa_1，所以开头稍作改变。

看到代码，你会觉得很简单的。

时间复杂度 O(n)。

#include <iostream>
#include <cstdio>
#include <queue>
#define N 10000005
using namespace std;
typedef unsigned int UI;
typedef unsigned long long ULL;
inline UI get_next(UI &seed)
{
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}
UI a[N], fa[N];
int main()
{
    int n;
    UI seed;
    scanf("%d%u", &n, &seed);
    for (int i = 1; i <= n; i++) a[i] = get_next(seed);
    for (int i = 2; i <= n; i++) fa[i] = get_next(seed) % (i-1) + 1;
    ULL sum = a[1]; //注意这里需要 long long 来储存。
    for (int i = 2; i <= n; i++) a[i] = min(a[i], a[ fa[i] ]), sum += a[i];
    printf("%llu", sum);
    return 0;
}

希望能帮助到大家，谢谢！