# TopCoder TCO 2018 Round 1A 500 （思维）

## Problem Statement

The Resistance is a multiplayer board game. During the game each player belongs into one of two groups: some are resistance members, others are spies. In this problem there are P players, and exactly S of them are spies. The players are numbered 0 through P-1.

The game is played in rounds. In each round of the game a subset of all players goes on a mission. Each player who goes on the mission casts a secret vote on whether they want it to succeed or to fail. Resistance members always vote for the mission to succeed, and spies may cast either vote. (Sometimes a spy will vote for a mission to succeed in order to gain trust of the other players.) If at least one player on a mission voted for it to fail, the mission fails. If everybody voted for the mission to succeed, it succeeds.

You are given the ints P and S. You are also given the vector <string> missions: data on all the missions that already took place. Each mission is described by a string. The first character of that string is ‘F’ for a failed mission or ‘S’ for a successful one. The next P characters describe which players went on the mission: for each valid i, character (i+1) is ‘1’ if player i went on the misson and ‘0’ otherwise.

Verify whether the mission history is valid. If there is no assignment of roles (spies / resistance members) to players that would be consistent with the given mission history, return an empty vector <double>.

If the mission history is valid, assume that each of the matching assignments of roles to players is equally likely. Return a vector <double> containing P elements. For each i, the i-th element of the return value should be the probability that player i is a spy, given the above assumption.

## Examples

4
1
{"S0110",
"F1100",
"S0011"}
Returns: {0.5, 0.5, 0.0, 0.0}


## AC 代码

#include <bits/stdc++.h>
#define IO                       \
ios::sync_with_stdio(false); \
cin.tie(0);                  \
cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;

class Resistance {
public:
bitset<32> sk;
bool judgeX(int P, vector<string> &missions) {
unordered_set<int> vis;
for (int i = 0; i < P; i++) {
if (sk[i]) {
for (int k = 0; k < (int)missions.size(); k++) {
if (missions[k][i + 1] == '1') {
vis.insert(k);
}
}
}
}
for (int i = 0; i < (int)missions.size(); i++) {
if (missions[i] == 'F') {
if (!vis.count(i))
return false;
}
}
return true;
}

vector<double> spyProbability(int P, int S, vector<string> missions) {
int num = {0};
for (int i = 0; i < (1 << P); i++) {
sk = i;
if (sk.count() != S || !judgeX(P, missions))
continue;
for (int i = 0; i < P; i++) {
if (sk[i]) {
num[i]++;
}
}
}
int cut = 0;
for (int i = 0; i < P; i++) {
cut += num[i];
}
if (cut == 0)
return vector<double>();
double mis = S * 1.0 / cut;
vector<double> ans;
for (int i = 0; i < P; i++) {
ans.push_back(num[i] * mis);
}
return ans;
}

};