Visits: 364

Codeforces Round #647 (Div. 1) – Thanks, Algo Muse!

Johnny and Contribution

傻逼模拟题，用 stable_sort 排序一下，然后判一下无解。

const int N = 5e5 + 7;
int n, m, a[N], p[N], q[N];
vi e[N];

int main() {
    rd(n, m);
    for (int i = 1, x, y; i <= m; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x);
    rda(a, n);
    for (int i = 1; i <= n; i++) p[i] = i;
    stable_sort(p + 1, p + n + 1, [&](int i, int j) {
        return a[i] < a[j];
    });
    for (int i = 1; i <= n; i++) q[p[i]] = i;
    for (int x = 1; x <= n; x++) {
        map<int, bool> v;
        for (int y : e[p[x]])
            if (q[y] < x) v[a[y]] = 1;
        int t = 1;
        while (v[t]) ++t;
        if (t != a[p[x]]) return print(-1), 0;
    }
    printa(p, n);
    return 0;
}

Johnny and Grandmaster

从大到小贪心，每次往少的里面放。

其实是好题，只不过细节很多。

const int N = 1e6 + 7;
int n, p, a[N];

inline void solve() {
    rd(n, p), rda(a, n);
    if (p == 1) return print(n & 1);
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    modint ans = (modint)p ^ a[1];
    ll c = 1;
    int k = a[1], w = log(n) / log(p) + 1;
    for (int i = 2; i <= n; i++) {
        if (k - a[i] > w) {
            if (c > 0) c = n;
            else if (c < 0) c = -n;
            k = a[i];
        } else while (k > a[i]) {
            --k;
            c *= p;
            if (c > n) {
                c = n;
                break;
            }
            if (c < -n) {
                c = -n;
                break;
            }
        }
        if (c <= 0) {
            ans += (modint)p ^ a[i];
            ++c;
        } else {
            ans -= (modint)p ^ a[i];
            --c;
        }
    }
    print(ans);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Johnny and Megan’s Necklace

枚举所有答案，找到答案之后跑个欧拉回路即可。

注意：欧拉回路的路径方案必须在 dfs 之后放入答案，否则是错的！！！！！！

const int N = 2e6 + 7;
int n, a[N], b[N];

int d[N];
vi e[N];
bool v[N];

void dfs(int x) {
    v[x] = 1;
    for (int y : e[x])
        if (!v[y]) dfs(y);
}

inline bool pd(int t) {
    t = (1 << t) - 1;
    for (int i = 0; i <= t; i++)
        d[i] = 0, e[i].clear(), v[i] = 0;
    for (int i = 1; i <= n; i++)
        e[a[i]&t].pb(b[i] & t), e[b[i]&t].pb(a[i] & t),
        ++d[a[i]&t], ++d[b[i]&t];
    for (int i = 0; i <= t; i++)
        if (d[i] & 1) return 0;
    dfs(a[1] & t);
    for (int i = 0; i <= t; i++)
        if (d[i] && !v[i]) return 0;
    return 1;
}

namespace Euler {
    int h[N], e[N], t[N], tot = 1;
    bool v[N];
    vi ans;

    inline void add(int x, int y, int o = 1) {
        e[++tot] = y, t[tot] = h[x], h[x] = tot;
        if (o) add(y, x, 0);
    }

    void dfs(int x) {
        for (int &i = h[x]; i; i = t[i]) {
            if (v[i]) continue;
            v[i] = v[i^1] = 1;
            int y = e[i], j = i ^ 1;
            dfs(y);
            ans.pb(j);
        }
    }

    inline void main(int t) {
        t = (1 << t) - 1;
        for (int i = 1; i <= n; i++)
            add(a[i] & t, b[i] & t);
        dfs(a[1] & t);
        for (int x : ans) print(x - 1, ' '), print((x ^ 1) - 1, ' ');
    }
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i], b[i]);
    int t = 0;
    while (t < 20)
        if (pd(t + 1)) ++t;
        else break;
    print(t);
    Euler::main(t);
    return 0;
}

Johnny and James

咕

James and the Chase

咕

Johnny and New Toy

咕