2023年CSP-J第二轮认证

阅读量: 311 编辑

[CSP-J 2023] 小苹果 P9748

小 Y 的桌子上放着 n 个苹果从左到右排成一列,编号为从 1 到 n。

小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。

每天在拿的时候,小苞都是从左侧第 1 个苹果开始、每隔 2 个苹果拿走 1 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

小苞想知道,多少天能拿完所有的苹果,而编号为 n 的苹果是在第几天被拿走的?

【输入格式】

输入的第一行包含一个正整数 n,表示苹果的总数。1≤n≤109

【输出格式】

输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为 n 的苹果是在第几天。

【输入样例】

8

【输出样例】

5 5

【样例解释】

小苞的桌上一共放了 88 个苹果。

小苞第一天拿走了编号为 11、44、77 的苹果。

小苞第二天拿走了编号为 22、66 的苹果。

小苞第三天拿走了编号为 33 的苹果。

小苞第四天拿走了编号为 55 的苹果。

小苞第五天拿走了编号为 88 的苹果。

【参考程序】

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

int n, ans, num;

int main() {
    cin >> n;
    while (n) {
        ans++;
        if (n % 3 == 1 && !num) {
            num = ans;
        }
        n = n - (n + 2) / 3;
    }
    cout << ans << ' ' << num << endl;
    return 0;
}

[CSP-J 2023] 公路 P9749

小苞准备开着车沿着公路自驾。

公路上一共有 n 个站点,编号为从 1 到 n。其中站点 i 与站点 i+1 的距离为 vi 公里。

公路上每个站点都可以加油,编号为 i 的站点一升油的价格为 ai 元,且每个站点只出售整数升的油。

小苞想从站点 1 开车到站点 n,一开始小苞在站点 1 且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进 d 公里。问小苞从站点 1 开到站点 n,至少要花多少钱加油?

【输入格式】

输入的第一行包含两个正整数 n 和 d,分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 n−1 个正整数 v1, v2 ... vn-1,分别表示站点间的距离。

输入的第三行包含 n 个正整数 a1, a… an,分别表示在不同站点加油的价格。

数据范围:1≤n≤105,1≤d≤105,1≤vi≤105,1≤ai≤105

【输出格式】

输出一行,仅包含一个正整数,表示从站点 1 开到站点 n,小苞至少要花多少钱加油。

【输入样例】

5 4
10 10 10 10
9 8 9 6 5

【输出样例】

79

最优方案下:小苞在站点 1 买了 3 升油,在站点 2 购买了 5 升油,在站点 4 购买了 2 升油。

【参考程序】

#include <bits/stdc++.h>
using namespace std;

// ans为总价钱,num为还能多跑多少
long long n, d, x, ans, num, s[100005], a[100005];

int main() {
    cin >> n >> d;
    for (long long i = 1; i < n; i++) {
        cin >> x;
        s[i] = s[i - 1] + x;
    }
    for (long long i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (long long i = 0, j = 1; i < n - 1;) {
        while (a[i] <= a[j] && j < n) {
            j++;
        }
        if (j == n) {
            j--;
        }
        ans += (s[j] - s[i] - num + d - 1) / d * a[i];
        num = (s[j] - s[i] - num + d - 1) / d * d + num - s[j] + s[i];
        i = j;
    }
    cout << ans << endl;

    return 0;
}

[CSP-J 2023] 一元二次方程 P9750

【题目背景】

众所周知,对一元二次方程 ax+ bx + c = 0, (a ≠ 0),可以用以下方式求实数解:

计算 Δ=b2 − 4ac,则:

1、若 Δ < 0,则该一元二次方程无实数解。

2、否则 Δ≥0,此时该一元二次方程有两个实数解 x1,2 = (−b±√Δ)/2a。(√为开根号,√Δ即对Δ开根号)

例如:

x2 + x + 1 = 0 无实数解,因为 Δ=12 − 4×1×1 = −3 < 0 。

x2 - 2x + 1 = 0 有两相等实数解 x1,2 = 1。

x2 - 3x + 2 = 0 有两互异实数解 x1 = 1, x2 = 2。

在题面描述中 a 和 b 的最大公因数使用 gcd(a, b) 表示。例如 12 和 18 的最大公因数是 6,即 gcd(12,18)=6。

【题目描述】

现在给定一个一元二次方程的系数 a, b, c,其中 a, b, c 均为整数且 a≠0。

你需要判断一元二次方程 ax2 + bx + c = 0 是否有实数解,并按要求的格式输出。

在本题中输出有理数 v 时须遵循以下规则:

1、由有理数的定义,存在唯一的两个整数 p 和 q,满足 q>0,gcd(p, q) = 1 且 v = p/q。

2、若 q = 1,则输出 {p},否则输出 {p}/{q},其中 {n} 代表整数 n 的值;例如:

  • 当 v = −0.5 时,p 和 q 的值分别为 −1 和 2,则应输出 -1/2;

  • 当 v = 0 时,p 和 q 的值分别为 0 和 1,则应输出 0。

对于方程的求解,分两种情况讨论:

1、若 Δ = b2 − 4ac < 0,则表明方程无实数解,此时你应当输出 NO;

2、否则 Δ≥0,此时方程有两解(可能相等),记其中较大者为 x,则:

  • (1) 若 x 为有理数,则按有理数的格式输出 x。

  • (2) 否则根据上文公式,x 可以被唯一表示为 x = q1 + q2√r 的形式,其中:

    • q1, q2 为有理数,且 q2 > 0;

    • r 为正整数且 r > 1,且不存在正整数 d > 1 使 d2 | r(即 r* 不应是 d2 的倍数);

​ 此时:

  • (1) 若 q1 ≠ 0,则按有理数的格式输出 q1,并再输出一个加号 +;

  • (2) 否则跳过这一步输出;

​ 随后:

  • (1) 若 q2 = 1,则输出 sqrt({r});

  • (2) 否则若 q2 为整数,则输出 {q2}*sqrt({r});

  • (3) 否则若 q3 为整数,则输出 sqrt({r})/{q3};

  • (4) 否则可以证明存在唯一整数 c, d 满足 c, d > 1, gcd(c, d) = 1 且 q2 = c/d,此时输出 {c}*sqrt({r})/{d};

上述表示中 {n} 代表整数 {n} 的值,详见样例。

如果方程有实数解,则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解,则输出 NO。

【输入格式】

输入的第一行包含两个正整数 T, M,分别表示方程数和系数的绝对值上限。

接下来 T 行,每行包含三个整数 a, b, c。

数据范围:1≤T≤5000,1≤M≤1000,|a|,|b|,|c| ≤ M,a ≠ 0

【输出格式】

输出 T 行,每行包含一个字符串,表示对应询问的答案,格式如题面所述。

每行输出的字符串中间不应包含任何空格。

【输入样例】

9 1000
1 -1 0
-1 -1 -1
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1

【输出样例】

1
NO
1
-1
-1/2
12*sqrt(3)
3/2+sqrt(5)/2
1+sqrt(2)/2
-7/2+3*sqrt(5)/2

【参考程序】

#include <bits/stdc++.h>
using namespace std;
int t, m, a, b, c;

int gcd(int p, int q) {
    int u;
    while (q != 0) {
        u = p % q;
        p = q;
        q = u;
    }
    return p;
}

void fun1(int p, int q) {
    if (p * q < 0)
        cout << '-';
    if (p < 0)
        p = 0 - p;
    if (q < 0)
        q = 0 - q;
    int g = gcd(p, q);
    if (g == q)
        cout << p / g;
    else
        cout << p / g << '/' << q / g;
    return;
}
void fun2(int p, int q) {
    if (p < 0)
        p = -p;
    if (q < 0)
        q = -q;
    int u = 1;
    for (int i = sqrt(p); i >= 2; i--) {
        if (p % (i * i) == 0) {
            p = p / (i * i);
            u = u * i;
            break;
        }
    }
    int g = gcd(u, q);
    u = u / g;
    q = q / g;
    if (u != 1)
        cout << u << "*";
    if (p != 1)
        cout << "sqrt(" << p << ")";
    if (q != 1)
        cout << "/" << q;
}
int main() {
    cin >> t >> m;
    while (t--) {
        cin >> a >> b >> c;
        int d = b * b - 4 * a * c;
        if (d < 0) {
            cout << "NO";
        } else {
            int q = sqrt(d);
            if (q * q == d) {
                double ans1 = 1.0 * (-b + q) / (2 * a);
                double ans2 = 1.0 * (-b - q) / (2 * a);
                if (ans1 > ans2) {
                    if (-b + q == 0)
                        cout << 0;
                    else
                        fun1(-b + q, 2 * a);
                } else {
                    if (-b - q == 0)
                        cout << 0;
                    else
                        fun1(-b - q, 2 * a);
                }
            } else {
                if (b != 0)
                    fun1(-b, 2 * a);
                if (b != 0)
                    cout << "+";
                fun2(d, 2 * a);
            }
        }
        cout << endl;
    }
    return 0;
}

[CSP-J 2023] 旅游巴士 P9751

小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有 n 处地点,在这些地点之间连有 m 条道路。其中 1 号地点为景区入口,n 号地点为景区出口。我们把一天当中景区开门营业的时间记为 0 时刻,则从 0 时刻起,每间隔 k 单位时间便有一辆旅游巴士到达景区入口,同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能单向通行。对于每条道路,游客步行通过的用时均为恰好 1 单位时间。

小 Z 希望乘坐旅游巴士到达景区入口,并沿着自己选择的任意路径走到景区出口,再乘坐旅游巴士离开,这意味着他到达和离开景区的时间都必须是 k 的非负整数倍。由于节假日客流众多,小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动,而不想在任何地点(包括景区入口和出口)或者道路上停留。

出发前,小 Z 忽然得知:景区采取了限制客流的方法,对于每条道路均设置了一个 “开放时间” ai,游客只有不早于 ai 时刻才能通过这条道路。

请帮助小 Z 设计一个旅游方案,使得他乘坐旅游巴士离开景区的时间尽量地早。

【输入格式】

输入的第一行包含 3 个正整数 n, m, k,表示旅游景点的地点数、道路数,以及旅游巴士的发车间隔。

输入的接下来 m 行,每行包含 3 个非负整数 ui, vi, ai,表示第 i 条道路从地点 ui 出发,到达地点 vi,道路的“开放时间”为 ai

数据范围:2 ≤ n ≤ 104,1 ≤ m ≤ 2 × 104,1 ≤ k ≤ 100,1 ≤ ui, vi ≤ n,0 ≤ ai ≤ 106

【输出格式】

输出一行,仅包含一个整数,表示小 Z 最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案,输出 -1。

【输入样例】

5 5 3
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1

【输出样例】

6

小 Z 可以在 3 时刻到达景区入口,沿 1→3→4→5 的顺序走到景区出口,并在 6 时刻离开。

【参考程序】

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pir;
const int N = 1e4 + 10, M = 2e4 + 10, K = 110, INF = 0x3f3f3f3f;
int n, m, k;
int d[N][K];
int idx, h[N], ne[M], e[M], w[M];
bool vis[N][K];

inline int read() {
    int r = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        r = (r << 3) + (r << 1) + c - '0';
        c = getchar();
    }
    return r * f;
}

inline void add(int a, int b, int c) {
    ne[idx] = h[a];
    e[idx] = b;
    w[idx] = c;
    h[a] = idx++;
}

inline int up(int a, int b) {
    if (a % b == 0)
        return a / b;
    return a / b + 1;
}

inline int get(int x, int y) {
    if (x >= y)
        return x;
    return up(y - x, k) * k + x;
}

inline void dijkstra(int s) {
    priority_queue <pir, vector <pir>, greater <pir> > q;
    d[s][0] = 0;
    q.push({0, s});
    while (!q.empty()) {
        pir t = q.top();
        q.pop();
        int dist = t.first % k;
        if (vis[t.second][dist])
            continue;
        vis[t.second][dist] = true;
        for (int i = h[t.second]; ~i; i = ne[i]) {
            int j = e[i], lim = w[i];
            int ndist = (dist + 1) % k, ntime = get(t.first, lim) + 1;
            if (d[j][ndist] > ntime) {
                d[j][ndist] = ntime;
                q.push({d[j][ndist], j});
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof(h));
    memset(d, INF, sizeof(d));
    n = read();
    m = read();
    k = read();
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        a = read();
        b = read();
        c = read();
        add(a, b, c);
    }
    dijkstra(1);
    if (d[n][0] >= INF)
        cout << "-1" << endl;
    else
        cout << d[n][0];
    return 0;
}
爱码岛编程公众号
微信扫码关注
爱码岛编程小程序
微信扫码打开
苏ICP备13052010号
©2023 南京匠成信息科技有限公司