P1642 字符串区间翻转 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年3月22日 12:45

字符串区间翻转题解：ac80的同学应该是没有设置多组输入，这题也没说

P1642

回复 0 | 赞 0 | 浏览 719

#include<bits/stdc++.h> using namespace std; const int N = 1e7+5; int arr[N]; int dp[N]; //char s[N]; int main() { int n; // string s; while (cin >> n) { string s; cin >> ...

我要上岸！

2024年3月7日 16:14

字符串区间翻转题解：

P1642

回复 0 | 赞 0 | 浏览 820

此题参考书上有讲 #include<bits/stdc++.h> using namespace std; int dp[10000001] = { 0 }; int arr[10000001]; char str[10000001]; int main() { int n; while (scanf_s("%d", &n) != EOF) { scanf_s(&quo...

2022年9月5日 09:23

最大连续字串问题的注意事项

P1642

回复 0 | 赞 1 | 浏览 5.5k

最大连续子串和的核心思想在于以每个数字作为字串的最后一位，看其和是多少而反转问题转化为最大连续子串和后，需注意可以一个数字也不选，比如1111111 #include<bits/stdc++.h> using namespace std; int a[10000001]; int dp[10000001]; char s[10000001]; int main() { int n; while (scanf("...

2021年2月18日 23:30

字符串翻转

P1642

回复 0 | 赞 0 | 浏览 9.1k

思路：遇1见一，遇0加一，和最大子列和差不多 /* * Description: 字符串区间翻转 (http://noobdream.com/DreamJudge/Issue/page/1642/) * Author: 鱼翔浅底 * Date: 2021-02-18 22:57:14 */ #include <cstdio> #include <cstdlib> using namespace std; //翻转后得到的最多1的个数 int StringFlip(char s[], int N) { ...

2020年5月31日 20:57

P1642

回复 0 | 赞 2 | 浏览 8.8k

代码有点丑见谅，拿到题可以想到，如果反转，那么我们必须翻转一个0的数目多余1的数目的子串，而且是差值越大越好，那么我们将1看作-1，0看作1，求最大连续区间和，该值就是我们最多可以通过反转再得到的1的数目，加上串中本来的1的数目就是答案 #define ll long long #define inf 0x3f3f3f3f #define MAX 10000007 #define vec vector<int> #define P pair<int,int> int main() { string s; int n, dp[MAX], ...

2020年3月16日 11:41

动态规划&&字符串翻转

P1642

回复 0 | 赞 2 | 浏览 8.1k

这个题如果看了对应的动态规划的视频或者n诺的教程，这个题的原理应该不难理解。主要是有两个细节，这里我最开始考虑的是把输入的字符0换做-1，字符1就是1，为了统计数量方便，和最大字段和的思路一样。后来发现没有必要，这里是动态规划的思想，没必要强行去套格式，主要是理解到这里的核心是这里的递推或者说迭代更新，不需要强行去修改原来的字符串。实际上，要找到动态规划中的递推式并不容易，如果是机试遇到的题目没有见过，那还是大概率凉凉，还是要多积累。另一个细节是这里的dp数组记录的是差值，即我们需要的值，我想这个是关键点，无论是不是动态规划，这个翻转的本质就是某子段中的数...

题目字符串区间翻转

题解数量6

热门题解

1 有趣的dp题

2 动态规划&&字符串翻转

3 最大连续字串问题的注意事项

4 字符串区间翻转题解：

5 字符串区间翻转题解：ac80的同学应该是没有设置多组输入，这题也没说多组输入啊

6 字符串翻转