C
Problem - C - Codeforces
题意：
给定一个 ![]() 到 ![]() 的排列 ![]() 。问有多少种 ![]() 到 ![]() 的排列 ![]() ，满足对于任意的区间 ![]() 都有 ![]()
其中 ![]() 为最小未出现非负整数，如
![]() ![]()
做法：
如果你从未接触过mex的话可以看下
严格鸽：序列中未出现的最小的非负整数 mex 入门
严格鸽：Codeforces Round #767 (Div. 2) C(原题) D(枚举)
回到这个题目上来。
我们考虑，如果一个区间 ![]() 其 ![]() 则说明 ![]() 的数都在这个区间里出现过了。
所以我们需要从 ![]() 到 ![]() 枚举 ![]() ，并且维护 ![]() 出现的数的最左和最右的端点 ![]()
那么，如果枚举到的 ![]() 的位置 ![]() 落在了区间 ![]() 中，那么剩下的位置 ![]() , ![]() 是可以随便放的。
( ![]() , ![]() )
![]()
比如上图，无论我的5放到了哪里，都不会影响这个区间 ![]() 是否全部出现。
这里大家可以尝试模拟一下
![]()
code
void slove() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> a, pos[a] = i;
int L = INF, R = -INF;
int ans = 1;
for (int i = 0; i < n; i++) {
if (L <= pos && pos <= R) {
ans *= (R - L + 1 - i);
ans %= mod;
}
L = min(L, pos);
R = max(R, pos);
}
cout << ans << endl;
}
D
Problem - D - Codeforces
题意：
给定一个长度为 ![]() 的数组 ![]() ,每次操作你可以删除相邻的两个不同的数。
![]() 删除这两个数，剩下的数保持原来的顺序。
问经过多次操作后，使得整个数组的数都是相同的，求这样的最长长度。
例子
![]()
![]()
![]()
做法：
如果这里有两个数 ![]() ，我们想要他俩可以出现在最后的数组中并且相邻，需要满足什么？
需要保证 ![]() 的数可以全部消除掉。
比如 ![]() 最后是可以变成 ![]() 的。
那么我们需要解决的问题就是，如何判断一个区间是否可以被完全删除。
首先，这个区间的长度必须是偶数，如果是奇数的话，一定会剩下一个的。
并且我们有个结论，区间内出现次数的最大值，不能超过总长度的一半。
比如 ![]() 我们是可以完全删除掉的
而 ![]() 是无论如何都删除不完的（一定会剩下一个1）
因为，假设出现次数的最大值为 ![]() 且 ![]() ，那么剩下不到一半的数，就算都去和 ![]() 配对来删除 ![]() ，最后 ![]() 还是会剩下的。
ps：评论有人问为什么 ![]() 就一定可以删除完，方案是什么？
实际上，我们可以每次操作都删除出现次数最多的那个数，这样会有 ![]()
![]()
这样的方案会始终保证 ![]() （当然在某次操作后，出现次数最大的那个数是可能会变的）最后的情况就是还剩下两个不同的数。
所以我们这样来检查区间是否可以被完全删除。
定义 ![]() 为区间 ![]() 是否满足 ![]()
for (int i = 1; i <= n; i++) {
vector<int>cnt(n + 1, 0);
int mx = 0;
for (int j = i; j <= n; j++) {
mx = max(mx, ++cnt[a[j]]);
f[j] = (2 * mx <= (j - i + 1));
}
}
然后我们写一个函数（注意，区间长度小于0的区间是一定可以被删除完的（因为本身就没有数2333）
bool ok(int L, int R) {
if (R - L + 1 <= 0)return 1;
return (R - L + 1) % 2 == 0 && f[L][R];
}
然后我们开始进行dp，我们定义 ![]() 为区间 ![]() 的最大长度。
那么显然我们有以下的转移
如果 ![]() 并且 ![]() 是可以被完全删除的，则有 ![]()
for (int j = 1; j <= n; j++)
for (int i = j - 1; i >= 1; i--)
if (ok(i + 1, j - 1) && a == a[j])
dp[j] = max(dp[j], dp + 1);
当然dp需要初始化，我们只需要枚举 ![]() ，然后看看 ![]() 是否可以被完全删除。
for (int i = 1; i <= n; i++)
if (ok(1, i - 1))dp = 1;
那么最后我们统计答案的时候，如果我们希望 ![]() 的答案可以被统计上，则需要保证 ![]() 是可以被完全删除的。
int ans = 0;
for (int i = 1; i <= n; i++)
if (ok(i + 1, n))ans = max(ans, dp);
code
bool ok(int L, int R) {
if (R - L + 1 <= 0)return 1;
return (R - L + 1) % 2 == 0 && f[L][R];
}
void slove() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> a;
for (int i = 1; i <= n; i++) {
vector<int>cnt(n + 1, 0);
int mx = 0;
for (int j = i; j <= n; j++) {
mx = max(mx, ++cnt[a[j]]);
f[j] = (2 * mx <= (j - i + 1));
}
}
vector<int>dp(n + 5, -INF);
for (int i = 1; i <= n; i++)
if (ok(1, i - 1))dp = 1;
for (int j = 1; j <= n; j++)
for (int i = j - 1; i >= 1; i--)
if (ok(i + 1, j - 1) && a == a[j])
dp[j] = max(dp[j], dp + 1);
int ans = 0;
for (int i = 1; i <= n; i++)
if (ok(i + 1, n))ans = max(ans, dp);
cout << ans << endl;
} |
|
转播
