20级训练赛Round #5

A - 凯少与素数

签到 & 思维题,

要使每一对数字 \((i,j)\) 的最大公约数都等于 1,简单来说区间相邻的两个数一定 \(gcd(i,j) = 1\)

并且 \((r - l)\) 为奇数保证区间每一个数都能用于构成整数对

【AC Code】

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, mod = 1e9 + 7;
void solve() {
    ll a, b; cin >> a >> b;
    cout << "YES\n";
    while (a < b) cout << a++ << " " << a++ << "\n";
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

B - 尚佬与糖果售卖会

模拟,

简单概括一下题意:\(n\) 种糖果围成一圈,每种糖果每个 \(a_i\) 元。初始时你有 \(T\) 元,接着你从 \(1\) 开始绕圈。一旦你发现有糖果能买,你就买一个。直到一个糖果都买不起。问最后买了多少个糖果。


首先对数据进行处理:\(n\) 种糖果全部买一次需要多少钱,找到 \(n\) 种糖果中最便宜的价格

然后计算所有的糖果均能买的圈数有多少。

将剩余的钱进行进行按圈数模拟:一圈一圈的模拟肯定是不行的,稳稳地超时,所以需要进行优化

将剩余的钱数与当前所在位置的糖果价格进行比较,更新钱数,并记录每一圈结束后的次大值,当次大值等于最小值的时候,证明已经不能买除了最便宜的糖果外的其他糖果,此时结束循环。将剩余的钱数除以最小值(向下取整)可得到最终剩余的钱能买糖果数

【AC Code】

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, mod = 1e9 + 7;
void solve() {
    ll n, t, ans = 0;
    cin >> n >> t;
    vector<ll>a(n);
    for (ll &x : a)cin >> x;
    while (t) {
        ll s = 0;
        ll c = 0;
        for (int i = 0; i < a.size(); ++i) {
            if (s + a[i] <= t)
                s += a[i], c++;
        }
        if (s == 0)break;
        ans += (t / s) * c;
        t %= s;
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

C - 凯少与图

考察点:图论基本知识

题意: 给定顶点数和边数,找出被孤立点的最小数量和最大数量。(孤立即是没有和其他顶点相连。)

最大孤立点:运用完全图 \(m=n*(n-1)/2\) 得到公式 \(maxi = n-(1+sqrt(1+8*m))/2\)

最小孤立点:\(mini = n-2*m\); (注意:当mini < 0时,需要让 \(mini=0\))

【AC Code】

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, mod = 1e9 + 7;
void solve() {
    ll n, m;
    cin >> n >> m;
    ll maxi = 0, mini = 0;
    maxi = n - (1 + sqrt(1 + 8 * m)) / 2;
    mini = n - 2 * m;
    if (mini < 0) mini = 0;
    if (m == 0) {
        maxi = n;
        mini = n;
    }
    cout << mini << " " << maxi << endl;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

另外,本题还有一种数学解法,有兴趣的可以自己寻找

D - 数字再分配

基础DP + 规律题

将问题变为用>=3的整数组成S有多少种方案.

令 \(d[i]\) 表示组成i的方案数,边界为 \(d[0]=1\)
转移方程 \(d[i]=sum(d[j])\) ,其中 \(0<=j<=i-3\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, mod = 1e9 + 7;
int d[N];
void solve() {
    int n; cin >> n;
    d[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i - 3; ++j)
            d[i] = (d[i] + d[j]) % mod;
    cout << d[n];
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

如果有尝试手写前面几种情况或者打表了的话很容易发现一个规律

\[a_i = a_{i - 1} + a_{i - 3}\\a_0 = 1,a_1 = a_2 = 0 \]

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int s, a[2010] = {0};
    cin >> s;
    a[0] = 1, a[1] = a[2] = 0;
    for (int i = 3; i <= s; ++i)
        a[i] = (a[i - 1] + a[i - 3]) % mod;
    cout << a[s];
    return 0;
}

E - 曼哈顿距离

数学公式推导

题意:二维平面上有N个点 $$(x_i,y_i)$$。 找到其中两个点的最大曼哈顿距离。

思路:两点之间的位置关系可以有以下两种模式。

20级训练赛Round #5

考虑两个最远点之间的位置关系...

  • \[x_i + y_i$$ 的最大值 $$M_1$$ 和最小值 $$m_1$$ 之间的差异,当两个最远的点是右侧图形时; \]

因此,从直觉上讲,最 $$max(M_1-m_1,M_2-m_2)$$ 似乎是答案。 让我们在公式转换的基础上进一步说明这一点。

公式变形:

关于绝对值问题前提:$$|x| = max(x,-x)$$

通常情况下,前景会更好。 对于每对(i,j),即使xi <xj,它也不会失去通用性(反之亦然,交换)。

\[|x_i - x_j| + |y_i - y_j| \\ =(x_j - x_i +max(y_j-y_i,y_i-y_j))\\ =max((x_j + y_j) - (x_i + y_i),(x_j - y_j)-(x_i,y_i)) \]

由上面的变形

  • 求各个 $$(i,j)$$ 的 $$(x_j + y_j) - (x_i + y_i)$$ 的最大值
  • 求各个 $$(i,j)$$ 的 $$(x_j - y_j) - (x_i - y_i)$$ 的最大值

所以再回到上面:$$max(M_1-m_1,M_2-m_2)$$ 正是答案

  • \[\mathcal{O}(N)$$,但由于用了 `sort` 时间复杂度为 $$\mathcal{O}(NlogN) \]

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    vector<int> a, b;
    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        a.emplace_back(x + y); // emplace_back 等价于 push_back,但某些情况效率更好
        b.emplace_back(x - y);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    cout << max(a[n - 1] - a[0], b[n - 1] - b[0]);
    return 0;
}

F - RioTian与星际航线

考察点:BFS

题意概括:有 $$n$$ 个城市和 $$m$$ 条双向道路

假设在 $$t$$ 时刻经过了第 $$i$$ 条道路,则通过的时间为 $$C_i + ⌊\frac{D_i}{t+1}⌋$$

现在请问最短的时间是多少,可以从城市 $$1$$ 到达城市 $$n$$ ,如果到达不了则输出 $$-1$$


利用优先队列跑 BFS,同时用 tuple 元组存储数据 (记得开启 C++17 来保证 tuple 可通过编译)

#define inf 9223372036854775807LL
#define N  100005
using ll = long long;
using Edge = tuple<int, int, int>;
using pli = pair<ll, int>;
vector<Edge> e[N];
ll dist[N];
void solve() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (--a == --b)continue;
        e[a].emplace_back(b, c, d);
        e[b].emplace_back(a, c, d);
    }
    dist[0] = 0LL;
    for (int i = 1; i < n; i++) dist[i] = inf;
    priority_queue<pli, vector<pli>, greater<pli>>q;
    q.emplace(0, 0);
    while (!q.empty()) {
        auto [t, u] = q.top();
        q.pop();
        if (dist[u] != t)continue;
        for (auto [v, c, d] : e[u]) {
            ll t2 = sqrt((long double) d) - 0.5;
            if (t2 < t) t2 = t;
            t2 += ll(c) + ll(d) / (t2 + 1ll);
            if (t2 < dist[v])
                q.emplace(dist[v] = t2, v);

        }
    }
    cout << (dist[n - 1] == inf ? -1 : dist[n - 1]) << endl;
}
上一篇:python 浮点数四舍六入五成双


下一篇:Codeforces Round #723