QQQQQQ5292

分类

未归档(2) 题解(11)

/ 注册

全部文章（共13篇）

题解 | #1919810#

题目描述样例 Input 19198210 Output 5 算法1 (类似状态机的dp) O(n)O(n)O(n) 这题其实不难，仔细思考片刻这题其实就可以把他分成多个部分：将题目中的2 3 4 5 6 7 部分我们分为2 3 4 5 6 7阶段上升部分：就是 a1a_1a1...

C++

2022-10-30

2 558

"蔚来杯"2022牛客暑期多校训练营1

G - 签到题 A - 简单题题意就是给一堆区间把所有相交的区间合并，找出合并后，所有区间后的空隙有多少 void solve() { cin >> n; vector<pii> a; for (int i = 1, x, y; i <= n; i++) ...

C++ C

2022-07-18

2 397

DP小结Part.2

接下来就是区间dp区间dp有个可以套模板，就是枚举区间长度，然后每个区间等于他的两个子区间相加最大/最小。。。直接上例题。最典型例题合并石子：http://120.78.128.11/Problem.jsp?pid=2385直接枚举每个区间长度一层一层往上就好了，类似于归并排序。需要注意的是这个是一...

dp学习

2021-08-12

0 398

DP小结 part.1

————dp非常灵活，对像我这样的蒟蒻及其不友好。写此小结记录下自己成长的过程首先呢，拿到一个题怎么发现他是由dp来解决的呢？有以下几点：1.可以由一个子问题推出一个全局最优解2.无后效性而做dp的题无非就三部曲1.确认子问题及其边界2.推出状态转移方程3.进行动态规划编程线性dp：线性dp过于灵活...

dp学习

2021-08-07

1 460

题解 | #King of Range#

题目描述：题目给你一个长度为n的序列，m次询问，每次询问给一个k，寻找有多少个区间【l，r】满足区间内的数组最大值减数组最大值大于k（不等于k）思路分析：我们给定一个i，为满足条件的区间左边界。然后往后找右区间边界，我们令j为区间右边界，而我们只需要找出这个区间内满足条件的最小j即可，因为这个j后面...

2021-08-01

4 595

题解 | #[NOIP2018]货币系统#

题目描述 :在网友的国度***有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一个非负整数x，都存在n个非负整...

2021-08-01

0 631

题解 | #[NOIP2000]方格取数#

题目描述：设有NxN的方格图(N ≤ 10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例)：某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。此人从A点到B 点共走两次...

2021-07-28

0 797

题解 | #Inverse Pair#

题目描述：给你一个数组a，a[i]可以加1或者不加，求进行所有操作完后最小的逆序对数思路：先把所有的逆序对数求出来，然后再找满足(a[i]>a[j]&&i<j&&a[i]==a[j]+1)条件的对数，再用所有的逆序对数减去满足条件对数就可以的出最小对数。A...

2021-07-27

2 464

题解 | #逆序数#

题目描述：求一个数组求逆序对的数量。方法与解析：直接套归并排序的板子，归并板子来自牛客笔记 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; void b_sort(int l,int r); void bi...

2021-07-27

0 579

题解 | #Average#

题目描述：简单来说就是给你两个数组，a和数组b。然后定义矩阵w[i][j]=a[i]+b[i]，在这个矩阵内找一个子矩阵得到，这个字矩阵内的平均值最大，这个子矩阵长不得小于x,宽不得小于y。题目分析：每个矩阵的平均值为:又由于w[i][j]=a[i]+b[j]得子矩阵的和就等于平均值...

2021-07-27

6 547