https://codeforc.es/contest/1697/problem/C

因为规则中,两种字符串变换都与‘b’有关,所以我们根据b的位置来进行考虑;

先去掉所有的'b',如果两字符串不相等就“NO”;

否则通过‘b'在a,b串中的位置,如果posa>posb,那么他们之间如果出现'a'就说明不可能

如果posb<posa,那么他们之间如果出现'c'说明不可能

 1 # include<iostream>
2 # include<bits/stdc++.h>
3 using namespace std;
4 const int N = 3e5 + 10;
5 #define int long long
6 # define endl "\n"
7 int suma[N], sumc[N];
8 char a[N], b[N];
9 char newa[N], newb[N];
10 int posa[N], posb[N];
11 void solve() {
12 int n;
13 cin >> n;
14 cin >> a + 1 >> b + 1;
15 int cnt1 = 0, cnt2 = 0;
16 for (int i = 1; i <= n; ++i) {
17 if (a[i] == 'a') suma[i] = suma[i - 1] + 1;
18 else suma[i] = suma[i - 1];
19 if (a[i] == 'c') sumc[i] = sumc[i - 1] + 1;
20 else sumc[i] = sumc[i - 1];
21 if (a[i] != 'b') newa[++cnt1] = a[i];
22 if (b[i] != 'b') newb[++cnt2] = b[i];
23 }
24
25 if (cnt1 != cnt2) {
26 cout << "NO" << endl;
27 return;
28 }
29 for (int i = 1; i <= cnt1; ++i) {
30 if (newa[i] != newb[i]) {
31 cout << "NO" << endl;
32 return;
33 }
34 }
35 cnt1 = 0, cnt2 = 0;
36 for (int i = 1; i <= n; ++i) {
37 if (a[i] == 'b') posa[++cnt1] = i;
38 if (b[i] == 'b') posb[++cnt2] = i;
39 }
40 if (cnt1 != cnt2) {
41 cout << "NO" << endl;
42 return;
43 }
44 for (int i = 1; i <= cnt1; ++i) {
45 int x = posa[i], y = posb[i];
46 if (x < y) {
47 if (suma[y] - suma[x - 1] != 0) /*前缀和判断a的位置*/
         {
48 cout << "NO" << endl;
49 return;
50 }
51 }
52 if (x > y) {
53 if (sumc[x] - sumc[y - 1] != 0) {
54 cout << "NO" << endl;
55 return;
56 }
57 }
58
59 }
60 cout << "YES" << endl;
61 }
62 int tt;
63 signed main() {
64 ios::sync_with_stdio(false);
65 cin.tie(0);
66 cout.tie(0);
67
68 cin >> tt;
69
70 while (tt--)solve();
71 return 0;
72 }
73 /*
74
75 */

主要是通过前缀和来判断两个pos之间是否存在'a'或者'c'的操作

最新文章

  1. C#异常处理经验(原则与方法)
  2. Redis在windows下安装过程
  3. WM_COPYDATA进程间通信方案
  4. 时间改成24小时制 和pc mobile链接自动转化
  5. Android悬浮窗实现 使用WindowManager
  6. C语言面试题(二)
  7. 在线制作h5
  8. 关于seajs
  9. nginx php解析过慢
  10. VMware vSphere Client为虚拟机制定物理网卡(图文并茂)
  11. Hadoop2.6 Ha 安装
  12. Azure Messaging-ServiceBus Messaging消息队列技术系列5-重复消息:at-least-once at-most-once
  13. PHP站内搜索
  14. 实现Redhat Linux 6和Windows通过Windows Server AD统一认证并共享访问Oracle ZS存储系统
  15. 使用velodyne16线激光雷达跑loam-velodyne
  16. Long类型参数传到前端精度丢失的解决方案
  17. AGC027 D - Modulo Matrix 构造
  18. mysql 操作sql语句 目录
  19. Struct2中自定义的Filter无效
  20. xen 安静的角落

热门文章

  1. 【漏洞分析】KaoyaSwap 安全事件分析
  2. 第七十三篇:解决Vue组件中的样式冲突
  3. KingbaseES R6 集群创建流复制只读副本库案例
  4. HDFS 分布式环境搭建
  5. 目标检测-SSD算法从零实现
  6. 【ASP.NET Core】自定义Session的存储方式
  7. c#中容易被忽视的foreach
  8. Python 代码智能感知 —— 类型标注与特殊的注释(献给所有的Python人)
  9. Django 创建 APP和目录结构介绍
  10. 基于深度学习的文本分类案例:使用LSTM进行情绪分类