D. a-Good String

el/2024/5/21 22:16:13

传送门

题意

一个字符串如果长度为1 并且为’a’ 那么就是 a -good 字符串,
当长度大于1时, 需要满足 : 将总区间划分成一半, 其中一半全是a,另一半必须为b-good 字符串 以此类推

分析

这道题的做法比较直观,不断将字符串分段,然后递归下去,主要思想为分治,时间复杂度为标准的nlogn

代码

用dfs,类似于归并排序的思想,统计出上半段符合当前深度的字母,下半段符合当前深度的字母,然后递归下去即可

好像没有合适的剪枝方法,我剪枝三次一直是WA2,后来直接暴力ac了2333

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;const int N = 131080;
int a[N];int dfs(int l,int r,int d){if(r - l == 1){if((a[l] == d && a[r] == d + 1 )|| (a[l] == d + 1 && a[r] == d)) return 0;if(a[l] == d || a[l] == d + 1 || a[r] == d || a[r] == d + 1) return 1;return 2;}int m = (r + l - 1) / 2;int sum1 = 0,sum2 = 0;for(int i = l;i <= m;i++) if(a[i] == d) sum1++;for(int i = m + 1;i <= r;i++) if(a[i] == d) sum2++;int ans1 =(m - l + 1 - sum2) + dfs(l,m,d + 1);int ans2 =(m - l + 1 - sum1) + dfs(m + 1,r,d + 1);return min(ans1,ans2);
}int main(){int T,n;cin >> T;while(T--){cin >> n;char str[N];cin >> (str + 1);for(int i = 1;i <= n;i++) a[i] = str[i] - 'a' + 1;if(n == 1){if(a[1] == 1)cout << 0 << endl;elsecout << 1 << endl;continue;}cout << dfs(1,n,1) << endl;;}}

http://www.ngui.cc/el/5239385.html

相关文章

大师 洛谷P4933

大师 题目链接 大师 题目描述 建筑大师最近在跟着数学大师ljt12138学数学&#xff0c;今天他学了等差数列&#xff0c;ljt12138决定给他留一道练习题。 ljt12138首先建了n个特斯拉电磁塔&#xff0c;这些电塔排成一排&#xff0c;从左到右依次标号为1到n&#xff0c;第i个…

C. Good String

传送门 分析 给你一串字符串&#xff0c;你可以擦去一部分字符&#xff0c;剩下一个字符串t,要求最后剩下的字符串t满足这样的性质&#xff1a;字符串&#x1d461;2&#x1d461;3…&#x1d461;&#x1d45b;−1&#x1d461;&#x1d45b;&#x1d461;1和字符串 &#x…

Travel 最短路

链接&#xff1a;https://ac.nowcoder.com/acm/problem/14292 来源&#xff1a;牛客网 题目描述 精灵王国有N座美丽的城市&#xff0c;它们以一个环形排列在Bzeroth的大陆上。其中第i座城市到第i1座城市花费的时间为d[i]。特别地&#xff0c;第N座城市到第1座城市花费的时间为…

飞行路线 |分层图初步学习

链接&#xff1a;https://ac.nowcoder.com/acm/problem/15073 来源&#xff1a;牛客网 题目描述 Alice和Bob现在要乘飞机旅行&#xff0c;他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务&#xff0c;设这些城市分别标记为0到n-1&#xff0c;一共有m种航…

设计密码 —— 状态机

来源&#xff1a;acwing 题目描述 你现在需要设计一个密码 S&#xff0c;S 需要满足&#xff1a; S 的长度是 N&#xff1b; S 只包含小写英文字母&#xff1b; S 不包含子串 T&#xff1b; 例如&#xff1a;abc 和 abcde 是 abcde 的子串&#xff0c;abd 不是 abcde 的子串…

A. Remove Smallest

传送门 分析 这道题的意思大概是说有一串数字&#xff0c;你每次可以取出两个数字x&#xff0c;y&#xff0c;但要求是x和y相差不能超过1&#xff0c;然后你可以任意删去一个数字&#xff0c;这种操作可以进行无数次。 给你一个数组&#xff0c;然后让你判断能不能通过这种操…

迷宫2 ——单调队列解决bfs问题

链接&#xff1a;https://ac.nowcoder.com/acm/problem/15196 来源&#xff1a;牛客网 题目描述 这是一个关于二维格子状迷宫的题目。迷宫的大小为N*M&#xff0c;左上角格子座标为(1,1)、右上角格子座标为(1,M)、左下角格子座标为(N,1)、右下角格子座标为(N,M)。每一格都用-…

D. 505

传送门 分析 这个道题的题意是给你一个n * m的01矩阵&#xff0c;然后可以更改矩阵中的数字&#xff0c;比如把0改成1&#xff0c;或者把1改成0&#xff0c;要求最后矩阵中没有任何一个边长为偶数的子矩阵中含有偶数个1&#xff0c;如果不含偶数边长的子矩阵&#xff0c;则不…

Fluctuation Limit 构造

链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6860. 来源&#xff1a;杭电多校第八场 题目描述 给你n个范围[li,ri]和一个整数x&#xff0c;要求构建一个长度为n的数组ai&#xff0c;要求保证ai > li && ai < ri,并且保证相邻两个x之间的差值的…

C. Boboniu and Bit Operations

传送门 分析 写的时候没注意到数据范围&#xff0c;一直在想dp的做法&#xff0c;后来才发现这个数据范围其实可以枚举暴力的 我们从0开始枚举答案&#xff0c;如果有一个答案满足对任意一个ai&#xff0c;均能找到一个bj&#xff0c;使得(a[i] & b[j]) | x) x&#xf…