250 EllysJuice:

Brief description:

有两杯果汁饮料，有 n 个人次，每人每次可以喝其中的一杯，每次喝一半。
现在只知道人次信息，不知道顺序，问有多少人有可能喝的是最多的。
（n <= 8)

Analysis:

注意到当第有人喝了 2 次时，可以安排其喝第一杯的第一口和第二杯的第一口。
之后其他人无论怎么喝也超不过这个值即可。

500 EllysFractions:

Brief description:

问分子和分母的积是一个阶乘数（不超过 N!）的假分数一共有多少。

Analysis:

注意到因子的独立性即可。

1000 EllysLights:

Brief description:

给定一个灯和一组开关，每个灯至多和两个开关联系。
给定初始灯的状态，问最少需要次开关操作可以熄灭所有灯。

Analysis:

亦或方程组，注意到问题的特殊性大概暴搜也是可以的。

/* -&$&#*( &#*@)^$@&*)*/

const int MOD = 1000000007;
const int INF = 0x7fffffff;

const int N = 50;


class EllysJuice {
public:
	vector <string> getWinners(vector <string> players) {

		map<string ,int> Hash; int up = 0;

		REP(i, SZ(players)) checkMax(up, ++Hash[players[i]]);

		vector <string> res;

		if (up >= 2){
		    for(map<string, int>::iterator it = Hash.begin(); it != Hash.end(); ++it)
		        if (it->second >= 2) res.PB(it->first);
		}
		else {
		    if (SZ(Hash) == 1) res.PB(players[0]);
		}

		return res;
	}
};

/* -&$&#*( &#*@)^$@&*)*/

const int MOD = 1000000007;
const int INF = 0x7fffffff;

const int N = 50;

bool isPrime(int n){
    FOR(i, 2, n) if (n % i == 0) return false;
    return true;
}


class EllysFractions {
public:
	long long getCount(int n) {
        LL res = 0; int cnt = -1;
        FOR(i, 2, n+1) cnt += isPrime(i), res += 1LL << cnt;
		return res;
	}
};

/* -&$&#*( &#*@)^$@&*)*/

const int MOD = 1000000007;
const int INF = 999;

const int N = 50;

vector<int> L[N]; LL op[N], state, forbid;
int n, m, res;

#define o1 L[x][0]
#define o2 L[x][1]

int dfs(int x = 0){

    if (x == n) return 0;

    int res = INF;

    if (SZ(L[x]) == 0){
        if (!_1(state, x)) res = dfs(x+1);
    }
    else if (SZ(L[x]) == 1){
        if (_1(state, x)){
            state ^= op[o1];
            res = dfs(x+1)+1;
            state ^= op[o1];
        }
        else {
            res = dfs(x+1);
        }
    }
    else if (SZ(L[x]) == 2){
        if (_1(state, x)){
            state ^= op[o1];
            res = dfs(x+1)+1;
            state ^= op[o1];
            state ^= op[o2];
            checkMin(res, dfs(x+1)+1);
            state ^= op[o2];
        }
        else {
            res = dfs(x+1);
            state ^= op[o1], state ^= op[o2];
            checkMin(res, dfs(x+1) + 2);
            state ^= op[o1], state ^= op[o2];
        }
    }

    return res;
}


class EllysLights {
public:
	int getMinimum(string initial, vector <string> switches) {

	    n = SZ(initial), m = SZ(switches);

	    REP(i, n) CLR(L[i]); RST(op), res = state = forbid = 0;

	    REP(i, m) FOR(j, i+1, m) if (switches[i] == switches[j]){
	        switches[j] = string('N', n);
	    }

	    REP(i, m) REP(j, n){
            if (switches[i][j] == 'Y'){
                L[j].PB(i), op[i] |= _1(j);
            }
	    }

        REP(i, n) if (initial[i] == 'Y') state |= _1(i);

        REP(x, n) if (_1(state, x)){
            if (L[x].empty()) return -1;
            if (SZ(L[x]) == 1) state ^= op[o1], forbid |= _1(o1), ++res;
        }
        else {
            if (SZ(L[x]) == 1) forbid |= _1(o1);
        }

        REP(i, n) CLR(L[i]);

	    REP(i, m) if (!_1(forbid, i)){
            REP(j, n){
                if (switches[i][j] == 'Y'){
                    L[j].PB(i); break;
                }
            }
	    }

        res += dfs(); if (res >= INF) res = -1;

		return res;
	}
};

Posted by xiaodao
Category: TopCoder