数字三角形模型 摘花生 思路： 根据数据范围以及求最大值我们可以得知是动态规划的题目 状态表示：f[i][j]：走到（i，j）能够摘到的花生的集合。属性：最大值 状态转移：用当前的状点更新下一个点：f[nex][ney] = max(f[nex][ney], f[i][j] + a[nex][ney]) 代码： #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N = 1e2 + 10; const int INF = 0x3f3f...

C 小红充电 思路：这题的坑点就是，我们可以先把手机玩没电再用超级充电充，可能会花更少的时间。 由题知：a >=b >= c, 所以a是没用的，纯迷惑你。 实现代码： #include <bits/stdc++.h> using namespace std; #define int long long #define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) #define endl '\n' const int N = 1e5 + 10; signed main() ...

if(x == 1) cout << a << endl; 卡了一个小时，呜呜呜

睿抗 7-2 拼题A打卡奖励 思路 01背包问题 复杂度为O（N * M）= 5e8, 肯定超时，要换个思路。 我们看到金币的数量小于等于30，及价值的最大值为1000 * 10，我们可以考虑求价值为j时的最小体积。区别于第一种：体积为j时的最大价值。复杂度：1000 * 1000 * 30 = 3e7 空间为64B，所以我们考虑用一维数组优化。 #include<bits/stdc++.h> #define int long long #define endl "\n" //加快cout输出换行速度的 using namespace std; const int N = ...

题解与反思 做这套题最大的感触就是前几道题没有思路，题目问的都是最少或者至少操作几次，我会往贪心方面去想，怎样才能让操作次数最少，其实不然，题目的意思只是防止重复操作而已。。 班级活动 我们我编号分为两类： a[i]，出现了一次，这个编号可以改或者不改。 a[i], 出现了两次，这两个编号已经符合题意了，不需要再修改。 a[i], 出现大于两次，这个编号的前两个不需要修改，后边剩下的cnt - 2 个一定要修改，因为之前的a[i]编号已经不能使用。 所以我们统计出现一次的编号数量sum1, 出现大于等于两次的编号-2，剩余的编号数sum2, sum1 和 sum2 都是要修改的。如果sum1...

题解与反思 前三题在大佬的带领下，做的飞快，我的脑子转的太慢了 B 小苯的好数组 猜证题。 我们根据题意可以得知，只要数组不是完全单调递增的，好数组的长度就是n，我们要找的就是，不完全单调递增的序列的最大长度。刚开始以为是DP。。。 我们再进一步想一下，是不是一个序列就分为：完全单调递增和不完全单调递增两类。 所以只要数组不是完全单调递增，答案就是n，反之就是0。 #include<iostream> #include<vector> using namespace std; int main() { int n; cin >> ...

题解与反思 P2196 [NOIP1996 提高组] 挖地雷 思路 图的DP问题，就是找一条最大的价值最大的路径。 经过某个点的价值可以由以上一个点为结尾的路径推导过来，所以我们考虑用DP。 （1）状态表示：f[i] 表示以i点结尾的路径的价值的集合，属性值：最大值 （2）状态转移：我们以第i个点前驱结点进行划分， f[i] = max(f[j] + a[i], f[i]),其中j为i的前驱结点。 题目要求记录路径，所以我们用pre[i] 存储i的前驱结点。 在更新f[i]的过程中记录，最大值和最大路径的结尾ed，通过dfs，pre[ed]，输出最佳路径。 #inclu...

题解与反思 这次的题目比较正常吧，就是感觉做题太少了，思路打不开，有些不是很难的题目想不到。 D - Permutation Subsequence 滑动窗口的经典题目。 首先要弄明白，怎样才能选出来好索引序列。只要对应的元素集合是sort（）之后是一个公差为1等差数列即可，我们可以考虑对原来的数组进行排序，然后选取k长度的序列对应的索引序列，这个索引必然是好索引序列。 我们如何快速求解索引序列的最大值，最小值呢？我们可以用set来存储，一个按greatr, 一个按less , 这时候极差等于 两个set.begin() 的差值。 我们要做的就是维护一个长度为k的序列，每次删掉...

题解与反思 练习赛的题真的很难，对小白不是很友好！！！ 最近做题有点静不下心来，没有思路之后老是想着去查资料，自己独立思考的时间很少。 B 选择游戏 一开始认为，质数减一之后一定不在是质数，那么我们只需要统计一下，原来的质数数量，并且让他变为奇数个即可，但是交了几发都WA了，开始思考特殊情况。 为什么想到质数减一就不是质数了呢，因为质数肯定不是偶数（！！！），减一之后肯定变为偶数，就一定不是质数了，但是有一个特例：3。3是质数减一之后还是质数。 那我们怎么解决这个3呢？刚开始，犯了一个糊涂的错误。单独考虑3，发现不管是偶数个3还是奇数个3，小灰灰先操作都会输掉。然后我就想，是不是要...

思路 刚学完背包问题，比较熟悉。每个物品的个数有限制----> 多重背包问题 用多重背包考虑的时候有两个问题，数据范围太大， 考虑二进制优化；题目要求某种的物品不能使用，我们考虑如何解决。 二进制优化比较简单，我们把每种物品的数量按照：1，2，4，.... , 2^n, 打包。 第i个物品不能使用，我们要找到第i个物品打包之后，被分在了那几个包。我们可以用l[i], r[i]，记录每个物品打包之后被分的包的左右端点。 因为中间被断开了一部分，所以我们要预处理两个f[i][j], 其中fl[i][j], 表示从左到右（1 ~ i）的最大值，fr[i][j]表示从右到左的（c...

思路 题目的思维量很高，参考大佬的题解 要想用的币最少，我们可以用贪心的思想，用的币值越大越好 因为大的币值一定是小的币值的倍数，所以一个大的币值一定可以代替i个相等小的币值，所以我们可以用小的币值的更新大的币值。 状态定义：f[i] 表示在使用面值最大为i合法硬币序列时，我们用的最少钱币数量 状态转移，根据前面的分析可以得知，f[i] 可以用来更新大面值的结果，所以我们可以用f[i] 更新f[i * j] , f[i * j] = min(f[i * j], f[i] - cnt), cnt ： 使用面值i * j 之后可以减少的钱币数量。 cnt 的计算方法，每个兔子减...

思路 分组背包板子题 状态表示：f[i][j] : 考虑前i种模式，体力消耗不超过j的集合 属性值：最大值 状态转移；类似于01背包问题，考虑每种模式中的第k种操作选不选：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k]) #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1e3 + 10; typedef long long LL; int...

思路 每个技能可以放无限次，并且有时间限制和伤害数值，我们想到完全背包模型。但是最后一个技能有多种情况，我们考虑如何转化。本题一个坑点，有多组测试数据！！！ 1、我们可以把最后一个技能斤进行转化，转化为几个普通的技能。每个技能的时间为：t = l + i;伤害为：tmp + A * i；其中i为蓄力的时间。 2、由于题目给的数据范围比较大1e5，我们考虑用优化版的完全背包，转移方程为：f[i][j] = max(f[i - 1][j], f[i][j - t[i]] + w[i]) 3、空间也要优化：f[j] = max(f[j], f[j - t[i]] + w[i]) #include&l...

题解与反思 第一次打Rating，被薄纱！！！！ A - Buildings #include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod = 998244353; const int N = 2e5 + 10; int main() { int n, x; cin >> n >> x; int flag = 0; for(int i = 2; i <= n; i ++) { int t; ...