Codeforces Round 467 (Div. 2)

比赛链接：https://codeforces.com/contest/937

A. Olympiad

找有多少个不同的数，0不算

int a[N];
void solve() {
    int n; cin >> n;
    int f = 0;
    set<int> st;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 0) f = 1;
        st.insert(a[i]);
    }
    if (f) cout << st.size() - 1 << endl;
    else cout << st.size() << endl;
}

B. Vile Grasshoppers

在2y上找一个最大的数不能被2p上的数整除

只要从后往前暴力找就可以了，质数距离越到后面越小

假设当前数不是质数且不被2~p上的数整除，那么这个数最小为(p+1)*(p+2)

因此

1. 当$(p+1)*(p+2)>y$时，就是找小于等于y的第一个质数，由于质数距离很小，因此复杂度没问题

2. 当$(p+1)*(p+2)<=y$时，p最多为$\sqrt{y}$ ，因此时间复杂度是$O(\sqrt{y}*w)$，w为最大质数距离

int n, p;
bool check(int x) {
    for (int i = 2; i <= p && 1ll*i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
void solve() {
    cin >> p >> n;
    if (n == p) {
        cout << -1 << endl;
        return;
    }
    for (int i = n; i >= max(p+1,n-2000); i--) {
        if (check(i)) {
            cout << i << endl;
            return;
        }
    }
    cout << -1 << endl;
}

C. Save Energy!

每k分钟自动点火，每d分钟手动点火

首先如果d整除k，那么直接输出t

否则二分答案计算当前时间为mid时，实际加热度为多少

我们发现其实是个循环，每个k到后面那个d的时间是m=d- k%d，那么一个周期就是k+m

ll k, d, t;
bool check(double x) {
    ll m = d - k % d;
    ll mm = k + m;
    ll cnt = x / mm;
    double left = x - cnt*mm;
    double ans = cnt * m * 0.5 + cnt * k;
    if (left - k >= eps) ans += k + (left-k)*0.5;
    else ans += left;
    return ans >= t;
}
void solve() {
    cin >> k >> d >> t;
    if (k % d == 0) {
        cout << t << endl;
        return;
    }
    double l = t, r = 2*t;
    for (int i = 0; i <= 1000; i++) {
        double mid = (l + r) * 0.5;
        if (check(mid)) r = mid;
        else l = mid;
    }
    printf("%0.9lf\n", l);
}

D. Sleepy Game

目的：找环和奇数路径

找环可以直接用tarjan算法，然后把环标记上记号

找奇数路径可以存一个$vis[x][2]$ 代表走到x这个节点经过了偶数/奇数步，这样每个点最多被访问两次

int vis[N][2], flag, ff;
vector<int> G[N];
vector<int> ve;
int dfn[N], low[N], idx, tp, in_stk[N], Vis[N], sd[N], scc;
int vvis[N];
set<int> st[N];
void dfs(int x, int st) {
    if (vis[x][st]) return;
    if (vvis[x]) ff = 1;
    vis[x][st] = 1;
    for (auto v : G[x]) {
        dfs(v, st^1);
        if (flag) {
            ve.push_back(x);
            return;
        }
    }
    if (!G[x].size() && st == 1) {
        ve.push_back(x);
        flag = 1;
    }
}
void tarjan(int x) {
    low[x] = dfn[x] = ++idx;
    Vis[x] = 1;
    in_stk[++tp] = x;
    for (auto v : G[x]) {
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if (Vis[v]) {
            low[x] = min(low[x], dfn[v]);
        }
    }
    if (low[x] == dfn[x]) {
        int y;
        ++scc;
        while(y = in_stk[tp--]) {
            sd[y] = scc;
            Vis[y] = 0;
            st[scc].insert(y);
            if (x == y) break;
        }
    }
}
 
void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int num; cin >> num;
        for (int j = 1; j <= num; j++) {
            int x; cin >> x;
            G[i].push_back(x);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= scc; i++) {
        if (st[i].size() == 1) continue;
        for (auto it : st[i]) vvis[it] = 1;
    }
    int s; cin >> s;
    dfs(s, 0);
    if (flag == 1) {
        cout << "Win" << endl;
        reverse(ve.begin(), ve.end());
        for (auto it : ve) cout << it << ' ';
        cout << endl;
    } else {
        if (scc != n && ff) cout << "Draw" << endl;
        else cout << "Lose" << endl;
    }
 
}