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}]+1到n,每一项的除值都为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%。玩家重复如下操作:
- 玩一局游戏,胜率为p%;
- 若获胜,则进行第3步操作,否则执行第4步;
- 以q为成功率进行抽奖,若成功则结束游戏,若失败则令q=min{100%, q+2%},返回第1步;
- 令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;
}