祝馀宫

题面小A和小B又在通过游戏决一胜负了。 今天他们玩的游戏是这样的，小A拿出了张卡片，每张卡片上都写了一个数 $a$ 。他们每个人轮流交替取走一张卡片，直到取完，小A先取。 记小A取走的卡片的权值和为 $A$ ，小B取走的卡片的权值和为 $B$ ，则小A最终得分为 $|A|-|B|$ 。小A自然希望自己的得分最大，小B则希望其得分最小。 优策略的情况下，小A的最终得分是多少？ $n\le 1e5$ 思路不难发现，这就是一道非常经典的博弈类型的贪心题。这里有两个人，小A和小B，他们分别有着自己的决策 $A,B$ ，得分的表现形式为 $|A|-|B|$ ，所以说这是一道双变量的博弈。而处理这种问题的方法之一，就是把双变量转化为单变量。而想要把双变量转化为单变量，我们需要找到不变量。 观察题目，不难发现不变量就是所有元素之和。我们记 $sum = \sum\limits_{i=1}^n a_i$ 。那么当小A取得行动得分 $|A|$ 时，小B的分数自然是 $|sum-A|$ 。最后的答案就等价于 $|A|-|sum-A|$ 。如果我们用函数 $f(A)$ 表示结果，我们可以得到函数 $f(A) ...

题面大秦为你打开题目传送门 题目背景模板题，没有 $rap$ 。 题目描述在一片土地上有 $n$ 个城市，通过 $n-1$ 条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为 $1$，其中第 $i$ 个城市的价值为 $value_i$。 不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。 接下来你需要在线处理 $m$ 次操作： 0 x k 表示发生了一次地震，震中城市为 $x$，影响范围为 $k$，所有与 $x$ 距离不超过 $k$ 的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。 1 x y 表示第 $x$ 个城市的价值变成了 $y$ 。 为了体现程序的在线性，操作中的 $x$、$y$、$k$ 都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为 $0$ 。 输入格式第一行包含两个正整数 $n$ 和 $m$ 。 第二行包含 $n$ 个正整数，第 $i$ 个数表示 $value_i$ 。 接下来 $n-1$ 行，每行包含两个正整数 $u$、$v$，表示 $u$ 和 $v$ 之间有一条无向边。 接下来 $m$ ...

题面大秦为你打开题目传送门 题目描述Z 国有 $n$ 座城市，$(n - 1)$ 条双向道路，每条双向道路连接两座城市，且任意两座城市都能通过若干条道路相互到达。 Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件： 一座城市可以驻扎一支军队，也可以不驻扎军队。 由道路直接连接的两座城市中至少要有一座城市驻扎军队。 在城市里驻扎军队会产生花费，在编号为 $i$ 的城市中驻扎军队的花费是 $p_i$。 小 Z 很快就规划出了一种驻扎军队的方案，使总花费最小。但是国王又给小 Z 提出了 $m$ 个要求，每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言，如果国王提出的第 $j$ 个要求能够满足上述驻扎条件（不需要考虑第 $j$ 个要求之外的其它要求），则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第 $j$ 个要求无法满足，则需要输出 $-1$。现在请你来帮助小 Z。 输入格式第一行有两个整数和一个字符串，依次表示城市数 $n$，要求数 $m$ 和数据类型 $type$。$type$ ...

题面大秦为你打开题目传送门 题目描述彼得正在开发新的赌博软件。现在他正在编写一部分软件，可以处理纸牌组。为此，他需要生成从 $1$ 到 $n$ 的整数的随机排列。 不幸的是，彼得不知道这样做的好算法。所以他使用以下算法。首先初始化 $a[i] = i$ 。然后 $t$ 次选择从 $1$ 到 $n$ 的均匀随机 $i$ 和从 $1$ 到 $n$ 的随机 $j$ ，并交换 $a[i]$ 和 $a[j]$ 。 约翰了解了彼得生成随机排列的方法，并决定利用他的知识在赌场获胜。约翰想知道在彼得方法生成的排列中，哪种排列最常发生，它的概率是多少。 请帮助越好找到这个序列以及他的概率。 输入格式输入包含多组数据。 每一组数据输入一行两个整数 $n,t$ 含义如题面 $(\ 1\le n\le 14,0\le t\le 300\ )$ 。 最后一行输入两个零表示读入结束。 输出格式对于每组数据，输出两行，第一行输出出现概率最大的序列，第二行输出它出现的概率，用最简分数表示。 样例输入1233 3 3 4 0 0 样例输出12341 2 3 5/271 2 3 43/243

题面大秦为你打开题目传送门 题目描述安德鲁在圣彼得堡国立搜索大学教授算法和数据结构课程，教授信息纳米技术、力学和光学。今天，他正在为他的学生举办笔试。考试包括 $n$ 个必须解决并提交评估的任务。 安德鲁检查了所有学生的考试作业，并了解每个学生和每个任务是否解决了。现在，他想为每个任务分配积分，以便由较少的学生解决的更难的任务获得更多积分。分配给任务的分数必须加起来为 $s$ 。 形式上，设 $a_i$ 为完成第 $i$ 个任务的学生人数，设 $a_i$ 为每个 $i$ 且大于 $0$ 。安德鲁想要一些 $b_i$ ，即 $a_ib_i = c$ 对于所有 $i$ ，其中 $c$ 是常数，$\sum\limits_{i = 1}^{n}b_i = s$ 。 不幸的是，这样的 $b_i$ 可能是分数。安德鲁不喜欢分数，所以他想用最小二乘法用整数 $p_i$ 来近似 $b_i$ 。此外，安德鲁认为给某些任务打得太低或太高都是不公平的。因此，对于给定的 $L$ 和 $U$ ，每个任务的分数必须介于 $L$ 和 $U$ 之间（包括 $L$ 和 $U$ ）。 所以现在安德鲁需要找到整数值 $p ...

题面大秦为你打开题目传送门 题目描述丹正在计划一场国际塔防游戏比赛，比赛拥有如下规。 战斗场地一排的十个格子，编号从 $1$ 到 $10$ 。每一个格子都有一些塔防守卫。同时有 $10 $ 个怪物，每个怪物的生命值为 $h$ 点，游戏时常的单位为秒。在 $1$ 到 $10$ 的每一秒开始时，一个新的怪物进入第一个单元格。每个怪物都有名为 delay 的特殊参数，默认情况下它等于 $1$ 。延迟塔可以增加怪物的延迟。如果一个怪物的的延迟是 $d$ ，并且在第 $t$ 秒开始时进入其当前单元格，则它会在第 $t +d$ 秒开始时移动到下一个单元格。有三种类型的塔： 枪炮塔：每一秒攻击当前格子的怪物。如果有多个怪物，则只有一个收受到伤害，受到伤害的顺序是先来先打。一个枪炮塔需花费 $3$ 美元建造，每次对于收到攻击的每个怪物造成 $1$ 点伤害。 用字母 $\tt G$ 表示 火箭塔：每三秒攻击当前格子的所有怪物。每次对于受到攻击的每个造成 $4$ 伤害，需要 $10$ 美元建造。用字母 $\tt R$ 表示。 延迟塔：每个怪物经过的最后五个格子中的延迟塔会造成怪物的延迟增加一点。举个 ...

题面大秦为你打开题目传送门 题目描述众所周知，排序算法冒泡排序可以用如下的伪代码表示出来 12345define BubbleSort(a: array [1...n]) : for i from 1 to n - 1 : for j from 1 to n - 1 : if a[j] > a[j + 1] swap(a[j], a[j + 1]) 我们把内部的一次循环称为冒泡迭代： 1234define BubblePass(a: array [1...n]) : for j from 1 to n - 1 : if a[j] > a[j + 1] : swap(a[j], a[j + 1]) 实际上，不是所有的 $n - 1$ 次冒泡迭代都会被冒泡排序执行，一些数组会在一定次数的冒泡迭代后变得有序。比如说，数组 $[2,1,3,4]$ 在一次冒泡迭代后就会变得有序。 其实有很多的数组都只会经过一次冒泡迭代就变得有序，比如说由区间 $[1,3]$ 组成的数组的数字的 $6$ 个全排列中有 $4$ 个都只需要一次冒泡迭代就可以变得有序。 ...