A. Rudolf and the Ticket
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9;
const int N = 1e4;
vi vis(N);
vector<vector<pii>> e(N);
vector<pii> path;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vi a(n), b(m);
for (auto &i: a) cin >> i;
for (auto &i: b) cin >> i;
int res = 0;
for (auto &i: a)
for (auto &j: b)
if (i + j <= k) res++;
cout << res << "\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int TC = 1;
for (cin >> TC; TC; TC--)
solve();
return 0;
}
B. Rudolf and 121
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9;
const int N = 1e4;
vi vis(N);
vector<vector<pii>> e(N);
vector<pii> path;
void solve() {
int n;
cin >> n;
vi a(n);
for (auto &i: a) cin >> i;
int f = 1;
for (int i = 0; f and i + 2 < n; i++) {
if (a[i] < 0) f = 0;
else if (a[i] == 0) continue;
a[i + 1] -= a[i] * 2, a[i + 2] -= a[i], a[i] = 0;
}
if (a[n - 2] != 0 or a[n - 1] != 0) f = 0;
if (f) cout << "YES\n";
else cout << "NO\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int TC = 1;
for (cin >> TC; TC; TC--)
solve();
return 0;
}
C. Rudolf and the Ugly String
TC = int(input())
for _ in range(TC):
n = int(input())
s = input()
a = s.count("map")
b = s.count("pie")
c = s.count("mapie")
print(a + b - c)
D. Rudolf and the Ball Game
只要保证当前没有重复的状态,则总状态数不超过\(2\cdot10^5\)
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9;
const int N = 1e4;
vi vis(N);
vector<vector<pii>> e(N);
vector<pii> path;
void solve() {
int n, m, x;
cin >> n >> m >> x;
set<int> f;
f.insert(x - 1);
string op;
for (int r; m; m--) {
cin >> r >> op;
set<int> g;
if (op == "0") {
for (auto i: f)
g.insert((i + r) % n);
} else if (op == "1") {
for (auto i: f)
g.insert((i - r + n) % n);
} else {
for (auto i: f)
g.insert((i - r + n) % n), g.insert((i + r) % n);
}
f.swap(g);
}
cout << f.size() << "\n";
for (auto &i: f)
cout << i + 1 << " ";
cout << "\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int TC = 1;
for (cin >> TC; TC; TC--)
solve();
return 0;
}
E. Rudolf and k Bridges
如果可以每一行都 dp 出答案,然后双指针扫描出最优解即可。
对于单行的 dp,首先\(f[i]\)表示把桥修到\(i\)的最小花费,转移看似是\(O(d)\)但实际上只要区间最小值,所以可以用set
维护前\(d\)个状态即可。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = LLONG_MAX;
const int N = 1e4;
vi vis(N);
vector<vector<pii>> e(N);
vector<pii> path;
void solve() {
int n, m, k, d;
cin >> n >> m >> k >> d, d++;
vi g(n), a(m), f(m);
for (auto &val: g) {
for (auto &i: a) cin >> i;
multiset<int> cnt;
cnt.insert(1), f[0] = 1;
for (int i = 1; i < m; i++) {
f[i] = *cnt.begin() + a[i] + 1;
cnt.insert(f[i]);
if (cnt.size() > d) cnt.erase(cnt.find(f[i - d]));
}
val = f.back();
}
int res = inf, cnt = 0;
for (int i = 0; i < k - 1; i++)
cnt += g[i];
for (int l = 0, r = k - 1; r < n; l++, r++)
cnt += g[r], res = min(res, cnt), cnt -= g[l];
cout << res << "\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int TC = 1;
for (cin >> TC; TC; TC--)
solve();
return 0;
}
F. Rudolf and Imbalance
首先我们要使得最大值减小,这必要在最大值的所在的区间内内插入一个值。
如果最大区间是\([l,r]\),插入的值是\(x\),次大值是\(ans2\),则答案就是\(\max(x – l , r – x , ans2)\)
所以,如果可以枚举\(d_i\)则对于\(f_j\)答案就是一个单谷函数,我们找到离\([l-x,r-x]\)最近的点就是当前的最优解。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = LLONG_MAX;
const int N = 1e4;
vi vis(N);
vector<vector<pii>> e(N);
vector<pii> path;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vi a(n), d(m), f(k);
for (auto &i: a) cin >> i;
for (auto &i: d) cin >> i;
for (auto &i: f) cin >> i;
int ans = -1, L, R, ans2 = -1;
for (int i = 1, x; i < n; i++) {
x = a[i] - a[i - 1];
if (x > ans) ans2 = ans, ans = x, L = a[i - 1], R = a[i];
else ans2 = max(ans2, x);
}
if (ans == ans2) {
cout << ans << "\n";
return;
}
sort(f.begin(), f.end());
int res = ans;
int mid;
for (auto &di: d) {
if (di + f.front() >= R) continue;
if (di + f.back() <= L) continue;
mid = (L + R) / 2 - di;
mid = lower_bound(f.begin(), f.end(), mid) - f.begin();
for (int i = max(0ll, mid - 5); i <= min(k - 1, mid + 5); i++)
res = min(res, max({ans2, abs(f[i] + di - L), abs(f[i] + di - R)}));
}
cout << res << "\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int TC = 1;
for (cin >> TC; TC; TC--)
solve();
return 0;
}
G. Rudolf and Subway
把地铁线路抽象为若干个虚点,然后结点到地铁的权值为 1,地铁到节点的权值为 0,相当于上地铁花费 1,下地铁没有花费。然后求一下最短路即可。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = LLONG_MAX;
const int N = 1e4;
vi vis(N);
vector<vector<pii>> e(N);
vector<pii> path;
void solve() {
int n, m;
cin >> n >> m;
vector<array<int, 3>> edge(m);
vi line;
for (auto &[x, y, z]: edge) cin >> x >> y >> z, line.push_back(z);
sort(line.begin(), line.end());
line.resize(unique(line.begin(), line.end()) - line.begin());
vector<set<pii>> e(n + line.size() + 1);
for (auto &[x, y, z]: edge) {
z = lower_bound(line.begin(), line.end(), z) - line.begin() + n + 1;
e[x].emplace(z, 1);
e[y].emplace(z, 1);
e[z].emplace(x, 0);
e[z].emplace(y, 0);
}
int sta, ed;
cin >> sta >> ed;
vi dis(n + line.size() + 1, inf);
dis[sta] = 0;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.emplace(0, sta);
vi vis(n + line.size() + 1);
while (not q.empty()) {
auto [d, u] = q.top();
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w]: e[u]) {
if (vis[v]) continue;
if (dis[v] > d + w) {
dis[v] = d + w;
q.emplace(dis[v], v);
}
}
}
cout << dis[ed] << "\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int TC = 1;
for (cin >> TC; TC; TC--)
solve();
return 0;
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。