文章

43

粉丝

180

获赞

21

访问

195.0k

头像
O(n)做法
推荐阅读
P1490 北京邮电大学2018年机试题
发布于2022年5月21日 17:38
阅读数 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, res = 0, b[N] = {0};
	    for(auto& t : s)
	    {
	        t & 1 ? ++ y : ++ x;
			int &p = b[y - x + M];
			p || x == y ? res = max(res, x + y - p) : p = x + y;
	    }
	    cout << res << "\n";
	}
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发