A.Tales of a Sort
题目大意
Alphen has an array of positive integers \(a\) of length n.
Alphen can perform the following operation:
- For all \(i\) from 1 to n, replace \(a_i\) with \(\max(0,a_i−1)\) .
Alphen will perform the above operation until \(a\) is sorted, that is \(a\) satisfies \(a_1≤a_2≤…≤a_n\). How many operations will Alphen perform? Under the constraints of the problem, it can be proven that Alphen will perform a finite number of operations.
思路
记录最大的逆序对的值即可
#include <bits/stdc++.h>
using namespace std;
const int N = 550;
int a[N];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
if (a[i] > a[j])
ans = max(ans, a[i]);
}
cout << ans << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
B.Good Arrays
题目大意
Let's call an array of positive integers b of length n good if:
- \(a_i≠b_i\) for all i from \(1 \ to \ n\) ,
- $a_1+a_2+…+a_n=b_1+b_2+…+b_n $.
思路
这道题将非 \(1\) 的数把值累加到 \(1\) 上面，让自己等于 \(1\), 然后 \(1\) 变成非 \(1\) 。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve()
{
int n;
cin >> n;
LL cnt1 = 0, sum = 0;
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
if (x == 1)
cnt1++;
else
sum += (x - 1);
}
if (n == 1)
{
puts("NO");
return;
}
if (sum >= cnt1)
{
puts("YES");
return;
}
else
{
puts("NO");
return;
}
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
C.To Become Max
题目描述
You are given an array of integers $ a $ of length $ n $ .
In one operation you:
- Choose an index $ i $ such that $ 1 \le i \le n - 1 $ and $ a_i \le a_{i + 1} $ .
- Increase $ a_i $ by $ 1 $ .
Find the maximum possible value of $ \max(a_1, a_2, \ldots a_n) $ that you can get after performing this operation at most $ k $ times.
输入格式
Each test contains multiple test cases. The first line of input contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \le n \le 1000 $ , $ 1 \le k \le 10^{8} $ ) — the length of the array $ a $ and the maximum number of operations that can be performed.
The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le 10^{8} $ ) — the elements of the array $ a $ .
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 1000 $ .
输出格式
For each test case output a single integer — the maximum possible maximum of the array after performing at most $ k $ operations.
样例 #1
样例输入 #1
6
3 4
1 3 3
5 6
1 3 4 5 1
4 13
1 1 3 179
5 3
4 3 2 2 2
5 6
6 5 4 1 5
2 17
3 5
样例输出 #1
4
7
179
5
7
6
提示
In the first test case, one possible optimal sequence of operations is: $ [\color{red}{1}, 3, 3] \rightarrow [2, \color{red}{3}, 3] \rightarrow [\color{red}{2}, 4, 3] \rightarrow [\color{red}{3}, 4, 3] \rightarrow [4, 4, 3] $ .
In the second test case, one possible optimal sequence of operations is: $ [1, \color{red}{3}, 4, 5, 1] \rightarrow [1, \color{red}{4}, 4, 5, 1] \rightarrow [1, 5, \color{red}{4}, 5, 1] \rightarrow [1, 5, \color{red}{5}, 5, 1] \rightarrow [1, \color{red}{5}, 6, 5, 1] \rightarrow [1, \color{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1] $ .
思路
我们二分答案，下界设为 \(0\)，而 \(\max(a_1,…a_n)+k\) 作为上界。
设 \(b\) 是 \(a\) 在执行 \(k\) 次操作后的数组。假设对于一个数 \(x\)，我们想要检查是否可以在 \(k\) 次操作中得到\(\max(b_1,…b_n)≥x\)。也就是说，通过 \(k\) 次操作使得存在某个索引 \(i\) 使得 \(b_i≥x\) 。
因此，让我们从遍历一下 \(b\) 数组 ，看看是否可以在 \(k\) 次操作中使得 \(b_i≥x\) 。
设 \(f(i,y)\) 为使得 \(b_i≥y\) 所需的最小操作数。那么有：
显然计算 \(f(i,x)\) 最坏情况下需要 \(O(n)\) 的时间。因此，我们看看 \(\sum _{i=1}^{n}f_{i,x}≤k\)
如果操作次数 \(≤k\)，那么在 \(k\) 次操作中可能存在某个 \(b_i≥x\)，并在更新当前答案后让 \(l=mid\)。否则这个 \(x\) 没有办法满足，让 \(r=mid\)。复杂度：\(O(n^2\log A)\)，其中 \(A\) 是 \(a_i\) 和 \(k\) 的最大可能值。
我们这里再来看
一个优化空间的思路，因为我们只需要计算所有 \(f\) 值的和，所以 \(\text{O(1)}\) 空间复杂度就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
vector<ll> a(N);
ll n, k;
bool check(ll x)
{
for (int i = 1; i <= n; i++)
{
vector<ll> minneed(n + 1);
minneed[i] = x;
ll ut = 0;
for (int j = i; j <= n; j++)
{
if (minneed[j] <= a[j])
break;
if (j == n)
{
ut = k + 1;
break;
}
ut += minneed[j] - a[j];
minneed[j + 1] = max(0ll, minneed[j] - 1);
}
if (ut <= k)
return true;
}
return false;
}
void solve()
{
cin >> n >> k;
ll maxnum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
maxnum = max(maxnum, a[i]);
}
// cout << *max_element(a.begin(), a.end()) + k + 1 << endl;
ll l = -1, r = maxnum + k + 1, ans = 0;
// cout << r << endl;
while (l + 1 < r)
{
ll mid = (l + r) >> 1;
if (check(mid))
ans = mid, l = mid;
else
r = mid;
}
cout << l << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
E1 .PermuTree(easy version)
题目大意
给定一棵以 \(1\) 为根的有根树，你需要给出一个 \(1\) 到 \(n\) 的排列 \(a\)，最大化二元组 \((u,v)\) 的数量，满足 \(a_u<a_{lca(a_u,a_v)}<a_v\)，输出这个最大值。
\(2≤n≤5000\)。
思路
这道题等价于给每个点重新赋一个值 \(a_i\) 然后满足条件即可
对于一个节点 \(i\) ，我们可以使得一部分 \(i\) 的子树的 \(a\) 值均小于 \(a_i\)，一部分子树的 \(a\) 值均大于 \(a_i\) ，因为 \(a\) 是排列所以所有 \(a_i\) 的值都不会重复
易得两棵子树的节点个数和的乘积就是 \(i\) 的贡献(乘法原理)
我们设 \(f_x\) 表示是否存在一个子树大小为 \(x\) ，\(siz_i\) 为以 \(i\) 为根的子树的节点个数
那么当 \(u\) 的有子树节点个数为 \(i\) 时，易得这时分界后 \(u\) 的贡献为 \(i\times(siz_u-1-i)\) 减去 \(1\) 是因为根节点不能算。
然后对于每一个 \(u\) 递归求和即可，不能忘了把 \(f\) 初始化为 \(0\).
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 50;
vector<int> e[N];
bool f[N];
int a[N], siz[N];
int n;
void dfs0(int u, int fa)
{
siz[u] = 1;
if (e[u].empty())
{
siz[u] = 1;
return;
}
for (auto nxt : e[u])
{
if (u == fa)
continue;
dfs0(nxt, u);
siz[u] += siz[nxt];
}
return;
}
int ans = 0;
void dfs1(int u, int fa)
{
f[0] = 1; // f为是否存在一个子树大小为u
for (auto nxt : e[u])
{
if (u == fa)
continue;
for (int j = siz[u]; j >= siz[nxt]; j--)
f[j] |= f[j - siz[nxt]]; //如果去掉这个子树有值,就把子树siz[nxt]加上
}
int bst = 0;
for (int i = 1; i <= siz[u]; i++)
if (f[i])
bst = max(bst, i * (siz[u] - 1 - i));
ans += bst;
memset(f, 0, sizeof(f));
for (auto nxt : e[u])
{
if (u == fa)
continue;
dfs1(nxt, 1);
}
return;
}
int main()
{
cin >> n;
for (int i = 2; i <= n; i++)
{
int x;
scanf("%d", &x);
e[x].emplace_back(i);
}
dfs0(1, 0);
dfs1(1, 0);
cout << ans << endl;
return 0;
}