A. Mixed Messages
dp[i][j]
表示前i位,选择\(j\)个移动到一起的最小花费。
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1E9;
int32_t main() {
int n;
string s;
cin >> n >> s;
const string t = "spbsu";
array<int, 6> dp;
dp.fill(inf), dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 4; j >= 0; j--)
if (t[j] == s[i])
dp[j + 1] = min(dp[j + 1], dp[j] + (j < 2 ? -1 : j > 2 ? 1 : 0) * i);
}
cout << dp[5] - 6 << "\n";
return 0;
}
B. I Flipped The Calendar...
直接模拟这个过程
#include <bits/stdc++.h>
using namespace std;
set<int> s;
int m[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 1791 61
int32_t main() {
for (int i = 2000; i <= 2037; i += 4) s.insert(i);
for (int i = 2000; i >= 1970; i -= 4) s.insert(i);
int Y = 1970, Date = 3;
int y;
cin >> y;
for (int i = 1970; i < y; i++) {
Date = (Date + 365 + s.count(i)) % 7;
}
int res = 0;
for (int i = 1, M, ans; i <= 12; i++) {
M = m[i];
if (i == 2) M += s.count(y);
ans = 1, Date = (Date + 1) % 7;
for (int j = 2; j <= M; j++, Date = (Date + 1) % 7) {
if( Date == 6 ) cout << "\n";
if (Date == 0) ans++;
}
res += ans;
}
cout << res << "\n";
return 0;
}
I. Password
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int n;
cin >> n;
if (n & 1) {
int m = (n + 1) / 2;
cout << (m + 2) / 3 * 2 - 1;
} else {
int m = n / 2;
cout << (m + 2) / 3 * 2;
}
cout << " " << n << "\n";
return 0;
}
J. Transport Pluses
可以注意到的是,任意两个加号是一定相交的,所以最多只用经过两个加号,这样的话我们只需要枚举中间经过那些加号即可。
#include<bits/stdc++.h>
using namespace std;
//#define int long long
constexpr int inf = 1E9;
using vi = vector<int>;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, t;
cin >> n >> t;
int xh, yh;
cin >> xh >> yh;
int xe, ye;
cin >> xe >> ye;
vi x(n), y(n);
for (int i = 0; i < n; i++)
cin >> x[i] >> y[i];
double ans = sqrt((xh - xe) * (xh - xe) + (yh - ye) * (yh - ye));
vector<array<int, 3>> path;
path.push_back({0, xe, ye});
for (int i = 0, cost; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j) {
cost = min(abs(xh - x[i]), abs(yh - y[i])) + t + min(abs(xe - x[i]), abs(ye - y[i]));
if (cost >= ans) continue;
ans = cost, path.clear();
if (abs(xh - x[i]) < abs(yh - y[i]))
path.push_back({0, x[i], yh});
else
path.push_back({0, xh, y[i]});
if (abs(xe - x[i]) < abs(ye - y[i]))
path.push_back({i + 1, x[i], ye});
else
path.push_back({i + 1, xe, y[i]});
path.push_back({0, xe, ye});
} else {
cost = min(abs(xh - x[i]), abs(yh - y[i])) + t + t + min(abs(xe - x[j]), abs(ye - y[j]));
if (cost >= ans) continue;
ans = cost, path.clear();
if (abs(xh - x[i]) < abs(yh - y[i]))
path.push_back({0, x[i], yh});
else
path.push_back({0, xh, y[i]});
path.push_back({i + 1, x[i], y[j]});
if (abs(xe - x[j]) < abs(ye - y[j]))
path.push_back({j + 1, x[j], ye});
else
path.push_back({j + 1, xe, y[j]});
path.push_back({0, xe, ye});
}
}
cout << fixed << setprecision(10) << ans << "\n" << path.size() << "\n";
for (auto [a, b, c]: path)
cout << a << " " << b << " " << c << "\n";
return 0;
}
- Universal Stage The 2nd Cupuniversal stage the 2nd universal qingdao stage the universal stage hefei the universal shenyang stage the universal binjiang stage the universal okayama stage the universal taipei stage the universal stage 6555 good universal contest nanjing stage universal shaanxi stage 6735