【例2-1】周末舞会

题目描述

男队 $m$ 人、女队 $n$ 人，编号为初始位置 $1..m$ 与 $1..n$ 。每支舞曲取两队队头各一人配成一对，配完的两人立刻回到各自队尾，共跳 $k$ 支舞曲。输入：第一行 $m$ $n$ ，第二行 $k$ （ $m, n, k \le 100$ ）。输出： $k$ 行，每行为「男队编号女队编号」。样例：输入 4 6 换行 7，输出 1 1、2 2、3 3、4 4、1 5、2 6、3 1。

思路

出队者立刻回到队尾，队伍的内容从不改变，只是整体轮转，所以第 $i$ 支舞曲两队的出场编号分别是两条循环序列 $1..m$ 与 $1..n$ 。于是第 $i$ 支配对就是 $((i-1) \bmod m)+1$ 与 $((i-1) \bmod n)+1$ ，循环 $k$ 次直接输出，时间 $O(k)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 05:44
# update_at: 2026-09-30 05:44

import sys
from collections.abc import Iterator
from itertools import cycle, islice


def dance_lines(men_count: int, women_count: int, dances: int) -> Iterator[str]:
    """产出前 dances 支舞曲的配对行「男生号 女生号」。

    队头出队、同一个人再排回队尾，在编号上就是 1, 2, ..., 人数, 1, 2, ...
    无限循环；两支队伍的出队序列各是一个 cycle，逐支舞曲并排配对即可。
    """
    men = cycle(range(1, men_count + 1))      # 男队队头序列
    women = cycle(range(1, women_count + 1))  # 女队队头序列
    return islice(map('{} {}'.format, men, women), dances)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    men_count, women_count = next(data), next(data)
    dances = next(data)  # 舞曲数目
    sys.stdout.write('\n'.join(dance_lines(men_count, women_count, dances)) + '\n')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:01
 * update_at: 2026-10-05 10:01
 */
// roj 1332 【例2-1】周末舞会
#include <iostream>
using namespace std;

typedef long long ll;

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

    ll men_count, women_count, dances;
    cin >> men_count >> women_count;
    cin >> dances;

    // 出队者立刻回到队尾，队伍只是整体轮转，
    // 所以第 i 支舞曲的出场编号就是两条长度分别为 m、n 的循环序列。
    for (ll i = 1; i <= dances; i++) {
        ll man = (i - 1) % men_count + 1;     // 男队队头编号
        ll woman = (i - 1) % women_count + 1; // 女队队头编号
        cout << man << ' ' << woman << '\n';
    }
    return 0;
}

【例2-1】周末舞会

目录

题目描述

思路

参考代码