这个题挺有意思的，他是要找连续的子序列，并且在子序列中唯一存在。这个就很有意思了，为什么呢？ 先来看一下子序列的定义： 子序列是原来序列中的一部分序列，并且不一定连续。 所以题目要找连续的子序列，并且在子序列中唯一存在，这就说明了，这个连续子序列的左端点一定是从左往右第一个出现，并且右端点也是从右往左第一个出现，为什么这么说呢？ 举个例子： 2 3 2 1 这个数组，2 1是一段连续的子序列，但是因为在整个序列中存在 2 1这个不连续的子序列，不满足了题意，所以一个连续子序列要想在子序列中唯一存在，他的左右端点一定都是第一个出现的。 我们使用map来记左右端点出现的次数就ok了。 然后就是对每...

这里采用了一个技巧，可以有效地避免了超时，记录一下前一个数乘2的数量，这是什么用处呢？举个例子： 7 1 5这个数组，首先1乘以3个二会大于7，记录pre=3，因为1* 2=2，2* 2=4，而4小于5，这意味着从5乘到大于等于8只需要1个2，因为1到五之间已经乘了两个2了，这就避免了许多不必要的运算。 就比如，当要改变的数组元素位置已经非常靠后面的情况下，显然它前一个数已经变得非常大，当前位置的元素又很不巧的是1，那么就需要很多次循环直到它再次大于前一个数为止，这样时间复杂度过高了，相比之下，直接在前一个数的乘2次数上修改时间复杂度大大下降 #include<bits/stdc++.h...

这道题问，存不存在一对不相交的段，举个例子：（1，2）、（2，3）、（3，4）这三个段，（1，2）、（2，3）是相交的，但是（1，2）、（3，4）不是相交的，就找到了一对不相交的段，输出yes. 所以要找有没有不相交的对，就找最小的r和最大的l的位置关系就ok了 这里也是新了解到了一个不错的stl容器multiset这个容器可以自己排序，元素可以重复，并且每次插入删除的时候的时间复杂度是logn级别 multiset学习链接 下面是ac代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; cons...

由题意k可取2、3、4、5 这四个值，其中2、3、5是素数，一个素数的倍数可以是任意一个数和他的倍数的乘积。 而4的倍数可以是任意一个数和他的倍数的乘积，也可以是两个2的倍数的乘积，要判断这两种情况那种最优。 k==4 1.数组中2的倍数大于等于两个，那么不用变动，输出0 2.数组中有四的倍数，输出0 3.数组中有一个2的倍数，那么其他数一定是奇数，把任意一个数加一变成偶数即可，输出1 4.数组中没有2的倍数，那么所有数都是奇数，需要把任意两个奇数变成偶数即可，输出2 #include<bits/stdc++.h> using namespace std; const int M=...

这道题没有什么难点，有一点思维量，题目告诉说，每次把数组第一个元素移到最后，然后再让它向前移动，直到它绝对大于它前面的值就停止，侧面说明了，当数组头为最小元素的时候，数组无论如何也无法再改变了，那么操作的次数就是最小元素前面的元素个数。 然后需要判断，是否可以完成排序，因为最小元素作为数组头的时候，数组就无法再排序了，那么未排序之前的在最小元素后面的元素是无序的话，那么到了最后依旧无序。输出-1 #include<bits/stdc++.h> using namespace std; const int M=2e5+5; typedef long long ll; ll a[M];...

需要推导出来一个等式  这个等式是符合要求的数对，用map来统计每种符合要求的数对中数的个数。然后再从每一种数对里面符合要求数中求组合数就ok了，例如符合要求的数有3个，那么就任意从三个里面去出两个来，组合数个数就是数对的个数。 组合数是从n个数中取出m个 C(n,m) #include<bits/stdc++.h> using namespace std; const int M = 2e5 + 5; typedef long long ll; ll a[M]; ll ans; inline void deal() { map< pair<ll, ll>, ll...

经典动态规划求最大子序和的问题，思路不算难，但是数据量比较大，这里应用一个小技巧 将dp的初始化大小始终设置为n+1的大小，这样能避免memset给许多不必要的下标内容赋值，可以减少时间复杂度 #include<bits/stdc++.h> using namespace std; const int M=2e5+5; typedef long long ll; ll a[M]; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n...

一、判断是否可以用递归 1.原问题： 小球从小曼手里传出去经过三次传递又回到小曼手里的可能方案数。 子问题： 从1开始传球第i次传递时到达j的手里的方法数 符合具有相同子问题的条件 2.符合最优决策： 3.解决当前的决策与之前怎么决策的没有关系 满足无后效性 二、递推公式易错，因为是环形站位，所以还要注意取模，并且是从1开始，与平常的循环的写的方式不一样，要推一下怎么写。 三、每次传递可以由左边那个人传递过来，也可以从右边。 #include<bits/stdc++.h> using namespace std; int n,m; const int M=50; long long...

一、判断能否用动态规划 1.原问题： 从起点到终点的路径条数 子问题：从起点到位置（i，j）的路径条数 可以知道，具有相同的子问题 2.每一个子问题都是包含了它的子问题的最优解 满足此后决策是基于当前状态的最优决策 3.解决当前的决策和过去的状态没有关系 满足无后效性 综上可以使用动态规划 二、推状态转移方程 因为每一个位置都可以从上面和左面走来，所以可知，状态转移方程为 dp[i][j]=dp[i-1][j]+dp[i][j-1]; #include<bits/stdc++.h> using namespace std; int n,m,x,y; const int mod=10...