A. Square of Rectangles
显然只有两种组合方式，三个叠放，两个小的组合，和大的叠放
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int a[3], b[3];
for (int i = 0; i <= 2; i++) cin >> a[i] >> b[i];
bool flag = 0;
if (a[0] == a[1] && a[1] == a[2]) {
if (b[0] + b[1] + b[2] == a[0]) flag = 1;
}
if (b[0] == b[1] && b[1] == b[2]) {
if (b[0] == a[0] + a[1] + a[2]) flag = 1;
}
if (a[1] == a[2]) {
if (a[1] + a[0] == b[0] && b[1] + b[2] == b[0]) flag = 1;
}
if (b[1] == b[2]) {
if (b[1] + b[0] == a[0] && a[1] + a[2] == a[0]) flag = 1;
}
cout << (flag ? "Yes" : "No") << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
B. Square Pool
只有对角线上的球能进袋，小球互相碰撞其实就是交换了运动状态，实际不影响总个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, s;
cin >> n >> s;
int ans = 0;
for (int i = 1; i <= n; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a == b) ans += (c == d);
else ans += (c + d == s);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
C. Divine Tree
首先能注意到某一点为根时，对应的总神圣值有上下限，下限为其他所有点接到 1 后面，上限为菊花图，全部接到根上。
先找到根节点 rt 应该是几，初态为上限，即菊花图，此时总神圣值 now 为 $rt! + (n-rt)*rt$。
接下来从大到小，遍历每个点，记录当前点贡献为 v = min(rt, i)，如果 $now - (v - 1) >= s$ 就把当前这个点接到 1 后。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
#define int long long
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
ll m;
cin >> n >> m;
int rt = 0;
for (int i = 1; i <= n; i++) {
ll l = i + n - 1, r = (i + 1ll) * i / 2 + (n - i) * i;
if (l <= m && m <= r) {
rt = i;
break;
}
}
if (rt == 0) {
cout << "-1" << endl;
return;
}
vector<int> fa(n + 1);
for (int i = 1; i <= n; i++) fa[i] = rt;
ll now = (1ll + rt) * rt / 2 + (n - rt) * rt;
for (int i = n; i >= 1; i--) {
if (now == m) break;
int v = min(rt, i);
if (now - (v - 1) <= m) {
int u = m - now + v;
fa[i] = u;
now -= (v - u);
break;
}
fa[i] = 1;
now -= (v - 1);
}
cout << rt << endl;
for (int i = 1; i <= n; i++) {
if (i != rt) cout << fa[i] << " " << i << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
D. Matrix game
首先注意到，n 的值为 $a*(k-1)+1$，每种数字都出现 k - 1 次，接下来随便出现任意一个数字即可满足 a 的需求。
重点是确定了 n，如何求得 m：
$C(a,n)$ 保证有一列是完全相同的值，有 k 种值，那就需要 $(b-1)kC(a,n)+1$ 来取得 b 列完全相同的颜色。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
ll f[N], inv[N];
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void init() {
f[0] = 1;
inv[0] = 1;
for (int i = 1; i < N; i++) {
f[i] = f[i - 1] * i % mod;
}
inv[N - 1] = qpow(f[N - 1], mod - 2);
for (int i = N - 2; i >= 1; i--) {
inv[i] = inv[i + 1] * (i + 1) % mod;
}
}
ll C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
if (n == m || m == 0) return 1;
ll res = 1;
for (int i = 0; i < m; i++) {
res = (res * (n - i)) % mod;
}
return (res * inv[m]) % mod;
}
void solve() {
int a, b, k;
cin >> a >> b >> k;
ll n = (1ll * a * k - (k - 1)) % mod;
ll m = (1ll * (b - 1) * k % mod * C(n, a) % mod + 1) % mod;
cout << n << " " << m << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
E. Lanes of Cars
这个问题的核心是在 “减少基础愤怒值” 和 “支付换道惩罚” 之间做权衡。
换道决策: 什么时候换道是划算的？
假设我们把一辆车从一条有 $c_1$ 辆车的车道（它本来是第 $c_1$ 辆车）移动到一条有 $c_2$ 辆车的车道。
- 收益: 我们省去了它作为第 $c_1$ 辆车产生的 $c_1$ 点愤怒值。
- 成本: 它在新车道成为第 $c_2+1$ 辆车，产生 $c_2+1$ 点基础愤怒值，并额外支付 $k$ 点惩罚。
- 净收益: $c_1 - (c_2+1+k)$。
只有当净收益为正，即 $c_1 > c_2+1+k$ 时，这次移动才是划算的。
问题转化:
我们可以把所有要移走的车看作“供给”，所有要填入的空位看作“需求”。
- 供给: 初始时，最长的车道队尾的车是最好的“供给”，因为它们的基础愤怒值最高。
- 需求: 初始时，最短的车道队尾的下一个空位是最好的“需求”，因为它们的基础愤怒值最低。
我们应该不断地用最好的供给满足最好的需求，直到不再划算为止。
直接模拟这个过程（比如用优先队列）会很慢。我们可以发现，如果我们移动 $P$ 辆车，总成本是关于 $P$ 的一个凸函数。这类“求最优策略下的最优值，但策略执行次数受限”的问题，通常可以转化为“每次操作附加一个额外成本（或收益）$\lambda$，求无限制次数下的最优值”，然后通过二分这个 $\lambda$
我们不直接对 $\lambda$ 二分，而是对一个更直观的量——移动的车辆数 $P$——进行二分。
二分答案（移动次数 P）:
假设我们决定移动 $P$ 辆车。
哪些车被移走？ 为了最大化收益，我们应该移走初始状态下基础愤怒值最高的 $P$ 辆车。
它们去哪里？ 为了最小化成本，它们应该被移到基础愤怒值最低的 $P$ 个可用“空位”上。
我们可以通过二分来找到最优的移动次数 $P_{opt}$。
二分检查 check(P): 对于一个给定的移动次数 $P$，我们是否应该移动更多或更少的车？
找到第 $P$ 昂贵的车的愤怒值（边际收益 $R_T$）。
找到第 $P$ 便宜的空位的愤怒值（边际成本 $L_T+1$）。
如果 $R_T > L_T+1+k$，说明移动第 $P$ 辆车仍然是划算的，我们应该尝试移动更多的车，所以我们增大 $P$ 的搜索范围。
否则，移动 $P$ 辆车已经不划算了，我们应该减少移动次数，减小 $P$ 的搜索范围。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
ll k, sum = 0;
cin >> n >> k;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += (a[i] + 1) * a[i] / 2;
}
sort(a.begin() + 1, a.end());
vector<ll> prep(n + 1), pres(n + 1), sufp(n + 2), sufs(n + 2);
for (int i = 1; i <= n; i++) {
pres[i] = pres[i - 1] + a[i];
prep[i] = prep[i - 1] + a[i] * a[i];
}
for (int i = n; i > 0; i--) {
sufs[i] = sufs[i + 1] + a[i];
sufp[i] = sufp[i + 1] + a[i] * a[i];
}
auto bs1 = [&](ll x) { //计算将所有 a[i] <= num 的车道填满到 num+1 辆车需要多少辆车
int id = upper_bound(a.begin() + 1, a.end(), x) - a.begin() - 1;
return id * x - pres[id] + id;
};
auto bs2 = [&](ll x) { //计算从所有 a[i] >= num 的车道抽调车辆，使它们都变成 num-1 辆，能提供多少辆车
int id = lower_bound(a.begin() + 1, a.end(), x) - a.begin();
return sufs[id] - (n - id + 1) * x + (n - id + 1);
};
auto suml = [&](ll x) { //计算将所有 a[i] <= num 的车道填满到 num 辆车，增加的愤怒值总和
int id = upper_bound(a.begin() + 1, a.end(), x) - a.begin() - 1;
return (x * (x + 1) * id - prep[id] + pres[id]) / 2;
};
auto sumr = [&](ll x) { //计算从所有 a[i] >= num 的车道抽调车辆，使它们都变成 num 辆，减少的愤怒值总和
int id = lower_bound(a.begin() + 1, a.end(), x) - a.begin();
return (sufp[id] + sufs[id] - x * (x -1) * (n - id + 1)) / 2;
};
auto getidl = [&](ll x) { //给定移动数量 x，找到第 x 便宜的空位所在的原始愤怒值 L_T
ll l = 0, r = 1e12, ans = 0;
while (l <= r) {
ll mid = (l + r) / 2;
if (bs1(mid) >= x) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
};
auto getidr = [&](ll x) { //给定移动数量 x，找到第 x 贵的空位所在的原始愤怒值 R_T
ll l = 0, r = 1e12, ans = 0;
while (l <= r) {
ll mid = (l + r) / 2;
if (bs2(mid) >= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
};
ll l = 0, r = 1e18, ops = 0; //二分最优移动次数
while (l <= r) {
ll mid = (l + r) / 2;
if (getidr(mid) - getidl(mid) >= k + 1) {
ops = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ops == 0) {
cout << sum << endl;
return;
}
ll L_T = getidl(ops), R_T = getidr(ops);
ll rmv = sumr(R_T) - R_T * (bs2(R_T) - ops); //计算移走的总愤怒值
ll add = suml(L_T) - L_T * (bs1(L_T) - ops); //计算填满的总愤怒值
cout << sum + add - rmv + (k + 1) * ops << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|