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