Codeforces Round 525 (Div. 2)

还可以。

A

Description

有一个整数 $x$，找到一对满足以下条件的两个正整数 $a,b$：

$1\leq a,b\leq x$；
$a$ 能被 $b$ 整除；
$ab>x$；
$\dfrac{a}{b}<x$。

$x\leq100$。

Solution

$x$ 很小，直接枚举 $a,b$。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using std::cin;
using std::cout;
using std::endl;

int main()
{
    int x;
    cin >> x;
    for (int a = 1; a <= x; a++)
        for (int b = 1; b <= x; b++)
            if (a % b == 0 && a * b > x && 1.0 * a / b < x)
            {
                cout << a << " " << b << endl;
                return 0;
            }
        }
    cout << -1 << endl;
}

B

Description

有一个数组 $a$，和一个正整数 $k$，你需要重复一下操作 $k$ 次：找到最小的非零数，把其它的数都减去这个数，把这个数变为 $0$。输出每次操作找到的数。

Solution

排序然后模拟。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1e5 + 10;

int n, a[maxn], k;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    std::sort(a + 1, a + 1 + n);
    int pos = 1, lzy = 0;
    while (k--)
    {
        int now = pos;
        if (pos > n)
        {
            cout << 0 << endl;
            continue;
        }
        while (pos <= n && a[pos] == a[now])
            pos++;
        cout << a[now] - lzy << endl;
        lzy += a[now] - lzy;
    }
}

C

Description

有一个长度为 $n$ 的数组 $\{a_i\}$，你可以对其进行一下两个操作之一：

选一个下标 $i$ 和一个正整数 $x$，将这个数组以 $i$ 为结尾的前缀都加上 $x$；
选一个下标 $i$ 和一个正整数 $x$，将这个数组以 $i$ 为结尾的前缀都加对 $x$ 取模。

你需要在 $n+1$ 个操作内把这个数组变成严格单调递增的，输出你的操作。、

$1\leq n\leq2000,0\leq a_i\leq10^5$，你选择的 $x$ 需要满足 $1\leq x\leq10^6$。

Solution

发现 $n,a_i$ 都和 $x$ 差了很多，很容易想到构造一个 $1\sim n+1$ 的数组的方法：我们可以直接把整个数组都加上一个很大的数，设这个数是 $X$，那么接下来 $n$ 次操作依次取模即可。

具体地，第 $i$ 次第二个操作是把以 $i$ 为结尾的前缀对 $a_i+X-i$ 取模。

确定 $X$ 的值也很简单，$X=(a_i-i)_{max}$。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 2010;
int X = 1e6;

int a[maxn], n;

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], mx = std::max(mx, a[i] - i);
    X -= mx;
    cout << n + 1 << endl;
    cout << 1 << " " << n << " " << X << endl;
    for (int i = 1; i <= n; i++)
        cout << 2 << " " << i << " " << a[i] + X - i << endl;
    return 0;
}

D

Description

这是一道交互题。

交互库选择了两个数 $(a,b)$ 。每次询问一个二元组 $(c,d)$，返回 $a\oplus c$ 和 $b\oplus d$ 的大小关系。你需要在 $62$ 次询问内确定 $a,b$，保证 $0\leq a,b\leq2^{30}$。

Solution

我们显然可以一位一位考虑，尝试在 $2$ 次操作之内得到一位的答案。

考虑我们能得到什么信息，显然一开始询问 $(0,0)$ 可以得到 $a,b$ 的大小关系，那么我们就从大小关系入手。

因为大小比较是从高到低比的，我们就从高到低确定每一位。

假设我们在第 $i$ 位，有 $a,b$ 中包括这一位以及比这一位低的数的大小关系 $flag$，比第 $i$ 位高的已经确定好的 $a,b$ 。我们先问一遍 $c=a\oplus2^i,d=b\oplus2^i$。如果得到的大小关系和 $flag$ 不一样，那么 $a,b$ 在这一位就不相等，根据原先的 $flag$ 就能确定这一个 $1$ 在 $a,b$ 的哪个数上，然后再问一次更新 $flag$；如果相等就再问一次确定这一位是 $1$ 还是 $0$。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

int flag;

int ask(int a, int b)
{
    int x;
    cout << "? " << a << " " << b << endl;
    cin >> x;
    if (x == -2)
        exit(0);
    return x;
}

int a, b, lsta, lstb;

int main()
{
    flag = ask(0, 0);
    for (int i = 29; i >= 0; i--)
    {
        int res = ask(a ^ (1 << i), b ^ (1 << i));
        if (res != flag)
        {
            if (flag == -1)
                b ^= 1 << i;
            else
                a ^= 1 << i;
            flag = ask(a, b);
        }
        else
        {
            int p = ask(a ^ (1 << i), b);
            if (p == -1)
                a ^= 1 << i, b ^= 1 << i;
        }
    }
    cout << "!" << " " << a << " " << b << endl;
}

E

Description

给定一棵 $n$ 个节点的树，点有点权 $a_u$，可能为负。现在请你在树上找出 $k$（$1~\leq~k~\leq~n$）个不相交集合，每个集合中的点构成一个联通块。

设选出的所有点的集合为 $s$，最大化 $\dfrac{\sum_{u\in s}a_u}{k}$，在满足前面那个东西最大的前提下，最大化 $k$。

Solution

发现我们是要最大化每个集合中点权和的平均值。

那么有一个结论（感性理解）：我们选点权最大的集合，平均值最大。

那么还要最大化 $k$，就尽可能多选这个点权最大的集合就行。

设计一个很简单的树形 DP：$f(i)$ 为选 $i$ 为根子树最大权值。$f(i)=w_i+\sum max(0,f(v))$。

然后统计一下最大值，再 DP 一次，然后再算一次 $f(i)$，这次当其已经成为最大值时，我们直接把这个连通块删掉，即把 $f(i)$ 设置为极小值即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 3e5 + 10;
const long long inf = 1ll << 60;

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

int w[maxn], n;
long long f[maxn], ans = -inf, cnt;

void dfs(int x, int fa)
{
    f[x] = w[x];
    for (int v : e[x])
        if (v != fa)
            dfs(v, x), f[x] += std::max(f[v], 0ll);
}

void dfs2(int x, int fa)
{
    f[x] = w[x];
    for (int v : e[x])
        if (v != fa)
            dfs2(v, x), f[x] += std::max(f[v], 0ll);
    if (f[x] == ans)
        cnt++, f[x] = -inf;

}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, add(x, y);
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        ans = std::max(ans, f[i]);
    memset(f, 0, sizeof(f));
    dfs2(1, 0);
    cout << ans * cnt << " " << cnt << endl;
}

F

Description

有一个给定一棵树，点有点权，其中这棵树满足除了权值最小的点外，每个点都有一个权值比它小的点与它相邻。权值最小的点唯一要求你重新构建这棵树，使得代价最小。计算代价的方法如下：

一个点的代价为：$\text{deg}_u \times a_u$，其中 $\text{deg}_u$ 表示点 $u$ 的度数，即新树中与 $u$ 直接相连的节点数。
一条边 $(u,v)$ 的代价为 $\lceil \log_2 \text{dis}(u,v) \rceil \times \min(a_u,a_v)$)，其中 $\text{dis}(u,v)$ 为 $u$ 和 $v$ 在原树中的距离。

Solution

考虑最小生成树。

这个点的代价就很怪，发现可以转到边上，那么在 $(u,v)$ 之间加一条边的代价就是 $a_u+a_v+\lceil \log_2 \text{dis}(u,v) \rceil \times \min(a_u,a_v)$。

直接加边是 $O(n^2)$ 的，过不去。

发现有一个条件没用，这个条件就是说如果我们以最小值为根遍历原树，每个点有且仅有一个点的权值小于它，就是他的父亲。

边太多了，我们考虑少加一些边，即去掉一些肯定不优的。

再次看一下式子，并想一想生成树——每个点只会往生成树里连一条边，也就是说我们需要给每个点找一个代价最小的边。

那么对于一个点 $u$ ，显然不能从它的儿子里找，这显然比从祖先找要劣。再想一想，最远就是和根连边，因为如果不从他到根这条路径上找点，其他的点权值肯定比根大，距离也更长。

因此就是要最小化 $a_v\times(\lceil \log_2 \text{dis}(u,v)\rceil+1)$，因为有 $\log_2$，我们可以倍增找这个最小值。

然后就做完了。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

namespace IO
{
	// 省略
}
using namespace IO;

const int maxn = 5e5 + 10, inf = 1 << 30;
typedef long long ll;

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

int f[maxn][26], a[maxn], n;
int mi[maxn][26], mii;
int dep[maxn];
long long ans = 0;

void dfs(int x, int fa)
{
    f[x][0] = fa, mi[x][0] = a[fa];
    dep[x] = dep[fa] + 1;
    long long m = a[fa];
    for (int i = 1; i <= 25; i++)
    {
        f[x][i] = f[f[x][i - 1]][i - 1];
        if (f[x][i] == 0)
            break;
        m = std::min(m, 1ll * a[f[x][i]] * (i + 1));
    }
    m = std::min(m, 1ll * a[mii] * (int(ceil(log2(dep[x] - 1))) + 1));
    if (fa != 0)
        ans += m + a[x];
    for (int v : e[x])
        if (v != fa)
            dfs(v, x);
}

int main()
{
   n = read(), a[0] = inf;
   for (int i = 1; i <= n; i++)
       a[i] = read(), mii = a[i] < a[mii] ? i : mii;
   for (int i = 1; i < n; i++)
       add(read(), read());
    dfs(mii, 0);
    writeln(ans);
    return 0;
}

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

F¶

Description¶

Solution¶

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code

F

Description

Solution