小猿有两张分别写着字符串s1、s2的纸条，字符串由大小写字母组成。小猿会进行n次操作，每次操作时小猿会选择其中一张纸条，把它从左侧撕下一段或把它全部交给你。你按收到纸条的顺序，从左到右将收到的n张纸条拼接成一张新的纸条。
已知字符串s1、s2，求是否存在一种方案使新纸条上的字符串与s3相同、且满足n<=K。
[编程题]小猿的纸条
- 热度指数：347 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行输入T（T ≤ 20），表示输入T组数据。接下来T行，每行按顺序输入字符串s1、s2、s3和正整数K（K ≤ 50），用空格分开。字符串s1、s2长度不超过200，s3长度不超过400。
输出描述:
输出T行，每行输出对应组数据方案是否存在。存在输出1，不存在输出0。
示例1
输入
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;
}
发表于 2021-06-26 15:09:36
回复(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;
}
}
发表于 2021-04-10 20:33:47
回复(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);
}
}
编辑于 2022-08-07 15:54:56
回复(0)
dp[i][j][k] 为 使用第一个串的 前 i 个字符 和 使用第二个串的 前 j 个字符 组合成 第三个串的前 i+j 个字符，并且最后一个字符来自第一个串(k = 0) 或者第二个串(k = 1) 的时候，需要的最少撕纸的次数
那么子问题就是：
1、如果最后一个字符来自于第一个串(k = 0)，那要么倒数第二个字符来自于第一个串(不增加撕纸次数)，要么倒数第二个字符来自于第二个串(撕纸次数+1)
2、如果最后一个字符来自于第二个串(k = 1)，情况和上面相反
#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;
}
发表于 2021-08-13 19:39:04
回复(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;
}
编辑于 2021-08-01 18:01:27
回复(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");
}
}
}
发表于 2021-04-09 11:04:07
回复(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
