P1642 字符串区间翻转 - 题解

登录注册上岸

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

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

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

2026年3月24日 23:04

字符串区间翻转题解：

P1642

回复 0 | 赞 5 | 浏览 74

#include<iostream> #include<vector> #include<cstring> using namespace std; const int N = 1e7 + 10; int dp[N]; int main() { int n; string str; while(cin >> n >> str) { // 统计1的数量 int cnt = 0; for (int i ...

2026年3月22日 20:09

字符串区间翻转题解：

P1642

回复 0 | 赞 0 | 浏览 48

#include<bits/stdc++.h> using namespace std; int main() { int n; while(scanf("%d",&n)!=EOF) { char s[n]; scanf("%s",s); ...

2026年3月21日 20:19

字符串区间翻转题解：

P1642

回复 0 | 赞 2 | 浏览 74

#include<bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n) { char s[n]; for(int i=0;i<n;i++) &n...

2026年2月16日 11:43

字符串区间翻转题解有一个小细节漏掉了，全1的情况吐了喵：

P1642

回复 1 | 赞 6 | 浏览 237

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n; string s; while (cin >> n >> s) { int start = 0, end = 0, temp_start = 0; int cur_total = 0, max_total = 0; for (int i = 0; i < n; i++) { ...

2026年3月15日 11:30

字符串区间翻转题解：

P1642

回复 0 | 赞 10 | 浏览 121

#include<bits/stdc++.h> using namespace std; const int N = 1e7 + 5; int dp[N]; int a[N]; int main(){ int n; string s; while(cin >> n){ cin >> s; int total = 0; for(int i = 0; i < s.size(); i++){ if(s[i] == '1')...

2020年3月16日 11:41

动态规划&&字符串翻转

P1642

回复 2 | 赞 104 | 浏览 10.4k

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

2026年3月6日 20:59

字符串区间翻转题解：

P1642

回复 0 | 赞 19 | 浏览 284

#include<bits/stdc++.h> using namespace std; const int maxn = 10000005; int a[maxn]; int dp[maxn]; int main(){ int n; while(cin >> n){ string str; cin >> str; int cnt = 0,k = 0; for(char ch:str){ //将0转1,1转-1，然后求最大字段和就可得最多的0个数（转为1），再加上1的个数得答案 if(ch ==...

2026年2月25日 21:38

字符串区间翻转题解：

P1642

回复 0 | 赞 10 | 浏览 178

#include<bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n) { int count = 0;//统计翻转区间能增加的1 int max0 = 0;//最大 ...

岸上的乌龟

2026年2月23日 23:11

字符串区间翻转题解：ac80的原因：使用for循环太多次

P1642

回复 0 | 赞 3 | 浏览 268

因为n最大到10的7次，1s内支持1e7，所以即使时间复杂度是o(n)也得减小n前面省去的常系数，也就是说，少用for循环遍历数组 #include <bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ char buf[n]; for(int i=0;i<n;i++) &...

2026年2月10日 15:58

字符串区间翻转题解：

P1642

回复 0 | 赞 4 | 浏览 172

#include <iostream> using namespace std; int main() { int n; while (cin >> n) { string s; cin >> s; long long cnt = 0, cur = 0, maxx = 0; for (char c : s) { if (c == '1') { cnt++; cu...

1
2

题目字符串区间翻转

题解数量19

发布题解在线答疑

热门题解

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

2 有趣的dp题

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

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

5 字符串区间翻转题解：

6 字符串区间翻转题解：贪心算法最大子列和

7 字符串区间翻转题解：Kadana算法（卡丹算法）

8 字符串区间翻转题解：answer=原字符串1的个数+字符串字区间内0的个数减去1的个数的最大值

9 字符串区间翻转题解：

10 字符串区间翻转题解：