文章

68

粉丝

691

获赞

26

访问

575.6k

头像
妙啊
P1490 北京邮电大学2018年机试题
发布于2020年5月26日 21:31
阅读数 10.1k

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)
	{
		s = ' ' + s;
		map<int, int> m;
		m[0] = 0;
		for (int i = 1; i < s.size(); i++) {
			if (s[i] == '0')dp[i] = dp[i - 1] - 1;
			else dp[i] = dp[i - 1] + 1;
			if (m.find(dp[i]) == m.end())
				m[dp[i]] = i;//记录最早出现的这些值的位置
		}
		int res = 0;
		for (int i = 1; i < s.size(); i++) {
			int l = m[dp[i]];
			if (i - l > res)res = i - l;
		}
		cout << res << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发