首页 > 试题广场 >

小猿的纸条

[编程题]小猿的纸条
  • 热度指数：343 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小猿有两张分别写着字符串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

输入

1
ac bb abbc 3

输出

1

说明

方案为：1.小猿从第一张纸条撕下a给你。2.小猿将第二张纸条bb给你。3.小猿将第一张纸条剩下的c给你。你收到3张纸条，按顺序拼成abbc，符合条件。
算法知识视频讲解
添加回答
J-Young头像 J-Young 
#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)
牛客880888088头像 牛客880888088 
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)
LKOne头像 LKOne 
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)
JCoder头像 JCoder
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)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 2021 数据库工程师 测试开发工程师 猿辅导 大数据开发工程师 Java工程师
上传者：小小
难度：
6条回答 1746浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号