[语言月赛202306] 纸条 题解

· · 题解

Source & Knowledge

2023 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

有 n 张纸条，根据内容的连贯性被分为若干段，给出每张纸条在其连贯内容后的纸条编号，或给出下一段内容的开头纸条编号，或者说明已经没有更靠后的纸条。给出纸条按照时间顺序排序后的编号。

题目分析

本题考察数组的运用。

经过思考可以发现：除了时间最早的纸条，即排好序后的第一张纸条以外，所有的纸条都会出现在某一张纸条的后方，也就都会被提及——如果一张处于一段连贯内容的开头，就会在前一张纸条的输入部分被提及，否则，就会在连贯内容的前面的纸条中被提及。而第一张纸条在一段连贯内容的开头，但前面已经没有纸条了，所以不会被提及。所以，可以建立一个 vis 数组判断每张纸条是否出现在输入部分中。只会有一张纸条不会出现，那张纸条就是开头。这里要注意，由于输入可能会有 -1 直接访问会因数组越界导致 RE，要特殊判断。

知道了开头就好办了。我们对每一张纸条开一个数组，从开头的纸条开始，先把它的连贯内容之后的纸条依次输出，然后，通过连贯内容最后一张纸条得到下一段连贯内容的开头，再把之后的输出……以此类推，直到发现了结束标志 -1，输出就停止。

数组的存储方式有两种，一是开一个二维数组，这样空间开销有一点大，但也没有问题。第二种方法是使用 vector 存储，能够动态申请空间，且长度可以直接查询，非常方便。这里给出使用 vector 的核心代码：

vector<int>p[2010];
bool vis[2010];

for(int i=1;i<=n;i++){
    cin >> m;
    if(m)
    for(int j=1;j<=m;j++){
        int x;
        cin >> x;
        vis[x]=1;
        p[i].push_back(x);//vector的插入
    }
    else {
        int x=read();
        if(x>0)vis[x]=1;//注意防止数组越界
        p[i].push_back(x);
    }
}
int s;
for(int i=1;i<=n;i++)if(!vis[i])s=i;//寻找起点
while(1){
    if(s==-1)return 0;//遇到终点，程序结束
    int siz=p[s].size();//这个函数指的是p[s]中的元素个数
    cout <<s<<" ";
    if(p[s][siz-1]==-1)return 0;//s是终点，程序结束
    for(int i=0;i<siz;i++)cout <<p[s][i]<<" ";//依次输出，注意 vector 的下标从0开始
    s=p[p[s][siz-1]][0];//vector 的下标从 0 开始，故最后一个元素的下标为 siz-1
}

视频题解