Good Bye 2019 题解

作者: xht37 分类: 题解 发布时间: 2020-01-02 17:24

点击数:138

Good Bye 2019

Card Game

谁有 $n$ 谁赢。

inline void solve() {
    int n, a, b, x;
    bool ok;
    rd(n), rd(a), rd(b);
    for (int i = 1; i <= a; i++) {
        rd(x);
        if (x == n) ok = 1;
    }
    for (int i = 1; i <= b; i++) {
        rd(x);
        if (x == n) ok = 0;
    }
    prints(ok ? "YES" : "NO");
}

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

Interesting Subarray

显然如果存在要求的序列,必然存在长度为 $2$ 的要求的序列。

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

inline void solve() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]);
    bool ok = 0;
    for (int i = 1; i < n; i++)
        if (abs(a[i] - a[i+1]) > 1) ok = 1;
    prints(ok ? "YES" : "NO");
    if (ok) {
        for (int i = 1; i < n; i++)
            if (abs(a[i] - a[i+1]) > 1) {
                print(i, ' '), print(i + 1);
                break;
            }
    }
}

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

Make Good

限定所有数异或起来等于一个很大的 $2$ 的幂,同时限定加上的三个数中有两个一样,就可以做了。

const int N = 1e5 + 7;
int n;
ll a[N], s, x;

inline void solve() {
    rd(n), s = x = 0;
    for (int i = 1; i <= n; i++) rd(a[i]), s += a[i], x ^= a[i];
    ll w = 1ll << 54, k;
    vector< ll > ans;
    ans.pb(k = w ^ x);
    w <<= 1;
    w -= s + k;
    ans.pb(w >> 1), ans.pb(w >> 1);
    print(3), print(ans[0], ' '), print(ans[1], ' '), print(ans[2]);
}

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

Strange Device

交互题。

首先可以通过 $n-k+1$ 次询问确定 $n-k+1$ 个位置的值。

若 $n – k + 1 \ge k$,则直接询问已知的 $k$ 个找到 $m$ 即可。

否则,考虑最后一次询问会产生一个已知的位置 $x$ 和 $k-1$ 个未知的位置,我们可以拿另外一个已知的位置 $y$ 分别替换这 $k-1$ 个未知的位置,然后根据回答与不替换时的回答是否一致判断这个位置与 $x$ 位置上的数的大小关系,即可找到这些数中有多少个比位置 $x$ 上的数小,从而求出 $m$。

const int N = 507;
int n, k, a[N];

inline pi ask(vi o) {
    vi O = o;
    sort(o.begin(), o.end());
    cout << '?';
    for (auto c : o) cout << ' ' << c;
    cout << endl;
    fflush(stdout);
    int a, b;
    cin >> a >> b;
    o = O;
    return mp(a, b);
}

int main() {
    cin >> n >> k;
    if (k == 1) return cout << "! 1" << endl, 0;
    vi o, q;
    for (int i = 1; i <= k; i++) o.pb(i);
    for (int i = k; i <= n; i++) {
        pi p = ask(o);
        a[p.fi] = p.se;
        q.pb(p.fi);
        if (i != n)
            for (ui j = 0; j < o.size(); j++)
                if (o[j] == p.fi) o[j] = i + 1;
    }
    if (n - k + 1 >= k) {
        o.clear();
        for (int i = 0; i < k; i++) o.pb(q[i]);
        pi p = ask(o);
        int ans = 0;
        for (int i = 0; i < k; i++)
            if (a[o[i]] <= p.se) ++ans;
        cout << "! " << ans << endl;
        return 0;
    }
    int x = q.back();
    q.pop_back();
    int y = q.back();
    for (ui i = 1; i < o.size(); i++)
        if (o[i] == x) swap(o[0], o[i]);
    int ans = 0;
    for (ui i = 1; i < o.size(); i++) {
        int z = o[i];
        o[i] = y;
        pi p = ask(o);
        if (p.fi == x) ans += a[y] < a[x];
        else ans += a[x] < a[y];
        o[i] = z;
    }
    cout << "! "  << ans + 1 << endl;
    return 0;
}

Divide Points

并查集。

首先把必须在同一组的弄到一起,否则随便分成两组。

const int N = 1e3 + 7;
int n, f[N], t;
ll a[N], b[N];
pair< ll, int > p[N];
pair< ll, pi > q[N*N];

int get(int x) {
    return x == f[x] ? x : (f[x] = get(f[x]));
}

inline ll S(int i, int j) {
    return abs(a[i] - a[j]) * abs(a[i] - a[j]) + abs(b[i] - b[j]) * abs(b[i] - b[j]);
}

inline void work(int x) {
    for (int i = 1; i <= n; i++) p[i] = mp(S(x, i), i);
    sort(p + 1, p + n + 1);
    for (int i = 1; i < n; i++)
        if (p[i].fi == p[i+1].fi)
            f[get(p[i].se)] = get(p[i+1].se);
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), rd(b[i]), f[i] = i;
    for (int i = 1; i <= n; i++) work(i);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            q[++t] = mp(S(i, j), mp(i, j));
    sort(q + 1, q + t + 1);
    for (int i = 1; i < t; i++)
        if (q[i].fi == q[i+1].fi) {
            int j = i + 1;
            int a1 = get(q[i].se.fi), b1 = get(q[i].se.se);
            int a2 = get(q[j].se.fi), b2 = get(q[j].se.se);
            if (a1 == a2) f[b1] = b2;
            else if (a1 == b2) f[b1] = a2;
            else if (b1 == a2) f[a1] = b2;
            else if (b1 == b2) f[a1] = a2;
            else if (a1 == b1) f[a2] = b2;
            else if (a2 == b2) f[a1] = b1;
            else f[a1] = a2, f[b1] = b2; 
        }
    vi ans;
    for (int i = 1; i <= n; i++)
        if (get(i) == get(1)) ans.pb(i);
    print(ans.size());
    for (ui i = 0; i < ans.size(); i++) print(ans[i], ' ');
    return 0;
}

Awesome Substrings

先求出前缀和 $s_{0\dots n}$,转化为求满足 $0 \le i < j \le n$ 且 $j – i = d(s_j – s_i)$ 的 $(i,j)$ 的个数,其中 $d$ 为 $\in [1,n]$ 的正整数。

考虑根号分治,给定一个限制 $T$,移项得 $s_jd – j = s_id – i$,设 $f_i(d) = s_id – i$。

对于 $1 \le d \le T$ 的情况,我们对每个 $d$ 求出 $f_{0\dots n}(d)$ 的值,然后对于每个值 $x$,若有 $k$ 个 $i$ 满足 $f_i(d) = x$,则对答案有 $\binom{k}2$ 的贡献。

这一部分实现优秀的话可达到 $\mathcal O(nT)$。

对于 $T < d \le n$ 的情况,由于 $s_j – s_i = \frac{j-i} d < \frac nT$,即有贡献的 $(a,b)$ 对应的区间中 $1$ 的个数 $k < \frac nT$。因此我们对每个 $i$ 和 $k$ 找到 $j$ 的范围 $(l,r]$,其对答案的贡献为 $\lfloor \frac {r – i}k \rfloor – \lfloor \frac {l – i}k \rfloor$ 去掉 $d \le T$ 的部分。

这一部分实现优秀的话可达到 $\mathcal O(n\frac nT)$。

因此总时间复杂度为 $\mathcal O(nT + n\frac nT)$,取 $T = \sqrt n$ 即可达到最优时间复杂度 $\mathcal O(n \sqrt n)$。

const int N = 2e5 + 7, M = 507;
int n, T, s[N], a[N*M];
char c[N];
ll ans;

int main() {
    rds(c, n), T = sqrt(n);
    for (int i = 1; i <= n; i++) s[i] = s[i-1] + c[i] - '0';
    for (int d = 1, x; d <= T; d++) {
        vi p;
        for (int i = 0; i <= n; i++) x = s[i] * d - i + n, ++a[x], p.pb(x);
        while (p.size()) x = p.back(), p.pop_back(), ans += 1ll * a[x] * (a[x] - 1) / 2, a[x] = 0;
    }
    for (int k = n / T - (T * T == n); k; k--) {
        int l = 0;
        while (l < n && s[l+1] < k) ++l;
        if (l == n) continue;
        int r = l + 1;
        while (r < n && s[r+1] <= k) ++r;
        for (int i = 0; i < n; i++) {
            if (s[r] - s[i] < k) {
                if (r == n) break;
                l = r;
                while (r < n && s[r+1] - s[i] <= k) ++r;
            }
            if ((r - i) / k > T) ans += (r - i) / k - max((l - i) / k, T);
        }
    }
    print(ans);
    return 0;
}

Subset with Zero Sum

由于 $i – n \le a_i \le i – 1$,所以 $1 \le i – a_i \le n$。

建立一张 $n$ 个点的有向图,对于每个点 $i$,连边 $i \to i – a_i$。

这张图中每个点的出度都为 $1$,因此这张图是一个基环内向森林。

可以发现对于任意一个环,环上的点对应的下标就是我们要找的答案。

const int N = 1e6 + 7;
int n, x, t[N], v[N];

inline void solve() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(x), t[i] = i - x, v[i] = 0;
    x = 1;
    while (!v[x]) v[x] = 1, x = t[x];
    vi ans;
    ans.pb(x), x = t[x];
    while (x != ans[0]) ans.pb(x), x = t[x];
    print(ans.size());
    while (ans.size()) print(ans.back(), " \n"[ans.back()==ans[0]]), ans.pop_back();
}

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

Number of Components

题目太神仙了,先咕咕咕着。

Xor on Figures

题目太神仙了,先咕咕咕着。

发表评论

电子邮件地址不会被公开。 必填项已用*标注