题解 P6853 【station】

· · 题解

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;
}