洛谷P4694 [PA2013] Raper 题解
洛谷P4694 [PA2013] Raper 题解 题目链接:P4694 [PA2013] Raper 题意: 你需要生产 \(k\) 张光盘。每张光盘都要经过两道工序:先在 A 工厂进行挤压,再送到 B 工厂涂上反光层。 你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 \(n\) 天时间,每天可以先送一张光盘到 A 工厂(或者不送),然后再送一张已经在 A 工厂加工过的光盘到 B 工厂(或者不送),每家工厂一天只能对一张光盘进行操作,同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。 求生产出 \(k\) 张光盘的最小花费。 输入格式 第一行包含两个整数 \(n, k\),表示有 \(n\) 天,要生产 \(k\) 张光盘。 第二行包含 \(n\) 个整数,第 \(i\) 个整数表示第 \(i\) 天送到 A 工厂加工光盘的花费。 第三行包含 \(n\) 个整数,第 \(i\) 个整数表示第 \(i\) 天送到 B 工厂加工光盘的花费。 输出格式 输出一行一个整数,表示最小花费。 数据范围: 保证 \(1 \le k \le n...
CF1147F Zigzag Game 题解
CF1147F Zigzag Game 题解 题目链接:Zigzag Game 题意: 这是一道交互题,并且有 \(T\) 组数据。 给出一个两边均有 \(n\) 个节点的完全二分图,左部点由 \(1\) 到 \(n\) 编号,右部点由 \(n+1\) 到 \(2n\) 编号。输入中会给出一个 \(n \times n\) 的矩阵 \(a\),其中 \(a_{i,j}\) 表示连接 \(i\) 和 \(j+n\) 的边的边权。 现在有两个玩家 Alice 和 Bob 在这个图上玩游戏。首先 Alice 会选择 “increasing”(增加)或者 “decreasing”(减少)中的一个属性,Bob 则会自动选择另一个。接下来由 Alice 在图上选择一个起始节点 \(p\) 放上一枚棋子,Bob 选择一条连接节点 \(p\) 的边 \((p,q)\),将棋子移动到 \(q\)。 接下来由 Alice 先手轮流进行操作。每一次操作时操作方需要选择一个与当前节点 \(x\) 相邻的未被经过的节点 \(y\)。设 \(w\) 为 \((x,y)\) 的边权,\(w'\) 为...
洛谷P4055 [JSOI2009] 游戏 题解
洛谷P4055 [JSOI2009] 游戏 题解 题目链接:P4055 [JSOI2009] 游戏 题意: Alice 和 Bob 得到了《喜羊羊和灰太狼》的电影票,都很想去观看,但是电影票只有一张,于是他们用智力游戏决定胜负,赢得游戏的人可以获得电影票。 在 \(n,m\) 的迷宫中有一个棋子,Alice 首先任意选择棋子放置的位置。然后, Bob 和 Alice 轮流将棋子移动到相邻的格子里。游戏的规则规定,在一次游戏中,同一个格子不能进入两次,且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时,游戏结束,最后一个移动棋子的玩家赢得了游戏。 例如下图所示的迷宫,迷宫中 . 表示棋子可以经过的格子,而 # 表示棋子不可以经过的格子: .## ... #.# 若 Alice 将棋子放置在 \((1,1)\),则 Alice 则无论如何都无法赢得游戏。 而若 Alice 将棋子放置在 \((3,2)\) 或 \((2,3)\),则Alice 能够赢得游戏。例如,Alice 将棋子放置在 \((3,2)\),Bob 只能将它移动到 \((2,2)\),此时 Alice 再将...
洛谷P4424 [HNOI/AHOI2018] 寻宝游戏 题解
洛谷P4424 [HNOI/AHOI2018] 寻宝游戏 题解 题目链接:P4424 [HNOI/AHOI2018] 寻宝游戏 题意: 某大学每年都会有一次 Mystery Hunt 的活动,玩家需要根据设置的线索解谜,找到宝藏的位置,前一年获胜的队伍可以获得这一年出题的机会。 作为新生的你,对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊,这条走廊是如此的长,以至于它被人戏称为 infinite corridor。一次,你经过这条走廊时注意到在走廊的墙壁上隐藏着 \(n\) 个等长的二进制的数字,长度均为 \(m\)。你从西向东将这些数字记录了下来,形成一个含有 \(n\) 个数的二进制数组 \(a_1,a_2,...,a_n\)。 很快,在最新的一期的 Voo Doo 杂志上,你发现了 \(q\) 个长度也为 \(m\) 的二进制数 \(r_1,r_2,...,r_q\)。 聪明的你很快发现了这些数字的含义。 保持数组 \(a_1,a_2,...,a_n\) 的元素顺序不变,你可以在它们之间插入 \(\land\)(按位与运算)或者 \(\lor\)(按位或...
AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift 题解
AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift 题解 题目链接:Largest Smallest Cyclic Shift 题意: 定义 \(f(S)\) 为:对于一个字符串 \(S\),每次将它最左边的字符放置到字符串末尾生成的字符串集合中,字典序最小的字符串。例如:对于 \(S\) 为 babca 的情况,\(f(S)\) 即为 babca、abcab、bcaba、cabab、ababc 中最小的那个,即 ababc。 你需要构造一个字符串 \(T\),共包含 \(X\) 个字符 a、\(Y\) 个字符 b 和 \(Z\) 个字符 c,使得 \(f(T)\) 尽可能大,输出这个 \(f(T)\)。 数据范围:\(1 \le X + Y + Z \le 50\) 。 非常有趣的贪心题。注意到 \(X=Y=Z\) 时,最优方案是 \(\tt abc\) 。 考虑递归的构建字符串。设 \(s_1,s_2,s_3\) 是当前最优的三个字符串,规定 \(s_1 < s_2 < s_3\) 。 显然我...
CF1451F Nullify The Matrix 题解
CF1451F Nullify The Matrix 题解 题目链接:Nullify The Matrix 题意: Ashish 和 Jeel 在玩游戏,有一个 \(n\times m\) 的棋盘,每个格子有一个非负整数的权值。 两个人轮流操作,每次操作先选择一个权值非 \(0\) 的格子作为起点,然后选择起点右下角的一个格子作为终点,然后选择它们之间的一条最短路径,然后给起点的权值减一个正整数、路径上每个点的权值随意加减(也可以不改变),但是都不能改成负数。 不能操作(全变成 \(0\))就输了,Ashish 先手,问谁必胜。 这道题的思路和 CF1149E 挺像的。 记 \(f_i = \bigoplus_{x+y=p}a_{x,y}\) ,那么先手必败当且仅当 \(\forall i\) 有 \(f_i = 0\) ;否则先手必胜。 证明 记 \(\rm N\) 为先手必胜态,\(\rm P\) 为先手必败态。 考虑证明在此最优策略下原问题转化一个有向图游戏。 终止状态,显然为 \(\rm P\) 。 对于 \(\rm P\) 态,即 \(\forall i, f_...
CF1149E Election Promises 题解
CF1149E Election Promises 题解 题目链接:Election Promises 题意: 给定一张 \(n\) 个点 \(m\) 条边的有向图(不一定连通),每个点有一个权值 \(a_i\) 。 两人轮流进行操作,每次操作可以选择任意一个节点 \(u\) 并将其点权减小为一个非负整数, 之后可以将所有节点 \(v \in\{v \mid (u,v) \in E\}\) 的权值更改为任意非负整数 最先不能操作者输(指减小 \(u\) 的操作),求先手有无必胜策略。 若有必胜策略则接下来输出第一次操作后能够确保获胜的每个节点的权值 数据范围: \(1 \leq n \leq 2 \times 10^5, 0 \leq m \leq 2 \times 10^5,~0 \le a_i \le 2\times 10^{18}\) 。 可以发现,如果这张图全是单点,即出度全为 \(0\) 时,这就是一个 Nim 游戏。 考虑对每个点进行如下分组: 出度为 \(0\) 的点标号为 \(0\) 。 对原图拓扑排序,每个点的标号是它后继节点的 \(\operatorna...
洛谷P5300 [GXOI/GZOI2019] 与或和 题解
洛谷P5300 [GXOI/GZOI2019] 与或和 题解 题目链接:P5300 [GXOI/GZOI2019] 与或和 题意: Freda 学习了位运算和矩阵以后,决定对这种简洁而优美的运算,以及蕴含深邃空间的结构进行更加深入的研究。 对于一个由非负整数构成的矩阵,她定义矩阵的 \(\texttt{AND}\) 值为矩阵中所有数二进制 \(\texttt{AND(\&)}\) 的运算结果;定义矩阵的 \(\texttt{OR}\) 值为矩阵中所有数二进制 \(\texttt{OR(|)}\) 的运算结果。 给定一个 \(N \times N\) 的矩阵,她希望求出: 1. 该矩阵的所有子矩阵的 \(\texttt{AND}\) 值之和(所有子矩阵 \(\texttt{AND}\) 值相加的结果)。 2. 该矩阵的所有子矩阵的 \(\texttt{OR}\) 值之和(所有子矩阵 \(\texttt{OR}\) 值相加的结果)。 接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题,所以这个问题就交给你了。 由于答案可能非常的大,你只需要输出答案对...
洛谷P8348 「Wdoi-6」未知之花魅知之旅 题解
洛谷P8348 「Wdoi-6」未知之花魅知之旅 题解 题目链接:P8348 「Wdoi-6」未知之花魅知之旅 题目描述 称一个长度为 \(n\) 的正整数数列是「\(k\) - 好」的,当且仅当它满足以下条件: 对于 \(1< i< n\),满足 \(a_{i-1},a_i,a_{i+1}\) 中最大的一个等于其他两个之和。 所有元素都不小于 \(k\)。 \(T\) 组询问,每次询问给定 \((a_0,a_1,x,y,k)\),问是否存在「\(k\) - 好」数列(长度不小于 \(2\)),前两项为 \(a_0,a_1\) 并且有相邻两项依次为 \(x,y\) 。 输入格式 第一行输入一个正整数 \(T\),表示数据组数,对于每一组数据: 每行输入 \(5\) 个正整数,以空格隔开,分别为 \(a_0,a_1,x,y,k\),含义如题目所述。 输出格式 对于每一组数据,输出一行 yes 或 no,即是否存在一种可以使得神社变得美观的方法。 数据范围 \(1 \leq \max(a_0,a_1,x,y,k) \leq 10^9,1 \leq T \le...
K–Nim 游戏
K–Nim 游戏 K–Nim 游戏是 Nim 游戏的推广。 描述 有 \(n\) 堆石子,其中第 \(i\) 堆有 \(a_i\) 个,每次可以从 \(1\) 到 \(k~(k \le n)\) 堆石子中取走任意个石子,不能操作者失败。 结论 记 \(x\) 二进制下的第 \(i\) 位为 \((x)_i\) ,若对于任意 \(s\) 均有 \[ \sum_{i=1}^n\left(a_i\right)_s \equiv 0\pmod{k+1} \] 则先手必败;否则先手必胜。 换言之,只要 \(a_i\) 在二进制下某一位的和模 \(k+1\) 为不为 \(0\) ,先手必胜。 证明 考虑证明上述策略可以将 K–Nim 游戏转化为有向图游戏。 记先手必胜态为 \(\rm N\) ,必败态为 \(\rm P\) 。有向图游戏有如下性质: 终止状态为 \(\rm P\) 。 \(\rm P\) 的后继均为 \(\rm N\) 。 \(\rm N\) 的后继存在至少一个 \(\rm P\) 。 那么我们只需证明最优策略满足以上性质即可: 所有堆为 \(0\) 是终止状态,显然...
洛谷P2490 [SDOI2011] 黑白棋 题解
洛谷P2490 [SDOI2011] 黑白棋 题解 题目链接:P2490 [SDOI2011] 黑白棋 题意: 小 A 和小 B 又想到了一个新的游戏。 这个游戏是在一个 \(1 \times n\) 的棋盘上进行的,棋盘上有 \(k\) 个棋子,一半是黑色,一半是白色。 最左边是白色棋子,最右边是黑色棋子,相邻的棋子颜色不同。 小 A 可以移动白色棋子,小 B 可以移动黑色的棋子,其中白色不能往左,黑色不能往右。他们每次操作可以移动 \(1\) 到 \(d\) 个棋子。 每当移动某一个棋子时,这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。 小 A 和小 B 轮流操作,现在小 A 先移动,有多少种初始棋子的布局会使他胜利呢? 输入格式: 输入三个数 \(n,k,d\)。 输出格式: 输出小 A 胜利的方案总数。答案对 \(10^9+7\) 取模。 数据范围: 保证 \(1 \leq d \leq k \leq n \leq 10^4\),\(k\) 为偶数,\(k \leq 100\)。 由于终止状态一定是 “……黑白…黑白…黑白……” 的情况...
洛谷P3172 [CQOI2015] 选数 题解
洛谷P3172 [CQOI2015] 选数 题解 题目链接:P3172 [CQOI2015] 选数 题意: 我们知道,从区间 \([L,H]\)(\(L\) 和 \(H\) 为整数)中选取 \(N\) 个整数,总共有 \((H-L+1)^N\) 种方案。小 z 很好奇这样选出的数的最大公约数的规律,他决定对每种方案选出的 \(N\) 个整数都求一次最大公约数,以便进一步研究。然而他很快发现工作量太大了,于是向你寻求帮助。你的任务很简单,小 z 会告诉你一个整数 \(K\),你需要回答他最大公约数刚好为 \(K\) 的选取方案有多少个。 由于方案数较大,你只需要输出其除以 \(10^9+7\) 的余数即可。 输入格式: 输入一行,包含四个空格分开的正整数,依次为 \(N,K,L,H\)。 输出格式: 输出一个整数,为所求方案数除以 \(10^9 + 7\) 的余数。 数据范围: 对于 \(100\%\) 的数据,\(1\le N,K\le 10^9\),\(1\le L\le H\le 10^9\),\(H-L\le 10^5\)。 设 \(F(k)\) 表示从 \([L,R]...
![洛谷P4694 [PA2013] Raper 题解](/qwq/img/p134.webp)

![洛谷P4055 [JSOI2009] 游戏 题解](/qwq/img/p68.webp)
![洛谷P4424 [HNOI/AHOI2018] 寻宝游戏 题解](/qwq/img/p6.webp)



![洛谷P5300 [GXOI/GZOI2019] 与或和 题解](/qwq/img/p57.webp)


![洛谷P2490 [SDOI2011] 黑白棋 题解](/qwq/img/p94.webp)
![洛谷P3172 [CQOI2015] 选数 题解](/qwq/img/p158.webp)
![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)