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)$$。 找到其中两个点的最大曼哈顿距离。
思路:两点之间的位置关系可以有以下两种模式。
考虑两个最远点之间的位置关系...
- \[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;
}