动态规划思想
思路：
本题需要用动态规划求解，MCS[i][j] 记录短字符串 s1 前 i 个字符和长字符串 s2 前 j 个字符的最长子串的长度，初始化所有值为 0 。当 s1[i-1] = s2[j-1] 时， MCS[i][j] = MCS[i - 1][j - 1] + 1 ，这里使用一个额外的值 start 来记录最长子串在短字符串 s1 中出现的起始位置， maxlen 记录当前最长子串的长度，当 MCS[i][j] > maxlen 时， maxlen = MCS[i][j] ， 则 start = i - maxlen ；档 s1[i-1] != s2[j-1] 时不需要任何操作，最后获取 substr(start, maxlen) 即为所求
1、转移方程为： 如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，
（dp[i][j]=dp[i−1][j−1]+1），如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
2、
vector<vector<int>> MSC(len1+1,vector<int>(len2+1,0));
解析：
用vector构造二维数组，用len2+1构造行并全部初始化为0，用vector<int>(len2+1,0)（初始化为0的行）构造len1+1个列；即：将整个数组初始化为0
（建议先看第二题）
#include <iostream> #include<vector> using namespace std; string getcomsubstr(string &s1,string &s2) { if(s1.size()>s2.size()) swap(s1,s2);//要输出在较短串中最先出现的 int len1=s1.size(); int len2=s2.size(); vector<vector<int>> MSC(len1+1,vector<int>(len2+1,0)); int start=0,maxsize=0; for(int i=1;i<=len1;i++) //一较短串为基础，才能找较短串中最先出现的 for(int j=1;j<=len2;j++) { if(s2[j-1]==s1[i-1]) MSC[i][j]=MSC[i-1][j-1]+1; if(MSC[i][j]>maxsize)//有更长公共子串，更新长度 { maxsize=MSC[i][j]; //以i结尾的最大长度max，则起始位置为i-max start=i-maxsize; } } return s1.substr(start,maxsize); } int main() { string str1,str2; while(cin>>str1>>str2) { string sub=getcomsubstr(str1,str2); cout<<sub<<endl; } return 0; }
经典DP
思路：
求最大公共子串，使用递推实现 假设 x(i): 字符串第 i 个字符 y(j): 字符串第 j 个字符 dp[i][j]: 以 x(i),y(j) 结尾的最大子串长度 比如： x: "abcde" y:"bcdae" dp[2][1]: 以 x(2),y(1) 结尾的最大子串长度 即： x 遍历到 "abc", y 遍历 到 "bc", 都以字符 'c' 结尾时最大公共子串为 "bc" 故：当计算 dp[i][j] 时，首先看 x(i),y(j) 的值：
（ 1 ） : x(i) == y(j) 当前两个字符串结尾的字符相等， dp[i][j] = dp[i-1][j-1] + 1 即个它的长度加 1 （2 ） : x(i) != y(j) 当前两个字符 串结尾的字符不相等，说明没有以这连个字符结尾的公共子串 即 dp[i][j] = 0
（3 ） : dp[0][j] 和 dp[i][0] 表示以 某个子串的第一个字符结尾，最大长度为 1 如果 x(0) == y(j) 或者 x(i) == y(0), 则长度为 1 ，否则为 0 当 dp 中的 所有元素计算完之后，从中找打最大的值输出
#include <iostream> #include<vector> using namespace std; int getcomsubstr(string &s1,string &s2) { int len1=s1.size(); int len2=s2.size(); vector<vector<int>> MSC(len1+1,vector<int>(len2+1,0)); int start=0,maxsize=0; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(s2[j-1]==s1[i-1]) MSC[i][j]=MSC[i-1][j-1]+1; if(MSC[i][j]>maxsize)//有更长公共子串，更新长度 { maxsize=MSC[i][j]; } } return maxsize; } int main() { string str1,str2; while(cin>>str1>>str2) { int maxv=getcomsubstr(str1,str2); cout<<maxv<<endl; } return 0; }
简单的数学问题
看到题目字数和样例人麻了？其实只是一道小学奥数题
思路：
每次读取一个数之后，算出他经过 k 次洗牌后的位置，只用一个长度为 2n 数组用来输出
根据当前数的位置，可以算出经过一次洗牌后的位置
如果当前数小于等于n（即在左手），则他下次出现的位置是 2*当前位置
与之对应的当前位置 + n（即在右手）的牌,则他下次出现的位置是 2*当前位置 + 1
高效率地把一个数组的内容复制给另一个数组:
#include <stdio.h> #define SIZE 3 int main() { int a[SIZE], b[SIZE]={1,2,3}; register int *x, *y; for( x = a, y = b ; y < &b[SIZE] ; ) *x++ = *y++; return 0; }
#include <iostream> using namespace std; int main() { int T,n,k; cin>>T; while(T--) { cin>>n>>k; int num=2*n; int card[num+1]; for(int i=0;i<num;i++) cin>>card[i]; while(k--) { int tmp[num+1]; int *x,*y; for(x=tmp,y=card;y<&card[num+1];) *x++=*y++; for(int j=0;j<n;j++) { card[2*j]=tmp[j]; //左手的牌排放的位置 card[2*j+1]=tmp[j+n];//右手的牌排放的位置 } } for(int i=0;i<num-1;i++) cout<<card[i]<<" "; cout<<card[num-1]<<endl; } } // 64 位输出请用 printf("%lld")
