自己网站的登录api怎么做,网站公众号建设工具,市场营销策划书模板,58同城做网站怎么做思路#xff1a;
对于一个类似的东西进行前缀和#xff1a;
G R G G R G
G#xff1a;1 1 2 3 3 4
R#xff1a;0 1 1 1 2 2
差#xff1a;1 0 1 2 1 2
所得关于差的数列#xff0c;同样的数最左最右的位置差为一个答案#xff0c;选取最大的答案即为解#xff0…思路
对于一个类似的东西进行前缀和
G R G G R G
G1 1 2 3 3 4
R0 1 1 1 2 2
差1 0 1 2 1 2
所得关于差的数列同样的数最左最右的位置差为一个答案选取最大的答案即为解注意为0特判位置即答案。
至于为什么用前缀和的思想同位差相等那么这段区间的差就相等所以记录一个差的最早出现位置就行注意负数溢出加上一个常数便可。 ACcode: #includebits/stdc.h
using namespace std;
#define int long long
const int N1e610;
int p[2*N],laN,ans;
string s;
void solve() {cins;int lens.size();for(int i1; ilen; i) {if(s[i-1]R)la;else la--;if(p[la]0)p[la]i;else ansmax(ans,i-p[la]);if(laN)ansi;}coutans\n;
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t1;
// cint;while(t--) {solve();}return 0;
}
over~
