8.14 洛谷月赛

标签：洛谷 Min mnp mn T2 T1 int 8.14

感觉没有 tg 难
\(\rm Link\)

目录

• \(T1\)
• \(T2\)
• \(T3\)

（主打\(div2\)）

\(T1\)

这个 \(T1\) 是个神仙题，我甚至为它写了一个 \(45pts\) 的暴力分 然后过去切了\(T2\)再回来看才发现思路

设 \(f[i]\) 表示 \(n=i\) 时的答案，仔细研究发现有

\[f[i] = f[i - 1] \times (2^i - 1) \]

注意特判 \(n=1,n=2\) 即可。

貌似可以打表

LL f[N], g[N];

signed main() {
    cin >> n;
    g[0] = 1;
    for(int i = 1; i <= n; ++i) g[i] = (g[i - 1] << 1) % mod;
    f[1] = 1, f[2] = 3;
    for(int i = 3; i <= n; ++i) {
        f[i] = f[i - 1] * (g[i] - 1) % mod;
    }
    cout << f[n];
    return 0;
}

\(T2\)

真正的简单题，一眼鉴定为贪心
一开始开了 \(4\) 个 \(1e7\) 的数组结果爆空间了
这要是 \(OI\) 赛制就起飞了

Generator 真高级 \(qwq\)

signed main() {
    cin >> n >> k1 >> k2 >> thres;
    Generator::generate();
    //mn[n + 1] = 2e9;
    Min = 2e9;
    for(int i = n; i; --i) {
        if(a[i] < Min) mnp[i] = i, Min = a[i];
        //else mn[i] = mn[i + 1], mnp[i] = mnp[i + 1];
        else mnp[i] = mnp[i + 1];
    }

    for(int i = 1; i < n; ++i) {
        int k = a[mnp[i + 1]], p = mnp[i + 1];
        if(k < a[i]) {
            to[i] = p;
            to[p] = i;
            i = p;
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(to[i]) {
            swap(a[i], a[to[i]]);
            to[to[i]] = 0;
        }
    }
    ULL ans = 0;
    for(int i = 1; i <= n; ++i) ans += 1llu * i * a[i];
    cout << ans;
    return 0;
}

\(T3\)

朴素 \(dp\) 能拿大概 \(40\) 分，加上特殊性质的部分分能拿 \(60pts\)。止步于此

打 \(div2\) 的貌似只有一个人 \(A\) 了？那正解得多神仙

就这么点分就能拿 \(rk40\) 左右，真水

标签：洛谷,Min,mnp,mn,T2,T1,int,8.14
From： https://www.cnblogs.com/Doge297778/p/16585870.html