。。。。这场我睡过了。。 /$:o~o ）。。
（。。另外题目好像略水。。

DIV 1 Level 2:

Brief description:

… n 个字符串。。玩家 1 选择一个字符串作为主串。。并且可以制定一个字符表的排列顺序。。再任意重排该字符串。。
。。玩家 2 可以任意重排其他字符串。。问有多少字符串作为主串时。。玩家 2 无论怎么重排其他串。。都无法小于主串。。（字典序。。

Analysis:

。。显然对于每个字符串只需要保存每个字符出现了多少次。。。枚举每个字符串。。判断其是否可以成为先手必胜串。
。。。。算法是反复迭代。每一轮至少去掉一个字符。或者宣判失败。。因此复杂度 O(n × nc)..

const int N = 59;

int freq[N][26];

class StringGame {
public:
	vector <int> getWinningStrings(vector <string> s) {

		int n = SZ(s);
		RST(freq); REP(i, n) REP(j, SZ(s[i])) ++freq[i][s[i][j] - 'a'];

		VI res; REP(i, n){
            static bool used[26]; RST(used);
		    VI rest; REP(j, n) if (i != j) rest.PB(j);
            for (bool flag = true; flag;){
                flag = false; REP(c, 26) if (!used[c]){
                    int j; REP_N(j, SZ(rest)) if (freq[rest[j]][c] > freq[i][c]) break;
                    if (j != SZ(rest)) continue;
                    VI next; REP(j, SZ(rest)) if (freq[rest[j]][c] == freq[i][c]) next.PB(rest[j]);
                    rest = next, used[c] = flag = true;
                }
                if (rest.empty()) res.PB(i), flag = false;
            }
		}

		return res;
	}
};

（。。完整代码、、

DIV 1 Level 3:

Brief description:

给定一个 2 维格点。。按照顺序在上面绘制 n 座　“山”　型的图案。。（有覆盖关系。。
。。山型的图案由山顶的坐标唯一确定。。。现在给定每座山的高度。。以及每一列出现过哪些山。
。。。计数满足该要求的山顶坐标方案的总数。。
（ 。。n <= 10。。列数 <= 50 。。。

Analysis:

。。。初看题目非常不容易下手。。但是山的数目只有 10 。。而且覆盖关系是固定的、、
。以前设想过对 vector<int> 进行编码后。。进行的记忆化搜索。。虽然总是有其他正确解法。）
。。不过对这题来说居然就是这么做的。。

算法就是从后往前。。进行暴力记忆化搜索。。对每一层记录当前的最大高度。。
。。。用这个高度来判断遮盖关系。。（注意常数。。。

const int P = 3214567;
const int N = 50;

map<ULL, int> F[10];
VI h; bool v[10][N]; int n, m;

int f(int k, int h[N]){
    if (k < 0) return 1;
    ULL x = 0; REP(i, m) x *= P, x += h[i];

    if (F[k].count(x)) return F[k][x];
    int &res = F[k][x], hh[N]; REP(i0, m){
        int i; REP_N(i, m){
            int hi = ::h[k] - abs(i-i0);
            if (hi > h[i] != v[k][i]) break;
            hh[i] = max(h[i], hi);
        }
        if (i == m) INC(res, f(k-1, hh));
    }
    return res;
}


class Mountains {
public:
	int countPlacements(vector <int> h, vector <string> v) {
	    ::h = h, n = SZ(h), m = SZ(v[0]); //REP(i, n) CLR(F[i]);
	    REP_2(i, j, n, m) ::v[i][j] = v[i][j] == 'X';
	    int _h[N]={}; return f(n-1, _h);
	}
};

（。。完整代码.。。

Posted by xiaodao
Category: TopCoder