C
C
观察题意, 模拟样例, 首先 \(0\) 不能动, 因为相邻的 \(mex\) 会改变, 然后 \(1\) 也是如此, 所以我们固定了 \(0\) 和 \(1\), 设两个指针 \(l\) 和 \(r\) 表示固定的位置, 那么此时在他们两个中间的数可以随便移动, 假设有 \(x\) 个空位, 那么如果 \(2\) 在里面, \(2\) 的选择则是 \(x\) 个, 如果不在, 那么很明显我们不能把 \(2\) 放进去, 接着我们固定 \(1\) 和 \(2\), 现在可用的空位为 \(r - l - (i + 1)\), 如果 \(3\) 在这个空位里面, 那么同理, 会有 \(r - l - 1 - i\) 随便选择, 这里的 \(i + 1\) 指的是已经固定了的位置, 依次类推即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7;
void solve(){
int n; cin >> n;
map<int, int> mp;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i];
mp[a[i]] = i;
}
int l = mp[0], r = mp[0], res = 1;
for(int i = 1; i < n; i++){
int x = mp[i];
if(x < l) l = x;
else if(x > r) r = x;
else res = res * (r - l + 1 - i) % mod;
}
cout << res << '\n';
}
signed main(){
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}
D
D
最优方案题, 我们要考虑贪心或者 \(dp\) 或者图论
贪心明显不可以, 因为我们无法保证当前操作不会影响前面的操作, 并且难以维护
考虑\(dp\), 设 \(dp_i\) 为 \(a_i\) 在 \(i\) 位置最多能保留多少个
下面给出一个函数 \(deletable\), 定义如下:
- 一个区间 \([l,r]\) 若可删除, 则有 \(deletble [l,r]\)
- 区间必须是偶数长度
- 若区间 \([l,r]\) 内的众数不大于区间长度的一半则可以完全删除
那么 \(dp_i\) 是由 \(dp_{j∈(0, i - 1)}\) 转移而来, 需要满足:
\[dp_i = \max_{j=0}^{i-1} \left( \text{Deletable}(j+1, r) \land (a_i = a_j \mid j=0) \right) \cdot (dp_j + 1) \]由于我们的 \(dp_i\) 表示的是前 \(i\) 个, 所以我们 \(i → n\) 是不要了的, 也需要满足 \(Deletabele[i + 1, n]\), 那么答案就是:
\[ \text{ans} = \max_{i=1}^{n} \text{Deletable}(i+1, n) \cdot dp_i \]#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int cnt = 0;
void solve(){
int n; cin >> n;
vector<int> a(n + 1);
vector<vector<int>> sum(n + 1, a);
for(int i = 1; i <= n; i++){
cin >> a[i];
for(int j = 1; j <= n; j++){
sum[i][j] = sum[i - 1][j];
}
sum[i][a[i]]++;
}
vector<int> f(n + 1), g(n + 1);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
g[i] = max(g[i], sum[n][j] - sum[i][j]);
}
}
int res = 0;
vector<int> dp(n + 1, -1e9);
dp[0] = 0;
for(int i = 1; i <= n; i++){
int tot = 0;
for(int j = i - 1; j >= 0; j--){
int l = j + 1, r = i - 1;
tot = max(tot, sum[r][a[l]] - sum[l - 1][a[l]]);
if((r - l + 1) % 2 == 0 && tot <= (r - l + 1) / 2 && (j == 0 || a[i] == a[j])){
dp[i] = max(dp[i], dp[j] + 1);
}
}
if((n - i) % 2 == 0 && g[i] <= (n - i) / 2){
res = max(res, dp[i]);
}
}
cout << res << '\n';
}
signed main(){
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}