专栏文章

题解：P11391 [COCI 2024/2025 #1] 疑惑 / Zbunjenost

PPetit_Souris
P11391题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minhq4ig
此快照首次捕获于
2025/12/02 02:36
3 个月前
此快照最后确认于
2025/12/02 02:36
3 个月前
查看原文
Fastest solution :D
我们考察一个环的形态。以环上编号最小的点为起点，我们考虑如果说某一次用了三角剖分上的一条边向后跳，那么不可能再跳回来，因为这些边两两互不相交。
所以最后的路径应该形如走一段外面的环，跳一步，重复若干次直到最后跳一步回到起点。这里我们的点的编号一定是单调递增的。（当然这里把 n→1n\to 1 也视为一条额外边）
那么我们可以枚举最后一步走的是哪条边，也就是要计算在链上从 ss 走到 tt 的方案数。乍一看有些不可做，但是实际上发现我们本质上在计算有多少种选出额外边的方式，使得他们可以串成一条路径，也就是说他们互不相交。
由于是三角剖分，额外边一定是两两包含或相离，所以可以建成一棵树的结构。问题变成在这棵树上选出一些点使得不存在任何有祖先后代关系的点同时被选择。
可以轻松写出一个 dp：设 fuf_u 为子树 uu 中合法非空点集的个数，那么 fu=1+∏(fv+1)f_u = 1+\prod(f_v+1)，其中 vv 是 uu 的儿子。那么我们实际上算的就是所有 fuf_u 之和，因为每条额外边都要累加一次。
直接用单调栈扫一遍 dp 就 ok 了，不需要把树建出来。用桶排可以做到 O(n)\mathcal O(n)。
CPP
const ll N = 2e5 + 9, Mod = 1e9 + 7;
ll n, stk[N], top, dp[N], ans;
array<ll, 2> a[N];
Ve<pii> vec[N];
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read();
    rep(i, 1, n - 3) {
        a[i][0] = read(), a[i][1] = read();
        if(a[i][0] > a[i][1]) swap(a[i][0], a[i][1]);
        vec[a[i][0]].pb({a[i][1], i});
    }
    a[n - 2] = {1, n};
    sort(a + 1, a + n - 1, [&](array<ll, 2> a, array<ll, 2> b) {
        return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
    });
    rep(i, 1, n - 2) {
        dp[i] = 1;
        while(top && a[stk[top]][1] <= a[i][1]) dp[i] = dp[i] * (dp[stk[top]] + 1) % Mod, --top;
        stk[++top] = i, ans += dp[i];
    }
    write(ans % Mod), putchar('\n');
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...