A-Haitang and Game

题意

给出一个数组，两人轮流，每次选择数组中的两个数，若这两个数的$gcd$不在当前的数组里，就将这两个数的$gcd$加入到数组中，不能再加数的一方输。

数据范围

• $1\leq t\leq 100$
• $1\leq n\leq 10^5$
• $1\leq a_i\leq 10^5$

思路

整个数组的最终含有哪些数是确定的，枚举$1\sim a_{max}$的每个数，记为$x$，查看数组中大于$x$的整数倍的数，若这些倍数的$gcd$恰好等于$x$，则$x$会出现在最终的数组中。

I-Fight Against the Monster

题意

使用机器对抗怪兽，一台机器有以下两种功能：

• 战斗：使怪兽血量减少1点，后技巧丧失所有功能
• 创造：需要$m$台机器同时使用，创造出$k$台新机器，每台机器仅能使用一次创造功能。

怪兽初始血量是$h$，血量下降至$0$​时死亡，请计算初始最少需要多少机器才能打败怪兽。

A-Cake

题意

Oscar和Grammy玩游戏，第一阶段两人轮流在有根树上走，走到叶子停止，经过的边有两种，标0边或者标1边，记录走下的01串。设01串的长度是$m$，第二阶段Oscar将蛋糕切成$m$份，有些蛋糕可以是空的，按照第一阶段的01串顺序依次拿蛋糕（1代表Grammy拿，0代表Oscar拿），两人都想获得最多的蛋糕，求最后Grammy获得的蛋糕比例。

数据范围

• $1\leq n\leq 2\times 10^5$

思路

在第二阶段，Oscar分蛋糕的时候，是对当前串寻找一个0占比最大的前缀，然后拿走占比一致的蛋糕。

于是，在第一阶段时，首先树上每个节点即代表一个前缀，预处理出每个节点为前缀时0的占比，在之后两人轮流取数时，Oscar会取选择下一个节点轮流选择后0占比最大的节点，Grammy会选择0占比最小的节点。

A-LCT

题意

给定一棵有根树，每次询问前$i$条边组成的森林中，第$c_i$个点为根的树的深度。

数据范围

• $2\leq n\leq 10^6$
• $1\leq a_i,b_i,c_i\leq n,a_i\neq b_i$

思路

带权并查集，维护每个节点在当前所属树的层数，维护所有以该节点为根节点的树的深度。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

int deep[maxn], fa[maxn], dis[maxn];
int findfa(int x) {
    if (x == fa[x])return x;
    int fx = findfa(fa[x]);
    // 更新deep,旧根:fa[x],新根:fx
    deep[x] += deep[fa[x]];
    return fa[x] = fx;
}

void merge(int u, int v) {
    int fu = findfa(u);
    fa[v] = fu;
    deep[v] = deep[u] + 1;
    dis[fu] = max(dis[fu], dis[v] + deep[v]);
}

void solve() {
    int n;cin >> n;
    for (int i = 1;i <= n;i++) {
        fa[i] = i;
        deep[i] = 0;
        dis[i] = 0;
    }
    for (int i = 1;i <= n - 1;i++) {
        int u, v, c;cin >> u >> v >> c;
        merge(u, v);
        cout << dis[c] << " ";
    }
    cout << "\n";
}

C-Sort4

题意

给出一个排列，每次选择四个位置交换其中的元素，求将该排列排序成上升序列的最小操作次数。

A-Bridging the Gap 2

题意

在河岸的一侧有$n$个人，每个人有一个体力值$h_i$，有一艘船可以将人从一侧载到另一侧，每次航行需要至少$L$个人掌舵，每次掌舵会花费每个掌舵人的一点体力，当体力不足一点时，这个人不能再掌舵，船的容量最大是$R$，提问是否能够将这些人都运送到对岸。

数据范围

• $1\leq L\lt R\leq n\leq 5\times 10^5$​
• $1\leq h_i\leq 5\times 10^5$

思路

贪心的运输，从左岸运输的最小次数是$k=\lceil \frac{n-R}{R-L} \rceil$，计算每个人最多的来回次数$a_i$，假如满足$\sum_{i-1}^{n} min(k,a_i)\geq k\times L$，则可以将所有人都运输到对岸。