链接：https://codeforces.com/gym/104369
A. Programming Contest
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int y1, y2;
cin >> y1;
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cin >> y2;
int ans = y2 - y1 + 1;
for (int i = 0; i < n; i++) {
if (a[i] >= y1 && a[i] <= y2) {
ans--;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. Trading
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
sort(a.begin(), a.end());
i64 ans = 0;
for (int l = 0, r = n - 1; l < r; ) {
auto &[x1, y1] = a[l];
auto &[x2, y2] = a[r];
int c = min(y1, y2);
ans += 1LL * (x2 - x1) * c;
y1 -= c;
y2 -= c;
if (y1 == 0) {
l++;
}
if (y2 == 0) {
r--;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D. New Houses
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
}
vector<int> v(n);
for (int i = 0; i < n; i++) {
v[i] = a[i] - b[i];
}
i64 sum = 0;
i64 ans = 0;
sort(v.begin(), v.end(), greater());
for (int i = 0; i < n; i++) {
sum += b[i];
}
if (m >= 2 * n - 1) {
ans = max(ans, sum);
}
sum += v[0];
for (int i = 1; i < n; i++) {
sum += v[i];
if (m >= 2 * n - (i + 1)) {
ans = max(ans, sum);
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
F. Traveling in Cells
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
template <typename T>
struct Fenwick {
int n;
vector<T> a;
Fenwick(const int &n = 0) : n(n), a(n, T()) {}
void modify(int i, T x) {
for (i += 1; i <= n; i += i & -i) {
a[i - 1] += x;
}
}
T get(int i) {
T res = T();
for (; i > 0; i -= i & -i) {
res += a[i - 1];
}
return res;
}
T sum(int l, int r) { // [l, r)
return get(r) - get(l);
}
int kth(T k) {
int x = 0;
for (int i = 1 << __lg(n); i; i >>= 1) {
if (x + i <= n && k >= a[x + i - 1]) {
x += i;
k -= a[x - 1];
}
}
return x;
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<int> c(n), v(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
c[i]--;
}
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<vector<int>> pos(n);
for (int i = 0; i < n; i++) {
pos[c[i]].push_back(i);
}
vector<pair<int, vector<int>>> que(q);
for (int i = 0; i < q; i++) {
vector<int> qi;
int o;
cin >> o;
if (o == 1) {
int p, x;
cin >> p >> x;
p--, x--;
pos[x].push_back(p);
qi.push_back(p);
qi.push_back(x);
} else if (o == 2) {
int p, x;
cin >> p >> x;
p--;
qi.push_back(p);
qi.push_back(x);
} else {
int x, k;
cin >> x >> k;
x--;
qi.push_back(x);
for (int j = 0; j < k; j++) {
int x;
cin >> x;
x--;
qi.push_back(x);
}
}
que[i] = {o, qi};
}
vector<Fenwick<int>> col(n);
vector<Fenwick<i64>> val(n);
for (int i = 0; i < n; i++) {
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
int N = pos[i].size();
col[i] = Fenwick<int>(N);
val[i] = Fenwick<i64>(N);
}
for (int i = 0; i < n; i++) {
int j = lower_bound(pos[c[i]].begin(), pos[c[i]].end(), i) - pos[c[i]].begin();
col[c[i]].modify(j, 1);
val[c[i]].modify(j, v[i]);
}
for (int i = 0; i < q; i++) {
auto &[o, vec] = que[i];
if (o == 1) {
int p = vec[0];
int x = vec[1];
int j = lower_bound(pos[c[p]].begin(), pos[c[p]].end(), p) - pos[c[p]].begin();
col[c[p]].modify(j, -1);
val[c[p]].modify(j, -v[p]);
j = lower_bound(pos[x].begin(), pos[x].end(), p) - pos[x].begin();
col[x].modify(j, +1);
val[x].modify(j, +v[p]);
c[p] = x;
} else if (o == 2) {
int p = vec[0];
int x = vec[1];
int j = lower_bound(pos[c[p]].begin(), pos[c[p]].end(), p) - pos[c[p]].begin();
val[c[p]].modify(j, x - v[p]);
v[p] = x;
} else {
int x = vec[0];
vec.erase(vec.begin());
int ql = x, qr = x + 1;
auto check1 = [&](int r, const vector<int> &a) {
int l = x;
int res = 0;
for (auto &ai : a) {
int jl = lower_bound(pos[ai].begin(), pos[ai].end(), l) - pos[ai].begin();
int jr = lower_bound(pos[ai].begin(), pos[ai].end(), r) - pos[ai].begin();
res += col[ai].sum(jl, jr);
}
return r - l == res;
};
int l = x + 1, r = n;
while (l <= r) {
int m = (l + r) >> 1;
if (check1(m, vec)) {
l = m + 1;
qr = m;
} else {
r = m - 1;
}
}
auto check2 = [&](int l, const vector<int> &a) {
int r = x + 1;
int res = 0;
for (auto &ai : a) {
int jl = lower_bound(pos[ai].begin(), pos[ai].end(), l) - pos[ai].begin();
int jr = lower_bound(pos[ai].begin(), pos[ai].end(), r) - pos[ai].begin();
res += col[ai].sum(jl, jr);
}
return r - l == res;
};
l = 0, r = x;
while (l <= r) {
int m = (l + r) >> 1;
if (check2(m, vec)) {
r = m - 1;
ql = m;
} else {
l = m + 1;
}
}
i64 ans = 0;
for (auto &xi : vec) {
int jl = lower_bound(pos[xi].begin(), pos[xi].end(), ql) - pos[xi].begin();
int jr = lower_bound(pos[xi].begin(), pos[xi].end(), qr) - pos[xi].begin();
ans += val[xi].sum(jl, jr);
}
cout << ans << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
I. Path Planning
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<int> p(n * m);
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];
}
}
auto check = [&](int x) {
int pre = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] < x) {
if (pre > j) {
return false;
}
pre = j;
}
}
}
return true;
};
int ans = 0;
int l = 0, r = n * m;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
K. Peg Solitaire
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
x--, y--;
a[x][y] = 1;
}
int dx[] = {+1, -1, +0, +0};
int dy[] = {+0, +0, +1, -1};
int ans = 1E9;
function<void(int)> dfs = [&](int res) {
ans = min(ans, res);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j]) {
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
int tx = i + 2 * dx[k];
int ty = j + 2 * dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (tx < 0 || ty < 0 || ty >= m || tx >= n) {
continue;
}
if (a[nx][ny] && !a[tx][ty]) {
a[tx][ty] = 1;
a[i][j] = a[nx][ny] = 0;
dfs(res - 1);
a[tx][ty] = 0;
a[i][j] = a[nx][ny] = 1;
}
}
}
}
}
};
dfs(k);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
- 2023 Programming Collegiate Provincial Guangdongprogramming collegiate provincial guangdong 2023 programming collegiate provincial programming collegiate provincial contest programming collegiate provincial shandong programming provincial collegiate sichuan programming provincial collegiate shandong programming collegiate provincial counting programming provincial collegiate sponsored 题解programming collegiate provincial heilongjiang programming collegiate provincial