E. Matrix Distances
因为行列的贡献是独立的,所以可以按照颜色分别统计
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
unordered_map<int, vi> cnt;
for (int i = 1, c; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
cnt[c].push_back(i);
cnt[-c].push_back(j);
}
}
int res = 0;
for (auto &[k, v]: cnt) {
sort(v.begin(), v.end());
for (int sum = 0, cnt = 0; auto i: v)
res += cnt * i - sum, cnt++, sum += i;
}
cout << res * 2 << "\n";
return 0;
}s
F. Colorful Balloons
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
map<string, int> cnt;
string s;
for (int i = 1; i <= n; i++) cin >> s, cnt[s]++;
for (auto [k, v]: cnt) {
if (v * 2 > n) {
cout << k << "\n";
return 0;
}
}
cout << "uh-oh\n";
return 0;
}
G. Streak Manipulation
可以二分答案,check 可以 dp
二分的第\(k\) 长的段长度是\(x\),则至少有\(k\)个段长度大于等\(x\)
dp 状态为\(f[i][j][0/1]\)表示前\(i\)位,\(j\)个大于等于\(x\)段且第\(i\)是\(0/1\)的最小操作次数
因为只能把 0 变为 1,如果要改变最后一段的最优解最后一段的长度就是刚好\(x\),注意的是最后一段前一个位置必须是 0,否则无法转移,转移的代价就是最后一段内0的个数。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
using vi = vector<int>;
using i32 = int32_t;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
string s;
cin >> s;
s = ' ' + s;
vi pre(n + 1);
for (int i = 1; i <= n; ++i)pre[i] = pre[i - 1] + (int) (s[i] == '0');
auto check = [&](int x) {
vector f(n + 1, vector(k + 1, vi(2, inf)));
f[0][0][0] = f[0][0][1] = 0;
int res = inf;
for (int i = 1; i <= n; ++i) {
if (s[i] == '0') f[i][0][0] = 0, f[i][0][1] = 1;
else f[i][0][1] = 0;
for (int j = 1; j <= k; ++j) {
f[i][j][0] = min(f[i - 1][j][0], f[i - 1][j][1]);
if (i - x >= 0 and j - 1 >= 0)
if (s[i - x] != '1') f[i][j][1] = f[i - x][j - 1][0] + (pre[i] - pre[i - x]);
}
res = min({res, f[i][k][0], f[i][k][1]});
}
return res <= m;
};
int l = 1, r = n, res = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
cout << res << "\n";
return 0;
}
下面的思路基本相同,但是可以省掉最后一维度。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m, k;
string s;
cin >> n >> m >> k >> s;
s = " " + s;
vi sum(n + 1);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == '0');
auto check = [=](int x) {
vector f(n + 1, vi(k + 1, inf));
f[0][0] = 0;
for (int i = 1, val; i <= n; i++) {
f[i] = f[i - 1];
if (i >= x and s[i - x] != '1') {
val = sum[i] - sum[i - x];
for (int j = 1; j <= k; j++)
f[i][j] = min(f[i][j], f[max(0ll, i - x - 1)][j - 1] + val);
}
}
return f[n][k] <= m;
};
int l = 1, r = n, res = -1;
for (int mid; l <= r;) {
mid = (l + r) / 2;
if (check(mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
cout << res << "\n";
return 0;
}
J. Takeout Delivering
首先我们可以用 dij 求出从1到每个点路径上的最大边,和从n 到每个点路径上的最大边。然后枚举每一条边\((u,v,w)\)做最大边,则第二长的边一定出现在\((1,u)\)和\((v,n)\)之间
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 2e9+5;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<int, 3>> edge(m);
vector<vector<pii>> e(n + 1);
for (auto &[u, v, w]: edge) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
auto dij = [e, n](int x) {
priority_queue<pii, vector<pii>, greater<pii>> q;
vi dis(n + 1, inf);
vector<bool> vis(n + 1);
dis[x] = 0, q.emplace(0, x);
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] or max(d, w) >= dis[v]) continue;
dis[v] = max(d, w), q.emplace(dis[v], v);
}
}
return dis;
};
auto d1 = dij(1), dn = dij(n);
int res = inf;
for (auto [u, v, w]: edge) {
if (max(d1[u], dn[v]) <= w)
res = min(res, w + max(d1[u], dn[v]));
if (max(dn[u], d1[v]) <= w)
res = min(res, w + max(dn[u], d1[v]));
}
cout << res << "\n";
return 0;
}
E. Matrix Distances
因为行列的贡献是独立的,所以可以按照颜色分别统计
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
unordered_map<int, vi> cnt;
for (int i = 1, c; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
cnt[c].push_back(i);
cnt[-c].push_back(j);
}
}
int res = 0;
for (auto &[k, v]: cnt) {
sort(v.begin(), v.end());
for (int sum = 0, cnt = 0; auto i: v)
res += cnt * i - sum, cnt++, sum += i;
}
cout << res * 2 << "\n";
return 0;
}s
F. Colorful Balloons
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
map<string, int> cnt;
string s;
for (int i = 1; i <= n; i++) cin >> s, cnt[s]++;
for (auto [k, v]: cnt) {
if (v * 2 > n) {
cout << k << "\n";
return 0;
}
}
cout << "uh-oh\n";
return 0;
}
G. Streak Manipulation
可以二分答案,check 可以 dp
二分的第\(k\) 长的段长度是\(x\),则至少有\(k\)个段长度大于等\(x\)
dp 状态为\(f[i][j][0/1]\)表示前\(i\)位,\(j\)个大于等于\(x\)段且第\(i\)是\(0/1\)的最小操作次数
因为只能把 0 变为 1,如果要改变最后一段的最优解最后一段的长度就是刚好\(x\),注意的是最后一段前一个位置必须是 0,否则无法转移,转移的代价就是最后一段内0的个数。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
using vi = vector<int>;
using i32 = int32_t;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
string s;
cin >> s;
s = ' ' + s;
vi pre(n + 1);
for (int i = 1; i <= n; ++i)pre[i] = pre[i - 1] + (int) (s[i] == '0');
auto check = [&](int x) {
vector f(n + 1, vector(k + 1, vi(2, inf)));
f[0][0][0] = f[0][0][1] = 0;
int res = inf;
for (int i = 1; i <= n; ++i) {
if (s[i] == '0') f[i][0][0] = 0, f[i][0][1] = 1;
else f[i][0][1] = 0;
for (int j = 1; j <= k; ++j) {
f[i][j][0] = min(f[i - 1][j][0], f[i - 1][j][1]);
if (i - x >= 0 and j - 1 >= 0)
if (s[i - x] != '1') f[i][j][1] = f[i - x][j - 1][0] + (pre[i] - pre[i - x]);
}
res = min({res, f[i][k][0], f[i][k][1]});
}
return res <= m;
};
int l = 1, r = n, res = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
cout << res << "\n";
return 0;
}
下面的思路基本相同,但是可以省掉最后一维度。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m, k;
string s;
cin >> n >> m >> k >> s;
s = " " + s;
vi sum(n + 1);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == '0');
auto check = [=](int x) {
vector f(n + 1, vi(k + 1, inf));
f[0][0] = 0;
for (int i = 1, val; i <= n; i++) {
f[i] = f[i - 1];
if (i >= x and s[i - x] != '1') {
val = sum[i] - sum[i - x];
for (int j = 1; j <= k; j++)
f[i][j] = min(f[i][j], f[max(0ll, i - x - 1)][j - 1] + val);
}
}
return f[n][k] <= m;
};
int l = 1, r = n, res = -1;
for (int mid; l <= r;) {
mid = (l + r) / 2;
if (check(mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
cout << res << "\n";
return 0;
}
J. Takeout Delivering
首先我们可以用 dij 求出从1到每个点路径上的最大边,和从n 到每个点路径上的最大边。然后枚举每一条边\((u,v,w)\)做最大边,则第二长的边一定出现在\((1,u)\)和\((v,n)\)之间
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 2e9+5;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<int, 3>> edge(m);
vector<vector<pii>> e(n + 1);
for (auto &[u, v, w]: edge) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
auto dij = [e, n](int x) {
priority_queue<pii, vector<pii>, greater<pii>> q;
vi dis(n + 1, inf);
vector<bool> vis(n + 1);
dis[x] = 0, q.emplace(0, x);
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] or max(d, w) >= dis[v]) continue;
dis[v] = max(d, w), q.emplace(dis[v], v);
}
}
return dis;
};
auto d1 = dij(1), dn = dij(n);
int res = inf;
for (auto [u, v, w]: edge) {
if (max(d1[u], dn[v]) <= w)
res = min(res, w + max(d1[u], dn[v]));
if (max(dn[u], d1[v]) <= w)
res = min(res, w + max(dn[u], d1[v]));
}
cout << res << "\n";
return 0;
}
- Universal Stage Hefei The 2nduniversal stage hefei the universal stage the 2nd universal qingdao stage 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