【XJTU 2020暑期集训】Day8 - 2018 CCPC 吉林赛区

A - The Fool

签到题,整除分块板题,总复杂度 O(\sqrt{n})

B - The World

简单模拟。注意坑点:12:XX AM表示当天凌晨XX分,12:XX PM表示当天中午XX分。

C - Justice

优先队列维护 k 值,不断地将最大的两个相同的 k 合并为 k-1,同时用并查集维护id。当最大值为1时,记录其id。当最大值唯一时,直接将其丢弃,因为它不会对答案再产生贡献。最后将第一个1所在集合中的数设为一组,将其余数设为另一组即可。总复杂度 O(n\log n)

D - The Moon

期望dp。设 f[q] 表示对于概率 q,获胜的期望轮数,转移方程为 f[q]=1+p(1-q)f[\min(100\%,q+2\%)]+(p-1)f[\min(100\%,q+1.5\%)],边界条件为 f[100\%]=1/p,答案即为 f[2\%]

E - The Tower

F - The Hermit

G - High Priestess

H - Lovers

I - Strength

J - Wheel of Fortune

K - The Magician

L - The Hanged Man

Code

A - The Fool

#include <iostream>
#include <stdio.h>
#include <string.h>
#define int long long

using namespace std;

int T, n;

signed main() {
    scanf("%lld", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%lld", &n);
        int ans = 0;
        for (int i = 1, t; i <= n; i = t + 1) {
            t = min(n, n / (n / i));
            ans = (ans + (t - i + 1) * (n / i)) & 1;
        }
        printf("Case %lld: %s\n", cas, ans ? "odd" : "even");
    }
}

B - The World

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int T, h, m;
char s[16];

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d:%d", &h, &m);
        scanf("%s", s);
        if (s[0] == 'A' && h == 12) {
            h = 0;
        }
        if (s[0] == 'P' && h != 12) {
            h += 12;
        }
        scanf("%s", s);
        if (s[0] == 'B') {
            h -= 8;
        } else if (s[0] == 'W') {
            h += 5;
        } else if (s[0] == 'M') {
            h -= 3;
        }
        scanf("%s", s);
        if (s[0] == 'B') {
            h += 8;
        } else if (s[0] == 'W') {
            h -= 5;
        } else if (s[0] == 'M') {
            h += 3;
        }
        printf("Case %d: ", cas);
        if (h < 0) {
            printf("Yesterday ");
            h += 24;
        } else if (h >= 24) {
            printf("Tomorrow ");
            h -= 24;
        } else {
            printf("Today ");
        }
        if (h < 12) {
            printf("%d:%02d AM\n", h ? h : 12, m);
        } else {
            printf("%d:%02d PM\n", h == 12 ? h : h - 12, m);
        }
    }
}

C - Justice

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX_N 100005
#define pii pair<int, int>

using namespace std;

int T, n;
int a[MAX_N];
int ids[MAX_N];
int par[MAX_N];

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

void merge(int x, int y) {
    par[find(x)] = find(y);
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }
        for (int i = 1; i <= n; i++) {
            par[i] = i;
        }
        priority_queue<pii> q;
        for (int i = 1; i <= n; i++) {
            q.push(pii(a[i], i));
        }
        int cnt = 0;
        while (!q.empty()) {
            pii p1 = q.top();
            q.pop();
            if (p1.first == 1) {
                ids[++cnt] = p1.second;
                continue;
            }
            if (!q.empty()) {
                pii p2 = q.top();
                q.pop();
                if (p1.first == p2.first) {
                    merge(p1.second, p2.second);
                    q.push(pii(p1.first - 1, p1.second));
                } else {
                    q.push(p2);
                }
            }
        }
        if (cnt >= 2) {
            printf("Case %d: YES\n", cas);
            for (int i = 1; i <= n; i++) {
                if (same(i, ids[1])) {
                    printf("0");
                } else {
                    printf("1");
                }
            }
            printf("\n");
        } else {
            printf("Case %d: NO\n", cas);
        }
    }
}

D - The Moon

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 205

using namespace std;

int T;
double p, q;
double f[MAX_N];

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%lf", &p);
        p *= 0.01;
        f[200] = 1 / p;
        for (int i = 199; i >= 4; i--) {
            q = i * 0.005;
            f[i] = 1 + p * (1 - q) * f[min(200, i + 4)] + (1 - p) * f[min(200, i + 3)];
        }
        printf("Case %d: %.10f\n", cas, f[4]);
    }
}

E - The Tower


F - The Hermit


G - High Priestess


H - Lovers


I - Strength


J - Wheel of Fortune


K - The Magician


L - The Hanged Man


点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注