小苹果

链接：https://www.luogu.com.cn/problem/P9748

思路

第一问比较简单。我们发现，每天拿走的苹果的总数除 $3$ 向上取整，换种说法：定义 $m$ 为目前的总数，那么每天取走的就是 $\lfloor\frac{m}{3}\rfloor$。

在看第二问的时候，我们发现了题目问的恰好是第 $n$ 个苹果什么时候取走，那么我们按上面的方式，当 $m \bmod 3 = 1$，那么苹果就是那一轮拿走的。

代码

#include <bits/stdc++.h>
using namespace std;
long long a[10005] = {1}, n, I, tt, II;
int main() {
    cin >> n;
    for (int i = 1; i <= 33; i ++) a[i] = a[i - 1] * 3;
    int nn = n;
    while (n) {
        long long t = (n + 2) / 3;
        n -= t;
        I ++;//计数器

    }
    while (nn) {
        long long t = (nn + 2) / 3;
        if (nn % 3 == 1) {
            tt = II;
            //发现答案
            break;
        }
        nn -= t;
        II ++;
        // if (nn % 3 == 1) {
        //     tt = II;
        //     break;
        // }
    }
    cout << I << " " << tt + 1;
    return 0;
}

公路

赤裸裸的贪心。

贪心思路：每次把油加到够到达下一个油费最小的，注意最后一个加油站的邮费为 -inf。

注意每次到达下一次加油时有可能有剩余的。

#include <bits/stdc++.h>
using namespace std;
long long n, m, v[100005], a[100005], s[100005], V;
int main() {
    // freopen("road.in", "r", stdin);
    // freopen("road.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i < n; i ++) {
        cin >> v[i];
    }

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    for (int i = 2; i <= n; i ++) {
        s[i] = s[i - 1] + v[i - 1];
        // cout << s[i] << "\n1\n";
    }
    // cout << "1";
    a[n] = 0;
    // cout << 1;
    long long ans = 0;
    for (int i = 1; i <= n;) {
        if (i == n) break;//注意终点站不用加油
        int minn = n;
        for (int j = i + 1; j <= n; j ++) {
            if (a[j] <= a[i]) {
                minn = j;//找到下一个要去加油的站
                break;
            }
        }
        if (V < 0) V = 0;
        int x = (s[minn] - s[i] + m - 1 - V) / m;//计算
        ans += x * a[i];

        // cout << minn << " " << i << " " << x * a[i] << " " << V << "\n";
        V = x * m - ((s[minn] - s[i] - V));
        i = minn;
        // cout << s[minn] - s[i - 1] << " " << minn << " " << i << "\n";
    }
    cout << ans;
    return 0;
}

一元二次方程

模拟题，就是题面对初一及以下的人有点不友好。

其实很见到，难点也就是输出实数。

#include <bits/stdc++.h>

using namespace std;
/*
*/
int T, M; 
void printnum(int p, int q, char ch) {
    double x = p * 1.0 / 1.0 / q;
    if (x == (int)x) {
        cout << x << ch;
    } else {
        int gpq = __gcd(p, q);
        gpq = abs(gpq);
        cout << p / gpq << "/" << q / gpq << ch;
    }
}
void printnum2(int p, int q) {
    double x = p * 1.0 / 1.0 / q;
    if (x == (int)x) {
        if (x != 0) cout << x << "+";
    } else {
        int gpq = __gcd(p, q);
        gpq = abs(gpq);
        cout << p / gpq << "/" << q / gpq << "+";
    }
}
void printnum3(int p, int q, int sq) {
    // cout << p << " " << q << " " << sq << "\n";
    double x = p * 1.0 / 1.0 / q;
    if (x == (int)x) {
        if (x != 1) cout << x << "*sqrt(" << sq << ")\n";
        else cout << "sqrt(" << sq << ")\n";
    } else {
        int gpq = __gcd(p, q);
        gpq = abs(gpq);
        // cout << "+";
        if (p / gpq != 1) cout << p / gpq << "*sqrt(" << sq << ")/" << q / gpq << "\n";
        else cout << "sqrt(" << sq << ")/" << q / gpq << "\n";
    }
}
int main() {
    // ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> T >> M;
    while(T --) {
        int a, b, c; cin >> a >> b >> c;
        if (a < 0) a = -a, b = -b, c = -c;
        if (b * b - 4 * a * c < 0) {
            cout << "NO\n";
            continue;
        }
        int del = b * b - 4 * a * c;
        if (int(sqrt(del)) * int(sqrt(del)) == del) {
            // cout << -b + int(sqrt(del)) << " " << 2 * a << "\n";
            printnum(-b + int(sqrt(del)), 2 * a, '\n');
        } else {
            // cout << "*" << "\n";
            printnum2(-b, 2 * a);
            int p2 = 1;
            for (int i = 1; i * i <= del; i ++) {
                if (del % (i * i) == 0) {
                    p2 = i;
                }
            }
            if (p2 == 1) {

                cout << "sqrt(" << del << ")/" << 2 * a << "\n";
            } else {
                printnum3(p2, 2 * a, del / p2 / p2);
            }
        }
    }
    return 0;
}

旅游巴士

图论题。

运用算法：dijkstra。

其实说是 dijkstra，但是实际上就是优先队列优化 bfs。

题目的难点就是转换，把题目变成一个图论模型。

我们定义 $dp_{i,j}$ 为到达第 $i$ 个点，用时模 $k$ 余 $j$，需要用的最短时间

对于每个优先队列的结构体：

struct N {
    int v, i, d;
    bool operator <(N y) const {
        return d > y.d;
    }
};

其中 v 为节点，i 为用时模 $k$，d 为总用时。

也就是 $dp_{v, i} = d$。

但是，我们发现题目有一个限制：

游客只有不早于 $a_i$ 时刻才能通过这条道路。

我们可以等一会再出发，这样就行了，设目前时间是 $t$，那么延后 $\lfloor\frac{a_i – t}{k}\rfloor \times k$ 就行了。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector <int> e[100005];
int t[100005], dp[10005][105], vis[10005][105];
map <pair <int, int>, int> mp;
#define mkp make_pair

struct N {
    int v, i, d;
    bool operator <(N y) const {
        return d > y.d;
    }//重载运算符，使得优先队列是从小到大
};

int main() {
    cin >> n >> m >> k;

    for (int i = 1; i <= m; i ++) {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].push_back(y);
        t[i] = z;
        mp[make_pair(x, y)] = i;
    }

    priority_queue <N> q;
    memset(dp, 0x7f, sizeof(dp));
    q.push((N) {
        1, 0, 0
    });
    dp[1][0] = 0;

    while (q.size()) {
        int vv = q.top().v;
        int ii = q.top().i;
        q.pop();//弹出

        if (vis[vv][ii])
            continue;//走过的

        vis[vv][ii] = 1;
//      cout << vv << " " << ii << "\n";

        for (int i = 0; i < e[vv].size(); i ++) {//遍历下一个可以去的节点
            int ww = e[vv][i];
            int tt = t[mp[mkp(vv, ww)]];
            int j = (ii + 1) % k;
            int t = dp[vv][ii];
//          cout << vv << " " << ww << " " << ii << " " << j << " " << t << " " << tt << " " << dp[ww][ii] << "\n";

            if (t < tt) {
                t += (tt - t + k - 1) / k * k;
            }

            if (dp[ww][j] > t + 1)
                dp[ww][j] = t + 1, q.push((N) {
                ww, j, t + 1
            });//继续 bfs
        }
    }

    if (dp[n][0] != dp[n + 1][0]) cout << dp[n][0];
    else cout << "-1";
}