链接：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;
}
- Universal Stage The 2nd Cupuniversal stage the 2nd universal qingdao stage the universal shenyang stage the universal stage hefei the universal binjiang stage the universal okayama stage the universal taipei stage the universal stage 6555 good universal contest nanjing stage universal northern stage good