[Fortuna OJ]Jul 4th – Group A 解题报告

A – 非回文数字

这道题还没写,是一道数位 DP,推荐记忆化搜索。

B – 管道

这道题是一道相当好的题目。

首先对于\(m = n – 1\)的情况,也就是树的形态下,可以考虑自下向上推,也就是从叶子节点开始推起,参考代码中 Toposort 的写法。然后,对于\(m > n\)的情况可以直接输出\(0\),因为这个方程组并不存在唯一的解:\(m\)个未知数仅提供\(n\)个条件,这样是不成立的。

最后考虑\(m = n\)的情况。这种情况就是基环树了。首先,Toposort 会把支链上的答案全部统计完毕,并且合并到环上的点。最后,我们唯一要多做的事情,就是处理环上的方程组。考虑一个这样的环:

继续阅读[Fortuna OJ]Jul 4th – Group A 解题报告

P1137:旅行计划题解

思路

好久没有写拓扑排序了。今天看到这题看了半天,由题解可知是拓扑序DP。原理根据拓扑序来进行DP。由于每个点在DAG是不会回路的,所以我们只需一头往下走就好,用dp[x]记录点x可到达的地方。使用拓扑排序就会让DP时不会出现影响其他已计算过的节点。

代码

// P1137.cpp
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 100010;
int points[maxn];
int to[2 * maxn];
int next[2 * maxn];
int indeg[maxn];
int res[maxn];
int dp[maxn];
int tot = 0;
int current = 0;
int n, m;

void add_edge(int a, int b)
{
    to[current] = b;
    next[current] = points[a];
    points[a] = current++;
}

void toposort()
{
    queue<int> waiting;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0)
            waiting.push(i), res[tot++] = i;
    while (!waiting.empty())
    {
        int curt = waiting.front();
        waiting.pop();
        for (int edge = points[curt]; edge != -1; edge = next[edge])
        {
            indeg[to[edge]]--;
            if (indeg[to[edge]] == 0)
                waiting.push(to[edge]), res[tot++] = to[edge];
        }
    }
}

void DP()
{
    for (int i = 1; i <= n; i++)
        dp[i] = 1;
    for (int i = 0; i < n; i++)
        for (int edge = points[res[i]]; edge != -1; edge = next[edge])
            dp[to[edge]] = max(dp[to[edge]], dp[res[i]] + 1);
}

int main()
{
    memset(points, -1, sizeof(points));
    memset(to, -1, sizeof(to));
    memset(indeg, 0, sizeof(indeg));
    cin >> n >> m;
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b, add_edge(a, b);
        indeg[b] += 1;
    }
    toposort();
    DP();
    for (int i = 1; i <= n; i++)
        cout << dp[i] << endl;
    return 0;
}