链接：https://codeforces.com/gym/104120
A. Average Walk
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
cout << min(15, (3000 + n - 1) / n);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
B. Business Stamps
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
sx--;
sy--;
ex--;
ey--;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
a[i][j]--;
}
}
int ans = 20;
int all = (1 << 10);
int mx[] = {-1, +1, 0, 0};
int my[] = {0, 0, -1, +1};
auto check = [&](int now) {
if (!(now & (1 << a[sx][sy]))) {
return false;
}
if (!(now & (1 << a[ex][ey]))) {
return false;
}
vector<vector<bool>> vis(n, vector<bool>(m));
vis[sx][sy] = 1;
queue<array<int, 2>> q;
q.push({sx, sy});
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + mx[i];
int ny = y + my[i];
if (nx < 0 || nx >= n) {
continue;
}
if (ny < 0 || ny >= m) {
continue;
}
if (vis[nx][ny]) {
continue;
}
if (!(now & (1 << a[nx][ny]))) {
continue;
}
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
return (bool)vis[ex][ey];
};
for (int i = 1; i <= all; i++) {
if (check(i)) {
ans = min(ans, __builtin_popcountll(i));
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
C. Company Layoffs
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
i64 sum = 0;
vector<i64> pre(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
for (int i = 0; i < n; i++) {
pre[i + 1] = pre[i] + a[i];
}
for (int i = 0; i < m; i++) {
int x;
cin >> x;
auto id = lower_bound(a.begin(), a.end(), x) - a.begin();
cout << pre[id] + (n - id) * x << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
D. Denji
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<i64> a(n + 1);
vector<i64> tree;
int now = 1;
for (int i = 0; i < n; i++) {
int op;
cin >> op;
if (op == 1) {
i64 x;
cin >> x;
a[now++] = x;
auto it = upper_bound(tree.begin(), tree.end(), x);
tree.insert(it, x);
} else if (op == 2) {
i64 x;
cin >> x;
x = a[x];
auto it = lower_bound(tree.begin(), tree.end(), x);
tree.erase(it);
now++;
} else if (op == 3) {
i64 x, y;
cin >> x >> y;
auto it = lower_bound(tree.begin(), tree.end(), a[x]);
tree.erase(it);
a[x] += y;
it = upper_bound(tree.begin(), tree.end(), a[x]);
tree.insert(it, a[x]);
now++;
} else {
i64 x;
cin >> x;
x = a[x];
cout << lower_bound(tree.begin(), tree.end(), x) - tree.begin() << '\n';
now++;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
G. Gustavos Modern Art
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
i64 n, m;
cin >> n >> m;
string d = "1234";
auto get = [&](i64 x, i64 y) {
if (d == "1234") {
return (x - 1) * n + y;
} else if (d == "1324") {
return (y - 1) * n + x;
} else if (d == "2143") {
return (x - 1) * n + n - y + 1;
} else if (d == "2413") {
return (y - 1) * n + n - x + 1;
} else if (d == "3412") {
return (n - x) * n + y;
} else if (d == "3142") {
return (n - y) * n + x;
} else if (d == "4321") {
return (n - x) * n + n - y + 1;
} else {
return (n - y) * n + n - x + 1;
}
};
for (int i = 0; i < m; i++) {
char op;
cin >> op;
if (op == 'r') {
char x;
cin >> x;
if (x == 'a') {
swap(d[1], d[2]);
} else if (x == 'b') {
swap(d[0], d[1]);
swap(d[2], d[3]);
} else if (x == 'c') {
swap(d[0], d[3]);
} else {
swap(d[0], d[2]);
swap(d[1], d[3]);
}
} else {
int x, y;
cin >> x >> y;
cout << get(x, y) << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
K. Keypad Repetitions
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<char> mp(26);
for (int i = 0; i < 3; i++) {
mp[i] = '2';
}
for (int i = 3; i < 6; i++) {
mp[i] = '3';
}
for (int i = 6; i < 9; i++) {
mp[i] = '4';
}
for (int i = 9; i < 12; i++) {
mp[i] = '5';
}
for (int i = 12; i < 15; i++) {
mp[i] = '6';
}
for (int i = 15; i < 19; i++) {
mp[i] = '7';
}
for (int i = 19; i < 22; i++) {
mp[i] = '8';
}
for (int i = 22; i < 26; i++) {
mp[i] = '9';
}
map<string, int> st;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
string t;
for (auto x : s) {
t.push_back(mp[x - 'a']);
}
st[t]++;
}
for (int i = 0; i < m; i++) {
string s;
cin >> s;
cout << st[s] << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
L. Ladybug And The Bullet Train
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, x;
cin >> n >> x;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> dep(n + 1), cnt(n + 1);
function<void(int, int)> dfs = [&](int cur, int pre) {
cnt[cur]++;
for (auto nex : g[cur]) {
if (nex != pre) {
dep[nex] = dep[cur] + 1;
dfs(nex, cur);
cnt[cur] += cnt[nex];
}
}
};
int ans = 2 * (n - 1);
function<void(int, int)> get = [&](int cur, int pre) {
for (auto nex : g[cur]) {
if (nex == x) {
ans -= 2 * (cnt[cur] - cnt[nex] - 1);
ans -= dep[nex];
ans -= 2 * (cnt[nex] - 1);
return;
}
}
for (auto nex : g[cur]) {
if (nex != pre) {
get(nex, cur);
}
}
};
dfs(1, 0);
get(1, 0);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}