csp-j题解

update :
2024.6.18 - 2024.6.25：重构题解

第一题：小苹果

原题洛谷P9748

思路

n 表示当前长度
求几天取完：每天取走 \((n - 1) / 3 + 1\) 个苹果，记录几天取完
第 \(n\) 个苹果第几天被取走：当 \(n \bmod 3 = 0\) 时被取走
时间复杂度约为 \(O(\log_n)\)

#include <iostream>
#include <cstdio>

using namespace std;

int n, tn = 1, day = 0, k;

int main()
{
    scanf("%d",&n);
    while (n){
        if ((n - 1) % 3 != 0 && k == 0) tn++;
        else k = 1;
        day++;
        n = n - (n - 1) / 3 - 1;
    }
    printf("%d %d", day, tn);
    return 0;
}

第二题:公路

原题洛谷P9749

思路

遍历每个油站，用当前到达的最小油价更新油费即可
因为从一个加油站到达下一个加油站不一定会将油消耗完，所以更新油费时应注意多出的油
时间复杂度为 \(O(n)\)

#include <iostream>
#include <cmath>

using namespace std;

const int N = 1e5 + 5;

long long n, d, v[N], a[N], w, x=N, tv, allv, gv;

int main(){
    scanf("%lld%lld", &n, &d);

    for(int i = 1;i < n; i++) 
        scanf("%lld", &v[i]), allv += v[i];

    for(int i = 1;i <= n; i++) 
        scanf("%lld", &a[i]);

    for(int i = 1, v1; i < n; i++)
    {
        gv += v[i];
        x = min(x, a[i]);
        v1 = ceil((gv - tv * d) * 1.0 / d);
        tv += v1;
        w += x * v1;
    }

    printf("%lld", w);
    return 0;
}

第三题：一元二次方程

原题洛谷P9750

分析

模拟题，模拟人类解一元二次方程即可

1. 将二次项系数变为正数，放便处理
2. 用 \(\Delta\) 判断根的情况
3. 开根

int ti(int n){
    for (int i = 2; i * i <= n; i++)
        if (n % (i * i) == 0)
            return i * ti(n / (i * i)); 

    return 1;
}

4. 约分,最大公约数用辗转相除法求最大公约数

// 辗转相除法
int gcd(int a,int b){
    return b ? gcd(b, a % b) : a;
}

5. 按题意输出即可

代码如下

#include <iostream>
#include <algorithm>

using namespace std;

int t, m;

int ti(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (n % (i * i) == 0) return i * ti(n / (i * i));
    return 1;
}

int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }

void solve()
{
    int a, b, c, delta;
    cin >> a >> b >> c;
    if (a < 0) a = -a, b = -b, c = -c;
    delta = b * b - 4 * a * c;

    if (delta < 0) { cout << "NO" <<endl; return; }
    int k = ti(delta);

    if (k * k == delta)
    {
        int f = abs(gcd(2 * a, -b + k));
        cout << (-b + k) / f;
        if (2 * a / f != 1) cout << "/" << 2 * a / f;
        cout << endl;
        return;
    }

    if(delta == 0){
        int f = abs(gcd(2 * a, -b));
        cout << -b / f;
        if (2 * a / f != 1) cout << "/" << 2 * a / f;
        cout << endl;
        return;
    }

    int f = abs(gcd(-b, 2 * a));
    if(b == 0){
        f = abs(gcd(k, 2 * a));
        if (k / f != 1) cout << k / f << "*";
        cout << "sqrt(" << delta / (k * k) << ")";
        if (2 * a / f != 1) cout << "/" << 2 * a / f;
        cout << endl;
        return;
    }

    cout << -b / f;
    if (2 * a / f != 1) cout << "/" << 2 * a / f;
    cout << "+";
    f = abs(gcd(k, 2 * a));
    if (k / f != 1) cout << k / f << "*";
    cout << "sqrt(" << delta / (k * k) << ")";
    if(2 * a / f != 1) cout << "/" << 2 * a / f;
    cout << endl;
    return;
}
int main(){
    cin >> t >> m;
    while(t--){
        solve();
    }
    return 0;
}

第四题 旅游巴士

分析

几乎是最短路模版。

假设当前时间为 \(t\) 。

因为游客只有不早于 \(a_i\) 时刻才能通过第 \(i\) 道路。
所以

1. 当 \(a_i > t\) 时，小Z不能通过这条路。
2. 当 \(a_i <= t\) 时，小Z能通过这条路，通过这条路后时间变为 \(t+1\) 。

对于 \(t\) 时刻不能通行的道路，等待，直到能通过这条路

因为不能原地等待，所以只能在起点等待。

\(t\) 时刻与 \(a_i\) 时刻相差了 \(a_i-t\) 的时间，则小Z至少要在起点等待 \(a_x-t\) 的时间，因为到达和离开景区的时间都必须是 \(k\) 的非负整数倍，所以应在起点等待的时间为 \(\lceil \frac{a_x-t}{k} \rceil\times k\),到达 \(i\) 点的时间为\(\lceil \frac{a_x-t}{k} \rceil\times k+t\)

该题所求的答案并非最小值，而是能被 \(k\) 整除的最小值。
并且 \(k\) 并不大。
定义 \(dis_{i,j}\) 表示:到达\(i\)点的时间 \(t \bmod k\) 恰好 \(j\) 的值的最短时间
答案存在\(dis_{n,0}\)

代码如下：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define int long long
#define pi pair<int, int>

using namespace std;

const int N = 1e4 + 5, M = 105;

vector<pi> edge[N];
int n, m, k, dis[N][M], vis[N][M];
priority_queue<pi, vector<pi>, greater<pi>> q;

void add(int a, int b, int c){ edge[a].push_back({b, c}); }

void bian()
{
    for (int i = 1, u, v, a; i <= m; i++)
    {
        cin >> u >> v >> a;
        add(u, v, a);
    }
}

void dijkstra (int x)
{
    dis[x][0] = 0, q.push({0, x});

    while(q.size()){
        int u = q.top().second, p = q.top().first;
        q.pop();
        if (vis[u][p%k]) continue;
        vis[u][p % k] = 1;
        for(auto d : edge[u]){
            int v = d.first, w = d.second, time1;
            if(p >= w) time1 = p;
            else time1 = ((w - p - 1) / k + 1) * k + p;
            if (dis[v][(time1 + 1) % k] > time1 + 1)
            {
                dis[v][(time1 + 1) % k] = time1 + 1;
                q.push({time1 + 1, v});
            }
        }
    }
}

signed main()
{
    memset (dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    cin >> n >> m >> k;
    bian(), dijkstra(1);
    if(vis[n][0] == 0) cout << -1;
    else cout << dis[n][0];
    return 0;
}

结尾

终于写完了，新年礼物哈哈哈