80901202-AGC029

B

给洛谷的题解先放到这里

首先能想到一个结论：尽可能消去更大的数时最优。

形式化的表达是：对于数 $a_j$ ，显然至多有一个 $i$ 满足 $i<j$ 且 $a_i+a_j=2^k$ ，如果不消去数对 $(a_i,a_j)$ ，则 $a_j$ 不可能被消去，最终答案不会更优。

再考虑题目中的 $2^t$ 以及 $A_i\leq 10^9$ ，则有 $a_i+a_j\leq 2^{30}$ 。

那么枚举范围内的所有 $2^t$ ，尺取法取当前符合条件的数对出来即可。

const int N=2e5+100;
int a[N],n,ans;

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(rei k=1<<30;k;k>>=1){
        rei l=1,r=n;
        while(l<r){
            if(a[l]==-1 || (~a[r] && a[l]+a[r]<k)) ++l;
            else if(a[r]==-1 || a[l]+a[r]>k) --r;
            else ++ans,a[l]=a[r]=-1;
        }
    }
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

C

$N$ 个字符串排成一排，对于 $1\leq i\leq N$ ，$S_i$ 的字典序应小于 $S_{i+1}$ ， $S_i$ 的长度为 $A_i$ ，求满足上述条件的的最小字符集的大小

答案显然能被二分出来，设字符集大小 $\sum_0$ ，判断是否能用 $\sum_0$ 使这些串的字典序递增

注意：判断有局部贪心，即，对于 $1\leq i\leq N$ ， $S_i=\Xi$ 使后面的串可以被构造，那么对于 $\forall \Xi’<\Xi$ ，若 $S_i=\Xi’$ 后面的构造仍可以被完成

$S_i$ 即为大于 $S_{i-1}$ ，长度为 $A_i$ 的最小字符串即可

考虑如何构造 $S_i$:

若 $A_{i-1}<A_i$ ，在后面补 $A_i-A_{i-1}$ 个 $a$ 即可，即 $S_i=S_{i-1}+a^{A_i-A_{i-1}}$

否则，取 $S_{i-1}$ 的一个长度 $A_i$ 的前缀，将最后一个字符向后移，即，$eg:a\rightarrow b$

这里要考虑溢出的问题，即 $z\rightarrow ?$ 此时考虑进位，即 $az\rightarrow ba$

构造每个字符串的时候，新增的非 $0$ 位置最多增加一个，$O(n\log n)$

const int N=2e5+100;
int n,a[N];
map<int,int> mp;

inline bool check(const int B){
    rei L=a[1]; bool result;
    map<int,int>::iterator it;
    mp.clear();
    for(rei i=2;i<=n;++i)
        if(a[i]<=L){
            for(L=a[i];mp.size();){
                it=--mp.end();
                if(it->first>=L) mp.erase(it);
                else if(it->first==L-1 && it->second==B-1) mp.erase(it),--L;
                else break;
            }
            if(!L) return false;
            tie(it,result)=mp.emplace(L-1,1);
            if(!result) ++it->second;
        }
        else L=a[i];
    return true;
}

int main(){
    scanf("%d",&n);
    bool flag=1;
    for(rei i=1;i<=n;++i){ scanf("%d",&a[i]); if(a[i]<=a[i-1]) flag=0;}
    if(flag) return puts("1"),0;
    rei l,r,mid;
    for(l=2,r=n;l<r;) check(mid=l+r>>1) ? r=mid : l=mid+1;
    printf("%d\n",l);
    getchar(),getchar();
    return 0;
}

E

给定一个 $n$ 顶点的树，在点 $v$ 需要回到点 $1$ ，过程中会选择并访问一个当前没有访问，但与访问过所有点相邻的点中编号最小的点，求回到点 $1$ 时经过了多少跳不同的边

首先显然有 $边数=点数-1$

设集合 $S_v$ 为 $v\rightarrow 1$ 所经过点的集合，那么显然有 $S_{fa_v}\in S_v$ ，可以考虑这两者之间的关系

设 $pmax_v$ 表示路径 $v\rightarrow 1$ 中点标号最大的点，而当 $pmax_v=v$ 时，点 $v$ 被称为极大点

考虑点 $v,fa_v$ 是否为极大点：

• $v,fa_v$ 均不是极大点：

  显然此时有 $S_v=S_{fa_v}$

• $v$ 是极大点：

  此时，显然路径 $fa_v\rightarrow 1$ 中不会经过 $subtree(v)$

  但对于路径 $v\rightarrow 1$ 来说，会经过 $v$ 的子树中那些编号小于路径中点编号的点，形式化的，会经过集合 $B_v=\{u\mid u\in subtree(v) \wedge \max(u,fa_u,fa_{fa_u},…)<pmax_{fa_v} \}$ 中所有的点

  此时有 $S_v=S_{fa_v}\cup B_v$

• $fa_v$ 是极大点

  此时，$v$ 子树中所有 $pmax_u=fa_v$ 的顶点 $u$ 都会被访问，有集合 $A_v=\{u\mid u\in subtree(v) \wedge pmax_u=v\}$ ，而对于极大点，有 $B_v\in A_v$

  那么有 $S_v=S_{fa_v}\cup \left(A_{fa_u}\cap subtree(v)\right)$

  可证明：$S_{fa_v}$ 与 $A_{fa_v}\cap subtree(v)$ 不相交，则可以直接加

直接搜就可以

const int N=2e5+100;
int head[N],Next[N<<1],ver[N<<1],tot;
int n,fa[N],A[N],B[N],pmax[N]/*极大点*/,S[N];

inline void up(int &x,const int y){ x<y ? x=y : 0;}
inline void add(const int u,const int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}

void dfs(const int x){
    rei z=pmax[x]; A[x]=B[x]=1;
    for(rei i=head[x],y;i;i=Next[i]){
        y=ver[i]; if(y==fa[x]) continue;
        fa[y]=x; up(pmax[y],z); dfs(y);
        if(y<z) A[x]+=A[y];
        if(y<pmax[ fa[z] ]) B[x]+=B[y];
    }
    if(x!=z && x>=pmax[ fa[z] ]) B[x]=0;
}

void solve(const int x){
    if(pmax[x]==x) S[x]+=B[x];//x是极大点,\cup集合B
    else if(pmax[ fa[x] ]==fa[x]) S[x]+=A[x]-B[x];//fa_x是极大点,\cup 集合A \cap集合B
    for(rei i=head[x],y;i;i=Next[i]){//对于普通的x，fa_x，S_x=S_fa_x
        y=ver[i]; if(y==fa[x]) continue;
        S[y]=S[x]; solve(y);
    }
}

int main(){
    scanf("%d",&n);
    for(rei i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    iota(pmax,pmax+1+n,0);
    dfs(1);
    B[1]=0; solve(1);
    for(rei i=2;i<=n;++i) printf("%d ",S[i]);
    puts("");
    getchar(),getchar();
    return 0;
}

F

给定 $n-1$ 个点集，从每个集合内选两个点连边，使最后形成一棵树，输出方案

考虑如何构成树：固定点 $rt$ 为根，整张图除去 $rt$ 之外的所有点和点集存在完美匹配，即：一张二分图，左边是除 $rt$ 以外的所有点，右边是点集 $E_{1\sim n-1}$ ，点 $v$ 与 $E_i$ 连边当且仅当 $u\in E_i$ ，该图存在完美匹配

但如此固定后的完美匹配不一定有解，且 $N\leq 10^5$ 无法维护 $\text{Hall}$ 定理
，故有以下构造方案：

首先固定根，得到一个匹配，设 $E_i$ 的匹配对象为 $e_i$ ，然后从所得的根 $\text{bfs}$ ，具体的，对于当前树上的点 $v$ ，寻找所有满足 $v\in E_i$ 的集合并将其对应的 $e_i$ 作为 $v$ 的子节点，如果所有顶点均被加入树种，则答案显然正确

那么，找图的完美匹配即可

const int N=1e5+100;
int n,que[N],match[N],matup[N],top=1;
vector<int> nb[N];

namespace network_flow{
    #define ad(x) ((x-1^1)+1)
    const int N=::N*2,M=::N*8;
    struct edge{
        int u,v,f;
        edge(int uu=0,int vv=0,int ff=0):u(uu),v(vv),f(ff){}
    }e[M];
    int si=1,ti=2,flow;
    int head[N],Next[M],tot;
    int depth[N],cur[N],que[N];
    inline void add(int u,int v,int f){ e[++tot]=edge(u,v,f),Next[tot]=head[u],head[u]=tot; e[++tot]=edge(v,u),Next[tot]=head[v],head[v]=tot;}
    inline bool bfs(){
        rei top=1;
        memset(depth,-1,sizeof depth);
        que[0]=si,depth[si]=0;
        for(rei h=0,x,y;h<top;++h){
            x=que[h]; if(x==ti) return true;
            for(rei i=head[x],y;i;i=Next[i]){
                y=e[i].v; if(depth[y]==-1 && e[i].f) que[top++]=y,depth[y]=depth[x]+1;
            }
        }
        return false;
    }
    int dfs(int x,int lim){
        rei f=0;
        if(x==ti || !lim) return lim;
        for(rei &i=cur[x];i;i=Next[i]){
            if(depth[ e[i].v ]==depth[x]+1 && e[i].f){
                rei a=min(lim-f,e[i].f);
                rei c=dfs(e[i].v,a);
                e[i].f-=c; e[ ad(i) ].f+=c;
                if((f+=c)==lim) return f;
            }
        }
        return f;
    }
    inline int dinic(){
        for(flow=0;bfs();flow+=dfs(si,INT_MAX)) memcpy(cur,head,sizeof cur);
        return flow;
    }
    inline int get(int x){
        for(rei i=head[x];i;i=Next[i]) if(i&1 && !e[i].f) return e[i].v;
        return -1;
    }
}

int main(){
    scanf("%d",&n);
    for(rei i=1;i<n;++i){
        network_flow::add(i+1+n,2,1);
        rei m,v; scanf("%d",&m);
        while(m--) scanf("%d",&v),nb[v].emplace_back(i),network_flow::add(v+1,i+1+n,1);
    }
    for(rei i=2;i<=n;++i) network_flow::add(1,i+1,1);
    if(network_flow::dinic()!=n-1) return puts("-1"),0;
    for(rei i=2;i<=n;++i) match[ network_flow::get(i+1)-n-1 ]=i;
    que[0]=1;
    for(rei h=0;h<top;++h){
        rei y=que[h];
        for(int s:nb[y]) if(!matup[s]) matup[s]=y,que[top++]=match[s];
    }
    if(top!=n) return puts("-1"),0;
    for(rei i=1;i<n;++i) printf(matup[i]<match[i] ? "%d %d\n" : "%2$d %1$d\n",matup[i],match[i]);
    getchar(),getchar();
    return 0;
}