所有效率之和等于零。
1
2
3
4
5
6
7
| public static void solve() {
int n = io.nextInt(), sum = 0;
for (int i = 0; i < n - 1; i++) {
sum += io.nextInt();
}
io.println(-sum);
}
|
贪心选择最小花费的通知，注意维护已经被通知的下标，根据该下标判断是否需要加 \(p\)，并且如果某个人通知其他人的成本大于 \(p\)，则他不会通知其他人。发现大佬的解法好简单，取一个最小值，维护一个剩余人数即可。
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
| public static void solve() {
int n = io.nextInt(), p = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
}
int[] b = new int[n];
for (int i = 0; i < n; i++) {
b[i] = io.nextInt();
}
var aux = new Integer[n];
for (int i = 0; i < n; i++) {
aux[i] = i;
}
Arrays.sort(aux, (i, j) -> b[i] - b[j]);
long ans = p;
int r = n - 1;
for (int i : aux) {
int x = Math.min(r, a[i]);
ans += (long) x * Math.min(p, b[i]);
r -= x;
}
io.println(ans);
}
|
分类讨论，注意被 \(n\) 整除的数。
1
2
3
4
5
6
7
| public static void solve() {
int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();
if (k == 3) io.println(Math.max(0, m - n - m / n + 1));
else if (k == 2) io.println(m / n + Math.min(n - 1, m));
else if (k == 1) io.println(1);
else io.println(0);
}
|
很容易的想到计算选择每个索引位置，能够得到的最大分数，时间复杂度为 \(O(n\log{n})\)。然后计算每个位置有多少种方案，比赛时我以为选择一个索引位置，默认就选择了它的所有倍数位置，导致不会做。其实只要排序，然后每个位置的方案数就是它左边的数选或不选的方案数，这样可以保证不会重复计算，所以快速幂计算方案数（可以在遍历的时候计算方案数），再乘以得分累加到答案即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| private static final int MOD = 998244353;
public static void solve() {
int n = io.nextInt();
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = io.nextInt();
}
dp[0] = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) {
for (int j = 2 * i; j <= n; j += i) {
dp[i] = Math.max(dp[i], dp[j]);
}
}
Arrays.sort(dp);
long ans = 0L, pow = 1L;
for (int i = 0; i < n; i++) {
ans = (ans + dp[i] * pow) % MOD;
pow = pow * 2 % MOD;
}
io.println(ans);
}
|
方法一：内向基环树
对于每个 \(i\)，建立一条从 \(i\) 指向 \(a_{i}\) 的边，最终会得到多个内向基环树。规则一：入度为零的节点不会被选择；规则二：如果一个节点的所有入度节点都被选择，那么它不会被选择；规则三：如果一个节点不被选择，那么它指向的节点会被选择。（以上规则可以使用拓扑序 + 染色法实现）
如图，数组为 \([2,3,4,5,6,3,3,4]\)，剩余索引 \([1,5,7,8]\)，剩余元素 \([2,6,3,4]\)，选择索引 \([2,6,3,4]\)。应用规则一，得出索引 \([1,7,8]\) 不被选择；应用规则三，得出索引 \([2,3,4]\) 被选择；应用规则二，得出索引 \([5]\) 不被选择；应用规则三，得出索引 \([6]\) 被选择。
特殊情况，如果内向基环树没有环外节点，无法应用上述规则，那么需要单独对环交替染色，若此时环的长度为奇数，则没有解，其他情况均有解。也就是说，当且仅当内向基环树没有环外节点，且环的长度为奇数时，无解。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| public static void solve() {
int n = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt() - 1;
}
int[] in = new int[n];
for (int i = 0; i < n; i++) {
in[a[i]]++;
}
int[] col = new int[n];
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (in[i] == 0) {
q.offer(i);
col[i] = -1;
}
}
while (!q.isEmpty()) {
int x = q.poll(), y = a[x];
if (col[y] != 0) continue;
if (--in[y] == 0 || col[x] == -1) {
q.offer(y);
col[y] = -col[x];
}
}
for (int i = 0; i < n; i++) {
if (col[i] != 0) continue;
int j = i, pre = -1;
while (col[j] == 0) {
col[j] = -pre;
pre = col[j];
j = a[j];
}
if (col[j] == pre) {
io.println(-1);
return;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (col[i] == -1) ans.add(a[i] + 1);
}
io.println(ans.size());
for (int x : ans) {
io.print(x + " ");
}
io.println();
}
|
方法二：外向基环树
好像有建立外向基环树的解法，没时间看，在此。