A 小苹果 apple

简单题。

先做询问 2 好像简单，我考场就是这么干的。

询问 2 就是问你删几次才能使剩下的数个数 $\bmod 3=1$。

你会发现每次是删掉 $\left\lceil\dfrac{1}{3} n\right\rceil$ 个数，$n$ 每次改变。

然后发现这个复杂度正确，直接莽。

询问 1 同理，看删几轮删完即可。

代码注释夹带了点考场私货。

/*
这段就当考场游记吧
8点20把对拍程序和自定义编译命令都调好了，写了个A+B对拍，wa on test 209
快读，不打了，听天由命

十点半，大样例全过。
T4 这么水？我应该没写错吧。欸T1很简单吗，T4一眼秒了T1我一眼不会啊/jk
10:45检查完毕开始睡觉
11:00发现咖啡效果来了睡不着，那就摆
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll m;
ll ans1, ans2 = 1;
int main()
{
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);
    cin >> n;
    m = n;
    while (m % 3 != 1)
    {
        ans2++;
        m -= (m + 2) / 3;
    }
    while (n)
    {
        ans1++;
        n -= (n + 2) / 3;
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}

B 公路 road

简单题。

考虑贪心。因为油箱无限大，所以你可以有一个虚拟的类似返回加油的过程。

什么意思呢，就是你现在加油比之前贵就不加了，改成之前的价格加。

所以就很简单了。

这个前缀和可能不用，我是怕出现加油有一些剩的可以多跑一点的情况。但也没啥事。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, d;
ll dis[100020];
ll a[100020];
ll val;
int main()
{
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);
    cin >> n >> d;
    for (int i = 2; i <= n; i++)
        cin >> dis[i], dis[i] += dis[i - 1];
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i > 1)
            a[i] = min(a[i], a[i - 1]);
    }
    for (int i = 1; i <= n; i++)
        dis[i] = (dis[i] + d - 1) / d;
    // for (int i = 2; i <= n; i++)
    //     cout << dis[i] << " ";
    // cout << endl;
    for (int i = 2; i <= n; i++)
        val += a[i - 1] * (dis[i] - dis[i - 1]);
    cout << val << endl;
    return 0;
}

C 一元二次方程 uqe

模拟题。

难点在于分数和平方根的化简。

做这类模拟题可以分步写，写完一类直接测相对应的数据，效果是很好的。

我为了防止 long long 使用平方根有奇怪错误还手写了一个，但复杂度是正确的。

这题不会有人超时吧？

先记一个 $dlt=b^2-4ac$，直接判断是否 $\lt 0$。

然后 $sq=\left\lfloor\sqrt dlt\right\rfloor$。如果 $sq^2=dlt$ 即 $dlt$ 为完全平方数那么就存在有理数解。有理数解还要根据 $2a$ 的正负性分讨一下。

如果不是完全平方数即存在两个无理数解，先写成 $\frac{p_1}{q_1}+\frac{p_2}{q_2}\sqrt dlt$ 的形式，然后化简。

平方根化简直接找有没有完全平方因子，有的话提给 $p_2$ 即可。

码量不算太大。但这题是考场上耗时最久的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m;
ll a, b, c;
ll dlt;
ll sq;
ll p, q;
ll p1, q1, p2, q2;
void F(ll &p, ll &q)
{
    ll g = __gcd(p, q);
    p /= g;
    q /= g;
}
void fprt(ll &p, ll &q)
{
    // cout << p << " " << q << endl;
    if (p * q < 0)
        printf("-");
    if (p < 0)
        p = -p;
    if (q < 0)
        q = -q;
    F(p, q);
}
void solve()
{
    sq = 0;
    cin >> a >> b >> c;
    dlt = b * b - 4 * a * c;
    if (dlt < 0)
        return printf("NO\n"), void();
    while ((sq + 1) * (sq + 1) <= dlt)
        sq++;
    if (sq * sq == dlt)
    {
        p = -b + sq;
        q = 2 * a;
        if (2 * a < 0)
            p = min(-b + sq, -b - sq);
        else
            p = max(-b + sq, -b - sq);
        fprt(p, q);
        if (q == 1)
            printf("%lld", p);
        else
            printf("%lld/%lld", p, q);
        printf("\n");
        return;
    }
    p1 = -b;
    q1 = 2 * a;
    p2 = 1;
    // cout << "Debug:" << sq << "/" << dlt << endl;
    for (ll d = 2; d <= sq; d++)
    {
        // cout << dlt << " " << d * d << " " << (dlt % (d * d) == 0) << endl;
        while (dlt % (d * d) == 0)
        {
            dlt /= d * d;
            p2 *= d;
        }
    }

    q2 = 2 * a;
    fprt(p1, q1);
    // cout << "debug:" << p1 << "/" << q1 << endl;
    if (q1 == 1)
    {
        if (p1 != 0)
        {
            printf("%lld", p1);
            printf("+");
        }
    }
    else
    {
        printf("%lld/%lld", p1, q1);
        printf("+");
    }
    if (p2 < 0)
        p2 = -p2;
    if (q2 < 0)
        q2 = -q2;
    F(p2, q2);
    if (p2 != 1)
        printf("%lld*", p2);
    printf("sqrt(%lld)", dlt);
    if (q2 != 1)
        printf("/%lld", q2);
    // printf("YES\n");
    printf("\n");
}
int main()
{
    freopen("uqe.in", "r", stdin);
    freopen("uqe.out", "w", stdout);
    int t;
    cin >> t >> m;
    while (t--)
        solve();
    return 0;
}

D 旅游巴士 bus

T1 和 T2 一眼不会 T4 看完题秒了还有救吗？

首先，这是可以二分答案的，这个看完题就能想出来。

为什么可以二分？二分什么？如何二分？

为什么可以二分？因为开始时间任意，如果你在 $t$ 时刻能过，你拖到 $t+k$ 更能过。因为限制随着时间推移只能更少。

二分什么？我们会发现从 1 号点开始二分开始时间得到的到达时间不一定是单调上升的。那么我们二分结束时间，建反图即可，这样子就只需要判断答案可行性。

如何二分？设结束时间为 $pk$，二分 $p$ 即可。

如何 check 也是个困难点。

你会发现因为边权是 $1$，所以直接大力 bfs 即可。这时候你就通过了小样例，大样例直接炸掉。

所以我不算一看完题就想出正解。

炸掉怎么办？你考虑进行拆点。这个 $k$ 很小肯定不是出题人少写了几个 $0$，你把每个点 $x$ 拆成 $(x,y)$，表示在 $t\equiv y\pmod{k}$ 时刻你到达了 $x$ 点。

拆点之后大力 bfs 即可通过。

因为每次 bfs 新的时间只会更短，所以走过的点不需要重复经过，复杂度有保障。

时间复杂度 $\mathcal O(nk\log V)$，其中 $V=\max{a_i}+m\leq 10^7$。大样例场上跑了 0.8s。

注意无解输出 $-1$，我是不会说有个小丑玩了一个多小时闲的没事干的时候，题面放的很大，一个字一个字研究题面才发现的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
int n, m;
ll k;
vector<pli> a[100020];
bool vis[100020][120];
bool check(ll et)
{
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < k; j++)
            vis[i][j] = 0;
    queue<pli> q;
    q.push({et, n});
    vis[n][et % k] = 1;
    while (!q.empty())
    {
        int u = q.front().second;
        ll t = q.front().first;
        q.pop();
        if (vis[1][0])
            return 1;
        for (pli p : a[u])
        {
            int v = p.second;
            ll w = p.first;
            if (t > w && !vis[v][(t - 1) % k])
            {
                vis[v][(t - 1) % k] = 1;
                q.push({t - 1, v});
            }
        }
    }
    return 0;
}
int main()
{
    freopen("bus.in", "r", stdin);
    freopen("bus.out", "w", stdout);
    scanf("%d%d%lld", &n, &m, &k);
    while (m--)
    {
        int u, v;
        ll w;
        scanf("%d%d%lld", &u, &v, &w);
        a[v].push_back({w, u});
    }
    //bs end time
    ll L = 0, R = 1e7, mid, ans = -1;
    while (L <= R)
    {
        mid = L + R >> 1;
        if (check(mid * k))
            R = (ans = mid) - 1;
        else
            L = mid + 1;
    }
    if (ans == -1)
        printf("-1\n");
    else
        printf("%lld\n", ans * k);
    // cerr << fixed << setprecision(5) << (double)clock() / CLOCKS_PER_SEC << endl;
    return 0;
}
最后修改：2023 年 11 月 07 日
© 允许规范转载
v我50吃疯狂星期四