Visits: 1880

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

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