下载爱城市网app官方网站,做视频网站视频放在哪里,计算机应用技术网站开发方向,打码挂机网站建设题意#xff1a; 给定两个字符串s1,s2利用s1去构造s2,s1有无限个#xff0c;可以翻转#xff0c;你最少要用几个s1才能构造s2。输出每一次使用的s1的有效区间。 伪思路#xff1a; 据说是暴力就能过的题目。然而自己就是暴力差#xff0c;模拟差#xff0c;DP差。。。… 题意 给定两个字符串s1,s2利用s1去构造s2,s1有无限个可以翻转你最少要用几个s1才能构造s2。输出每一次使用的s1的有效区间。 伪思路 据说是暴力就能过的题目。然而自己就是暴力差模拟差DP差。。。。mdzz好像都差不会怎么暴力。 其他思路都想过一点然后剩下两个比较可能的 ①我暴力一发s2以s2的字符为开始然后暴力过去让s1去正的反的匹配所以怎么记录但是这样细节上处理太多了比如这个刚好接上或者不是刚好接上。这样的细节处理。 ②我暴力一发s2每次取正反然后一直暴力到终点每次取正反暴力。如果正反都是没有结果直接可以标记掉然后put-1。 但是这样的不好就是中间的情况的太多了如果每次都有情况的话那么就是2^很多次左右吧但是这个len(s2)是有2100这么暴力无非是作死。如果每次取最优呢也就是每次我拿长的。。。这样真的可以么。。。直觉就是80%不行。就是觉得如果我这次正的比较长然后可能会比较短然后执行比较短的下次会比较长。然后好像举不出例子所以要试一发。其实打起来也是很吃力啊。 #include bits/stdc.h
//#includeiostream
//#includecstdio
//#includemath.h
//#includestring.h
//#includealgorithm
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const double eps1e-6;
const double piacos(-1.0);
const int mod998244353;
const int INF0x3f3f3f3f;const int N1200;char s1[N*2];
char s2[N*2];
int dp[N*2][3];int main()
{int flag,n,m,k,j,h1,h2;int num;int len1,len2;scanf(%s%s,s1,s2);len1strlen(s1);len2strlen(s2);flagk0;num0;int s,t;int x;for(int i0;ilen2;){int nextpos-1;int p1,p2;for(int j0;jlen1;j){int kj;int nexti;while(klen1s1[k]s2[next])k,next;if(nextnextpos){nextposnext;p1j1;p2k;}}for(int jlen1-1;j0;j--){int kj;int nexti;while(k0s1[k]s2[next]){next;k--;}if(nextnextpos){nextposnext;p1j1;p2k2;}}if(inextpos){puts(-1);return 0;}inextpos;dp[num][0]p1;dp[num][1]p2;num;}printf(%d\n,num);for(int i0;inum;i){printf(%d %d\n,dp[i][0],dp[i][1]);}return 0;
} 转载于:https://www.cnblogs.com/keyboarder-zsq/p/5934427.html
