某岛

… : "…アッカリ~ン . .. . " .. .
March 29, 2020

SRM 782

250

骰子最多只有 6 面,所以掷不出来的数直接加入最后的答案,状态压缩 DP 即可。

500

题意:给定一个图,问是否存在一种拓扑排序的方案,并要求点 i 出现的时刻不晚于 f[i]。
(好像是 old 题?)
先跑一遍拓扑排序,然后在 DAG 上用 f 数组 dp 出考虑后续状态的真实的 f 数组,排序判断一下即可。

const int N = 1009;

int Q[N], cz, op;
int in[N]; vector<int> adj[N];

class RankingStudents {
public:
    string rankingPossible(int n, vector <int> f, vector <int> a, vector <int> b) {

        RST(in);REP(i,n)adj[i].clear();
        REP(i, a.size()) {
            in[b[i]]++;
            adj[ a[i]] .PB(b[i] );
        }
        
        cz = 0, op = 0; REP(i, n)if(!in[i]) Q[op++]=i;
        while (cz < op) {
            int u = Q[cz++];
            for (auto v: adj[u]) if (!--in[v]) Q[op++]=v;
        }
        if (op != n) return "Impossible";
        DWN(i, n, 0) {
            int u = Q[i];
            for (auto v: adj[u]) checkMin(f[u], f[v]-1);
        }
        sort(ALL(f));
        REP(i, n) if (i > f[i]) return "Impossible";
        return "Possible";
    }
};

1000

给定一个连通的无向图,初始每个点都是白色,每访问一个节点就会把那个节点的颜色反白,
问是否存在一个不超过 5n 长度的路径,使得所有颜色皆为黑色。

???这题目我不是出过。。。
https://codeforces.com/problemset/problem/453/C

btw: 本场居然有 600 人注册。。说好的 dead game 呢。。