CCPC 2018 吉林站赛后总结及部分题解

CCPC 2018 吉林站

赛后总结

罚时、罚时、罚时……这次训练依然是BUPT校内训练,我依然是单开,但与上次不同的是,这次罚时真的可怕的飞起——以至于我D题写不出来之后直接心理崩溃,无法继续开题了。ACM的罚时机制其实让提交成本变得很高,所以自己的某些代码习惯还是要改改的。

部分题解

A. The Fool

题意:给定t组n \in N_{+},对于每一个n求:

\sum_{i=1}^{N} [\frac{n}{i}]

题解:在只有一个n的时候其实直接依题意枚举即可,当然10^9对于多组数据而言还是比较大的。我们直接考虑n=10^9的情况,容易发现从[\frac{n}{2}]+1n,每一项的除值都为1,所以直接对答案加上n-[\frac{n}{2}]即可。同理我们可以找到[\frac{n}{3}]+1[\frac{n}{2}]除值都为2,所以答案加上2 \times (n-[\frac{n}{2}])。如此反复我们发现只要到一个整除值,我们就可以直接跳过对应取整均等于该值的整数。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long _t;
    scanf("%lld", &_t);
    for (long long casecnt = 1; casecnt <= _t; ++casecnt)
    {
        long long sum = 0, n;
        scanf("%lld", &n);
        for (long long i = 1; i <= n;)
        {
            sum += (n / i) * (n / (n / i) - i + 1);
            i = n / (n / i) + 1;
        }
        printf("Case %lld: %s\n", casecnt, ((sum % 2) ? "odd" : "even"));
    }
}

B. The World

题意:给定t组数据,每次有一个地方的时间,请转换位同一时刻,另一地方的当地时间。

题解:先把输入时间转换为UTC也就是格林威治时间,直接减去对应时区即可。比如北京是UTC +8,那么就直接减8小时。然后再加上目标地区的时区,比如华盛顿是UTC -5,那么就直接+(-5)小时。对于所有的12点,将之转化为0点。之后,对PM,加上12小时。当处理完的时间小于0时,说明目标时间是昨天。当大于24时,说明在明天。对下午时间减去12后就得到了结果。

#include <bits/stdc++.h>

using namespace std;

int conv(string city)
{
    if (city == "Beijing")
        return 8;
    if (city == "Washington")
        return -5;
    if (city == "London")
        return 0;
    if (city == "Moscow")
        return 3;
    return 2147483647;
}

int read()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        x = x * 10 + c - '0', c = getchar();
    return x;
}

int main()
{
    int _t = read(), casecnt = 1;
    while (_t--)
    {
        int hour = read(), minute = read();
        string period, city, days;
        if (hour == 12)
            hour -= 12;
        cin >> period;
        if (period == "PM")
            hour += 12;
        cin >> city;
        hour -= conv(city);
        cin >> city;
        hour += conv(city);
        if (hour < 0)
            hour += 24, days = "Yesterday";
        else if (hour >= 24)
            hour -= 24, days = "Tomorrow";
        else
            days = "Today";
        if (hour >= 12)
            hour -= 12, period = "PM";
        else
            period = "AM";
        printf("Case %d: ", casecnt++);
        cout << days << ' ';
        if (hour == 0) cout << 12;
        else cout << hour;
        cout << ":";
        if (minute < 10) cout << "0";
        cout << minute;
        cout << " " << period << endl;
    }
}

D. The Moon

题意:给定胜率p%(p是不大于100的自然数),初始抽奖成功率位q=2%。玩家重复如下操作:

  1. 玩一局游戏,胜率为p%;
  2. 若获胜,则进行第3步操作,否则执行第4步;
  3. 以q为成功率进行抽奖,若成功则结束游戏,若失败则令q=min{100%, q+2%},返回第1步;
  4. q=min{100%, q+1.5%},返回第1步。

求当前情况下玩家玩到结束的轮数的期望。

#include <bits/stdc++.h>

#define eps 0.00000001

using namespace std;

int read()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        x = x * 10 + c - '0', c = getchar();
    return x;
}

double f[1111];

void init()
{
    memset(f, 0, sizeof(f));
}

int main()
{
    int _t = read(), casecnt = 1;
    while (_t--)
    {
        double p;
        scanf("%lf", &p);
        p = p / 100.0;
        init();
        f[1000] = (double)(1.0 / p);
        for (int i = 1000; i >= 20; i--)
        {
            if (f[i + 20] && i + 20 <= 1000)
            {
                f[i] = i / 1000.0 * p * 1.0;
                f[i] += p * (1.0 - i / 1000.0) * (f[i + 20] + 1.0);
            }
            if (f[i + 15] && i + 15 <= 1000)
            {
                if (f[i] > eps) f[i] += (1 - p) * (f[i + 15] + 1);
                else if (p < 1.0 - eps)
                    f[i] = i / 1000.0 * p * 1.0 + (1 - p) * (f[i + 15] + 1);
            }
        }
        printf("Case %d: %.10f\n", casecnt++, f[20]);
    }
    return 0;
}

发表评论