Visits: 461

Codeforces Round #623 (Div. 1, based on VK Cup 2019-2020 – Elimination Round, Engine)

Recommendations

用堆贪心。

const int N = 2e5 + 7;
int n;
ll s, ans;
pair<ll, ll> p[N];

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(p[i].fi);
    for (int i = 1; i <= n; i++) rd(p[i].se);
    sort(p + 1, p + n + 1);
    pq<ll> q;
    q.push(p[1].se), s += p[1].se;
    for (int i = 2; i <= n; i++) {
        while (p[i-1].fi < p[i].fi && q.size())
            ++p[i-1].fi, s -= q.top(), q.pop(), ans += s;
        q.push(p[i].se), s += p[i].se;
    }
    while (q.size()) s -= q.top(), q.pop(), ans += s; 
    print(ans);
    return 0;
}

Double Elimination

不知道哪儿来的屑题。

Au Pont Rouge

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

Tourism

无奇环就想到二分图染色，随机染色即可，碰到正解的概率应该是 $\frac {1}{512}$，卡时即可。

赛后加了一组 Hack 数据好像卡了随机，偷懒面向数据编程了。

const int N = 81, K = 11, inf = 1e9;
int n, k, a[N][N], c[N], f[K][N], ans;

inline int solve() {
    for (int i = 1; i <= n; i++) {
        c[i] = rand() & 1;
        for (int j = 0; j < k; j++) f[j][i] = inf;
    }
    f[0][1] = 0;
    for (int i = 1; i < k; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                if (c[j] ^ c[k]) f[i][j] = min(f[i][j], f[i-1][k] + a[k][j]);
    int ret = inf;
    for (int i = 1; i <= n; i++)
        if (c[1] ^ c[i]) ret = min(ret, f[k-1][i] + a[i][1]);
    return ret;
}

int main() {
    srand(time(0));
    double st = clock();
    rd(n), rd(k), ans = inf;
    for (int i = 1; i <= n; i++) rda(a[i], n);
    while ((clock() - st) / CLOCKS_PER_SEC < 2.9) ans = min(ans, solve());
    print(ans == 200000000 ? 0 : ans);
    return 0;
}

Strange Function

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

Bad Cryptography

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