NordicOI 2024 T2

Question

题目描述
题目译自 NordicOI 2024 T2 「Anime Shops」

考虑一个有 n 名玩家和 n 把椅子的游戏。椅子将被排列成一个圆圈，每个玩家将坐在一把椅子上。游戏中还会有一次铃声响起，次数不定。

每把椅子都有一个从 1 到 n 的整数，表示当铃声响起时，坐在椅子上的玩家必须顺时针移动的步数。如果铃声响起后每把椅子都正好有一个玩家，则椅子的排列是合法的。

你的任务是找到一个合法的椅子排列，或者判断没有这样的排列。

输入格式
第一行包含一个整数 t，表示输入数据的组数。接下来每两行描述了一组输入数据。每组数据第一行包含一个整数 n。第二行包含整数 s_1,s_2,\dots,s_n，表示椅子上的数字。

输出格式
对于每个测试用例，如果存在合法的椅子排列，则首先输出 YES，否则输出 NO。如果答案是 YES，还要输出一个可能的顺时针排列。如果有几个合法的排列，你可以输出其中的任何一个。

样例
输入
3
4
1 1 1 1
4
1 1 1 2
5
4 1 2 1 2
输出
YES
1 1 1 1
NO
YES
2 4 1 1 2

Answer 1

晚上好🌙🌙🌙
本答案参考通义千问

题目分析

题目要求我们找到一种合法的椅子排列方式，使得每次铃声响起时，每个玩家都能恰好移动到下一个位置。具体来说，给定一个整数 n 和一个长度为 n 的数组 s，我们需要检查是否存在一种排列方式，使得对于任意一个玩家，他按 s[i] 称的步数移动后能够恰好移动到下一个位置。

解题思路

1. 合法性检查：

   • 首先，我们需要检查是否所有椅子的步数之和能被 n 整除。因为每轮铃声后每个椅子上都应该有一个玩家，所以步数之和必须是 n 的倍数。

2. 构造排列：

   • 如果步数之和能被 n 整除，我们可以通过模拟的方式来验证是否存在合法的排列。
   • 我们可以使用一个循环队列来模拟玩家的移动过程，确保每个玩家最终能回到自己的位置。

伪代码

function is_valid_permutation(n, steps):
    total_steps = sum(steps)
    
    if total_steps % n != 0:
        return False
    
    # Initialize a list to track the current position of each player
    positions = [0] * n
    
    for i in range(n):
        positions[(positions[i] + steps[i]) % n] += 1
    
    for count in positions:
        if count != 1:
            return False
    
    return True

function solve():
    read number of test cases t
    for each test case:
        read n and the array of steps
        if is_valid_permutation(n, steps):
            print "YES"
            print one possible permutation (can be generated by the above function)
        else:
            print "NO"

Python 代码实现

def is_valid_permutation(n, steps):
    total_steps = sum(steps)
    
    if total_steps % n != 0:
        return False, None
    
    # Initialize a list to track the current position of each player
    positions = [0] * n
    next_positions = [0] * n
    
    for i in range(n):
        next_positions[(i + steps[i]) % n] += 1
    
    for count in next_positions:
        if count != 1:
            return False, None
    
    return True, next_positions

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    index = 0
    t = int(data[index])
    index += 1
    
    results = []
    for _ in range(t):
        n = int(data[index])
        index += 1
        steps = list(map(int, data[index:index+n]))
        index += n
        
        valid, perm = is_valid_permutation(n, steps)
        if valid:
            results.append("YES")
            results.append(" ".join(map(str, perm)))
        else:
            results.append("NO")
    
    print("\n".join(results))

# Example usage:
# solve()

测试样例解释

• 输入:

  3
  4
  1 1 1 1
  4
  1 1 1 2
  5
  4 1 2 1 2
  

• 输出:

  YES
  1 1 1 1
  NO
  YES
  2 4 1 1 2
  

代码解释

1. is_valid_permutation 函数:

   • 计算所有步数的总和，并检查是否能被 n 整除。
   • 使用一个辅助数组 next_positions 来记录每个位置上玩家的数量，确保每个位置只有一个玩家。

2. solve 函数:

   • 读取输入数据。
   • 对每个测试用例调用 is_valid_permutation 函数，判断是否存在合法的排列。
   • 如果存在合法排列，输出 YES 并输出一个可能的排列；否则输出 NO。

通过上述方法，我们可以有效地解决这个问题，并处理多个测试用例。