题目分析我们需要安排 n 个大臣的顺序，使得获得最多金币的大臣所获得的金币数尽可能少。金币计算公式对于第 i 个大臣，其金币数为：其中 表示国王的左右手数字。贪心策略证明我们需要找到一种排序方式，使得所有大臣中金币数的最大值最小化。按 升序排列是最优策略。数学证明考虑相邻两个大臣 i 和 j，且 ，设交换前（顺序：）:大臣 i 的金币：大臣 j 的金币：交换后（顺序：j→i）:大臣 j 的金币：大臣 i 的金币：由于 ，可得：因此交换前的最大金币数为 ，交换后的最大金币数为 ，且：所以交换后最大值不会更大，按 升序排列是最优策略。代码实现 import sys def main(): inpu...

import sys def main(): input = sys.stdin.readline # 读取输入 n = int(input()) a = list(map(int, input().split())) b = list(map(int, input().split())) # 把每个位置的 (a, b, id) 打包，方便排序和选择 nodes = [[a[i], b[i], i+1] for i in range(n)] # Step1: 按 a 从大到小排序 # - 确保选择的子集在 A 上容易超过总和的一半 nodes.sort(key=lambda x: x[0], ...

📌 题目回顾有一张有向图，n 个点，m 条边。每个点要染成 黑 或 白。一条边 起点黑、终点白 → 称为核心边。要求构造一种染色，使得核心边数量不少于 m/4（题目保证存在解），并输出所有核心边编号。📌 思路回顾：条件期望法随机染色时，每条边成为核心边的概率 = P(u黑) * P(v白) = 1/2 * 1/2 = 1/4，所以期望核心边数量是 m/4。因此一定存在一种确定染色，使核心边数 ≥ m/4。做法：依次处理每个点（顺序无所谓）。假设当前点未染色，计算：如果染成黑：贡献值 = 2 * 已定为白的出边数 + 出边未定数如果染成白：贡献值 = 2 * 已定为黑的入边数 + 入边未定数...

import sys # 基础代号/安全等级M # xx-xx-xx-xx-xx-xx/M # M在[0, 48]区间内 # M=48 时，要求身份代号完全匹配 # M<48 时，只要求身份代号的前 M 位与基础代号的前 M 位相同 # M=0 时， 不匹配任何位 input = sys.stdin.readline # 授权规则的总数 n = int(input()) rules = [] for _ in range(n): code, M = input().split('/') rules.append([code, int(M)]) # 待验证的特工数量 m = int(inp...

from collections import deque import sys # 0: 数据包可以在相邻的标准通道节点之间自由移动，每次移动消耗 1 个时间单位 # 1: 防火墙，不可通行 # 2: 量子纠缠门, 瞬间、不耗费任何时间直接传送到另一个纠缠门（DFS到所有其他纠缠门？） # S: 起点 # E: 终点 def main(): input = sys.stdin.readline m, n = list(map(int, input().split())) arr = [] # 获取起点和传送门 start_pos = (-1, -1) gates = [] for i in ...

import sys # 给定整数n，总能找到满足两个非负整数 x 和 y： # 满足 x + y == n, 且 |x的数字和 - y的数字和| <= 1 # 1. n 为偶数, 则 x = y = n // 2, 数字和之差 == 0 # 2. n 为奇数, 则 x == n // 2, y == x+1 # 2.1 若 y 的个位数不为0, 数字和之差 == 1，如 x==198, y==199，可以直接返回 # 2.2 否则，需要按位划分，每一位尽可能平分到 x 和 y def get_close_xy(n_str): x_str, y_str = [], [] switch =...

import sys t = int(sys.stdin.readline()) for _ in range(t): n, l, r = map(int, sys.stdin.readline().split()) cycle = l + r # 一个完整的取石子周期 remain = n % cycle # 如果剩余石子不足l，先手无法控制局面 if remain < l: print("NO") else: print("YES") """ 设 remain = n % (l + r) 1. 若 remain &...

import sys t = int(sys.stdin.readline()) for _ in range(t): n, m = map(int, sys.stdin.readline().split()) # 判断先手A是否必胜 def check(): # 情况1：A一次性拿走所有石子 if m >= n: return True # 情况2：A先取x个石子，能使剩余为 (m+1) 的倍数 # 即 (n - x) % (m+1) == 0 ⇔ (n-1)//(m+1) > (n-m)//(m+1) # 之后无论B取 y∈[1,m]，A都取 (m+1 - y)，保持剩余为 (...

import sys t = int(sys.stdin.readline()) for _ in range(t): """ Alice先手 0: 当前玩家败 1: 取 1 → 0(败), 胜 2: 取 2 → 0(败), 胜 3: 只能取 1 → 2(胜), 败 4: 取 1 → 3(败), 胜 5: 取 5 → 0(败), 胜 6: 取 1 → 5(胜), 2 → 4(胜), 败 7: 取 1 → 6(败), 胜 8: 取 2 → 6(败), 胜 9: 只能取 1 → 8(胜), 败 """ n = int(sys.stdin....

import sys def main(): n = int(sys.stdin.readline()) if n <= 2: print(-1) # 2, 1 或 1, 2 都会出现质数 return # 将奇偶数分组，奇数放在奇数位上，偶数放在偶数位上 # 奇数 + 奇数 = 偶数；偶数 + 偶数= 偶数 # 这样能保证都不是质数 # 生成初始排列[1, 2, 3, ..., n] arr = list(range(1, n+1)) # 因此只需要特别处理第一位 1+1=2 的情况, # 将最后一个奇数与1交换 if (n & 1) == 0: arr[0], arr[n-2...

import sys def main(): n, k = map(int, sys.stdin.readline().split()) # 构造解：只在对角线上放 k，其余填 0（非负整数） arr = [[0] * n for _ in range(n)] for i in range(n): arr[i][i] = k # 输出矩阵 for row in arr: print(' '.join(map(str, row))) main()

from math import inf import sys def main(): # 读取输入 n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) # 处理特殊情况：n=1时没有合法的(i,j)对 if n == 1: print(0) return # 分析问题： # 我们需要计算所有i<j时的表达式：j^2 - i^2 + |arr[i-1]^2 - arr[j-1]^2| # 这个表达式可以分为两种情况： # 情况1：当arr[j-1]^2 >= arr[i-1...