还可以。
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;
}