Oiclass P1993 题解 又是一道 DP 看到题目,我的第一反应就是:这鼹鼠是什么玩意儿? 额,\(\Huge 搞错了\) 再来 下面是传统的五步 1. 划分阶段 以每一只耐造的鼹鼠为一个阶段,表示在这只鼹鼠前面(包括这只鼹鼠)可以打到的鼹鼠的数量 2. 确定状态和状态变量 这里使用两个数组 \(f,\ a\) ,分别存储状态和输入的数据 3. 确定决策和状态转移公式 因为每一只鼹鼠都可以和他前面的任何一只鼹鼠结合,所以我 2023-01-05 #题解 #OiClass
Oiclass P1227 题解 这道题需要两次动规 (LIS DP) OK,再再再再是经典的五步 1. 划分状态 在这道题,我用每个人划分状态,每个人有两个状态,分别是以这个人结尾的最长不下降子序列长度和以这个人开头的最长不下降自序列的长度 2. 确定状态和状态变量 我使用三个数组 \(a,\ b,\ c\) 分别:存储输入的数据、存储状态一(以这个人结尾的最长不下降子序列长度)、存储状态二(以这个人开头的最长不下降自序列的长度 2023-01-05 #题解 #OiClass
Oiclass P1229 题解 这道题思路稍稍有那么一点绕 先理解一下题目,交叉着一点还是挺难理解的,我们把样例的图片画出来的话大概是这样的: 截屏2023-01-05 14.38.33 我们仔细观察一下,会发现,不交叉的的几项在下面(南岸)形成了一个上升序列(也可以说是不下降序列),那么求有多少项不交叉是不是可以改成当北岸按升序排好时南岸的数的最长不下降子序列的长度?这就很好理解了。先把北岸排序,让南岸跟着动,然后求南岸 2023-01-05 #题解 #OiClass
Oiclass P1226 题解 话不多说,这又是一道 DP 题 看题目就知道,这就是大名鼎鼎的最长不下降子序列 LIS 。所以我们用十分传统的五步(第六步是送的)解决这个问题 1. 划分阶段 我们的以每一个数划分阶段,也就是说每一个阶段存储的是以某个数结尾的子序列 2. 确定状态和状态变量 这里使用数组 \(f\) 来存放状态,数组 \(a\) 存储输入的数据,即状态 \(f_i\) 为以数字 \(a_i\) 结尾的最长不下降子 2023-01-04 #题解 #OiClass
Oiclass P1479 题解 这道题又又又又又是动规(我最近在学) 传统的五步: 1. 划分阶段 这里划分的阶段是在某个格子上时的最优解 2. 确定状态和状态变量 这里的状态数组 \(f\) 来进行存储,用数组 \(a\) 储存输入的数组。状态从他前面的格子获得,这些格子可能是: \[ a_{S},\ a_{S+1},\ a_{S+2}...a_{T-2},\ a_{T-1},\ a_{T} \] 3. 确定决策并写出状态转移 2023-01-03 #题解 #OiClass
Oiclass P1221 题解 这道题不用多说也知道是 DP (看标签) 那么,究竟要怎样 DP 呢?下面依然是那熟悉的五步 1. 划分阶段 这里我采用的方法是划分爬到每一个位置,也就是以空间划分阶段 2. 确定状态和状态变量 OK,进入下一步 。在这里我定义的状态是在第 \(i\ (0<i≤n)\) 个位置时以跳到达和以爬到达的最优解,分别记为 \(jump_i\) 和 \(climb_i\) 3. 确定决策井写出状态转 2023-01-03 #题解 #OiClass
Oiclass P3314 题解 这道题从题面就可以看出是经典的最长不下降子序列 对于这道一点都不简单的最长连续子序列和的模板题,我们还是直接暴力,代码: 123456789101112131415161718192021#include <iostream>using namespace std;int ans, n, a[1009];int main() { cin >> n; f 2023-01-03 #题解 #OiClass
Oiclass P1220 题解 从标签题面可以看出这是一道动规(DP) 进入正题,依旧是传统的五步 1. 划分阶段 这里我的思路是将每公里的数值作为一个阶段,即 \(n\) 公里就有 \(n\) 个阶段,分别是: \[ 1, 2, 3, 4, 5, 6 ....(n-2),(n-1),(n) \] 2. 确定状态和状态变量 这里使用一个数组 \(f\) 来保存状态,即第 \(i\) 个状态为 \(f_i\) ,然后就没有了 3. 2023-01-03 #题解 #OiClass
Oiclass P1235 题解 简单的一维动规 按照老师的要求 1. 划分阶段 非常容易的可以看出这道题目的阶段就是各个位置,即 \(i,\ j\) 。在这种划分下,每一种阶段的最优解可以由上一个阶段得到,且不会被右面的阶段所改变,故无后效性。综上,该题可以用 DP 求解 2. 确定状态和状态变量: 由 (1) 得:该题无后效性,故可用 递推的DP 进行求解,对于状态 \(i,\ j\) 的最优解,用 \(f_{i,j}\) 表 2023-01-03 #题解 #OiClass
Oiclass P1213 题解 很明显,这道题是二分答案 那么,需要二分的是什么?有脑子都知道是,间距。那么求的究竟是最大值最小还是最小值最大呢?我们看到题目,我们需要求的是 “那么相邻两块土地之间的间隔的最大值” 也就是最小值最大。好的,那么框架有了,如下: 1234567891011bool check(int x);// l 是田之间的距离while (r - l > 1) { int mid = 2023-01-02 #题解 #OiClass
Oiclass P3309 题解 这道是模拟题 思路如下 先输入 \(n\) 和 字符串 遍历字符串,如果没有出现过且\(当前排队人数<n\) ,将其标记,并将当前排队人数 \(+1\),如果\(当前排队人数 ≥n\) ,不标记,同时将答案 \(+1\) 如果已经出现过了,将当前人数 \(-1\) 同时将其标位为出现 实现 实现起来很简单,首先定义一个整数 \(n\) 、一个字符串 \(str\) 、一个布尔数组 \(p 2023-01-01 #题解 #OiClass
Oiclass P2107 题解 这道题的思路非常奇怪(至少我觉得是这样) 你需要把它当做一道找规律题 \(\Huge{进入正题}\) 先看题目: 小 S 想计算一个自然数 n \((n < 2000)\) 的所有回文分解的个数 \(\% 1000000007\) 的值。 我们来看一下 \(1\to10\) 的所有整数的回文分解个数。简单在草稿纸上枚举可以发现,分别是: \[ 1,2,2,4,4,6,6,10,10,14 \ 2022-12-25 #题解 #OiClass
Oiclass P1202 题解 这道题一看就是连通块 因为求连通块 DFS 最简单,所以我用 BFS 简单思路: 首先把外围的 0 给清除掉,然后统计数组里面还有多少个 0。 那么难点来了,究竟怎样能一次把外围所有的 0 给清除呢?记不记得我们在输入的时候一般都会从 [1][1] 开始输入,那么是不是从 [1][1] 到 [n][n] 都有值?没错,有脑子都知道有值,那么这个矩阵的四周是不是空出了一圈是没有值的,就像这样: 12 2022-12-05 #题解 #OiClass
Oiclass Q&A P1106 题目: 代码: 1234567891011121314151617181920212223242526272829#include "iostream"#include "cstring"using namespace std;int n, cnt, t;int main(){ cin >> n; int a[n + 1] 2022-08-11 #OiClass #Q&A
OiClass.com Q&A P1194 这次提问的人是自己 P1194 阿克曼函数超时怎么破? 代码: 1234567891011121314151617181920212223#include "iostream"using namespace std;int x, y, ans;int ack(int m, int n){ if (m == 0){ return n += 2022-08-09 #OiClass #Q&A
Oiclass Q&A P1626 OiClass.com Q&A P1626 问题: 提问: 帮我解决的人是我爸 1234567891011121314151617181920#include <bits/stdc++.h>#define space ' 'using namespace std;int main(){ int n; int a[33333]; 2022-08-04 #OiClass #Q&A
Oiclass Q&A P2569 OiClass Q&A P2569 问题: oiclassq&ap1problem.png 很显然这是一道很简单的问题(大水题),让我们来看看提问: 哪位兄台能告诉我哪里错了吗,输入输出符合要求的: 1234567891011121314#include<iostream>#include<math.h> using namespace std;int 2022-08-04 #OiClass #Q&A