Visits: 719

【LGR-071】洛谷 4 月月赛 & MdOI Round 2 Div.1

Odyssey

首先预处理所有数的分解式，次数模上 $k$。

然后 DP，设 $f_{i,j}$ 为到点 $i$ 且上一条边的权值为 $j$ 的最短路，DAG 转移即可，有效的状态数只有 $\mathcal O(m)$ 个，用一个 map 或者 unordered_map 存即可。

const int N = 1e5 + 7, M = 1e6 + 7;
int n, m, k, W, d[N], v[M], ans;
unordered_map<int, int> f[N];
vector<pi> p[M];
vector<pair<int, pi>> e[N];
queue<int> q;

inline void init(int n) {
    for (int i = 1; i <= n; i++) v[i] = i;
    for (int i = 2; i <= n; i++) {
        if (v[i] > 1)
            for (int x = v[i], j = x; j <= n; j += x) {
                p[j].pb(mp(x, 0));
                while (!(v[j] % x)) ++p[j].back().se, v[j] /= x;
                p[j].back().se %= k;
                if (!p[j].back().se) p[j].pop_back();
            }
        for (auto o : p[i])
            for (int t = o.se; t; t--)
                v[i] *= o.fi;
    }
}

int main() {
    rd(n, m, k);
    for (int i = 1, x, y, w, z; i <= m; i++)
        rd(x, y), rd(w, z), e[x].pb(mp(y, mp(w, z))), ++d[y], W = max(W, w);
    init(W);
    for (int x = 1; x <= n; x++)
        if (!d[x]) q.push(x);
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (auto o : e[x]) {
            int y = o.fi, w = v[o.se.fi], z = o.se.se;
            ll g = 1;
            for (auto p : ::p[w]) {
                for (int t = k - p.se; t; t--) {
                    g *= p.fi;
                    if (g > W) break;
                }
                if (g > W) break;
            }
            if (g <= W) z += f[x][g];
            ans = max(ans, f[y][w] = max(f[y][w], z));
            if (!--d[y]) q.push(y);
        }
    }
    print(ans);
    return 0;
}

Resurrection

AtCoder 型的小清新计数题。

首先转化题意，题意相当于除了根之外的每个点都像祖先连一条线，要求线与线之间没有交点。

这玩意儿可以拿到 $40$ 分。

然后进一步转化题意，显然最终是一棵以 $n$ 为根的树。

我们在最后形成的树上标上深度，根据上面的性质我们可以发现，深度序列与这棵树一一对应。

其中点 $i$ 向其在原树上的祖先中离 $i$ 最近且深度 $-1$ 的点连边。

于是问题转化成深度序列的个数，这个树形 DP 然后前缀和优化一下就好了。

const int N = 3e3 + 7;
int n;
vi e[N];
modint f[N][N];

void dfs(int x) {
    for (int i = 0; i < n; i++) f[x][i] = 1;
    for (int y : e[x]) {
        dfs(y);
        for (int i = 0; i < n; i++) f[x][i] *= f[y][i+1];
    }
    if (x != n) f[x][0] = 0;
    for (int i = 1; i <= n; i++) f[x][i] += f[x][i-1];
}

int main() {
    rd(n);
    for (int i = 1, x, y; i < n; i++) rd(x, y), e[max(x,y)].pb(min(x, y));
    dfs(n);
    print(f[n][0]);
    return 0;
}

Quo Vadis

垃圾题。

Little Goth

题目太神仙了，先咕咕咕着。