标签：ch int mex res2 集合 Day dp

Day 3

T1

考试思路就是拿出来最大的 \(mex\) 记为 \(Max\)

然后拿出来产生此 \(mex\) 的集合

剩下的数里面还能再拿出来一个目前最大的 \(mex\)

然后从 \(0 - mex\) 中枚举，看哪个和前面的 \(Max\) 异或出来最大

继续删掉产生此 \(mex\) 的集合，然后重复即可

数据比较水，无需重复就能过，重复三十次可基本挡掉 \(hack\)

代码：

#include <bits/stdc++.h>
#define ll long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
void file(){freopen("mexor.in", "r", stdin);freopen("mexor.out", "w", stdout);}
const int maxn = 1000006;
int n, a[maxn], cnt[maxn];
int ans = 0, res1;
void work(int tim)//重复消减
{
    if(tim == 0)return ;
    int res2 = 0;
    while(cnt[res2])
    {
        ans = max(ans ,res1 ^ (1 + res2));
        ++ res2;
    }//找到那个消减后与最初的异或最大值
    for(int i = 0; i <= (res1 ^ ans) - 1; ++ i)-- cnt[i];
    res1 = ans;
    work(-- tim);
}
int main()
{
    //file();
    n = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read(), ++ cnt[a[i]];
    res1 = 0;
    while(cnt[res1]) -- cnt[res1], ++ res1;//找最初的Mex
    ans = res1;
    work(30);
    cout << ans << '\n';
    return 0;
}

插个字防止vscode又卡bug

T2

赛时冲了一坤时导致后面T3没打暴力，爆了

“你最大的希望或许是你最大的羁绊”

赛时写的 \(60pts\) 的链，但是读错题了，给他完全转化成了一个序列问题，而实际上是子树。

所以对于每一个被匹配上的黑子，一定是由他的父亲白子匹配而来

白子深度固定，最小化到黑子深度之和：

• 从小到大枚举黑子，找未匹配的最深白子，并查集实现

T3

T2冲了俩个半点，T3没时间拿 \(Dij\) 暴力

题解没看懂

T4

赛时看了一眼溜了

正解 dp:

$ dp_{i, j, S}$ 表示走 \(S\) 部分，\(i\) 进 \(j\) 出，路径最小值

\[dp_{i, j, S} = min_{x, y}(dp_{i, x, S'} + dp_{y, j, S''} + dis_{x, y}) \]

\(O(n^4)\)

优化， 固定 \(x\)

\[dp_{x, j, S''} = dp_{y, j, S''} + dis_{x, y} \]

再改一个 \(dp\) 状态， \(S\) 这个集合中，走这个集合前最后一个点为 \(i\) ，从这个集合的 \(j\) 中出来

转移方程：

\[dp_{i, j, S} = min_{x, y}(dp_{i, x, S'} + dp_{x, j, S''}) \]

剩下待补

标签：ch,int,mex,res2,集合,Day,dp
From： https://www.cnblogs.com/qinzh/p/17739357.html