题意理解:给定一张带权无向图，依次从中拿走第i个点，求剩下的点到其他点的最短距离之和 分析问题：我们假设一张六个点的带权无向图，顶点编号0~5，按照题意我们可以得到所求： 拿掉0号点，求1,2,3,4,5分别到其他点的距离 拿掉1号点，求2,3,4,5分别到其他点的距离 拿掉2号点，求3,4,5分别到其他点的距离 拿掉3号点，求4,5分别到其他点的距离 拿掉4号点，求5分别到其他点的距离 拿掉5号点 我们倒着看分析过程： 拿掉5号点 拿掉4号点，求5分别到其他点的距离 拿掉3号点，求4,5分别到其他点的距离 拿掉2号点，求3,4,5分别到其他点的距离 拿掉1号点，求2,3,4,5分别到其...

本题和acwing的这道题一模一样最长公共子序列 相比于普通的LCS问题这道题的特点是： 第一个序列元素不重复，第二个序列元素可以重复。 先说结论： LCS和LIS问题是可以相互转化的，转化的关键是只要有一个序列满足所有元素不重复即可 思路： 假设A存储第一个序列，B存储第二个序列，B'存储B中的元素在A中的位置。 由此可知，B中的元素B[i]和B'的下标i是一一对应的 B'[i]表示B[i]在A中的位置 看图，假设在B'中存在一个长度为4的递增的序列，即： 这四个元素的下标i是递增的（在B中是递增的） 这四个元素的值B'[i]是递增的（在A中是递增的） 这里完成了一个LCS到LIS...

题意理解：若存在一种搜索路径，使起点被遍历两次，其他所有节点被遍历一次，则返回Y 大体思路： 用isvalid数组存储每个点是否被搜索过，用sum来标志棋盘还有多少点没有被搜索。 从起点开始深度优先搜索，终止条件是搜索到起点且sum==0。若搜索到非法点或者已经遍历过的点，则剪枝。 注意回溯之后的恢复现场！ 在main函数中，可以提前判断： 若棋盘面积为1，则返回Y 若行数或列数为1，则返回N C++代码 #include <iostream> #include <algorithm> #include <cstdio> #include <cstr...

题意理解：找出两个字符串的公共子串，且公共子串不包含数字 思路：参考最长公共子序列LCS的解题思路，用二维dp数组来表示以str1[i],str2[j]为结尾的两个字符串的最长公共子串。 当str1[i]==str2[j]时，dp[i][j]由dp[i-1][j-1]转移而来 若不相等，则dp[i][j]=0 状态表示： dp[i][j]表示以str1的第i个字母结尾，且以str2的第j个字母结尾的公共子串的集合；属性为公共子串的最大长度 状态转移： 若str1[i]==str2[j]，则dp[i][j]=dp[i-1][j-1]+1 若str1[i]!=str2[j]，则dp[i][j]=0...

考察分解质因数的思想 其中要求结尾0的个数，即求分解出的质因数中2和5的个数的最小值。 只需要不断地/2(/5)并计数即可 #include <iostream> #include <algorithm> using namespace std; int n; int cnt2,cnt5; int main() { while(cin>>n) { cnt2=cnt5=0; int temp=n; while(temp){ cnt5+=temp/5; ...

思路参考： 链接 链接 斐波那契数的重要性质（可以观察得到）： 大体思路： 先用一个数组存储斐波那契数（注意数据范围到1e8），然后求出斐波那契数列中小于n的最大的斐波那契数 利用递归思想，进行深度优先搜索。 ans=取该最大数的可行方案+不取该最大数的可行方案 返回条件： 若n==0，则说明当前方案可行，方案数+1 若f[index+2]-2<n，则说明从1~index的所有斐波那契数的和均小于n，方案数为0； #include <iostream> #include <algorithm> #include <cstdio> using name...

题意理解：在输入的数组中，找到所有的增-减-增...或减-增-减...子序列中最长的子序列长度。 思路：很经典的单串问题，考虑第i个位置必选的情况，且第i个位置的dp值与0~i-1均有关。 但是本题又有两种状态，所以考虑开一个dp[n][2]数组，分别存储两种情况。 本题和leetcode： 1567链接 122链接 309链接 有相似之处，均为二维dp分别表示两种状态的值。 本题： 状态表示： dp[i][0]表示以i为结尾，且是增加到i的所有子序列的集合，属性为子序列长度的最大值 dp[i][1]表示以i为结尾，且是减少到i的所有子序列的集合，属性为子序列长度的最大值 状态转移： #i...

理解题意：输入一个字符出啊str,字符串内可能包括空格 数字 字母 ，输出第一个有效数字 思路：因为cin会忽略有效数据前的所有空格、换行符、Tab，因此考虑cin吸收输入字符串开始的几个空格。 在for循环中遍历整个str： 当ans字符串为空时，所有满足1~9的数字都可以加入ans（0不能做最高位） 当ans字符串不空时，所有满足0~9的数字都可以加入ans；且若此时遍历到了非法字符串（非数字），则跳出循环，此时ans中保存的即为第一个合法数字 若ans长度大于10，跳出循环 判断ans是否为空： 若ans为空，则遍历str，查找是否有0：有0则输出0，否则输出-1表示该字符串没有数字 若...

题意：输入两个巨长无比的整数a,b;输出a+b,a-b,a*b 思路：因为整数非常大，所以考虑用字符串模拟的方法处理。 输入两行字符串，处理字符串：将每位数字反向压入vector中（因为+,-,*都是从低位向高位处理，所以反向压入）。 分别对两个vector A，B执行加法，减法（考虑两者大小关系），乘法，最后对结果反向输出即可。 处理字符串： for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//倒序压入数组中 for(int j=b.size()-1;j>=0;j--) B.push_back(b[j]-'0');//因为...

题意理解：输入是一串字符串，将字符串转换成int数组，并划分出两个子数组num1,num2，使其和的差最小。 做题思路：设分为两个数组后，这两个数组元素和分别sum1，sum2。这里的差是指绝对值，也就是大的减去小的。在这里，我们先假设sum1≥sum2。那么要求的就是sum1-sum2的值最小。 设sum=sum1+sum2。可以知道，sum的大小是不变的，它就是未划分之前所有元素的和。 那么sum1-sum2=sum1+sum2-2sum2=sum-2sum2。这里就很明显了，因为sum是不变的，我们只要求出满足条件的最大的sum2。这里要注意到sum2满足sum1≥sum2这个条件。那么...