总分 $500$，得分 $90$。非常裂开，非常无语(ˉ▽ˉ；)…

欢迎收看《关于 ljt 是怎么挂掉 $\text{240pts}$ 的》。

T1

一道很简单的贪心，把运动员按照能力大小排序，统计运动员的总参赛时间，如果没到就加上这个运动员的能力值与参加比赛时间之积。另外，因为我们是按照能力值从大到小排序的，所以需要让排在前面的运动员尽量多一些时间，也就是说，这道题里面我们要当万恶的资本家，把能力值最大的几个运动员都榨干。

不开 long long 见祖宗，挂了 $\text{40pts}$。另外一定要注意 long long 要开全，否则会导致 $\text{65pts}$ 惨案。

zszz，#define int long long 是个好东西。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;

const int maxn = 505;

struct node { int k, l; } a[maxn];
int m, n, tot, ans;

bool cmp(node x, node y) { return x.k > y.k; }

signed main() {
    freopen("marathon.in", "r", stdin);
    freopen("marathon.out", "w", stdout);
    scanf("%lld %lld", &m, &n);
    for(int i = 1; i <= n; i++) scanf("%lld %lld", &a[i].k, &a[i].l);
    stable_sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; i++) {
        if(tot >= 6 * m) break;
        else if(tot + a[i].l <= 6 * m) {
            ans += a[i].k * a[i].l;
            tot += a[i].l;
        } else {
            ans += a[i].k * (6 * m - tot);
            tot = 6 * m;
        }
    }
    printf("%lld", ans);
    return 0;
}

说句闲话：对了，你们有没有注意到 ljt 最近换码风了？我感觉之前那种太紧凑了不好调代码就换了 qwq。

T2

《关于 ljt 因为把 Friday 打成 Firday 而痛失 $\text{100pts}$ 这回事》

直接无语了。

小模拟，觉得这道题不过瘾的可以去做做儒略日，注意闰年的判断，以及初始值（$2011.1.1$ 是星期六）。

  1. 普通年能被 $4$ 整除且不能被 $100$ 整除的为闰年。(如 $2004$ 年就是闰年，$1901$ 年不是闰年)
  2. 世纪年能被 $400$ 整除的是闰年。(如 $2000$ 年是闰年，$1900$ 年不是闰年)

因为数据很大，而且是多组数据（考试范围写的是时间早于 $99999.12.31$ 后来数据只出到了 $3199.12.31$……离谱），我们可以使用一个办法来避免 TLE ——离线。

离线大概就是一次性把所有测试数据都存下来，按照大小排序，这样只用跑一遍从 $2011$ 到 $99999$ 的年份就可以判断完所有数据。

具体看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <algorithm>
using namespace std;

// 2011/01/01: Saturday

const int maxn =(int)1e5 + 5;

struct node { int y, m, d, num, ans; } a[105];
int M[2][13] = { {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} };
int date = 6;
// sunday,monday,tuesday,wednesday,thursday,friday,saturday
char ans[7][15] = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" };

bool earlier(int y1, int m1, int d1, int y2, int m2, int d2) {
    if(y1 < y2) return 1;
    else if(y1 > y2) return 0;
    else {
        if(m1 < m2) return 1;
        else if(m1 > m2) return 0;
        else {
            if(d1 < d2) return 1;
            return 0;
        }
    }
}

bool cmp1(node x, node y) { return earlier(x.y, x.m, x.d, y.y, y.m, y.d); }
bool cmp2(node x, node y) { return x.num < y.num; }

bool run(int y) {
    if(y % 4) return 0;
    else if(y % 100) return 1;
    else if(!(y % 400)) return 1;
    return 0;
}

int main() {
     freopen("date.in", "r", stdin);
     freopen("date.out", "w", stdout);
    int tot = 1, Num = 1;
    while(scanf("%d %d %d", &a[tot].y, &a[tot].m, &a[tot].d) != EOF) {
        a[tot].num = tot;
        ++tot;
    }
    --tot;
    stable_sort(a + 1, a + tot + 1, cmp1);
    for(int year = 2011; year <= a[tot].y; year++) {
        for(int month = 1; month <= 12; month++) {
            int t = run(year) ? 1 : 0;
            for(int day = 1; day <= M[t][month]; day++) {
                while(year == a[Num].y && month == a[Num].m && day == a[Num].d) {
                    a[Num].ans = date;
                    ++Num;
                }
                date = (date + 1) % 7;
            }
        }
    }
    stable_sort(a + 1, a + tot + 1, cmp2);
    for(int i = 1; i <= tot; i++) printf("%s\n", ans[a[i].ans]);
    return 0;
}

T3

出题人语文显然需要重修。

这道题是什么呢，大概就是给一个数 $m$，要求从 $1\sim m$ 中找到一个数 $n$ 使得 $1\sim n$ 中与 $m$ 互质的数的数量与 $n$ 之比最小。

数据范围是 $1\le m\le 10^{40}$，这不仅告诉我们要开高精，还告诉我们这题肯定有一些奇奇怪怪的性质。

通过分析样例：

样例输入 1：10

样例输出 1：6

$6=2\times 3$

也就是 $3$ 及以内的所有质数相乘。

样例输入 2：10000000000

样例输出 2：6469693230

$6469693230=2×3×5×7×11×13×17×19×23×29$

也就是 $29$ 及以内的质数相乘。别问我要怎么看出来，这是 zm 说的，我也不知道。

为什么是 $29$ 呢？因为如果取 $31$ 的话，就超过 $m$ 了，而选用 $29$ 是不超过 $m$ 中最大的那个。

到这里思路就很明显了：线性筛质数，然后疯狂相乘找答案。时间复杂度是 $O\text{(质数的个数)}$，绝对不会超过 $10^5$。

需要的高精是高精乘和高精比较，你们爱复制板子就去复制板子吧。反正我也是复制的板子。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = (int)1e5 + 5;

string m;
long long g[maxn], tot;
bool f[maxn];

void Prime() {
    for (int i = 2; i <= maxn >> 1; i++) {
        if (!f[i]) g[++tot] = i;
        for (int j = 1; j <= tot; j++) {
            long long t = i * g[j];
            if (t > maxn) break;
            f[t] = 1;
            if (!(i % g[j])) break;
        }
    }
    return;
}

string mul(string a1, string b1) {
    int a[10005] = {}, b[10005] = {}, c[10005] = {};
    if (a1 == "0" || b1 == "0") return "0";
    string c1;
    int lena = a1.size();
    int lenb = b1.size();
    for (int i = 0; i < lena; i++) a[lena - i] = a1[i] - '0';
    for (int i = 0; i < lenb; i++) b[lenb - i] = b1[i] - '0';
    int lenc;
    for (int i = 1; i <= lena; i++) {
        for (int j = 1; j <= lenb; j++) {
            lenc = i + j - 1;
            c[lenc] += a[i] * b[j];
            c[lenc + 1] += c[lenc] / 10;
            c[lenc] %= 10;
            lenc++;
        }
    }
    lenc = lena + lenb;
    while (!c[lenc]) lenc--;
    while (lenc >= 1) c1 += c[lenc--] + '0';
    return c1;
}

bool Max(string x, string y) {
    if(x.size() > y.size()) return 1;
    else if(x.size() < y.size()) return 0;
    int len = x.size();
    for(int i = 0; i <len; i++) {
        if(x[i] > y[i]) return 1;
        else if(x[i] < y[i]) return 0;
    }
    return 0;
}

string str(int x) {
    string a, b;
    while (x) {
        a += x % 10 + 48;
        x /= 10;
    }
    for (int i = a.size() - 1; i >= 0; i--) b += a[i];
    return b;
}

int main() {
    freopen("flower.in", "r", stdin);
    freopen("flower.out", "w", stdout);
    cin >> m;
    Prime();
    string qwq = "1";
    for(int i = 1; i <= maxn - 5; i++) {
        string r = qwq;
        qwq = mul(str(g[i]), qwq);
        if(Max(qwq, m)) {
            cout << r;
            return 0;
        }
    }
    return 0;
}

T4

LIS 板子题，LIS 普通版板子都能写挂我也是服了自己了。

首先初始长度（不斜对角穿）肯定是 $100\times(m+n)$，然后考虑穿对角线的情况。我们把所有允许穿对角线的方块按照 $x$ 值从小到大排序，然后找 $y$ 值的 LIS 即可。

来自 cgy：sqrt(2) 打成 1.414，精度挂了 $\text{60pts}$。为 cgy 大佬默哀。

LIS 是板子，不需要我讲了吧？

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxk = 1005;

struct node { int x, y; } a[maxk];
int m, n, k, qaq, dp[maxk]; // LIS

bool cmp(node x, node y) { return x.x < y.x; }

int main() {
    freopen("metro.in", "r", stdin);
    freopen("metro.out", "w", stdout);
    scanf("%d %d %d\n", &m, &n, &k);
    for(int i = 1; i <= k; i++) scanf("%d %d", &a[i].x, &a[i].y);
    stable_sort(a + 1, a + k + 1, cmp);
    //LIS
    dp[1] = 1;
    for(int i = 2; i <= k; i++) {
        int t = 1;
        for(int j = 1; j <= i; j++) {
            if(a[j].y < a[i].y) t = max(t, dp[j] + 1);
            qaq = max(qaq, t);
        }
        dp[i] = t;
    }
    printf("%d", (int)round(((m + n) * 100 - qaq * (200 - 100 * (long double)sqrt(2)))));
    return 0;
}

T5

骗分能拿 $\text{30pts}$：如果修改的次数大于等于掉头指令的个数，就把所有掉头改成前进，然后疯狂改一个指令根据奇偶性判断是不是能改到前进指令从而判断答案。

正解是 dp：

  • $dp_{i,j,0,0/1}$ 代表执行前 $i$ 条指令，改 $j$ 次指令，目前头朝正轴方向，在 正数区/负数区 离原点的最远距离。

  • $dp_{i,j,1,0/1}$ 代表执行前 $i$ 条指令，改 $j$ 次指令，目前头朝负轴方向，在 正数区/负数区 离原点的最远距离。

代码鸽掉了。