总结 | 2022牛客OI赛前集训营-提高组（第三场）

白给 $190190$ 分，直接爆炸。

T1 一般图最小匹配

$100100$ 分变 $1010$ 分，原因是没有删调试的 freopen，大悲。

一开始想的是先再完全图上跑最小生成树，不难证明最终选出来的边都会在最小生成树上。然后在最小生成树上找 $mm$ 条没有公共结点的边。

然而这是在太难打，而且 kruskal 在完全图上的时间复杂度也不是很优秀。写 prim 再加上调 DP 用了我 1.5h。

然后突然明悟，发现其实对 $aa$ 排序之后相邻的点之间连边得到的不仅是最小生成树，还是一条链。

这样就好打了。设 $d{p}_{i,j,1\mathrm{/}0}dp\_\{i,j,1/0\}$ 表示前 $ii$ 个点中选取了 $jj$ 个，第 $ii$ 个点是 $\mathrm{/}/$ 否 选取。

则有 DP 方程：

$d{p}_{i,j,0}=\min \{\min \{d{p}_{i-1,k,0},d{p}_{i-1,k,1}\}+d{p}_{i,j-k,0}\}dp\_\{i,j,0\}\; =\; \backslash min\backslash \{\backslash min\backslash \{dp\_\{i\; -\; 1,\; k,\; 0\},\; dp\_\{i\; -\; 1,\; k,\; 1\}\backslash \}\; +\; dp\_\{i,\; j\; -\; k,\; 0\}\backslash \}$

$d{p}_{i,j,1}=\min \{d{p}_{i-1,k,0}+d{p}_{i,j-k,1}\}dp\_\{i,j,1\}\; =\; \backslash min\backslash \{dp\_\{i\; -\; 1,\; k,\; 0\}\; +\; dp\_\{i,\; j\; -\; k,\; 1\}\backslash \}$

然后就愉快的保龄 AC 了。

#include<bits/stdc++.h>
#define MAXN 5010
#define MAXM 25000010
#define INF 0x3f3f3f3f
using namespace std;
int n, m, cnt;
int a[MAXN], dp[MAXN][MAXN][2], val[MAXN];
void dfs(int now){
    dp[now][0][0] = 0; dp[now][1][1] = val[now];
    if(now >= n) return ;
    val[now + 1] = a[now + 1] - a[now]; dfs(now + 1);
    for(int j = min(1 + (n - now), m); j >= 1; j--){
        for(int k = max(1, j - 1); k <= j && k <= (n - now); k++){
            dp[now][j][0] = min(dp[now][j][0], min(dp[now + 1][k][0], dp[now + 1][k][1]) + dp[now][j - k][0]);
            dp[now][j][1] = min(dp[now][j][1], dp[now + 1][k][0] + dp[now][j - k][1]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    sort(a + 1, a + n + 1);
    memset(dp, 0x3f, sizeof(dp));
    dfs(1);
    printf("%d\n",dp[1][m][0]);
    return 0;
}

T2 重定向

$100100$ 分变 $00$ 分，原因是编译错误，双倍大悲。

正解是构造，考试的时候开窍突然想到了。

然后因为“更改所有匹配项”改多了编译错误。

构造方法有空再来填坑

#include<bits/stdc++.h>
#define MAXN 200010
#define INF 0x3f3f3f3f
using namespace std;
struct node{ int val, pos; };
bool operator > (node a, node b){ return a.val > b.val; }
bool operator < (node a, node b){ return a.val < b.val; }
node lst[MAXN];
int t, n;
int a[MAXN], b[MAXN];
string ans;
bool vis[MAXN];
void pre_work(){
    for(int i = 1; i <= n; i++) lst[i].val = a[i] == 0 ? INF : a[i], lst[i].pos = i;
    for(int i = n - 1; i >= 1; i--) lst[i] = min(lst[i], lst[i + 1]);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int ce = 0;
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]), ce += a[i] == 0;
            pre_work();
            memset(vis, 0, sizeof(vis));
            for(int i = 1; i <= n; i++) vis[a[i]] = true;
            priority_queue<int, vector<int>, greater<int> > rst;
            for(int i = 1; i <= n; i++) if(!vis[i]) rst.push(i);
            bool flag = false;
            for(int i = 1; i < n; i++){
                if(a[i] != 0){
                    if(a[i + 1] != 0 && a[i] > a[i + 1]){
                        b[i] = -1; rst.push(a[i]);
                        for(int j = i + 1; j <= n; j++){
                            if(a[j] == 0) b[j] = rst.top(), rst.pop();
                            else b[j] = a[j];
                        }
                        flag = true;
                        break;
                    }else if(a[i + 1] == 0 && a[i] > rst.top()){
                        b[i] = -1; rst.push(a[i]);
                        for(int j = i + 1; j <= n; j++){
                            if(a[j] == 0) b[j] = rst.top(), rst.pop();
                            else b[j] = a[j];
                        }
                        flag = true;
                        break;
                    }else b[i] = a[i];
                }else{
                    int tmp = rst.top();
                    if(lst[i].val < tmp){
                        b[i] = lst[i].val;
                        for(int j = i + 1; j <= n; j++){
                            if(j == lst[i].pos) b[j] = -1;
                            else{
                                if(a[j] == 0) b[j] = rst.top(), rst.pop();
                                else b[j] = a[j];
                            }
                        }
                        flag = true;
                        break;
                    }else b[i] = tmp, rst.pop();
                }
            }
            if(!flag) b[n] = -1;
            for(int i = 1; i <= n; i++) if(b[i] != -1) printf("%d ",b[i]);
            printf("\n");
    }
    return 0;
}