Codeforces 1088 - 题集

in 题解 with 0 comment

Codeforces 1088A - Ehab and another construction problem

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1088/problem/A


题目

Given an integer $x$, find 2 integers $a$ and $b$ such that:


题意

  给你一个$x$,让你找一对$a$、$b$,使得$a$、$b$满足上述条件。


思路

  显然$x$等于$1$的时候无解,故特判掉,之后虽然可以观察出来解,但还是证明一下吧。

  令:$a = k \cdot b\ (k \in Z)$

  则有:$k \cdot b \cdot b > x$、$k < x$同时成立。

  不妨设:$k = 1$,则有:$b ^ 2 > x$,此时$a = b$,

  即:取$a = b = x$即可。


实现

https://pasteme.cn/2207

#include <bits/stdc++.h>
typedef long long ll;
int main() {
    ll x;
    std::cin >> x;
    if (x == 1) puts("-1");
    else printf("%lld %lld\n", x, x);
    return 0;
}

Codeforces 1088B - Ehab and subtraction

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1088/problem/B


题目

You're given an array $a$. You should repeat the following operation $k$ times: find the minimum non-zero element in the array, print it, and then subtract it from all the non-zero elements of the array. If all the elements are 0s, just print 0.


题意

  你有一个数组$a[n]$,你每次需要找出一个非$0$最小值$min\{a[n]\}$,然后输出这个最小值,并将这个数组中的每一个非$0$元素的值都减去这个最小值。如果这个最小值不存在则输出$0$。


思路

  根据题意模拟即可。


实现

https://pasteme.cn/2208

#include <bits/stdc++.h>
typedef long long ll;
ll base = 0;
std::priority_queue<ll, std::vector<ll>, std::greater<ll>> que;
int main() {
    ll n, k;
    std::cin >> n >> k;
    for (int i = 1, buf; i <= n; i++) std::cin >> buf, que.push(buf);
    while (k--) {
        while (!que.empty() && que.top() == base) que.pop();
        if (que.empty()) puts("0");
        else {
            printf("%lld\n", que.top() - base);
            base += que.top() - base;
            que.pop();
        }
    }
    return 0;
}

Codeforces 1088C - Ehab and a 2-operation task

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1088/problem/C


题目

You're given an array $a$ of length $n$. You can perform the following operations on it:

Can you make the array strictly increasing in no more than $n+1$ operations?


题意

  初始时你有一个元素个数为$n$的数组,第$i$个元素的初始值为$a_i$,你有两种操作:

  问能否在$n + 1$步之内将这个序列变成一个严格递增的序列。


思路

  考虑让$n$个数分别变为模意义下的$1 \dots n$,随便取一个大于$n$的模数,比如说$mod = n + 1$,也就是对于第$i$个数来说,我让其变为$k \cdot mod + i$,这样在进行了$n$次修改之后,第$n + 1$次修改我进行一次取模操作,第$i$个数就会变为$i$了。


实现

https://pasteme.cn/2209

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 2007;
ll a[maxn], base = 0, cnt = 1;
int n, mod;
std::queue<std::pair<int, ll>> ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", a + i);
    mod = n + 1;
    for (int i = n; i >= 1; i--) {
        if ((a[i] + base) % mod == i) continue;
        cnt++;
        ll cur = a[i] + base, add = (mod - cur % mod) + i;
        base += add;
        ans.emplace(i, add);
    }
    printf("%lld\n", cnt);
    while (!ans.empty()) printf("1 %d %lld\n", ans.front().first, ans.front().second), ans.pop();
    printf("2 %d %d\n", n, mod);
    return 0;
}

Codeforces 1088D - Ehab and another another xor problem

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1088/problem/D


题目

This is an interactive problem!

Ehab plays a game with Laggy. Ehab has 2 hidden integers $(a,b)$. Laggy can ask a pair of integers $(c,d)$ and Ehab will reply with:

Laggy should guess $(a,b)$ with at most 62 questions. You'll play this game. You're Laggy and the interactor is Ehab.

It's guaranteed that $0 \le a,b<2^{30}$.


题意

  对方隐藏了两个数$a$、$b$,你可以做一次询问? c d,对方会返回cmp(a ^ c, b ^ c)的值,要你在62步之内询问出$a$、$b$的值是多少。


思路

  总共有$30$位,给了$62$次机会,显然要逐个二进制搞一搞。对于最高位的二进制来说,不难发现,我们query一下1 0query一下0 1的返回值会很有意思:

  1. 如果当前最高位同为1,那么两次query的返回值一定为-11
  2. 如果当前最高位同为0,那么两次query的返回值一定为1-1
  3. 如果当前最高位不同,那么两次query的返回值一定相同。

  对于第三种情况看起来似乎有点难办?其实只要在最开始query一下0 0,根据返回值即可判断两个数的大小,那么最高位不同的时候大的那个数的最高位一定是1,另一个数则一定是0。随后更新一下两个数的大小关系即可。

  对于如何取最高位的问题,其实我们只要把前面已经得到的部分二进制和原数query一下,那么比当前位高的二进制位就自然变为0了。


实现

https://pasteme.cn/2210

#include <bits/stdc++.h>
int query(int a, int b, int ret = 0) {
    printf("? %d %d\n", a, b);
    fflush(stdout);
    scanf("%d", &ret);
    return ret;
}
int main() {
    int a = 0, b = 0;
    bool aIsBigger = true;
    if (query(a, b) < 0) aIsBigger = false;
    for (int i = 29; ~i; i--) {
        int x = query(a ^ (1 << i), b), y = query(a, b ^ (1 << i));
        if (x == y) {
            if (aIsBigger) a ^= (1 << i);
            else b ^= (1 << i);
            aIsBigger = (x == 1);
        } else if (x == -1 && y == 1) a ^= (1 << i), b ^= (1 << i);
    }
    printf("! %d %d\n", a, b);
    return 0;
}

Codeforces 1088E - Ehab and a component choosing problem

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1088/problem/E


题目

You're given a tree consisting of $n$ nodes. Every node $u$ has a weight $a_u$. You want to choose an integer $k$ $(1 \le k \le n)$ and then choose $k$ connected components of nodes that don't overlap (i.e every node is in at most 1 component). Let the set of nodes you chose be $s$. You want to maximize:

$$\frac{\sum\limits_{u \in s} a_u}{k}$$

In other words, you want to maximize the sum of weights of nodes in $s$ divided by the number of connected components you chose. Also, if there are several solutions, you want to maximize $k$.

Note that adjacent nodes can belong to different components. Refer to the third sample.


题意

  你有一个拥有 $n$ 个节点的树,你要选 $k$ 个联通块出来,使得这 $k$ 个联通块中所有点的权值总和 $sum$ 与联通块个数 $k$ 的比值最大,多解时应使联通块的数量尽可能地多。


思路

  考虑贪心,先求出权值和最大的联通块的权值和,记为 $max$ ,然后统计有多少个联通块的权值和与 $max$ 相等即可,显然,这样的贪心策略是最优的。


实现

https://pasteme.cn/2211

#include <bits/stdc++.h>
const int maxn = int(3e5) + 7;
int n, a[maxn], cnt;
std::vector<int> edge[maxn];
long long max = -(int(1e9) + 7);
long long dfs(int u, int pre, bool flag) {
    long long sum = a[u];
    for (int v : edge[u]) if (v != pre) sum += std::max(0ll, dfs(v, u, flag));
    if (!flag) max = std::max(max, sum);
    else if (sum == max) cnt++, sum = 0;
    return sum;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1, 1, false), dfs(1, 1, true);
    printf("%lld %d\n", cnt * max, cnt);
    return 0;
}
Responses