小猿有两张分别写着字符串s1、s2的纸条,字符串由大小写字母组成。小猿会进行n次操作,每次操作时小猿会选择其中一张纸条,把它从左侧撕下一段或把它全部交给你。你按收到纸条的顺序,从左到右将收到的n张纸条拼接成一张新的纸条。
已知字符串s1、s2,求是否存在一种方案使新纸条上的字符串与s3相同、且满足n<=K。
第一行输入T(T ≤ 20),表示输入T组数据。接下来T行,每行按顺序输入字符串s1、s2、s3和正整数K(K ≤ 50),用空格分开。字符串s1、s2长度不超过200,s3长度不超过400。
输出T行,每行输出对应组数据方案是否存在。存在输出1,不存在输出0。
1 ac bb abbc 3
1
方案为:1.小猿从第一张纸条撕下a给你。2.小猿将第二张纸条bb给你。3.小猿将第一张纸条剩下的c给你。你收到3张纸条,按顺序拼成abbc,符合条件。
#include <iostream> #include<cstring> using namespace std; bool compare(int p1,int p2,int p3,char s1[],char s2[],char s3[],int from,int k) { //from:1或者2,表示前一个字符来自于s1还是s2,0表示刚刚开始 //k:剩余的可以进行裁剪的次数,小于1时将停止! bool bools1,bools2; bools1 = false; bools2 = false; if(p1<strlen(s1)&&s1[p1]==s3[p3]) { int k1; k1 = (from==1||from==0)?k:k-1; if(k1>0){ if(p3==(strlen(s3)-1)) { bools1 = true; }else{ bools1 = compare(p1+1,p2,p3+1,s1,s2,s3,1,k1); } } } if(p2<strlen(s2)&&s2[p2]==s3[p3]) { int k2; k2 = (from==2||from==0)?k:k -1; if(k2>0) { if(p3==(strlen(s3)-1)) { bools2 = true; }else{ bools2 = compare(p1,p2+1,p3+1,s1,s2,s3,2,k2); } } } return (bools1||bools2); } int main() { int m; cin>>m; while(m--) { char s1[200]; char s2[200]; char s3[400]; int k; cin >> s1 >> s2 >> s3 >> k; int p1,p2,p3; p1 = 0; p2 = 0; p3 = 0; bool is_consistent = true; if(p1<strlen(s1)&&p2<strlen(s2)&&p3<strlen(s3)) { is_consistent = compare(p1,p2,p3,s1,s2,s3,0,k); } cout<<(is_consistent?1:0)<<endl; } return 0; }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for (int i = 0; i < t; i++) { String s1 = scanner.next(); String s2 = scanner.next(); String s = scanner.next(); int count = scanner.nextInt(); if (s1.length() + s2.length() < s.length() || count <= 0) { System.out.println(0); } else { System.out.println(isSuccess(s1.toCharArray(), s2.toCharArray(), s.toCharArray(), count, 0, 0, 0, 0)); } } } // aa bb abba 3 // 1 public static int isSuccess(char[] s1, char[] s2, char[] s, int count, int i, int j, int k, int who) { if (count >= 0 && k >= s.length) { return 1; } else if (count < 0) { return 0; } int res; if (i < s1.length && s1[i] == s[k]) { res = isSuccess(s1, s2, s, who == 0 ? count : count - 1, i + 1, j, k + 1, 0); if (res == 1) { return 1; } } if (j < s2.length && s2[j] == s[k]) { res = isSuccess(s1, s2, s, who == 1 ? count : count - 1, i, j + 1, k + 1, 1); if (res == 1) { return 1; } } return 0; } }
import java.util.Arrays; import java.util.Scanner; /* * * *添加下 @J-Young的答案的java注释版本: *思路是:递归和分类讨论,直接分情况从前一个状态到后一个状态过渡。(动态规划?) *三个指针分别指向三个字符串的开头。 *每次目的是要获取第三个字符串头部的值,只可能来自第一个字符串或者第二个字符串。 *而当前状态可能是由截取了第一个字符串,,或者截取了字符串后,过渡而来的。 * 在compare中体现为compare。而对于当前状态,我们可以分别取判断下一个s3开头的 * 目标字符分别和s1和s2中的哪个匹配。并根据from视情况更新k。比如当前是由截取了s1而来, * 接下来我要看看s3的第一个字符和s1的第一个是否相等,如果相等则有继续匹配的可能性, * 则不撕下来,继续递归,并且保留k不减小。其他情况类推。 * * */ public class Main { public static void main(String[] args) { //准备输入的处理 Scanner in = new Scanner(System.in); int m = in.nextInt();//输入计数 while (m > 0) { m--; char[] s1 = new char[200]; char[] s2 = new char[200]; char[] s3 = new char[400]; int k;//可以截取的次数 //输入的获取 s1 = in.next().toCharArray(); s2 = in.next().toCharArray(); s3 = in.next().toCharArray(); k = in.nextInt(); //三个指针 int p1, p2, p3; p1 = 0; p2 = 0; p3 = 0; //默认是可以的 boolean is_consistent = true; //要求指针满足在规定的范围内 if (p1 < s1.length && p2 < s2.length && p3 < s3.length) { is_consistent = compare(p1, p2, p3, s1, s2, s3, 0, k); } int ans = is_consistent ? 1 : 0; System.out.println(ans); } } public static boolean compare(int p1, int p2, int p3, char s1[], char s2[], char s3[], int from, int k) { //from:1或者2,表示前一个字符来自于s1还是s2,0表示刚刚开始 //k:剩余的可以进行裁剪的次数,小于1时将停止! boolean bools1, bools2; bools1 = false; bools2 = false; //如果s1的当前指针和s3的当前指针指向相同的值 if (p1 < s1.length && s1[p1] == s3[p3]) { int k1; //如果是刚开始,或者来自s1,则新的处理次数不变,否则是-1; k1 = (from == 1 || from == 0) ? k : k - 1; //只有当新的处理次数大于0的时候,才进行处理. if (k1 > 0) { //如果已经处理结束了,返回真 if (p3 == (s3.length - 1)) { bools1 = true; } else { //如果还要继续处理,,则继续比较,同时处理的次数不变,因为后面可能还能有配合的上的字母 bools1 = compare(p1 + 1, p2, p3 + 1, s1, s2, s3, 1, k1); } } } //如果s2的当前指针和s3的当前指针指向相同的值 if (p2 < s2.length && s2[p2] == s3[p3]) { //定义新的处理次数 int k2; //如果正好是从s2,过渡来的,则后面还有可比性,因此不着急处理,k不变,否则需要-1; k2 = (from == 2 || from == 0) ? k : k - 1; //只有当剩余的处理次数大于0的时候,才可以把当前字母截取下来.或者进一步处理 if (k2 > 0) { if (p3 == (s3.length - 1)) { bools2 = true; } else { bools2 = compare(p1, p2 + 1, p3 + 1, s1, s2, s3, 2, k2); } } } return (bools1 || bools2); } }
#include <bits/stdc++.h> using namespace std; int n, m, T; char a[205], b[205], c[405]; int dp[405][405][2]; int main() { scanf("%d", &T); while (T--) { scanf("%s", a); scanf("%s", b); scanf("%s", c); scanf("%d", &m); int la = strlen(a), lb = strlen(b), lc = strlen(c); if (la + lb < lc) { printf("0\n"); return 0; } memset(dp, 0x3f3f3f3f, sizeof dp); for (int i = 1; i <= la; i++) { if (i - 1 >= lc) {continue;} if (c[i - 1] == a[i - 1]) { dp[i][0][0] = 1; } else {break;} } for (int j = 1; j <= lb; j++) { if (j - 1 >= lc) {continue;} if (c[j - 1] == b[j - 1]) { dp[0][j][1] = 1; } else {break;} } for (int i = 1; i <= la; i++) { for (int j = 1; j <= lb; j++) { if (i + j - 1 >= lc) {continue;} if (c[i + j - 1] == a[i - 1]) { dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + 1); } if (c[i + j - 1] == b[j - 1]) { dp[i][j][1] = min(dp[i][j - 1][1], dp[i][j - 1][0] + 1); } } } if (dp[la][lb][0] <= m || dp[la][lb][1] <= m) { printf("1\n"); } else { printf("0\n"); } } return 0; }
#include <iostream> #include <string> using namespace std; // p1:s1-idx p2:s2-idx pt:ts-idx k:剩余匹配次数 from:上次从哪个 bool helper(string s1, string s2, string ts, int p1, int p2, int pt, int k, int from){ if(k==0) return false; // k次内未匹配 if(k>0 && pt==ts.size()) return true; // 全部匹配 bool t1 = false, t2 = false; if(p1<s1.size() && s1[p1]==ts[pt]){ // from==0为第一次匹配,没有上一次 from==1为从s1 from==2为从s2 // 若与上次为同一次,可合并为一次 int k1 = (from==0||from==1)?k:k-1; t1 = helper(s1, s2 ,ts, p1+1, p2, pt+1, k1, 1); } if(p2<s2.size() && s2[p2]==ts[pt]){ int k2 = (from==0||from==2)?k:k-1; t2 = helper(s1, s2, ts, p1, p2+1, pt+1, k2, 2); } return t1||t2; } int main(){ int n; cin >> n; while(n--){ string s1, s2, ts; int k; cin >> s1 >> s2 >> ts >> k; bool res = helper(s1, s2, ts, 0, 0, 0, k, 0); if(res) cout << "1" << endl; else cout << "0" << endl; } return 0; }
import java.util.*; public class Main { static int T; static boolean getAns(String a, String b, String c, int maxn) { char[] sa = a.toCharArray(); char[] sb = b.toCharArray(); char[] sc = c.toCharArray(); int l1 = sa.length; int l2 = sb.length; int l3 = sc.length; int[][][] f = new int[l1 + 1][l3 + 1][3]; for (int i = 0; i <= l1; i++) for (int j = 0; j <= l3; j++) for (int k = 0; k <= 1; k++) f[i][j][k] = 10000; int num; int rmax; rmax = Math.min(l3, l2); for (int j = 1; j <= Math.min(l2, l3); j++) if (sb[j - 1] == sc[j - 1]) { f[0][j][1] = 1; if (j == l3 && maxn >= 1) return true; } else { break; } for (int i = 1; i <= l1; i++) { rmax = Math.min(l3, i + l2); for (int j = i; j <= rmax; j++) { num = f[i][j][0]; if (sa[i - 1] == sc[j - 1]) { if(i == 1 && j == 1) num = f[1][1][0] = 1; num = Math.min(num, f[i - 1][j - 1][0]); num = Math.min(num, f[i - 1][j - 1][1] + 1); f[i][j][0] = num; if (j == l3 && num <= maxn) return true; } if (j > i) { num = f[i][j][1]; if (sb[j - i - 1] == sc[j - 1]) { num = Math.min(num, f[i][j - 1][0] + 1); num = Math.min(num, f[i][j - 1][1]); // f[i][j][1] = Math.min(f[i][j][1], Math.min(f[i][j - 1][0], f[i][j - 1][1])); f[i][j][1] = num; if (j == l3 && num <= maxn) return true; } } } } return false; } public static void main(String[] args) { Scanner reader = new Scanner(System.in); T = reader.nextInt(); reader.nextLine(); String[] strs; int num; for (int i = 1; i <= T; i++) { strs = reader.nextLine().split("\\s+"); num = Integer.parseInt(strs[3]); if (getAns(strs[0], strs[1], strs[2], num)) System.out.println("1"); else System.out.println("0"); } } }