Codeforces CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) E

Codeforces CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)

CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)

关于想提前下班然后用小号打然后好像还能拿2个虚拟币但懒得领奖这件事

E - Count Seconds

prob.： 给n点m边的DAG，保证有且仅有一个点没有出度，每个点有个点权，每单位时间对于每个点权大于0的点，该点权值-1，所有该点连向的点权值+1，问整个图所有点权值都变成0所需要的时间

ideas： 考虑一个点的点权变化，设点权大于0的状态为1状态，点权为0的状态为0状态，则可能是若干01交替之后一段很长的连续的1然后变成0

考虑出度为0的点什么时候最终变成0

前面01交替的状态比较想不清楚，但由于n其实不是很大，前n单位时间可以暴力计算，然后在此基础上计算对于出度为0的这个点这段为1的状态长度有多少

注意拓扑序遍历，初始化操作以及对于前n单位时间暴力时整个图就已经变成全0的情况

code：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 998244353;
const int N = 1e4 + 10;

ll a[N];
vector<int> g[N], t[N];
ll din[N], cnt[N];

signed main() {
    
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int _;
    cin >> _;
    while (_--) {
    
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
    
            cin >> a[i];
        }
        for (int i = 0; i < m; ++i) {
    
            int x, y;
            cin >> x >> y;
            g[x].push_back(y);
            t[y].push_back(x);
            din[y]++;
        }

        queue<int> que;
        int p = -1;
        for (int i = 1; i <= n; ++i) {
    
            if (g[i].size() == 0) {
    
                p = i;
            }
            if (din[i] == 0) que.push(i);
        }

        vector<int> idx;

        while (!que.empty()) {
    
            int tmp = que.front();
            que.pop();
            idx.push_back(tmp);
            for (auto to : g[tmp]) {
    
                din[to]--;
                if (din[to] == 0) {
    
                    que.push(to);
                }
            }
        }

        reverse(idx.begin(), idx.end());

        bool done = 1;
        for (int tt = 0; tt < n; ++tt) {
    
            done = 1;
            for (auto x: idx) {
    
                if (a[x] <= 0) continue;
                a[x]--;
                done = 0;
                for (auto to : g[x]) {
    
                    a[to]++;
                }
            }
            if (done) {
    
                cout << tt << endl;
                break;
            }
        }
        if (done) {
    
            for (int i = 0; i <= n; ++i) {
    
                g[i].clear();
                t[i].clear();
                din[i] = cnt[i] = 0;
            }
            continue;
        }

        reverse(idx.begin(), idx.end());

        for (auto x : idx) {
    
            cnt[x] = (cnt[x] + a[x]) % mod;
            for (auto to : g[x]) {
    
                cnt[to] = (cnt[to] + cnt[x]) % mod;
            }
        }

        cout << (n + cnt[p]) % mod << endl;

        for (int i = 0; i <= n; ++i) {
    
            g[i].clear();
            t[i].clear();
            din[i] = cnt[i] = 0;
        }
    }
}

F

博弈，sg函数，打表

改天一定