题解

题面描述

给定一个正整数 $m$和 $m$ 条链表，每条链表由若干数字构成，并且同一条链表中任一数字 $n$ 都满足计算公式 $\text{key} = (2 \times n + 1) \mod m$ 得到的关键字均相同。这 $m$ 条链表初始时已按“链表长度从小到大排序（若长度相同则关键字小的排前）”排列。

随后，给出两个数字 $x$ 和 $y$ ，要求对所有“尾数”为 $x$（即数字的个位数字等于$x$的元素执行更新操作：将该元素加上 $y$ 。更新后，重新计算其关键字： $\text{new\_key} = (2 \times (n+y) + 1)\mod m$ 若新关键字与原链表的关键字相同，则直接在原位置更新数字；否则，从原链表中删除该元素，并将更新后的数字插入到新链表的尾部。插入后依然要求每个链表中所有数字关键字相同。最后，所有链表按照“元素个数从小到大排列（若个数相同则关键字小的排前）”输出，每条链表一行。

解题思路

1. 存储与标识链表
   题目给出的 $m$ 行数字，每一行的第一个数字可以计算出该链表对应的关键字，故可将每条链表存为一个结构体，包含字段：

   • key：该链表的关键字。
   • data：存放链表中各个数字的数组（或 vector）。

2. 更新操作
   遍历每条链表中的所有元素：

   • 对于每个数字 $n$，判断其个位数字是否等于 $x$（即 $n$）。
   • 若不满足条件，则不变；若满足，则令 $n_{\text{new}} = n + y$ ，再计算新关键字：

$new_{key} = (2 * n_{new} + 1)mod m$

• 如果新关键字与当前链表的 key 相同，则直接将数字更新为 $n_{\text{new}}$（在原位置更新，不改变顺序）。
• 如果新关键字不同，则将该元素从当前链表中删除，并追加到目标链表（关键字为 new_key）的尾部。注意追加的顺序需要保持“插入到链表末尾”的要求。

3. 链表重新排序
   更新完成后，由于各链表的元素个数可能发生变化，需要将所有链表按照“元素个数从小到大排列；若个数相同，则关键字较小的排前”进行排序，最后按行输出每个链表中的数字。

cpp

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 定义结构体表示一条链表，包含关键字和数据数组
struct Chain {
    int key;              // 链表的关键字
    vector<int> data;     // 存储链表中的所有数字
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m;
    cin.ignore();  // 忽略行末换行符

    // 用一个 vector 保存 m 条链表
    vector<Chain> chains;
    chains.reserve(m);

    // 为了方便查找目标链表，将 key 和链表的对应关系记录下来
    // 先读取 m 行链表数据
    for (int i = 0; i < m; i++) {
        string line;
        getline(cin, line);
        if(line.empty()) { i--; continue; } // 处理可能的空行

        // 使用 stringstream 分割每行数字
        stringstream ss(line);
        vector<int> nums;
        int num;
        while(ss >> num){
            nums.push_back(num);
        }
        // 根据第一个数字计算链表关键字
        int key = (2 * nums[0] + 1) % m;
        chains.push_back({key, nums});
    }
    
    // 读取最后一行 x 和 y
    int x, y;
    cin >> x >> y;
    
    // 创建一个临时容器记录目标链表待追加的数字
    // 下标对应关键字
    vector<vector<int>> appended(m);
    
    // 对每个链表进行遍历更新
    for (auto &chain : chains) {
        vector<int> newData;  // 存放更新后仍留在本链表的元素
        // 遍历当前链表中的每个数字
        for (int n : chain.data) {
            // 判断是否满足尾数为 x（即个位数字）
            if(n % 10 == x) {
                int updated = n + y; // 更新后的值
                int newKey = (2 * updated + 1) % m; // 更新后的关键字
                // 若更新后关键字不变，则在本链表更新
                if(newKey == chain.key){
                    newData.push_back(updated);
                } else {
                    // 否则，将该数字从本链表删除，并追加到目标链表末尾
                    appended[newKey].push_back(updated);
                }
            } else {
                // 不满足条件的数字原样保留
                newData.push_back(n);
            }
        }
        // 更新本链表数据
        chain.data = newData;
    }
    
    // 将每个链表待追加的数字追加到链表末尾
    for (auto &chain : chains) {
        chain.data.insert(chain.data.end(), appended[chain.key].begin(), appended[chain.key].end());
    }
    
    // 对所有链表按照“元素个数从小到大排序；若个数相同则关键字较小的排前”排序
    sort(chains.begin(), chains.end(), [](const Chain &a, const Chain &b) {
        if(a.data.size() == b.data.size())
            return a.key < b.key;
        return a.data.size() < b.data.size();
    });
    
    // 输出所有链表，每条链表中的数字以空格分隔
    for (auto &chain : chains) {
        for (int i = 0; i < chain.data.size(); i++){
            cout << chain.data[i];
            if(i < chain.data.size()-1) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

python

# 读取输入
m = int(input())
chains = []  # 用于存放每条链表，存储形式为字典：{'key': key, 'data': [数字列表]}

# 读取 m 行链表数据
for _ in range(m):
    line = input().strip()
    # 跳过空行（若有）
    if not line:
        continue
    nums = list(map(int, line.split()))
    # 根据第一数字计算关键字 (2*n+1)%m
    key = (2 * nums[0] + 1) % m
    chains.append({'key': key, 'data': nums})

# 读取最后一行 x 和 y
x_y = input().split()
x, y = int(x_y[0]), int(x_y[1])

# 建立一个字典记录目标链表待追加的元素，key 为链表关键字
appended = {i: [] for i in range(m)}

# 对每个链表进行遍历更新
for chain in chains:
    new_data = []  # 存放更新后依然留在本链表的元素
    for n in chain['data']:
        # 判断数字尾数（个位）是否为 x
        if n % 10 == x:
            updated = n + y            # 更新后的值
            new_key = (2 * updated + 1) % m  # 更新后的关键字
            if new_key == chain['key']:
                # 关键字不变，直接更新
                new_data.append(updated)
            else:
                # 否则，从本链表删除，添加到目标链表末尾
                appended[new_key].append(updated)
        else:
            new_data.append(n)
    chain['data'] = new_data

# 将待追加的元素追加到各自链表末尾
for chain in chains:
    chain['data'].extend(appended[chain['key']])

# 对所有链表排序：先按照链表长度，从小到大；若长度相同则关键字小的排前
chains.sort(key=lambda ch: (len(ch['data']), ch['key']))

# 输出每条链表，数字之间以空格分隔
for chain in chains:
    print(" ".join(map(str, chain['data'])))

java

import java.util.*;
import java.io.*;

public class Main {
    // 定义一个类表示一条链表
    static class Chain {
        int key;              // 链表关键字 (由 (2*n+1)%m 得到)
        ArrayList<Integer> data;  // 存放链表中的数字
        
        public Chain(int key, ArrayList<Integer> data) {
            this.key = key;
            this.data = data;
        }
    }
    
    public static void main(String[] args) throws IOException {
        // 建立输入流
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine().trim());
        
        ArrayList<Chain> chains = new ArrayList<>();
        
        // 读取 m 行链表数据
        for (int i = 0; i < m; i++) {
            String line = br.readLine();
            // 若遇到空行，继续读取
            while(line.trim().isEmpty()){
                line = br.readLine();
            }
            String[] parts = line.trim().split("\\s+");
            ArrayList<Integer> nums = new ArrayList<>();
            for (String s : parts) {
                nums.add(Integer.parseInt(s));
            }
            // 根据第一个数字计算关键字
            int key = (2 * nums.get(0) + 1) % m;
            chains.add(new Chain(key, nums));
        }
        
        // 读取最后一行 x 和 y
        String[] lastLine = br.readLine().trim().split("\\s+");
        int x = Integer.parseInt(lastLine[0]);
        int y = Integer.parseInt(lastLine[1]);
        
        // 建立一个 List 数组，用于记录目标链表待追加的元素，下标对应链表关键字
        ArrayList<Integer>[] appended = new ArrayList[m];
        for (int i = 0; i < m; i++) {
            appended[i] = new ArrayList<>();
        }
        
        // 遍历每个链表，进行更新操作
        for (Chain chain : chains) {
            ArrayList<Integer> newData = new ArrayList<>();
            for (int n : chain.data) {
                // 判断数字的个位是否等于 x
                if(n % 10 == x) {
                    int updated = n + y; // 更新后的值
                    int newKey = (2 * updated + 1) % m; // 更新后的关键字
                    if(newKey == chain.key){
                        // 关键字未变，直接更新
                        newData.add(updated);
                    } else {
                        // 否则，从本链表中删除，添加到目标链表末尾
                        appended[newKey].add(updated);
                    }
                } else {
                    newData.add(n);
                }
            }
            chain.data = newData;
        }
        
        // 将各链表待追加的元素追加到链表末尾
        for (Chain chain : chains) {
            chain.data.addAll(appended[chain.key]);
        }
        
        // 对所有链表排序：先按照元素个数，从小到大；若个数相同则关键字较小的排前
        Collections.sort(chains, new Comparator<Chain>() {
            public int compare(Chain a, Chain b) {
                if(a.data.size() == b.data.size()){
                    return a.key - b.key;
                }
                return a.data.size() - b.data.size();
            }
        });
        
        // 输出结果，每条链表占一行，数字之间空格分隔
        StringBuilder sb = new StringBuilder();
        for (Chain chain : chains) {
            for (int i = 0; i < chain.data.size(); i++) {
                sb.append(chain.data.get(i));
                if(i < chain.data.size()-1) {
                    sb.append(" ");
                }
            }
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }
}

题目内容

给定一个数字 $m$ ，将一堆数字中的每一个按值(假定值为 $n$ )进行运算分成 $m$ 类，运算公式为 $(2*n+1)$%m ，算出结果值为关键字。相同关键字的数字组成一个链表，所以共有 $m$ 条链表，每条链表中的值占据一行，根据 $m$ 条链表的元素个数从小到大顺序排列(个数相同时，关键字小的排在前面)，先假定对于一个给定满足上述条件的数字已按规则排列完全后，在此基础上做一项操作，即把所有尾数是 $x$ 的值 $n$ 加上一个值 $y$ ,调整链表组成，插入的元素要求放在链表的末尾，使得变化后的链表依然满足上述条件，具体满足如下两点：

(1) 同一个链表中的元素值关健字一样

(2) 链表间的排列顺序：按元素个数从小到大排列(个数相同时，关键字小的排在前面)

调整链表组成时，如果让放到原链表，则只更新值即可，而且不需要调整顺序(即：不需要移动到链表末尾)。只有调整到其他链表时才需要。

输入描述

输入第一行是数字 $m$ ,接下来的 $m$ 行数字，用 $n$ 表示每一行的任一个数字，那么这一行按 $(2*n+1)$ 计算结果都一样，且已经按长度排序好，最后一行由两个数组组成 x y，表示对尾数是 $x$ 的元素值增加 $y$ ，$0<m≤10,0< n＜100, 0＜x, y≤100$

输出描述

满足上述条件调整后的 $m$ 个链表

样例1

输入

3
7 13
11 17 8
12 9 27 15
7 30

输出

37 13
11 47 8
12 9 57 15

说明

$m$ 值为 $3,3$ 条链表值已分类好，将尾数为 $7$ 的值加 $30$ 后，发生如下变化：

$7->37,17->47,27->57$ 关键字均不变，只需要修改原先的元素值

样例2

输入

3
7 13
11 17 8
12 9 27 15
5 2

输出

7 13
12 9 27
11 17 8 17

说明

$m$ 值为 $3,3$ 条链表值已分类好，将尾数为 $5$ 的值加 $2$ 后，发生如下变化：$15->17$ ,关键字由 $1$ 变为 $2$ ，$15$ 从原来位置删除，$17$ 插入新位置，同时链表长度变化，需要变化输出顺序