P1490 最长平衡串 - 题解

登录注册上岸

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

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

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

2020年3月13日 18:41

思路是用-1替换0，然后用前缀和的思想。主要的技巧是用map存begi

P1490

回复 1 | 赞 0 | 浏览 10.0k

#include<bits/stdc++.h> using namespace std; int main(){ string str; while(cin>>str){ map<int,int> m; int n=str.size(); int dp[n]; dp[0]=0; for(int i=1;i<=n;i++){ if(str[i-1]=='0'){ d...

2022年5月21日 17:38

O(n)做法

P1490

回复 0 | 赞 1 | 浏览 5.0k

把到每个坐标为止的串的位置用x，y记录下来。对于每一个位置得到的点，都能用一个对应的b以y = x + b的形式表示出来；最长串的大小也就是对于每一个存在的b最大的x + y与最小x + y的差的最大值。 #include<bits/stdc++.h> using namespace std; constexpr int N = 2e5 + 10, M = N / 2; int main() { string s; while (cin >> s) { int x = 0, y = 0, r...

2022年3月18日 10:17

啊这，线下耗时最久，考试必败题

P1490

回复 0 | 赞 0 | 浏览 6.0k

#include<iostream> using namespace std; int main() { string str; while (cin >> str) { int total, ans = 0; for (int i = 0; i < str.size(); ++i) { &n...

2021年3月31日 21:22

前缀和

P1490

回复 0 | 赞 0 | 浏览 9.6k

#include <iostream> #include <string.h> #include <map> using namespace std; int main() { string s; map<int, int> m; int len, ans, sum[100005]; memset(sum, 0, sizeof(sum)); while(cin >> s) { ans = 0; len = s.length();...

2020年5月26日 21:31

妙啊

P1490

回复 0 | 赞 0 | 浏览 10.2k

https://blog.csdn.net/csyifanZhang/article/details/106365500 ↑题解 #define ll long long #define vec vector<ll> #define inf 0x3f3f3f3f #define MAX 100005 #define P pair<ll,ll> #define MOD 100000 int main() { string s; int dp[MAX]; dp[0] = 0; while (cin>>s...

题目最长平衡串

题解数量5

热门题解

1 O(n)做法

2 妙啊

3 啊这，线下耗时最久，考试必败题

4 思路是用-1替换0，然后用前缀和的思想。主要的技巧是用map存begin，刚开始用两个循环直接炸了

5 前缀和