2023山东 IAGDL
I
think
我们状压一下所有可能时间复杂度是 $O(6^3)$ 显然跑的很绰绰有余
code
// Codeforces - The 13th Shandong ICPC Provincial Collegiate Programming Contest
// I. Three Dice https://codeforces.com/gym/104417/problem/I 2024-04-26 23:09:28
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
int a, b;
cin >> a >> b;
int x[] = {1, 2, 3, 4, 5, 6};
int y[] = {1, 0, 0, 1, 0, 0};
for (int i = 0; i < (6 * 6 * 6); i++) {
vector<int> tmp(3);
int idx = 0;
for (int j = 1; j <= 6 * 6; j *= 6) {
int now = i / j % 6;
// cout << now << " ";
tmp[idx++] = now;
}
// cout << "\n";
int A = 0;
int B = 0;
for (auto it : tmp) {
if (y[it]) {
A += x[it];
} else
B += x[it];
}
if (A == a and B == b) {
cout << "Yes\n";
return;
}
}
cout << "No\n";
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
https://codeforces.com/gym/104417/problem/A
A. Orders
某工厂在 $1$ 日初收到 $n$ 份订单。 $i$ 个订单可以用两个整数 $a_i$ 和 $b_i$ 来描述,表示在 $a_i$ 日结束时,工厂需要向客户交付 $b_i$ 个产品。
假设工厂每天可以生产 $k$ 件产品,而在 $1$ 天开始时,工厂没有库存产品,那么工厂能否完成所有订单?
THINK
长得就很前缀和
code
// Codeforces - The 13th Shandong ICPC Provincial Collegiate Programming Contest
// A. Orders https://codeforces.com/gym/104417/problem/A 2024-04-26 23:19:54
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, k;
using pii = pair<int, int>;
void solve() {
cin >> n >> k;
vector<pii> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
}
map<int, int> mp;
sort(all(a));
for (auto [x, y] : a) {
// cout << x << " " << y << " \n";
mp[x] += y;
}
int res = 0;
for (auto [x, y] : mp) {
res += y;
if (x * k < res) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
// cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
https://codeforces.com/gym/104417/problem/G
G. Matching
给定一个长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$ ,我们根据该序列构建一个无向图 $G$ 。更确切地说,对于所有 $1 \le i< j \le n$ ,如果 $i - j = a_i - a_j$ ,则在 $G$ 中会有一条无向边连接顶点 $i$ 和 $j$ 。这条边的权重为 $(a_i + a_j)$ 。
请为 $G$ 找出一个匹配,使匹配中所有边的权重之和达到最大,并输出最大值。
回想一下,无向图的匹配意味着我们从图中选择一些边,使得任何两条边都没有共同的顶点。具体来说,不选择任何边也是匹配。
输入
有多个测试用例。输入的第一行包含一个整数 $T$ ,表示测试用例的数量。对于每个测试用例
第一行包含一个整数 $n$ ( $2 \le n \le 10^5$ ),表示序列的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ( $-10^9 \le a_i \le 10^9$ ),表示序列。
保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$ 。
think
$i - j = a_i - a_j$
$i - a_i = j - a_j$
$i - a_i = j - a_j=d$
我们就记录所有的$i-a_i$
然后 用vector 存
配对的时候 优先配对最大的一对
如果权值和小于0 就退出
code
// Codeforces - The 13th Shandong ICPC Provincial Collegiate Programming Contest
// G. Matching https://codeforces.com/gym/104417/problem/G 2024-04-26 23:33:38
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
cin >> n;
vector<int> a(n);
for (auto &i : a) cin >> i;
map<int, vector<int>> mp;
for (int i = 0; i < n; i++) {
mp[i - a[i]].emplace_back(a[i]);
}
int ans = 0;
for (auto &[x, y] : mp) {
sort(all(y), greater<>());
// reverse(all(y));
for (int j = 0; j < y.size(); j += 2) {
if (j + 1 < y.size()) {
if (y[j] + y[j + 1] > 0) {
ans += y[j];
ans += y[j + 1];
}
} else {
break;
}
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
D. Fast and Fat
你们正在参加一项越野跑团体比赛。你们队有 $n$ 名队员,其中 $v_i$ 是 $i$ 名队员的速度, $w_i$ 是他/她的体重。
比赛允许每个队员单独行动或背着另一个队员行动。当队员 $i$ 背着队员 $j$ 时,如果队员 $i$ 的体重大于或等于队员 $j$ 的体重,则队员 $i$ 的速度保持不变,为 $v_i$ 。但是,如果成员 $i$ 的重量小于成员 $j$ 的重量,成员 $i$ 的速度将减小,减幅为两者重量之差,变为 $v_i - (w_j - w_i)$ 。如果成员 $i$ 的速度变为负值,那么成员 $i$ 就无法搬运成员 $j$ 。每个成员最多只能携带一名其他成员。如果一名成员被携带,他/她不能同时携带另一名成员。
对于所有未被携带的成员,速度最慢的成员的速度就是整个团队的速度。求全队可能的最大速度。
THINK
我们可以发现 对于答案是可以二分的
因为 一个X可以 ,那么一定可以跑比他更慢的速度
然后我们就可以check答案
然后我们发现 配对的时候也是可以二分的
就是将速度不及格的全部都扔到set里
然后每个跑的快的配对能背的最重的一个
如果最后还剩下 没能背的
那就是做不到
否则就是可以的
tips 这个题卡常
code
// Codeforces - The 13th Shandong ICPC Provincial Collegiate Programming Contest
// D. Fast and Fat https://codeforces.com/gym/104417/problem/D 2024-04-26
// 23:42:13
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
cin >> n;
vector<int> v(n), w(n);
for (int i = 0; i < n; i++) {
cin >> v[i] >> w[i];
}
int Lans = 0, Rans = INT_MAX;
int ans = -1;
// cout << "n=" << n << "\n";
auto check = [&](int mid) -> bool {
vector<int> st(n);
multiset<int> res;
for (int i = 0; i < n; i++) {
if (v[i] < mid) {
st[i] = true;
res.emplace(-w[i]);
}
}
// cout << "mid=" << mid << "\n";
// for (auto it : res) {
// cout << -it << " "; // 需要背的人的重量
// }
// cout << "\n";
for (int i = 0; i < n; i++) {
if (st[i]) {
// 是被背起来的
} else {
auto it = res.lower_bound(-v[i] - w[i] + mid);
if (it != res.end()) {
res.erase(it);
}
}
}
if (res.size() > 0) {
// cout << mid << " "
// << "NO\n";
return false;
} else {
// cout << mid << " "
// << "YES\n";
return true;
}
};
while (Lans <= Rans) {
int mid = Lans + Rans >> 1LL;
if (check(mid)) {
ans = mid;
Lans = mid + 1;
} else {
Rans = mid - 1;
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
L. Puzzle: Sashigane
给定一个有 $n$ 行和 $n$ 列的网格,网格中正好有一个黑色单元格,其他单元格都是白色的。假设 $(i, j)$ 是第 $i$ 行和第 $j$ 列上的单元格,这个黑色单元格位于 $(b_i, b_j)$ 处。
您需要用一些 L 形覆盖所有的白色单元格,这样每个白色单元格都正好被一个 L 形覆盖,而唯一的黑色单元格没有被任何 L 形覆盖。L 形不得超出网格边界。
更正式地说,网格中的 L 形由四个整数 $(r, c, h, w)$ 唯一确定,其中 $(r, c)$ 确定 L 形的转折点, $h$ 和 $w$ 确定 L 形两臂的方向和长度。这四个整数必须满足 $1 \le r, c \le n$ , $1 \le r + h \le n$ , $1 \le c + w \le n$ , $h \ne 0$ , $w \ne 0$ 。
- 如果 $h<0$ ,那么满足 $r + h \le i \le r$ 的所有单元格 $(i, c)$ 都属于这个 L 形;否则,如果 $h>0$ ,那么满足 $r \le i \le r + h$ 的所有单元格 $(i, c)$ 都属于这个 L 形。
- 如果 $w<0$ ,那么满足 $c + w \le j \le c$ 的所有单元格 $(r, j)$ 都属于这个 L 形;否则,如果 $w>0$ ,满足 $c \le j \le c + w$ 的所有单元格 $(r, j)$ 都属于这个 L 形。
下图展示了一些 L 型。
think
我们很快可以想到一个显然的策略
就是不断将象限 分治然后递归
然后就是一些小细节 了
code
// Codeforces - The 13th Shandong ICPC Provincial Collegiate Programming Contest
// L. Puzzle: Sashigane https://codeforces.com/gym/104417/problem/L 2024-04-27
// 00:46:55
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m, x, y;
struct p {
int a, b, c, d;
};
vector<p> s;
/*
u up
d down
l left
r right
*/
/*
*/
int dig(int x1, int y1, int x2, int y2) { // 判断是第几象限
int _x = (x1 + x2) / 2, _y = (y1 + y2) / 2;
if (x <= _x) {
if (y <= _y)
return 1;
else
return 3;
} else {
if (y <= _y)
return 2;
else
return 4;
}
}
int dig2(int x1, int y1, int x2, int y2) { // 判断是第几象限
int _x = (x1 + x2) / 2, _y = (y1 + y2) / 2;
if (x <= _x) {
if (y <= _y)
return 1;
else
return 3;
} else {
if (y <= _y)
return 2;
else
return 4;
}
}
int cnt;
// 必须分到方格中
void f(int x1, int y1, int x2, int y2) { // 分别是左下角和右上角坐标
// 4 1 5 3
// cerr << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
if ((x2 - x1) & 1 ^ 1) {
// cout << "xy " << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
// cout << c << "\n";
if (x1 == x2) return;
int c = dig(x1, y1, x2, y2);
// cout << "c=" << c << "\n";
int _x = (x1 + x2) / 2, _y = (y1 + y2) / 2;
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
// cout << _x << " " << _y << "\n";
if (c == 1) {
// 向左和向下填充
f(x1, y1, _x, _y);
cnt += (x2 - _x);
for (int i = _x + 1, j = _y + 1; i <= x2; i++, j++) {
s.emplace_back(i, j, x1 - i, y1 - j);
// cout << i << " " << j << " " << x1 - i << " " << y1 - j << "\n";
}
} else if (c == 2) {
// 向右和向下填充//看手臂的方向
cnt += _x;
f(_x, y1, x2, _y);
for (int i = _x - 1, j = _y + 1; j <= y2; i--, j++) {
s.emplace_back(i, j, x2 - i, y1 - j);
// cout << i << " " << j << " " << x2 - i << " " << y1 - j << "\n";
}
} else if (c == 3) {
// 向左和向上填充
cnt += (x2 - _x);
f(x1, _y, _x, y2);
for (int i = _x + 1, j = _y - 1; i <= x2; i++, j--) {
s.emplace_back(i, j, x1 - i, y2 - j);
// cout << i << " " << j << " " << x1 - i << " " << y2 - j << "\n";
}
} else {
// 向右和向上填充
cnt += _x;
f(_x + 1, _y + 1, x2, y2);
for (int i = _x, j = _y; j >= y1; i--, j--) {
s.emplace_back(i, j, x2 - i, y2 - j);
// cout << i << " " << j << " " << x2 - i << " " << y2 - j << "\n";
}
}
} else { // 边长偶数
if (x1 == x2) return;
int c = dig2(x1, y1, x2, y2);
// cout << "xy " << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
// cout << c << "\n";
int _x = (x1 + x2) / 2, _y = (y1 + y2) / 2;
// cout << "_xy " << _x << " " << _y << "\n";
if (c == 1) {
// 向左和向下填充
f(x1, y1, _x, _y);
cnt += (x2 - _x);
for (int i = _x + 1, j = _y + 1; i <= x2; i++, j++) {
s.emplace_back(i, j, x1 - i, y1 - j);
// cout << i << " " << j << " " << x1 - i << " " << y1 - j << "\n";
}
} else if (c == 2) {
// 向右和向下填充//看手臂的方向
cnt += _x;
f(_x + 1, y1, x2, _y);
for (int i = _x, j = _y + 1; j <= y2; i--, j++) {
s.emplace_back(i, j, x2 - i, y1 - j);
// cout << i << " " << j << " " << x2 - i << " " << y1 - j << "\n";
}
} else if (c == 3) {
// 向左和向上填充
cnt += (x2 - _x);
f(x1, _y + 1, _x, y2);
for (int i = _x + 1, j = _y; i <= x2; i++, j--) {
s.emplace_back(i, j, x1 - i, y2 - j);
// cout << i << " " << j << " " << x1 - i << " " << y2 - j << "\n";
}
} else {
// 向右和向上填充
cnt += _x;
f(_x + 1, _y + 1, x2, y2);
for (int i = _x, j = _y; j >= y1; i--, j--) {
s.emplace_back(i, j, x2 - i, y2 - j);
// cout << i << " " << j << " " << x2 - i << " " << y2 - j << "\n";
}
}
}
}
void solve() {
//
cin >> n >> x >> y;
cout << "Yes\n";
f(1, 1, n, n);
cout << s.size() << "\n";
for (auto [a, b, c, d] : s) {
cout << a << " " << b << " " << c << " " << d << "\n";
}
// cout << cnt << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}