SRM 567

Rating += 52

250
这个题写得圡爆了
因为bitset没有重载<弄了好久，最后直接重写了……搞得只剩100分多一点 太圡了。 本质是找<=n的数里面，分解素因子以后，指数奇偶性mask和自己相同的数的个数。 做法是把指数为奇的那些素数乘起来，然后得到一个最小的指数奇偶性mask和自己相同的数值。然后它可以乘的数就是一些完全平方数了。这个先把完全平方数存在一个vector里面然后lower_bound一下算数目就可以了。 500 先统计出每个字母的数目，如果想字典序最小，一定是aaabbbccc这样把相同的字母排在一起的形式。然后和另外的字符串比较的过程中，肯定都是先比a的数目，相等的话再比b的数目，如此下去…… 于是每次选一个X的拥有数目是最大之一的字母。如果此时，X是唯一一个最大的，那么就符合了，否则继续。 比赛的时候cha得不够果断啊，要不然起手就能cha两个500

int num[55][26];
int used[26];

vector  getWinningStrings(vector  S) {
	vector  ans;
	memset(num, 0, sizeof(num));
	int n = S.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < S[i].size(); j++)
			num[i][S[i][j] - 'a']++;
	}
	for (int i = 0; i < n; i++) {
		bool flag = 0;
		memset(used, 0, sizeof(used));
		vector  vec;
		for (int j = 0; j < n; j++) if (j != i) vec.push_back(j);
		while (!flag) {
			bool found = 0;
			for (int j = 0; j < 26; j++) {
				if (!used[j]) {
					int Max = -1;
					foreach (it, vec)
						if (num[*it][j] > Max) Max = num[*it][j];
					if (Max < num[i][j]) {
						flag = 1;
						found = 1;
						break;
					}
					if (Max == num[i][j]) {
						found = 1;
						used[j] = 1;
						vector  tmp_vec;
						foreach (it, vec) {
							if (num[*it][j] == Max) tmp_vec.push_back(*it);
						}
						vec = tmp_vec;
						break;
					}
				}
			}
			if (!found) break;
		}
		if (flag) ans.push_back(i);
	}
	return ans;
}

1000
从后往前搜索，每次对后面的决策有影响的就是那些山的轮廓线……要注意这个轮廓线高度只可能+1 -1或者不变……所以可以用一个初始高度h0加上一个50位的三进制数表示。
然后用map记忆化搜索就好了。
……至于轮廓线数目为什么很少，我也不是很清楚-.-，但是感觉已经把本质相同的状态都合并了，也没有什么再可以利用的信息的，所以不这么做大概也没法做了。
值得一提的是，似乎用map < vector , int >这样的记忆化方法也可以过……真是好像敢写就敢过……
推荐[[iwi]]的代码
还有练习房里WJMZBMR的无节操hash压状态版本……