SRM 567

Rating += 52

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int num[55][26];
int used[26];
 
vector <int> getWinningStrings(vector <string> S) {
	vector <int> 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 <int> 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 <int> 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压状态版本……

发表评论

电子邮件地址不会被公开。