给定一个长度为n的字符串,字符串只有4和7构成,因为BSNY认为只有4和7是幸运数。现在BSNY有m个任务给你,任务有2种: switch l r 把[l, r]区间内的4换成7,7换成4; count 计算这n个幸运数的最长不下降子序列长度。
时间: 2024-05-28 16:12:36 浏览: 9
这是一个比较有趣的问题,可以用线段树和DP相结合的方式来解决。
我们可以先用线段树来维护当前字符串中4和7的数量。对于每个节点,我们可以记录4和7的数量,以及该区间内最长不下降子序列的长度。这样,当我们执行 switch 操作时,可以利用线段树的区间修改操作来实现。
对于 count 操作,我们可以用 DP 来解决。设 dp[i] 表示以第 i 个位置结尾的最长不下降子序列长度。那么,我们可以根据前面的状态 dp[1], dp[2], ..., dp[i-1] 来计算 dp[i]。具体地,如果当前位置是4或7,则 dp[i] = dp[i-1] + 1;否则 dp[i] = 0。最终,最长不下降子序列的长度就是所有 dp[i] 中的最大值。
注意,由于线段树和 DP 都需要 O(nlogn) 的时间来处理,因此总时间复杂度为 O(mnlogn)。需要注意一下这个算法的常数项,可能需要进行优化。
相关问题
给定一个长度为n的字符串,求向左移k位的字符串
思路:将原字符串的前k个字符移到末尾即可。
代码实现:
```python
def left_rotate_string(s, k):
if not s:
return ''
n = len(s)
k %= n
return s[k:] + s[:k]
```
测试:
```python
s = 'abcdefg'
k = 2
print(left_rotate_string(s, k)) # 'cdefgab'
s = 'abc'
k = 5
print(left_rotate_string(s, k)) # 'cab'
```
用c帮我写给定一个长度为n的字符串,求向左移k位的字符串
以下是使用C语言编写的实现代码:
```
#include <stdio.h>
#include <string.h>
void leftShift(char *str, int k);
int main()
{
char str[100];
int k;
printf("请输入一个字符串:");
scanf("%s", str);
printf("请输入向左移动的位数:");
scanf("%d", &k);
leftShift(str, k);
printf("左移后的字符串为:%s", str);
return 0;
}
void leftShift(char *str, int k)
{
int len = strlen(str);
k %= len; // 确保k小于字符串长度
// 将前k个字符移动到字符串末尾
for (int i = 0; i < k; i++) {
char temp = str[0];
for (int j = 1; j < len; j++) {
str[j - 1] = str[j];
}
str[len - 1] = temp;
}
}
```
使用示例:
```
请输入一个字符串:abcdefg
请输入向左移动的位数:3
左移后的字符串为:defgabc
```
解释:将字符串 "abcdefg" 向左移动 3 位,结果为 "defgabc"。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)