自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 22:24:36，当前版本为作者最后更新于2020-10-06 22:51:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upd on 2020/10/14

被hack后修正了疏漏

一道相当有思维含量的构造题，让我找回了昔日做毒瘤数学题的感觉

这道题的计分方式其实就在提醒我们：不要一上来就想找到最优方案，先把一种合法的构造方案找出来把部分分拿到手再去考虑优化。

如果你也像我一样在草稿纸上写写画画了好久，就会发现第2条限制和第3条限制是很难同时满足的，至少我随缘画了十几次都没试出来（。这个时候就要有意识地先满足一个限制，再不断向另一个限制靠拢。我们先来看一下限制3：

为了保证交通顺畅，对于任意两条不同线路 $i,j(i \not = j)$，都存在第三条线路 $k (k \not = i, k \not = j)$，使得 $k$ 与 $i,j$ 均关联。

换句话说，就是任选两条线路，一定有另一条线路“横跨”在它们中间，但是要注意，这条“横跨”的线路与我们所选出的两条线路中的任意一条的组合也要满足限制3。这卡死了很多看起来可行的方案，因为如果你为了让这条“横跨”的线路与原本的两条线路之间的组合也满足限制3而不断“引入”新线路，一定会走向穷途末路，毕竟每“引入”一条新线路就会多出好多组新的限制要满足╮(╯▽╰)╭。

说这么多，其实就是想揭示一个道理：我们的方案应该是由多个“元结构”拼接而成的。每个“元结构”自身就是一个合法的方案（尽管线路条数不一定等于 $n$，但一定满足那三条限制），通过某种方式拼接起来后得到的整体也是一个合法的方案。比如说以下两个就是“元结构”（图有点粗糙，还请谅解QAQ）：

第一个显然不如第二个优秀。而对于第二个，我们很容易就能找到一种拼接方式：

（什么？你问我元结构中间那条线路哪去了？当然是被用来保证限制3了qwq）

这种方案简明易懂，尤其要注意的是下面那条最长的线路，这条线路的存在使得限制3一定被满足。这种方案的点数为 $n-1$。如果 $n$ 为偶数的话需要再添加一条经过上面那些点的线路，因此点数为 $n-2$。能拿到76分。

但是很显然这不是最优的，因为上面那一行点还没有达到承载的极限（每个点只有2条线路经过）。如果每个点能承载3条线路的话，点数将减小很多，因此就有了下面的构造方案（这实际上也是一个“元结构”）qwq：

这种方案里每5个点组成的元结构中有6条线路，我们只需要大概 $\frac{5}{6}(n-1)$ 个点，交上去，满分！

代码如下（码字不易，希望能给个赞QAQ）：

#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

vector<int> g;//g用来存储最下面那条线路 

int main(){
	int n=read(),k=(n-1)/6,ans=k*5,t=(n-1)%6,a,b,c,d,e;
	if(n==3){//注意当n等于3时最下面那条线路只会有1个车站，就会WA掉，特判一下就好了 
		puts("2\n2 1 2\n2 1 2\n2 1 2");
		return 0;
	} 
	//由于n-1不一定被6整除，因此在处理完前k个元结构后需要对剩下的t条线路进行特殊处理。 
	switch(t){
		case 1:ans+=2;break;
		case 2:ans+=2;break;
		case 3:ans+=3;break;
		case 4:ans+=4;break;
		case 5:ans+=5;break;	
	}
	cout<<ans<<endl;
	fo(i,1,k){
		a=(i-1)*5+1,b=a+1,c=b+1,d=c+1,e=d+1;//a,b,c,d,e是元结构里的五个顶点 
		printf("2 %d %d\n",a,d);
		printf("2 %d %d\n",a,d);
		printf("2 %d %d\n",b,d);
		printf("2 %d %d\n",b,e);
		printf("2 %d %d\n",c,e);
		g.push_back(a);g.push_back(b);g.push_back(c);
		if(t==1&&i==k){ 
			printf("2 %d %d\n2 %d %d\n",e+1,e+2,e+1,e+2);g.push_back(e+1);
			goto H;
		}
		printf("2 %d %d\n",c,e);
	}
	a=k*5+1,b=a+1,c=b+1,d=c+1,e=d+1;
	switch(t){
		//case 1:printf("2 %d %d\n",a,b);g.push_back(a);break;
		case 2:printf("2 %d %d\n2 %d %d\n",a,b,a,b);g.push_back(a);break;
		case 3:printf("2 %d %d\n2 %d %d\n2 %d %d\n",a,b,a,b,b,c);g.push_back(a);g.push_back(c);break;
		case 4:printf("2 %d %d\n2 %d %d\n2 %d %d\n2 %d %d\n",a,b,a,b,c,d,c,d);g.push_back(a);g.push_back(c);break;
		case 5:printf("2 %d %d\n2 %d %d\n2 %d %d\n2 %d %d\n2 %d %d\n",a,b,a,b,b,c,c,d,d,e);g.push_back(a);g.push_back(c);g.push_back(e);break;	
	}
	H:
	int s=g.size();
	cout<<s<<" ";
	fo(i,0,s-1) printf("%d ",g[i]); 
	return 0;
}