题目链接点这里
CF1918A Brick Wall
1
2
3
4
5
6
void solve()
{
ll n, m;
cin >> n >> m;
cout << n * (m / 2) << endl;
}
CF1918B Minimize Inversions
注意到，当其中一个排列有序时，总的逆序对数量最少()
今天找个时间补上证明
对于任意一对 $i,j$ 位置，其可能的逆序对总贡献度 $c_{i,j}$ 为 $0,1,2$ 。由于两个排列对应位置上的元素是绑定的，所以在任意操作后只可能会出现下面几种情况：
- 总贡献度 $c_{i,j}$ 由 $0$ 变成 $2$
- 总贡献度 $c_{i,j}$ 由 $1$ 变成 $1$
- 总贡献度 $c_{i,j}$ 由 $2$ 变成 $0$
那么令其中一个排列有序时，只会出现上面的第 2, 3 种情况（其中一个排列有序时 $c_{i,j}$ 不会取到 $2$ ）。这样所有的 $c_{i,j}$ 都取到了最小值，则此时答案最小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve()
{
int n;
cin >> n;
vector<pii> arr(n);
for (int i = 0; i < n; ++i)
cin >> arr[i].fi;
for (int i = 0; i < n; ++i)
cin >> arr[i].se;
sort(all(arr));
for (int i = 0; i < n; ++i)
cout << arr[i].fi << " ";
cout << endl;
for (int i = 0; i < n; ++i)
cout << arr[i].se << " ";
cout << endl;
}
CF1918C XOR-distance
为减少讨论，先假设 a > b。
首先将 $a$,$b$ 拆位。然后根据异或的性质，当 $x$ 的某一位取 $1$ 时，会将原本的 $0$ 和 $1$ 翻转，而本题求的是差，所以只要考虑不同的位。于是贪心的从高位到低位考虑，找到第一个不同的位置 $hdig$，若 $r$ 可以取这一位为 $1$，则可以分两种情况考虑：
- 翻转该位，则会使 $a<b$，然后在后面的位置上通过翻转尽量让 $a$ 贴近 $b$。
- 不翻转该位，则保留 $a>b$，然后在后面的位置上通过翻转尽量让 $b$ 贴近 $a$。
若 $r$ 这一位取不到 $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
void solve()
{
ll a, b, r;
cin >> a >> b >> r;
if (a == b || r == 0)
{
cout << abs(a - b) << endl;
return;
}
if (a <= b)
swap(a, b);
int hdig = -1;
for (int i = 62; i >= 0; --i)
{
if (((a >> i) & 1) != ((b >> i) & 1))
{
hdig = i;
break;
}
}
if (r >> hdig)
{
ll ans = 4e18;
// a > b
ll x = 0;
for (int i = hdig - 1; i >= 0; --i)
if (((a >> i) & 1) == 1 && ((b >> i) & 1) == 0)
if ((x ^ (1ll << i)) <= r)
x ^= 1ll << i;
ans = min(ans, abs((a ^ x) - (b ^ x)));
// a < b
x = 1ll << hdig;
for (int i = hdig - 1; i >= 0; --i)
if (((a >> i) & 1) == 0 && ((b >> i) & 1) == 1)
if ((x ^ (1ll << i)) <= r)
x ^= 1ll << i;
ans = min(ans, abs((a ^ x) - (b ^ x)));
cout << ans << endl;
}
else
{
// a > b
ll x = 0;
for (int i = __lg(r); i >= 0; --i)
if (((a >> i) & 1) == 1 && ((b >> i) & 1) == 0)
if ((x ^ (1ll << i)) <= r)
x ^= 1ll << i;
cout << abs((a ^ x) - (b ^ x)) << endl;
}
}
CF1918D Blocking Elements
这题用到了单调队列优化的 dp 和二分答案。
首先以题目要求的最小花费为 $mid$ 进行二分。在 $check$ 函数中，我们优先确保每一段的花费不超过 $mid$，然后就要考虑如何选择分割点。
在 $check$ 时直接贪心的选择分割点会 WA，所以我们用 dp 优化选择。定义 $dp[i]$ 是仅考虑前 $i$ 个位置，并且以第 $i$ 个位置作为分割点的分割点花费之和。在求 $dp$ 值时，先用双指针+前缀和快速确定一个 $j$ 位置，使得 $j$ 到 $i-1$ 这段的花费不大于 $mid$，即这些位置都是可以向 $dp[i]$ 转移的位置。然后根据单调队列的性质，队首即是可转移的最小值。最后检查分割点的花费之和是否超过了 $mid$，即 $dp[n + 1]$ 是否大于 $mid$。
- dp 转移方程：$dp[i]=\min \limits_{j \le x \le i-1}(dp[x]) + arr[i]$
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
void solve()
{
int n;
cin >> n;
vector<ll> arr(n + 2), pre(n + 2);
for (int i = 1; i <= n; ++i)
cin >> arr[i], pre[i] = pre[i - 1] + arr[i];
ll l = 1, r = 1e14, mid, ans = 1;
function<bool(ll x)> check = [&](ll x)->bool
{
vector<ll> dp(n + 2);
deque<ll> dq;
dq.pb(0);
for (int i = 1, j = 0; i <= n + 1; ++i)
{
while (pre[i - 1] - pre[j] > x)
++j;
while (!dq.empty() && dq.front() < j)
dq.pop_front();
if (dq.empty())
return false;
dp[i] = dp[dq.front()] + arr[i];
while(!dq.empty() && dp[dq.back()] >= dp[i])
dq.pop_back();
dq.pb(i);
}
return dp[n + 1] <= x;
};
while (l <= r)
{
mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
cout << ans << endl;
}
