某島

… : "…アッカリ~ン . .. . " .. .
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 呢。。