Educational Codeforces Round 38 部分题解

D. Buy a Ticket

分析

建一个源点，连向所有结点，边的花费为那个结点的花费，图中原有的边花费翻倍，最后跑一遍最短路即可。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

const long long INF = 2e18;

struct Edge { int to; long long w; };

vector<Edge> G[N];

long long d[N];

priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q;

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for(int i = 0; i < m; i++) {

        int u, v;

        long long w;

        scanf("%d%d%I64d", &u, &v, &w);

        G[u].push_back(Edge{v, 2 * w});

        G[v].push_back(Edge{u, 2 * w});

    }

    for(int i = 0; i < n; i++) {

        long long x;

        scanf("%I64d", &x);

        G[0].push_back(Edge{i + 1, x});

    }

    fill(d, d + N, INF);

    d[0] = 0;

    q.push(pair<long long, int>(0, 0));

    while(!q.empty()) {

        pair<long long, int> now = q.top(); q.pop();

        if(d[now.second] < now.first) continue;

        for(Edge e : G[now.second]) {

            if(now.first + e.w < d[e.to]) {

                d[e.to] = now.first + e.w;

                q.push(pair<long long, int>(d[e.to], e.to));

            }

        }

    }

    for(int i = 1; i <= n; i++) printf("%I64d%c", d[i], " \n"[i == n]);

    return 0;

}

E. Max History

分析

推公式。

过程这里很详细了。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 1;

const int MOD = 1e9 + 7;

int a[N];

long long qpow(long long x, long long k) {

    long long res = 1;

    while(k) {

        if(k & 1) res = res * x % MOD;

        x = x * x % MOD;

        k >>= 1;

    }

    return res;

}

int main() {

    int n;

    scanf("%d", &n);

    for(int i = 0; i < n; i++) {

        scanf("%d", &a[i]);

    }

    sort(a, a + n);

    long long x = 1, ans = 0;

    for(int i = 0; i < n; i++) x = x * (i + 1) % MOD;

    for(int i = 0; i < n - 1; i++) {

        if(a[i] == a[n - 1]) break;

        ans = (ans + (a[i] * x % MOD) * qpow(n - (lower_bound(a, a + n, a[i]) - a), MOD - 2) % MOD) % MOD;

    }

    cout << ans << endl;

    return 0;

}

F. Erasing Substrings

分析

这道题很神奇。

设 $n$ 为字符串长， $m$ 为不超过 $n$ 的最大的 $2$ 的倍数。

那么最后答案长度为 $n-m+1$，组成答案的这些字符中，第一个字符一定是在原子符串区间 $[0,m-1]$ 内取到的，第二个在区间 $[1,m]$ 内取到的，后面同理。

$f[i]$ 为 $1$ 则表示可以转移到 $i$ 这个状态，其中 $ 0\leq i < m$，二进制位为 $1$ 对应某个长度的删除操作已经执行过了。

每次右移一个字符，然后我们选择要转移到的状态，因为前面已经有一个字符成为答案中的一个字符了，所以比较的时候应该是 $s[i + j]$ 而不是 $s[j]$。

每次我们都要更新出下次可以转移到的合法状态，如果现在的状态是 $1001$ ，即前面已经删过了长度为 $1$ 和 $8$ 的子串，我们可以转移到 $1001, 1101, 1011, 1111$ ，即我们可以选择删掉长度为 $2$ 或 $4$ 的子串，或者不删，直接取接下来的字符。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int f[N], g[N];

char ans[N];

int main() {

    string s;

    cin >> s;

    int n = s.length();

    int m = 1;

    while(m <= n) m <<= 1; m >>= 1;

    for(int i = 0; i < m; i++) f[i] = 1;

    for(int i = 0; i <= n - m; i++) {

        ans[i] = 'z';

        for(int j = 0; j < m; j++) {

            if(f[j] && s[i + j] < ans[i]) ans[i] = s[i + j];

        }

        memset(g, 0, sizeof g);

        for(int j = 0; j < m; j++) {

            if(!g[j] && f[j] && ans[i] == s[i + j]) {

                int w = m - 1 - j;

                for(int k = w; k; k = w & (k - 1)) g[m - 1 - k] = 1;

                g[m - 1] = 1;

            }

        }

        for(int j = 0; j < m; j++) f[j] = g[j];

    }

    ans[n - m + 1] = 0;

    printf("%s", ans);

    return 0;

}

巴特西

Educational Codeforces Round 38 部分题解

D. Buy a Ticket

分析

code

E. Max History

分析

code

F. Erasing Substrings

分析

code

最新文章

热门文章