P1360 [USACO07MAR]Gold Balanced Lineup G TJ

题目链接

思路

本来用的模拟,结果发现码力过蒻,写不出来。
然后搞了一个 (hash) ,存每一天的能力提升数,循环加减,判断能否被 (111(m个1)) 整除,(TLE.)
(hash) 可以写正解,但是最后看到一个 (map) ,学着打了一遍。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
map <vector <int> ,int > s;
int n ,m ,ans = 0;
int main () {
	scanf ("%d%d",&n ,&m);
	vector <int > now (m);
	s[now] = 0;
	for (int q = 1 ,x;q <= n;++ q) {
		scanf ("%d",&x);
		for (int w = 0;w < m;++ w) {
			if (x & (1 << w)) now[w] ++;
		}
		if (x & 1)
			for (int w = 0;w < m;++ w) now[w] --;
		if (s.count(now)) ans = max (ans ,q - s[now]);
		else s[now] = q;
	}
	printf ("%d
",ans);
	return 0;
}

cb
原文地址:https://www.cnblogs.com/tuscjaf/p/13917260.html