Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) 题解

作者: xht37 分类: 题解 发布时间: 2020-03-04 05:18

点击数:378

Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)

Kuroni and the Gifts

由于 $a,b$ 分别互不相同,因此想让 $a+b$ 互不相同,对 $a,b$ 分别排序即可。

const int N = 107;
int n, a[N], b[N];

inline void solve() {
    rd(n), rda(a, n), rda(b, n);
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++)
        print(a[i], " \n"[i==n]);
    for (int i = 1; i <= n; i++)
        print(b[i], " \n"[i==n]);
}

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

Kuroni and Simple Strings

要求最终不能再存在 () 这样的子串,因此只能是若干个 ) 后接若干个 (

因此我们要找到一个位置,这个位置左边的 ( 全部被删掉,右边的 ) 全部被删掉。

由于只能删掉同等数量的 (),而这个位置一定存在,因此答案要么为 $0$,要么为 $1$。

const int N = 1e3 + 7;
int n, a[N], b[N];
char s[N];

int main() {
    rds(s, n);
    vi ans;
    for (int i = 1; i <= n; i++)
        a[i] = a[i-1] + (s[i] == '(');
    for (int i = n; i; i--)
        b[i] = b[i+1] + (s[i] == ')');
    for (int i = 0; i <= n; i++)
        if (a[i] == b[i+1]) {
            for (int j = 1; j <= i; j++)
                if (s[j] == '(') ans.pb(j);
            for (int j = i + 1; j <= n; j++)
                if (s[j] == ')') ans.pb(j);
            if (!ans.size()) {
                print(0);
                return 0;
            }
            print(1);
            print(ans.size());
            for (int x : ans) print(x, ' ');
            return 0;
        }
    return 0;
}

Kuroni and Impossible Calculation

这个绝对值看起来不太好搞,那么我们排序一下,就一定是后面减前面了。

依次考虑每个数与前面的数对答案的贡献,但我们显然不能 $\mathcal O(n^2)$ 枚举。

注意到这个模数非常小,因此我们对前面的数开一个桶,记录每个余数的个数。

那么我们只需要 $\mathcal O(nm)$ 就可以求出每个可能的差的数量,最后快速幂一下就能求出答案了。

什么,你问 $\mathcal O(nm)$ 不是 $2 \times 10^8$ 吗,怎么能过?

你要相信 CF 神机一秒跑十亿不成问题。

const int N = 2e5 + 7, M = 1e3 + 7;
int n, a[N], c[M];
ll f[M];
modint ans = 1;

int main() {
    rd(n), rd(P), rda(a, n);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] %= P;
        for (int j = 0; j < P; j++)
            f[(a[i]-j+P)%P] += c[j];
        c[a[i]]++;
    }
    for (int i = 0; i < P; i++) ans *= (modint)i ^ f[i];
    print(ans);
    return 0;
}

Kuroni and the Celebration

每次询问两个点的 LCA,最多询问 $\lfloor \frac{n}{2} \rfloor$ 次确定根。

很傻的一道交互题。

注意到如果一个叶子和另一个点的 LCA 就是这个叶子,那么这个叶子一定为根;如果不是,则这个叶子一定不是根。

那么我们每次询问两个叶子的 LCA 即可,如果是其中某一个点,则那个点就是根;否则删掉两个点,注意可能产生新的叶子。

最坏情况下,每次询问会删掉两个叶子,那么 $\lfloor \frac{n}{2} \rfloor$ 次后最多只剩下一个点,这个点显然就是根了。

const int N = 1e3 + 7;
int n, d[N], v[N];
vi e[N];

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, e[x].pb(y), e[y].pb(x), d[x]++, d[y]++;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (d[i] == 1) q.push(i);
    for (int i = 1; i <= n / 2; i++) {
        int x = q.front();
        q.pop();
        int y = q.front();
        q.pop();
        cout << "? " << x << " " << y << endl;
        fflush(stdout);
        int z;
        cin >> z;
        if (z == x || z == y) {
            cout << "! " << z << endl;
            return 0;
        }
        for (int z : e[x])
            if (!v[z] && (--d[z] == 1)) q.push(z);
        for (int z : e[y])
            if (!v[z] && (--d[z] == 1)) q.push(z);
        v[x] = v[y] = 1;
    }
    for (int i = 1; i <= n; i++)
        if (!v[i]) cout << "! " << i << endl;
    return 0;
}

Kuroni and the Score Distribution

要求构造一个长度为 $n$ 的单调上升序列 $a$,使得恰好有 $m$ 个三元组 $(i,j,k)(i < j < k)$ 满足 $a_i + a_j = a_k$。

很傻的一道构造题。

先 $1,2,3,4,5,\dots$ 的填,产生的三元组个数为 $0,0,1,1,2,\dots$。

一直填到第一次个数 $\ge m$ 的位置,假设多了 $k$ 个。

注意到在这个位置上的数每增加 $2$,个数会减 $1$,因此这个位置上的数加上 $2k$ 即可。

后面的不应该再存在满足条件的三元组了,那么填一定间隔下最大的几个数就够了。

如果填完 $n$ 个数,三元组的数量依旧 $< m$,则说明无解,因为这个填数的方法最大化了三元组的数量。

const int N = 5e3 + 7;
int n, m, a[N];

int main() {
    rd(n), rd(m);
    int t = 0;
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
        t += i >> 1;
        if (t >= m) {
            a[i] += (t - m) << 1;
            for (int j = n - 1, k = 1e9; j > i; j--, k -= i + 2)
                a[j] = k;
            for (int j = 0; j < n; j++)
                print(a[j], " \n"[j==n]);
            return 0;
        }
    }
    print(-1);
    return 0;
}

Kuroni and the Punishment

首先可以知道答案一定 $\le n$,这个界还可以再紧一点,一定 $\le$ 奇数的个数,设为 $t$。

考虑找到所有最终可能的 $\gcd$,随便找一个数 $x$,由于最多 $+t/-t$,因此这个 $x$ 最终只能在 $[a_i-t, a_i+t]$ 这个范围内,因此 $\gcd$ 也只能在这个范围内的数的质因数中。

我们对这个范围做区间筛,即可找到所有的质因数。具体而言,设这个区间为 $[l,r]$,则可能的 $\gcd$(即所有质因数)包括:

  1. $2 \sim \sqrt r$ 内的所有质数,称为小质数
  2. 对于 $x \in [l,r]$,$x$ 超过 $\sqrt r$ 的质因数,而这个质因数最多只有一个,称为大质数

把这些可能的 $\gcd$ 全部暴力 check,check 的时候剪枝就行了。

看起来复杂度不太对,但是实际上长得很像答案的 $\gcd$ 最多只有 $12$ 个,其中 $10$ 个是小质数,$2$ 个是相邻的大质数。

const int N = 2e5 + 7;
const ll M = 2e6;
int n;
bool v[M|1];
ll a[N];
vector<ll> p, q;

int main() {
    for (ll i = 2; i <= M; i++) {
        if (v[i]) continue;
        p.pb(i);
        for (ll j = i * i; j <= M; j += i) v[j] = 1;
    }
    q = p;
    rd(n), rda(a, n);
    sort(a + 1, a + n + 1);
    ll d = a[1];
    for (int i = 2; i <= n; i++) d = __gcd(d, a[i]);
    if (d != 1) return print(0), 0;
    ll t = 0;
    for (int i = 1; i <= n; i++) t += a[i] & 1;
    ll l = max(M + 1, a[n] - t), r = a[n] + t;
    map<ll, ll> w;
    for (ll i = l; i <= r; i++) w[i] = i; 
    for (ll x : p) 
        for (ll i = l / x * x; i <= r; i += x)
            if (i >= l) while (!(w[i] % x)) w[i] /= x;
    for (ll i = l; i <= r; i++)
        if (w[i] > M) q.pb(w[i]);
    for (ll x : q) {
        if (x == 2) continue;
        ll o = 0;
        for (int i = 1; i <= n; i++) {
            o += min(a[i] < x ? x : a[i] % x, x - a[i] % x);
            if (o >= t) break;
        }
        t = min(t, o);
    }
    print(t);
    return 0;
}

Kuroni and Antihype

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

Kuroni the Private Tutor

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

2条评论
  • lob

    2020年3月4日 下午10:32

    题解太棒了,简单易懂,谢谢博主分享

    1. xht37

      2020年3月4日 下午11:00

      不谢

发表评论

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