275分：
题目描述：
有N个纸牌，正面依次编号1~N，反面有颜色，素数为红色，否则为蓝色。
现在从这N个纸牌中抽取x张，按照由小到大的顺序摆放，反面朝上，问这x张有几张可以确定数字，能的话是多少。
N = 1000， x = 50
解题报告：
正反两边扫描
正向：从1~N，凡是满足颜色的就记录，得到数组A
反向：从N~1，凡是满足颜色的就记录，得到数组B
AB数据相同的就是可以确定的，否则不能确定。
代码如下：

http://s4/middle/64675f54t9afe8bad2293&690srm 495 div1 275 && 500" TITLE="topcoder srm 495 div1 275 && 500" />


500分：
题目描述：
有N个盒子，只有一个盒子是空的，其他都有萝卜，并且每个盒子都有一定的信息，指示其他的盒子是否为空，
比如有3个盒子的关系矩阵如下
YYN
NYY
YNY
表示第一个盒子可以知道第二个盒子有没有东西，
第二个盒子可以知道第三个，第三个盒子可以知道第一个。
问你兔子不用打开空的盒子就可以找出空的盒子的概率是多大，假定兔子采用最优策略。
例子：
YYYY
NYNN
NNYN
NNNY
概率为0.75（采用最优策略，盒子不在第一个盒子的概率为0.75，一旦兔子打开第一个盒子，就可以知道哪个盒子是空的）
解题报告：
把关系矩阵缩点后，很容易知道，从所有入度为0的点出发，可以得到所有盒子的信息。
假设有N个盒子，缩点后有k个点，那么我们至少可以以 (N - k) / N的概率找到空盒子（即空盒子不在那k个里面的概率）
但是这个不一定是最优的，比如
YNNN
NYNN
NNYN
NNNY
这样缩点后仍然是四个，(4 - 4) / 4 = 0不是最优的策略。
这种情况，存在更优的一种策略：即能够得到N - 1个盒子的信息，也便能够推测出N个盒子的信息（因为只有一个是空的）。
所以，得到如下算法：
对关系图缩点，得到k个点。
暂定概率为(N - K) / N
然后检测C（K, K - 1)能否推测出N - 1个盒子的信息（可以利用floyd简化处理），如果可以，概率就优化为：(N - (K - 1)) / N
主体代码如下：
int belong[SIZE], num[SIZE], cnt;
int dfn[SIZE], low[SIZE], index, instack[SIZE], sta[SIZE], top;
vector<int> v[SIZE];
void tarjan(int id)
{
    dfn[id] = low[id] = ++index;
    instack[id] = 1; sta[top++] = id;
    for(int i = 0; i < v[id].size(); i++)
        if (!dfn[v[id][i]])
        {
            tarjan(v[id][i]);
            if (low[v[id][i]] < low[id]) low[id] = low[v[id][i]];
        }
        else if (instack[v[id][i]] && dfn[v[id][i]] < low[id])
            low[id] = dfn[v[id][i]];
    if (dfn[id] == low[id])
    {
        int tmp;
        do
        {
            tmp = sta[--top]; instack[tmp] = 0;
            belong[tmp] = cnt;
            num[cnt]++;
        }while(tmp != id);
        cnt++;
    }
}

void solve(int n)
{
    memset(num, 0, sizeof(num));
    memset(instack, 0, sizeof(instack));
    cnt = 0; index = 0; top = 0;
    memset(dfn, 0, sizeof(dfn));
    for(int i = 0; i < n; i++) //i从1还是0开始视题目而定
 if (!dfn[i]) tarjan(i);
}
bool rd[SIZE];
double theProbability(vector <string> str)
{
    int n = str.size();
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if (str[i][k] == 'Y' && str[k][j] == 'Y') str[i][j] = 'Y';
    cout << "size " << n << endl;
    bool vst[SIZE];
    for(int i = 0; i < SIZE; i++) v[i].clear();
    for(int i = 0; i < str.size(); i++)
        for(int j = 0; j < str[i].length(); j++)
            if (str[i][j] == 'Y')
                v[i].push_back(j);
    solve(n);
    memset(rd, false, sizeof(rd));
    for(int i = 0; i < str.size(); i++)
        for(int j = 0; j < str[i].length(); j++)
            if (belong[j] != belong[i] && str[i][j] == 'Y')
                rd[belong[j]] = true;
    int rd0_num = 0;
    for(int i = 0; i < cnt; i++)
        if (rd[i] == false) rd0_num++;
    cout << "cnt " << cnt << endl;
    cout << "rd0_num " << rd0_num << endl;
    double ans = 1 - rd0_num * 1.0 / n;
    bool exist = false;
    for(int i = 0; i < cnt; i++)
        if (rd[i] == false)
        {
            memset(vst, false, sizeof(vst));
            int tmp = 0, id = -1;
            for(int j = 0; j < n; j++)
                if (belong[j] == i) tmp++, id = j;
            if (tmp == 1)
            {
                //cout << "exist!!!!" << endl;
                for(int j = 0; j < n; j++)
                    if (j != id && rd[belong[j]] == false)
                        for(int k = 0; k < str[j].length(); k++)
                            if (str[j][k] == 'Y') vst[k] = true;
                bool flag = true;
                for(int j = 0; j < n && flag; j++)
                    if (j != id && str[id][j] == 'Y' && !vst[j])
                        flag = false;
                if (flag)
                {
                    exist = true;
                    break;
                }

            }
        }
    cout << "exist " << exist << endl;
    if (exist) ans = 1 - (rd0_num - 1) * 1.0 / n;
    return ans;
}