当前位置: 首页 > news >正文

CRB and String

                        

           CRB and String

题目抽象:给你两个字符串s,t;  每次你可以从s中任选一个字符,再其后插入一个与该字符不相等的字符。经过一定的操作,是否可以是s变成t.

分析:插入一些字符,s要变成t,那么一定要满足s是t的子序列。在此基础上, 如果s[i] != t[j], 那么如果s[i-1] != t[j]或者 k>= 1, s[k -1 ] != s[k], s[k] == s[k+1] == ... == s[i]  ,那么可以插入相应的字符。如果k < 1,那么就不能在第二种情况中插入,那么这就要求,k  t[0] == t[1] == ... ==t[k], s[0->k] ==t[0->k]

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <string>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 #include <stack>
12 #include <cstdlib>
13 #include <sstream>
14 using namespace std;
15 typedef long long LL;
16 const LL INF = 0x5fffffff;
17 const double EXP = 1E-9;
18 const LL MOD = (LL)1E9+7;
19 const int MS = 100005;
20 
21 char s[MS], t[MS];
22 
23 //  s can convert to t
24 // 1: s is subsequence of t
25 // 2: k t[0] == t[1] == ……== t[k]  s[0->k] == t[0->k]
26 
27 int main() {
28     int T;
29     scanf("%d",&T);
30     while (T--) {
31         scanf("%s%s", s, t);
32         int len1 = (int)strlen(s);
33         int len2 = (int)strlen(t);
34         if (len1 >= len2) {
35             if (strcmp(s, t) == 0)
36                 printf("Yes\n");
37             else
38                 printf("No\n");
39             continue;
40         }
41         int k = 0;
42         while (k < len2 && t[k] == t[k + 1])
43             k++;
44         int ok = 1;
45         for (int i = 0; i <= k; i++) {
46             if (i > len1 -1 || s[i] != t[i]) {
47                 ok = 0;
48                 break;
49             }
50         }
51         if (!ok) {
52             printf("No\n");
53             continue;
54         }
55         int s1 = k;
56         int s2 = k;
57         while (s1 < len1 && s2 < len2) {
58             while (s2 < len2 &&s[s1] != t[s2]) {
59                 s2++;
60             }
61             if (s2 < len2) {
62                 s1++;
63                 s2++;
64             }
65             else {
66                 ok = 0;
67                 break;
68             }
69         }
70         if (ok)
71             printf("Yes\n");
72         else
73             printf("No\n");
74     }
75     return 0;
76 }

 

转载于:https://www.cnblogs.com/767355675hutaishi/p/4746220.html

相关文章:

  • CoCoaPods
  • Nova 操作汇总(限 libvirt 虚机) [Nova Operations Summary]
  • Hexo 个人博客搭建
  • 2.4-Apache访问控制
  • Excel文档上传
  • kvm 安装 centos7 文本模式 分辨率 太高修改
  • Android中Activity和Fragment与Fragment和Fragment之前互相传值方法
  • 浅谈sql中的in与not in,exists与not exists的区别
  • 软件工程相关问题
  • 数据结构Java实现04----循环链表、仿真链表
  • 将视频导入到iOS Simulator中
  • SPFA/Dijkstra POJ 3159 Candies
  • 异步函数
  • Android框架之Volley
  • OC变量数据类型
  • [case10]使用RSQL实现端到端的动态查询
  • 【腾讯Bugly干货分享】从0到1打造直播 App
  • 5、React组件事件详解
  • CNN 在图像分割中的简史:从 R-CNN 到 Mask R-CNN
  • gops —— Go 程序诊断分析工具
  • jquery ajax学习笔记
  • Node + FFmpeg 实现Canvas动画导出视频
  • PAT A1050
  • Python打包系统简单入门
  • python学习笔记-类对象的信息
  • React Transition Group -- Transition 组件
  • 前端面试题总结
  • 线上 python http server profile 实践
  • 用Node EJS写一个爬虫脚本每天定时给心爱的她发一封暖心邮件
  • 与 ConTeXt MkIV 官方文档的接驳
  • 阿里云IoT边缘计算助力企业零改造实现远程运维 ...
  • ​LeetCode解法汇总1410. HTML 实体解析器
  • ​软考-高级-信息系统项目管理师教程 第四版【第23章-组织通用管理-思维导图】​
  • #DBA杂记1
  • ( 用例图)定义了系统的功能需求,它是从系统的外部看系统功能,并不描述系统内部对功能的具体实现
  • (+3)1.3敏捷宣言与敏捷过程的特点
  • (2)MFC+openGL单文档框架glFrame
  • (8)Linux使用C语言读取proc/stat等cpu使用数据
  • (JSP)EL——优化登录界面,获取对象,获取数据
  • (pojstep1.1.2)2654(直叙式模拟)
  • (SpringBoot)第二章:Spring创建和使用
  • (八)光盘的挂载与解挂、挂载CentOS镜像、rpm安装软件详细学习笔记
  • (二十五)admin-boot项目之集成消息队列Rabbitmq
  • (附源码)springboot“微印象”在线打印预约系统 毕业设计 061642
  • (附源码)计算机毕业设计SSM在线影视购票系统
  • (九十四)函数和二维数组
  • (淘宝无限适配)手机端rem布局详解(转载非原创)
  • (转)AS3正则:元子符,元序列,标志,数量表达符
  • (转)IOS中获取各种文件的目录路径的方法
  • (转)MVC3 类型“System.Web.Mvc.ModelClientValidationRule”同时存在
  • (轉貼) 蒼井そら挑戰筋肉擂台 (Misc)
  • *上位机的定义
  • .babyk勒索病毒解析:恶意更新如何威胁您的数据安全
  • .NET 3.0 Framework已经被添加到WindowUpdate
  • .Net Core缓存组件(MemoryCache)源码解析