链接：https://contest.ucup.ac/contest/1356
A. Mixed Messages
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
vector<int> a(n, -1), b(n, -1);
vector<int> p(4, -1);
for (int i = 0; i < n; i++) {
if (s[i] == 's') {
p[0] = i;
}
if (s[i] == 'p') {
p[1] = i;
a[i] = p[0];
}
if (s[i] == 'b') {
p[2] = i;
a[i] = p[1];
}
if (s[i] == 'u') {
p[3] = i;
}
}
p.assign(4, -1);
for (int i = n - 1; i >= 0; i--) {
if (s[i] == 's') {
p[0] = i;
b[i] = p[3];
}
if (s[i] == 'p') {
p[1] = i;
}
if (s[i] == 'b') {
p[2] = i;
b[i] = p[0];
}
if (s[i] == 'u') {
p[3] = i;
}
}
int ans = 1E9;
for (int i = 0; i < n; i++) {
if (s[i] == 'b') {
int a2 = i;
int a1 = a[a2];
int a3 = b[a2];
if (a1 != -1 && a3 != -1) {
int a0 = a[a1];
int a4 = b[a3];
if (a0 != -1 && a4 != -1) {
ans = min(ans, abs(a0 - a2 + 2) + abs(a1 - a2 + 1) + abs(a3 - a2 - 1) + abs(a4 - a2 - 2));
}
}
}
}
cout << ans << '\n';
return 0;
}
B. I Flipped The Calendar...
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> ans(2038);
int d[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int cur = 2;
for (int i = 1970; i < 2038; i++) {
if (i % 400 == 0 || (i % 4 == 0 && i % 100 != 0)) {
d[1] = 29;
} else {
d[1] = 28;
}
for (int j = 0; j < 12; j++) {
ans[i]++;
for (int k = 0; k < d[j]; k++) {
cur++;
if (cur == 7) {
if (k != 0) {
ans[i]++;
}
cur = 0;
}
}
}
}
int y;
cin >> y;
cout << ans[y] << '\n';
return 0;
}
D. Bishops
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<int, int>> ans;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q[2];
vector<vector<pair<int, int>>> a(n + m - 1);
for (int i = -m + 1; i < n; i++) {
int l = max(-i, i);
int r = min(2 * n - 2 - i, 2 * m - 2 + i);
a[l].push_back({r, i});
}
for (int j = 0; j < n + m - 1; j++) {
int d = j % 2;
for (auto &x : a[j]) {
q[d].push(x);
}
while (!q[d].empty() && q[d].top().second < j) {
q[d].pop();
}
if (!q[d].empty()) {
auto [r, i] = q[d].top();
q[d].pop();
ans.push_back({(i + j) / 2, (j - i) / 2});
}
}
cout << ans.size() << '\n';
for (auto &[x, y] : ans) {
cout << x + 1 << ' ' << y + 1 << '\n';
}
return 0;
}
I. Password
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
if (n % 2 == 1) {
cout << 1 + (n / 2 / 3) * 2;
} else {
cout << 2 + ((n - 2) / 2 / 3) * 2;
}
cout << ' ' << n << '\n';
return 0;
}
J. Transport Pluses
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using Point = complex<double>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, t;
cin >> n >> t;
int x, y;
cin >> x >> y;
Point s(x, y);
cin >> x >> y;
Point e(x, y);
vector<Point> a(n);
for (int i = 0; i < n; i++) {
cin >> x >> y;
a[i] = Point(x, y);
}
vector<vector<int>> b;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
b.push_back({i, j});
}
}
b.push_back({});
double ans = 1E18;
for (int i = 0; i < (int) b.size(); i++) {
double res = 0;
if ((int) b[i].size() == 0) {
res += abs(s - e);
} else {
auto a0 = a[b[i][0]];
auto a1 = a[b[i][1]];
if (abs(real(s) - real(a0)) < abs(imag(s) - imag(a0))) {
res += abs(real(s) - real(a0));
} else {
res += abs(imag(s) - imag(a0));
}
res += t;
if (b[i][0] != b[i][1]) {
res += t;
}
if (abs(real(e) - real(a1)) < abs(imag(e) - imag(a1))) {
res += abs(real(e) - real(a1));
} else {
res += abs(imag(e) - imag(a1));
}
}
ans = min(ans, res);
}
cout << fixed << setprecision(9) << ans << '\n';
for (int i = 0; i < (int) b.size(); i++) {
double res = 0;
if ((int) b[i].size() == 0) {
res += abs(s - e);
} else {
auto a0 = a[b[i][0]];
auto a1 = a[b[i][1]];
if (abs(real(s) - real(a0)) < abs(imag(s) - imag(a0))) {
res += abs(real(s) - real(a0));
} else {
res += abs(imag(s) - imag(a0));
}
res += t;
if (b[i][0] != b[i][1]) {
res += t;
}
if (abs(real(e) - real(a1)) < abs(imag(e) - imag(a1))) {
res += abs(real(e) - real(a1));
} else {
res += abs(imag(e) - imag(a1));
}
}
if (abs(res - ans) <= 1E-9) {
if ((int) b[i].size() == 0) {
cout << "1\n0 " << real(e) << ' ' << imag(e) << '\n';
} else {
auto a0 = a[b[i][0]];
auto a1 = a[b[i][1]];
cout << 3 + (b[i][0] != b[i][1]) << '\n';
if (abs(real(s) - real(a0)) < abs(imag(s) - imag(a0))) {
cout << "0 " << real(a0) << ' ' << imag(s) << '\n';
} else {
cout << "0 " << real(s) << ' ' << imag(a0) << '\n';
}
if (b[i][0] != b[i][1]) {
cout << b[i][0] + 1 << ' ' << real(a0) << ' ' << imag(a1) << '\n';
}
if (abs(real(e) - real(a1)) < abs(imag(e) - imag(a1))) {
cout << b[i][1] + 1 << ' ' << real(a1) << ' ' << imag(e) << '\n';
} else {
cout << b[i][1] + 1 << ' ' << real(e) << ' ' << imag(a1) << '\n';
}
cout << "0 " << real(e) << ' ' << imag(e) << '\n';
}
break;
}
}
return 0;
}