整数因子分解问题 Description 大于1的正整数n可以分解为：n=x1x2…xm。例如，当n=12 时，共有8 种不同的分解式： 12=12； 12=62； 12=43； 12=34； 12=322； 12=26； 12=232； 12=22*3。 对于给定的正整数n，计算n共有多少种不同的分解式。 Input 输入数据只有一行，有1个正整数n (1≤n≤2000000000)。 Output 将计算出的不同的分解式数输出。 Sample Input 12 Output 8 思路： 就是暴力枚举因子。可以算出1，2，3，都是只有一种分解式可以作为递归出口。 递推式：dp[k] = dp...

最长公共子序列问题 Description 给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 Input 输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。 Output 每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。 Sample Input ABCBDAB BDCABA Output 4 思路： 乍一看的话不知如何下手，那就暴力出奇迹，考虑两个串最后一个字符，如果相等则说明存在公共子序列长度+1，序列长度各自-1，然后继续递归解决子问题...

问题描述： 矩阵连乘问题是通过给矩阵连乘时加括号，使得总的计算量最小。 考虑3个矩阵相乘的例子， A1,A2,A3,假设这3个矩阵的维数分别为 10x100,100x50,5x50 若按照（（A1A2）A3）方式计算，需要的数乘次数为10x100x5+10x5x50 = 7500 若按照（A1(A2A3)）方式计算，需要的数乘次数为100x5x50+10x100x50 =75000 思路： 你可以理解为给你一个区间问你这个区间里面有多少种区间长度为2的组合。（可能说的不太清楚，举个例子） 如果 给你区间[1,3]，我们可以把这个区间拆成[1,1] + [2,3] 或者[1,2]+[3,3]，那...

唉，补题补题，太菜了当时看到这个题一点思路没有。。。。看了大佬的思路才懂。。。唉，还是思维没有练起来得多多刷题咯，（为啥一天天的困得要死） 思路： 先求出k的所有因子，然后分别从向量a和向量b找连续k的因子个1的数量，然后求出所有的因子就行了。（想不到想不到！！）（至于为什么找连续个稍微用笔画一画就知道了，或者说是乘法原理） 代码： #include<bits/stdc++.h> using namespace std; const int maxn = 4e4 + 10; int a[maxn],b[maxn],p[maxn]; typedef long long int ll;...

思路： 看到这个题很容易想到(i,j)建边权就是上面的公式然后跑一下最小生成树就出来了。然后N=1e5，克鲁斯卡尔应该不会超时，但是会超空间。 事实上这个题目很简单。  通过这个式子可以反应出，原本两点之间的距离会依赖于两个点的坐标，但是化简后我们可以发现其实两点之间的距离并不需要依赖两点之间的坐标，一个点的(x,y)坐标我们就可以求出他的权，问题就转化成了，在X轴上有N个点现在我们需要化N-1条边使它任意两点都可以达，切权值最小。原本二维的问题就转化成为了一维问题，解决这个问题，我们只需要对他的权降序，然后取n-1条边，边的权就是|ai-aj|。问题就解决了。 收获：之前也遇到过很多题目中给...

题目大意： 先输入26个字符[‘a’,‘z’]的权值，然后给你一个字符串，问你满足以下条件的子串有多少个。 1：第一个和最后一个字符相等的子串。 2：在这个子串中除掉第一个和最后一个字符的权值，剩下的字符权值之和等于0。 思路：求一段区间和我们可以用前缀和O(1)解决，但是要在一个串中找所有首位字符相等的子串的时间复杂度是O(n^2),因为N=1e5，这个时间复杂度肯定超时，所有我们要从别的角度解决这个问题。 前缀和等于0意味着：sum[r - 1] - sum[ l ] = 0（减掉第一个和最后一个字符的权值），只要稍微移一下项，就可以降维了。即sum[r - 1] = sum[ l ]。也...

题意：给你一颗n个点的树，用[0,n-2]去给n-1条边编号，使得mex(u,v)的最大值最小。 mex(u,v)表示任意两点的简单路径中不在这条边上的最小非负整数。 思路： 这个题目好巧妙啊~~~~哈哈哈哈，题目中给了一个很重要的信息被我忽略了，那就是它给出的是一棵树，意味着任意两点有且仅有一条简单路径，这个条件对构造结果很重要。首先我们考虑只要两个点的情况，那么这条边只能标记0，mex(u,v)也是0,因为取值只有0。（这是个坑需要特判掉）。考虑n<=4，你会发现无论你怎么构造都是一条链那么他的mex(u,v)最大值就是n-1。但是当n>=5的时候，只有存在一个顶点的度>...

题意：给你u,v，要你构造一个最短的数组使得数组的各元素异或和为u，总和为v。 思路： 首先考虑几组特殊的情况 u == v == 0返回0即可 u == v != 0 返回u即可 u > v 返回 -1 这都比较简单验证 但凡要构造什么东西的题目都是比较难的。这道题我们可以从异或这个运算出发，有一个很重要的性质就是 a ^ a = 0。这个性质告诉我们为了满足异或和等于u,我们总是可以构造这样的数组出来[a,a,u]，这样就满足了异或和等于u。为了满足和为v。因为数组中有了一个u我们还需要(v-u) / 2 = a就可以构造出来了。 也就是返回的数组最长不会超过3，但是我们还需要考虑一...

题意：给你一个N*N的的矩阵，要你找到一条最大的路径，并且每次只能水平或者垂直的走不超过k步，并且下一步的值要大于上一步的值，要你输出路径的最大值。 思路： 这个题不太难想到dp[ i ][ j ]可以由四个方向转移过来，但是这样做不了。因为无论你怎么搞都会存在有些转移本身就不是最优解，无法转移过来。 这题需要用记忆化搜索思路和上面是一样的，不过记忆化搜索会搜到一个点，当他的四个方向的值都比他小这时就是递归出口了，然后把它转移出另外一个状态，每次取四个方向的最大值即可。 状态转移方程：  不过这个不能用循环做，只能用搜索取做。因为要找递归出口循环显然不太适合。 总结：是个好题，思路不太难，但是...

题意： 给你n个二元组(u,v)，要你求最长的u是递增，v是递减的子序列。 思路： 这个题乍一看不就是个最长上升子序列吗？然后满足一个约束v是递减的求不就行了？ 思路确实是这样，不过需要预处一下按u递增v递减排序(因为满足约束并且可以往回找)，这样可以把所有的子序列全部找出来，如果不预处理是找不出来的，因为可能要往回找，不太好处理，所以预处理了，前提是子序列不连续的，并且是可以往回找的(只要满足条件，最长上升子序列是不可以往回找了，注意区别)连续就不行。然后就是最长子序列问题了，需要处理一下路径(没有处理好细节，浪费了很多时间)。 代码： #include<bits/stdc++.h&g...

题意： 给你两个序列，序列的取值是(A,G,T,C)，并且给出一个他们之间的对应价值矩阵 现在问题是，给你两个序列，你可以通过增加在字符串中间增加空格，最后要你求增加空格后的最大价值。 思路：可以增加空格，那么一个简单的思想是通过增加空格使得字母匹配数最大化，这样就可以获得最大价值。那么难免会出现不匹配的情况，我们也需要考虑。这题和LCS的思路基本上是一样的，唯一不同的是LCS的三种状态转移是有条件的，而这个题是没有条件的，即价值越大越好。举个例子 给出两个序列加空格的方式只有三种，那么我们可以从这个角度出现，逐步往长度大的求就行了。 定义dp[i] [j]:字符串s1从[1，i ]与字符串s...

思路：最长单调递减子序列的个数 就是等于 最长单调递增子序列的长度(因为是递增这些序列要么独立驾一个炮台，要么加到其他的序列中去，因为它们是递增，那么不可能加到同一序列中去，最会最多加的炮台数量就是等于他们的长度)，所以这题就转化求最长上升子序列的长度了。 代码： #include<bits/stdc++.h> using namespace std; int n; int a[10000]; int main(){ while(scanf("%d",&n)!=EOF){ int dp[1000];dp[1] = 1; int ans = 0; for(...

题意： 给你一个序列找你找出一个单调递增子序列的和的最大值。 注意到这样一句话. but everyone must jumps from one chessman to another absolutely bigger. 看到这句话直接想到lis了，然后果断写了一个lis交上去wa了。 然后稍微分析一下，题目要求的是递增的子序列没错，但不是要它的长度，而是要他的值。比如这样一个例子：40 41 1 2 3 4 ，最长递增是[1,2,3,4]他们的和是10，但是[40,41]显然更好。所以我们可以想到用lis的思想稍微改一下。 定义dp[i]：表示考虑到前i个序列的最大和。 状态转移方程：d...

题意： 给你一个容量为n的背包，和数量为m的物品，每件物品有价值和重量，并且可以取无数次，问你怎样取得最小值，并把重量取满。 思路： 一开始写了一个01背包，稍微改了一下变成完全背包了，不过被卡空间了。 然后看了一下讨论区是用完全背包写的，就去学习了一下完全背包的做法，和优化空间。 这题就是一个裸的完全背包把dp初始化inf就行了。滚动数组优化空间也挺简单的。 代码：(01背包卡空间版本)  #include<bits/stdc++.h> using namespace std; int n; const int maxn = 1e4 + 10; struct node{ int ...