花菖蒲 2025.7.26 模拟赛题解
观察样例可知：
在一度点上连一条边可使一度点数量不变。
在一度点上连两条边可使一度点数量加一，三度点数量加一。
在三度点上连一条边可使三度点数量减一，一度点数量加一。
在大于三度的点上连一条边可使一度点数量加一
当a-b<2时无解
对于a<=3&&b<=1时进行特判
对于a>3&&b==0时进行直接输出
所以就可以发现正解是一个二叉树（根为三度点/三个儿子）+一个菊花图
代码
#include<bits/stdc++.h>
using namespace std;
bool tr[410][410];//存图
bool sd[410],yd[401];//存三度点，一度点
int main()
{freopen("irises.in", "r", stdin);freopen("irises.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int a,b;cin>>a>>b;//特判if(a==0&&b==0){cout<<1<<endl;return 0;}if(a==1&&b==0){cout<<2<<endl;cout<<1<<" "<<2<<endl;return 0;}if(a==2&&b==0){cout<<3<<endl;cout<<1<<" "<<2<<endl;cout<<1<<" "<<3<<endl;return 0;}if(a==3&&b==0){cout<<0<<endl;return 0;}if(a-b<2){cout<<0<<endl;return 0;}if(a==3&&b==1){cout<<4<<endl;cout<<1<<" "<<2<<endl;cout<<1<<" "<<3<<endl;cout<<1<<" "<<4<<endl;return 0;}if(a>3&&b==0){cout<<a+1<<endl;for(int i=2;i<=a+1;i++){cout<<1<<" "<<i<<endl;}return 0;}int siz=4;//使用过的点，用于输出int o=3,t=1;//从一度点数量是3，三度点数量是1开始加边tr[1][2]=1,tr[1][3]=1,tr[1][4]=1;//连边sd[1]=1;//1为三度点yd[2]=1,yd[3]=1,yd[4]=1;//2,3,4为一度点int yds=2;//最小的一度点，用于建树int lb=1;//非叶子节点的最大点，用于输出while(o<a&&t<b)//当没有条件满足时{siz++;tr[yds][siz]=1,yd[siz]=1;siz++;tr[yds][siz]=1,yd[siz]=1;//在最小的一度点上连两条边lb=yds;yd[yds]=0,sd[yds]=1;yds++;o++,t++;//更新}if(o!=a)//需要连一个菊花图{if(a-o==1)//无法建成的情况，可以尝试自己手推一下{cout<<0<<endl;return 0;}siz++;tr[yds][siz]=1,yd[siz]=1;siz++;tr[yds][siz]=1,yd[siz]=1;//因为此时三度点的数量足够，要添加一度点lb=yds; //所以要先在三度点上连一条边使其生成一个多度点方便构建菊花图yd[yds]=0,sd[yds]=1; //但会使三度点数量减一，就在构建菊花图之前再多建一个三度点yds++;o++;//创建三度点时多建了一个一度点while(o<a)//构建菊花图{siz++;tr[1][siz]=1,yd[siz]=1;o++;}}//输出cout<<siz<<endl;for(int i=1;i<=lb;i++){for(int j=1;j<=siz;j++){if(tr[i][j]==1){cout<<i<<" "<<j<<endl;}}}return 0;
}