AT_zone2021_e 题解 AT_zone2021_e 题意 由于洛谷的题意太不好理解了,我是看了英文题面才理解的。下面简述一下题意: 首先题目给定两个数 \(R\) 和 \(C\) ,同时给定两个数组 \(A\) 和 \(B\),\(A\) 的大小是 \(R \times C - 1\) ,\(B\) 的大小是 \(R - 1 \times C\) 。然后计算点 \((1,\, 1)\) 到点 \((R,\, C)\) 2023-10-20 #题解 #AtCoder
Oiclass PUJI 1353 题解 贪心 + 大模拟 题目简述 你是一名医生,是这家医院有且只有的一个医生。现在有 \(n\) 个患者要来手术,每个患者有四个属性:\(t\) 指患者到达医院的时间、\(a\) 指患者手术后会支付给你的钱、\(b\) 指患者所需的手术时间、\(p\) 是患者的严重程度,\(p\) 越小,患者就越严重。现在如果一个患者看到一个 \(p\) 值比他更大的患者正在手术,那么他就会很生气,你就会一分钱也得不到 2023-10-19 #题解 #OiClass
CSP 2023 考场注意事项 考场注意事项 入场问题 首先此次 CSP 是从 5 号门(侧门,也就是更靠近广工西区的那个)进。时间: J 组 ,早上 7:45 进场,8:10 截止进场,8:25 发卷,11:55 交卷。 S 组 ,13:30 进场,14:10 截止进场,14:25 发卷,18:25 交卷。 考试问题 广附提供了 Noi Linux 2.0 的虚拟机,但是用不明白的还是建议不要用。考场不允许吃东西,但是你可 2023-10-19 #杂项
Oiclass PUJI 1277 题解 博弈论 题目简述 有 \(n\) 个硬币,两位玩家,每次去取 \(l \sim r\) 个,取不到者负,都执行最优策略,哪一方必胜? 思路 和显然,这个问题就是博弈论中十分经典的 Nim 取子问题 。首先我们发现,对于一种状态,如果后面的任何状态都是必败状态,那么我们可以发现,这个状态就是我们常说的必胜态,因为,无论下一步怎么走,都是无法获胜。而同时,如果一个状态后面有必胜态,那么这个状态就是必败 2023-10-10 #题解 #OiClass
TYOI 暑假集训游记 TYOI 暑假集训游记 比赛复盘 分数 比赛 排名 分数 是否意外 2023 tyoi 普及模拟训练 01 \(21\) \(150\) 是 2023 tyoi 普及模拟训练 02 \(30\) \(220\) 是 2023 tyoi 普及模拟训练 03 \(13\) \(260\) 否 2023 tyoi 普及模拟训练(B --> C) \(5\) \(180\ 2023-08-22 #游记 #TYOI
MCOI 2023年6月月赛题解 MCOI 2023 年 6 月月赛题解 引言 这是一场个人认为难度 \(\approx\) J- 级的比赛,除了最后一题是一道非常怪的题以外其他的题目都是比较简单的,但是会有一些坑。由于出题人写 TJ 的时候你们的比赛还没有结束,因此没法评价本场比赛。个人估计应该不会有人 AK,但是这场比赛应该 \(300\) pts 的巨佬不少。下面是各题的题解,写的不好,请多多关照。 T1 - WTX 的文采 2023-06-08 #题解 #MCOI
Oiclass PUJI Circle 题解 泰裤辣!解析几何 引 首先我们看题,发现题目会给我们四个点,让我们判断这四个点是否共圆,那么如何判断这四个点是否共圆呢?我的思路是这样的: 首先以这四个点为顶点随便画出两个不同的三角形,求这两个三角形的外心 然后判断这两个外心是否相同,如果是的话,那么我们可以判断这四个点事共圆的 那么这种思路就会引起很多问题了,首先什么是外心?很巧,今天数学课数学老师留的思考题就是如何找到三角形的外心,也就是 2023-05-13 #题解 #OiClass
Oiclass PUJI 971 题解 数学题!!! 为了方便化简式子,我们首先简单的将 \[ d(x, y)=y-x \] 替代 \[ d(x, y)=\left\{ \begin{array}{l} 0\ \ (|x - y|\le1)\\ y - x\ \ (|x - y| > 1) \end{array} \right. \] 那么就可以令 \(n = 4\) 将原式( \[ \sum^{n}_{i = 1}\sum_{j 2023-04-13 #题解 #OiClass
Oiclass PUJI P1296 题解 这是一道几何题 看到题目,我们会发现,题目需要我们找到四个点,构成一些正方形(即四边等长的矩形,这个很重要,后面会用到),然后输出可以构成的正方形的个数 好的,那么作为一个暴力骗分的小能手,我的第一反应就是暴力,简单估一下,如果有 \(n\) 个点,那么时间复杂度就是 \(O(n^4)\) 很明显,这个时间复杂度直接原地起飞了,能 AC 我直接把题目吃下去好吧 那么我们现在就要来考虑如何尽可能的减 2023-03-04 #题解 #OiClass
Oiclass P2261 题解 这道题实际上很简单 先看题目,会发现,这道题似乎很想模拟题,但是又好像不是,因为用正常的方法没法模拟,或者说很难模拟。看标签仔细观察就可以知道,这是一道数据结构相关的模版题,具体会用到队列。 思路如下: 首先输入题目中提到的 \(n\) 和 \(c\) 在队列中压入 \(1 \to n\) 的所有自然数,对于 \(n = 6\) 的情况,队列应该是这样的:\(队头\ 1,2,3,4,5,6\ 队 2023-02-01 #题解 #OiClass
Oiclass 新 C 班选拔测试题解 终于考完了 额,这次一共 6 题,3 个小时,时间还是有点紧张,但是由于题目太难,最后还是比较舒服的拿了 15 名(总共多少人就不说了)。但是,满分 600 只骗拿到了 150。确实菜了点,下面总结一下每一道题目 A. #P3256. 排队 这一题一看就是打卡题,但是也是正常比赛我唯一 AC 的一题,呜呜。这道题又是一道 oiclass 从其他地方搬运的题,好像是来自 JZOI 的,但是我没有找到 2023-01-15 #题解 #OiClass
Oiclass P1266 题解 这道题绝对称得上是 DP Ultra So, what is DP Ultra ? The answer is: 环形区间 DP !!!!!!!真的离谱!!! 1. 划分阶段 一共有 \(2 \times n\) 个阶段,每个阶段表示 \(i\) 开始 \(j\) 结束的区间里面一共最多能产生多少能量。 2. 定义状态变量 直接搞一个万能二维数组 \(f\) , \(f_{i,\ j}\) 表示一 2023-01-12 #题解 #OiClass
Oiclass P1238 题解 又是一道烧脑的模板题 进入正题,以下是传统得无与伦比的五步 1. 划分阶段 这里以每一种花为一个阶段,表示从第 \(1\) 种花到这一种花之间的所有花一共最多能有几种方案 2. 状态和状态变量 直接用一个二维数组 \(f\) 用来存状态,状态: \(f_{i,\ j}\) 表示 表示第 \(i\) 种花共摆了 \(j\) 盆时一共最多能有几种方案,也就是一个最优解。 3. 确定决策和状态转移方程 2023-01-12 #题解 #OiClass
Oiclass P1255 题解 又是一个我背不动的背包 这次是 0/1 背包 plus——多重背包,下面是经典的五步 1. 划分阶段 以每一个物品为一个阶段,表示这个物品前的物品的最大值(包括这个物品自身)。 2. 确定状态和状态变量 搞一个一维数组 \(f\) ,即 \(f_i\) 表示第 \(1\) 个物品到第 \(i\) 个物品之间(算头算尾)的最优解,也就是在空间不超过 \(v\) 的情况下最大的价值总和。 3. 确定决 2023-01-12 #题解 #OiClass
Oiclass P1246 题解 你说为什么 01 背包模板不是偷东西呢? 额,搞错了,再来! 1. 划分阶段 一共划分 \(M\) 个阶段,每个阶段表示在这个阶段可以采的最多的草药 2. 确定状态和状态变量 状态变量就用一个二维数组 \(f\) 吧,也就是说 \(f_{i,\ j}\) 表示前 \(i\) 颗草药在前 \(j\) 的时间可以获得最大价值,也就是说我们想求的是用 \(j\) 的时间,如何在 \(a_{1 \to i 2023-01-12 #题解 #OiClass
Oiclass P1928 题解 这道题简直拓宽了回文这个词的定义 天哪,我见回文数,回文分解,回文日,还真的没有见过回文词,而且这个词还毫无任何美感可言,其他回文可都是很优雅的呀。不吐槽了,进入正题 1. 划分阶段 这里定义两个字符串,\(a\) 和 \(b\) ,\(a\) 是输入的字符串,\(b\) 是 \(a\) 的反串。对于这两个字符串,一共有 \(2 \times a.length()\) 种状态,也可以说有 \(a. 2023-01-12 #题解 #OiClass
Oiclass P1241 题解 这次是 LIS 的兄弟 LCS(最长公共子序列) 一个词概括,模板题。但是,模板题也很难啊啊啊啊啊啊。又是经典的五步: 1. 划分状态 假设 \(a\) 和 \(b\) 是本次主角字符串(好想把他们拉出去斩了) ,那么一共有 \(a.length() \times b.length()\) 种状态,每一种状态表示下标 \(i\) 之前的 \(a\) 的子串(即 a.substr(0, i))与下标 2023-01-12 #题解 #OiClass
Oiclass P1240 题解 这道题是真的难啊 这道题目中 \(\Huge 相邻\) 这个该 * 的词很容易 让人误以为这道题有后效性,当时我们全班都认为这道题有后效性,然而我们美丽的又和蔼的 Lily 却和我们说没有。仔细分析后发现,直接观察确实这道题目有后效性,但是如果深入分析,就会发现,只有前面的一项会影响它本身,在计算后一项的时候,对他本身并不会产生影响,他始终是最优解,行,确定能用 DP 了,开工!!!! 1. 划分 2023-01-12 #题解 #OiClass
Oiclass P1242 题解 这道题真的离谱 1. 划分阶段 对于这道题目,我以每一个字母为一个阶段,表示第一个字符串的前 \(i\) 个字母和第二个字符串的前 \(j\) 个字母之间的编辑距离(定义见题目) 2. 状态和状态变量 定义数组 \(f\) 用于存储状态,即 \(f_{i,\ j}\) 表示一个阶段(也就是(1) 里面提到的阶段),同时 \(a,b\) 分别是输入的两个字符串 3. 确定状态转移方程 这就是最难的部 2023-01-12 #题解 #OiClass
Oiclass P1263 题解 这真是一场愉快的传球游戏 再次是传统的五步 1. 划分阶段 这里我划分的状态是:每次传球完一种状态 2. 确定状态和状态变量 对于状态变量,我定义一个二维数组 \(f\) ,对于 \(f_{i,\ j}\) 他表示的是在 \(i\) 次传球后,\(j\) 手上的球的数量。 3. 确定决策和状态转移公式 对于这道题,决策的方式稍稍有那么一点点复杂,对于一种状态 (\(f_{i,\ j}\))它有以下 2023-01-05 #题解 #OiClass