【考试总结】2022-04-04
构树
给定的边是一定存在的，先连上
剩下的枚举不在联通块的两个点是不是能连边，能就连
如果出环或者到最后都不能联通就是无解
Code Display
const int N=1010;
int n,l[N],r[N];
vector >edge;
struct DSU{
int fa[N];
inline void init(int n){rep(i,1,n) fa[i]=i; return ;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){fa[find(x)]=find(y); return ;}
}Dsu;
map mp[N];
inline void ins(int x,int y){
mp[x][y]=1;
mp[y][x]=1;
edge.emplace_back(x,y);
Dsu.merge(x,y);
}
signed main(){
freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
n=read(); Dsu.init(n);
rep(i,1,n){
l[i]=read(),r[i]=read();
if(!mp[i].count(l[i])){
if(Dsu.find(l[i])==Dsu.find(i)) puts("-1"),exit(0);
ins(i,l[i]);
}
if(!mp[i].count(r[i])){
if(Dsu.find(r[i])==Dsu.find(i)) puts("-1"),exit(0);
ins(i,r[i]);
}
}
for(int i=1;i<=n;++i){
for(int j=l[i]+1;j 交互
\(\text{key observation}\) 是 \(1\) 号节点没有左儿子，那么可以从 \(1\) 开始不断迭代：
-
如果当前节点没有右子树，那么这个子树被确定，此时已知结构区间 \(1,i\) 的根的父亲是 \(i+1\) ，继续迭代
-
如果当前节点有右子树，右子树左端点确定，是一个子问题，递归求子树进行迭代
打字的时候 交 点出了 JOI ，不知道这是不是清明节的冥冥之中
Code Display
#include "interact.h"
using namespace std;
int n;
inline int solve(int L,int rt,int &R){
R=rt;
if(query(rt,L,R)) return rt;
for(int lst=0,nxt;;lst=nxt){
nxt=solve(rt+1,R+1,R);
if(lst) report(lst,nxt);
if(query(rt,L,R)) return report(rt,nxt),rt;
}
}
void guess(int N){
n=N;
int nxt,r=0;
for(int lst=0;r构图
枚举有多少点的度数是 \(k\) ，由于不能相邻，所以每次找到当前其它点中度数最小的点连边即可
对于度数超过 \(k\) 的点中完成连边且度数仍然不够的就自行连边即可，由于 \(n\le 1000\) 所以可以通过
Code Display
int n,k;
vector >ans,edge;
inline void solve(int lef){
edge.clear();
deque q;
vector deg(n+1);
for(int i=lef+1;i<=n;++i) q.push_back(i);
rep(i,1,lef){
int tmp=k;
while(tmp--){
int x=q.front(); q.pop_front();
deg[x]++;
q.push_back(x);
edge.emplace_back(x,i);
}
}
vector nds;
while(q.size()){
int x=q.front(); q.pop_front();
if(deg[x]+q.size()<=k) return ;
while(deg[x]<=k){
int y=q.front(); q.pop_front();
deg[x]++; deg[y]++;
edge.emplace_back(x,y);
q.push_back(y);
}
}
if(ans.empty()||ans.size()>edge.size()) swap(ans,edge);
}
signed main(){
freopen("graph.in","r",stdin); freopen("graph.out","w",stdout);
n=read(); k=read();
for(int i=1;i<=n-k;++i) solve(i);
if(ans.empty()) puts("Impossible"),exit(0);
cout<