省选武汉联测 13 题解

省选模拟赛俩构造一交互挺 nm 逆天。赛后题解区就一句 Surprise!!! 没题解也挺 nm 逆天。那建议组题人的马先消失一下。

这时候就体现学长博客的重要性了。搜关键词搜到三个：yspm，房屋，Max。膜拜以上大师。

然后犇犇里在倡议把某人踢出歌单。保持中立。

构树

签到题。\(O(n^2)\) 枚举点，能连就连。容易证明贪心是对的。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int n,fa[1010],a[1010],b[1010];
int g[1010][1010];
vector<pair<int,int> >v;
int find(int x){
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    g[x][y]=g[y][x]=1;
    if(x>y)swap(x,y);
    if(find(x)==find(y))return;
    v.push_back(make_pair(x,y));
    fa[find(x)]=find(y);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        if((find(a[i])==find(i)&&!g[a[i]][i])||(find(b[i])==find(i)&&!g[b[i]][i])){
            puts("-1");return 0;
        }
        merge(i,a[i]),merge(i,b[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(find(i)==find(j))continue;
            if(a[i]<=j&&j<=b[i]&&a[j]<=i&&i<=b[j])merge(i,j);
        }
    }
    if(v.size()!=n-1){
        puts("-1");return 0;
    }
    for(pair<int,int>p:v)printf("%d %d\n",p.first,p.second);
    return 0;
}

交互

赛时读错题了。怎么读错的和你一样。问了一圈一车读错的。

读对题了其实好像不难。

首先显然 \(1\) 号节点没左儿子。设确定了 \(1\sim i-1\) 节点的子树，那么对于 \(i\) 节点：

1. 有右儿子：此时知道左端点是自己，向下递归。
2. 没有右儿子：知道了所有的左边子树，那么可以直接连上左儿子返回这个子树。

代码很短。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include "interact.h"
using namespace std;
int solve(int rt,int L,int &R){
    R=rt;
    if(query(rt,L,R))return rt;
    for(int ls=0,rs;;ls=rs){
        rs=solve(R+1,rt+1,R);
        if(ls)report(ls,rs);
        if(query(rt,L,R)){
            report(rt,rs);
            return rt;
        }
    }
}
void guess(int n){
    int R=0;
    for(int ls=0,rs;R<n;ls=rs){
        rs=solve(R+1,1,R);
        if(ls)report(ls,rs);
    }
}

构图

场上就嗯想不到。还是菜的真实。

枚举度数 \(k\) 的点的个数，然后贪心往后连度数最小的点。剩下的度数不是 \(k\) 的点如果度数不到 \(k+1\) 就内部连边。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n,k,d[1010];
vector<pair<int,int> >g;
queue<int>q;
void solve(int i){
    vector<pair<int,int> >ret;
    for(int j=i+1;j<=n;j++)q.push(j),d[j]=0;
    for(int j=1;j<=i;j++){
        for(int cnt=1;cnt<=k;cnt++){
            int x=q.front();q.pop();d[x]++;q.push(x);
            ret.push_back(make_pair(x,j));
        }
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        if(d[x]+q.size()<=k)return;
        while(d[x]<=k){
            int y=q.front();q.pop();
            d[x]++;d[y]++;q.push(y);
            ret.push_back(make_pair(x,y));
        }
    }
    if(g.empty()||ret.size()<g.size())swap(g,ret);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n-k;i++)solve(i);
    printf("%d\n",(int)g.size());
    for(pair<int,int>p:g)printf("%d %d\n",p.first,p.second);
    return 0;
}