Educational Codeforces Round 130 (Rated for Div. 2) C. awoo's Favorite Problem
2022/7/8 6:20:04
本文主要是介绍Educational Codeforces Round 130 (Rated for Div. 2) C. awoo's Favorite Problem,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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'的操作
这篇关于Educational Codeforces Round 130 (Rated for Div. 2) C. awoo's Favorite Problem的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程