Tales of a Sort
题解
- 找到最大的能够产生逆序对的数即可
- 暴力\(O(n^2)\)枚举即可
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
int a[N];
void solve()
{
cin >> n;
int ans = 0;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
for (int i = 1; i <= n; ++i)
{
for (int j = i + 1; j <= n; ++j)
{
if (a[j] < a[i])
ans = max(ans, a[i]);
}
}
cout << ans << endl;
}
Good Arrays
题解
- 每一个大于\(1\)的数都能变成\(1\)
- 我们只需要统计出\(\sum{(a_i-1)}\)与\(1\)的个数比较即可
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
int a[N];
void solve()
{
cin >> n;
int cnt = 0;
int num = 0;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
cnt += a[i] - 1;
if (a[i] == 1)
num++;
}
if (n == 1)
{
cout << "NO" << endl;
return;
}
if (cnt >= num)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
To Become Max
\(1 \leq n \leq 1000\)
题解 : 二分答案
- 容易发现最大值具有单调性
- 所以我们考虑二分最大值
- 我们考虑如何\(check\)
- 我们\(O(n)\)枚举每个位置成为最大值，如果当前位置为\(x\)，那么其后面的一定为\(x - 1, x - 2,x - 3...\)
- 所以我们可以\(O(n)\)判断每个位置是否可以成为最大值
- 所以复杂度为\(O(n^2 logn)\)
const int N = 1e3 + 10, M = 4e5 + 10;
int n, k, a[N];
bool check(int mid)
{
for (int i = 1; i <= n; ++i)
{
int remain = k, cur = mid;
for (int j = i; j <= n; ++j, --cur)
{
if (a[j] >= cur)
return true;
if (remain - (cur - a[j]) < 0)
break;
remain -= cur - a[j];
}
}
return false;
}
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; ++i)
cin >> a[i];
int l = 0, r = 1e18;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
l = mid + 1;
else
r = mid - 1;
}
cout << r << endl;
}
More Wrong
题解：分治
我们考虑分治
我们可以求出每个子问题的最大位置，最后求出整个排列的最大位置
对于\([l,r]\)来说，如果\([l, r - 1]\)逆序对的数量等于\([l,r]\)，说明\(a_r > a_l\)，否则\(a_r < a_l\)
所以对于每个子问题我们可以这样确定最大位置
注意，题目要求\(l \neq r\)，所以如果我们询问\(l=r\)时，需要手动返回\(0\)，例如排列为\(2,1\)时，会存在询问\([1,1],[1,2]\)
时间复杂度\(O(nlogn)\)
代价复杂度：注意每次确定最大位置我们需要询问两次
\[2 \times (n^2 + 2\times(\frac{n}{2})^2 + 4 \times (\frac{n}{4})^2 + 8 \times (\frac{n}{8})^2...)\\ =2 \times n^2(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} ... ) < 2n^2\times 2 = 4n^2 < 5 n^2 \]
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
int query(int l, int r)
{
if (l == r)
return 0;
cout << "? " << l << " " << r << endl;
int res = 0;
cin >> res;
return res;
}
int solve(int l, int r)
{
if (l == r)
return l;
int mid = l + r >> 1;
int pos1 = solve(l, mid), pos2 = solve(mid + 1, r);
if (query(pos1, pos2) == query(pos1, pos2 - 1))
return pos2;
else
return pos1;
}
void solve()
{
cin >> n;
int ans = solve(1, n);
cout << "! " << ans << endl;
}
PermuTree (easy version)
\(1 \leq n \leq 5000\)
题解：树形\(DP\) + \(bitset\)优化
显然对于\(u\)来说，它的子节点的子树中的所有节点的点权一定\(>a_u\)或者\(< a_u\)
所以我们需要将这些子树分成两个集合\(S,T\)，集合\(S\)中的子树全部\(>a_u\)，集合\(T\)中的子树全部\(<a_u\)
那么\(u\)能够对答案做出的最大贡献为
\[\sum_{v \in S}sz[v] \times \sum_{w \in T} sz[w] \]
显然我们可以考虑枚举哪颗子节点的子树在集合\(S\)中，但是显然复杂度过高
我们可以考虑类似硬币问题进行\(dp\)，定义\(dp_i = true / false\)为集合\(S\)中存在\(i\)个节点是否合法
\[dp[i]\ \ |= dp[i - sz_v],sz_v代表子树v中节点数 \]
如果\(dp_i = true\)，那么对答案的贡献为\(i \times (sz_u - 1 - i)\)
那么\(u\)能够对答案做出的最大贡献为
\[max\sum_{i = 1}^{sz_u - 1}i \times (sz_u - 1 - i), dp_i = true \]
当前复杂度为\(O(n ^ 2)\)，已经可以通过
我们还可以通过\(bitset\)优化至\(O(\frac{n^2}{w}),w = 64\)
const int N = 5e3 + 10, M = 4e5 + 10;
int n;
int sz[N], ans;
vector<int> g[N];
void dfs(int u, int par)
{
sz[u] = 1;
bitset<N> dp;
dp.set(0); // f[0] = 1
for (auto v : g[u])
{
if (v == par)
continue;
dfs(v, u);
sz[u] += sz[v];
dp |= (dp << sz[v]);
}
int mx = 0;
for (int i = 1; i <= sz[u] - 1; ++i)
{
if (dp.test(i)) // f[i] = 1
mx = max(mx, i * (sz[u] - 1 - i));
}
ans += mx;
}
void solve()
{
cin >> n;
for (int i = 2; i <= n; ++i)
{
int u;
cin >> u;
g[i].push_back(u);
g[u].push_back(i);
}
dfs(1, 0);
cout << ans << endl;
}