【CCPC】CCPC 2023 Shenzhen Site A

#构造 #分治 #贪心

题目描述

A good problem should have a concise statement.
You are given an array $a$ of length $n$, initially filled with zeros, and another array $b$ of length $n$. Your goal
is to transform array $a$ into array $b$. You can perform the following two types of operations:
• $1x:$ Add $1$ to all elements in a that are equal to $x.$
• $2x:$ Add $1$ to the element in a at index $x.$
You can perform no more than $20000$ operations.

输入格式

The first line contains a positive integer $n(1\le n\le 1000).$
The second line contains $n$ non-negative integers representing the array $b(0\le bi\le n)$

输出格式

The first line should contain an integer k, representing the number of operations.
The following $k$ lines should each contain two integers $1$ $x$ or $2x$, representing an operation. For the
operation type $1x$, you must ensure that $0\le x\le n.$ For the operation type $2x$, you must ensure that$1\le x\le n.$

样例 #1

样例输入 #1

4
2 4 3 1

样例输出 #1

8
2 1
2 2
2 3
1 1
2 4
2 2
2 3
2 2

解法

首先，观察到$n\le 1000$，操作次数在$2e4$以内，大概是$nlo{g}_2$次数级别的，因此我们需要考虑如何得到这个$lo{g}_{2}n$。

首先对于$2$操作，一次只能操作一个下标，而对于$1$操作，可以操作多个数，因此我们要尽量减少$2$操作。

考虑如果尽量多的$1$操作：

初始数组全为$0$，即：
$$[0,0,0,0,0,0,0,0]$$
假设目标数组为
$$[1,2,3,4,5,6,7,8]$$
那么我们其实可以这样操作，先推平右半部分为$[5,5,5,5]$，具体而言就是：

$1.$进行$4$个$2$操作变为：$[1,1,1,1]$

$2.$进行$4$个$1$操作变为$[5,5,5,5,5]$

现在数组变为了
$$[0,0,0,0,5,5,5,5]$$

实际上右边部分仍然全部相等，我们依旧可以当做全为$0$的情况来讨论，依旧推平右半部分为：$[7,7]$

同样是通过$2$次$2$操作，$2$次$1$操作实现的，现在数组变为了：
$$[0,0,0,0,5,5,7,7]$$

那么这样实际上就是一种递归分治，因为每次的子问题都相同，就像下图所示：

![[Pasted image 20241011124648.png|700]]

由于值域只有$n\le 1000$，因此我们可以直接开个桶来存值的下标。

这样分治的操作次数在$nlo{g}_{2}n$左右。

代码

void solve() {
int n;
std::cin >> n;

std::vector<std::vector<int>>a(n + 1);

for (int i = 1; i <= n; ++i) {
int x;
std::cin >> x;
a[x].emplace_back(i);
}

std::vector<pii>res;
auto dfs = [&](auto&& self, int l, int r,int now)->void {
if (l > r) return;
int mid = l + r >> 1;
if (l == r) {
for (auto& idx : a[l]) {
for (int i = l + 1; i <= now; ++i) {
res.push_back({ 2,idx });
}
}
return;
}
if (mid + 1 <= r) {
int p = now;
bool ok = false;

for (int i = mid + 1; i <= r; ++i) { //整体+1
for (auto& idx : a[i]) {
res.push_back({ 2,idx });
ok = true;
}
}
p += ok;
if (ok) {
while (p < mid + 1) {
res.push_back({ 1,p });
p++;
}
}

self(self, mid + 1, r, p);

}
if (l <= mid) {
self(self, l, mid,now);
}
};

dfs(dfs, 0, n,0);

std::cout << res.size() << "\n";

for (auto& [x, y] : res) {
std::cout << x << " " << y << "\n";
}
}


signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);

int t = 1;
//std::cin >> t;

while (t--) {
solve();
}
};

原文地址：https://blog.csdn.net/Antonio915/article/details/142851204

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！