HaKu’s Blog

# Codeforces Round #764 (Div. 3)题解

# A. Plus One on the Subset (opens new window)

只能做加法，并且每次可以选取多个数+1，那操作数就是最大值减去最小值。

fun main(args: Array<String>) {
    val n = readLine()!!.trim().toInt()
    repeat(n) {
        readLine()
        val arr = readLine()!!.split(" ").map { it.toInt() }
        println(arr.maxOrNull()!! - arr.minOrNull()!!)
    }
}
1
2
3
4
5
6
7
8

# B. Make AP (opens new window)

形成等差数列，由于值只有三个，那么可以控制其中两个，那么另外一个值就可以确定。我们只需要确认另外的值，是否是其原始数值的正整数倍即可。

fun main(args: Array<String>) {
    val n = readLine()!!.trim().toInt()
    repeat(n) {
        val (a, b, c) = readLine()!!.split(" ").map { it.toInt() }
        if ((2 * b - c) % a == 0 && (2 * b - c) / a > 0) {
            println("YES")
        } else if ((2 * b - a) % c == 0 && (2 * b - a) / c > 0) {
            println("YES")
        } else if ((a + c) % (2 * b) == 0 && (a + c) / (2 * b) > 0) {
            println("YES")
        } else {
            println("NO")
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# C. Division by Two and Permutation (opens new window)

不需要排序，直接遍历原数组，若撞在所需要的区间且当前值还没有遇到，则使用该值。否则除以2，看是否继续利用。当遍历完成后时，检查是否1~n都被覆盖。

这里最开始使用优先级队列排序，被hackhack掉了，过多的相同元素导致排序复杂度过高。

fun main(args: Array<String>) {
    val t = readLine()!!.trim().toInt()
    repeat(t) {
        readLine()
        val arr = readLine()!!.split(" ").map { it.toInt() }
        val n = arr.size
        val seen = BooleanArray(n + 1)
        seen[0] = true
        arr.forEach {
            var cur = it
            while (cur > 0) {
                if (cur <= n && !seen[cur]) {
                    seen[cur] = true
                    break
                }
                cur /= 2
            }
        }
        println(if (seen.all { it }) "YES" else "NO")
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# D. Palindromes Coloring (opens new window)

将原字符串拆分成K个回文字符串，求其中的最小长度。计算字母有aa对并剩余bb个。将每一对分配给K个子串，基础长度就有a/k∗2a / k * 2个，这样我们剩余bb个单独字母以及aa剩余部分字母，若这部分字母大于等于kk，那么还可以给每个子串多分配一个字符。

fun main(args: Array<String>) {
    val t = readLine()!!.trim().toInt()
    repeat(t) {
        val (n, k) = readLine()!!.split(" ").map { it.toInt() }
        val str = readLine()!!
        val map = HashMap<Char, Int>()
        str.forEach {
            map[it] = map.getOrDefault(it, 0) + 1
        }
        var a = 0
        var b = 0
        for (i in 'a'..'z') {
            // 可以有多少对
            a += map.getOrDefault(i, 0) / 2
            // 可以有多少余量
            b += map.getOrDefault(i, 0) % 2
        }
        println("${a / k * 2 + if (b + 2 * (a - a / k * k) >= k) 1 else 0}")
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# E. Masha-forgetful (opens new window)

本题要注意点有两个：

  1. 可以只选取长度为2和长度为3的片段，因为4可以分解为2+2，5可以分解成2+3。这样可以最小化映射表。
  2. 结果的多行输出，不要每行写一个println，会超时... 将结果拼装到一个String中再打印出来... 这里第一次发现...
fun main(args: Array<String>) {
    val t = readLine()!!.trim().toInt()
    repeat(t) {
        readLine()
        val (n, m) = readLine()!!.split(" ").map { it.toInt() }
        val arr = ArrayList<String>()
        repeat(n) {
            val num = readLine()!!
            arr.add(num)
        }
        val map = HashMap<String, Triple<Int, Int, Int>>()
        for (i in arr.indices) {
            for (j in arr[i].indices) {
                for (k in j + 2..minOf(j + 3, arr[i].length)) {
                    map[arr[i].substring(j, k)] = Triple(j + 1, k, i + 1)
                }
            }
        }
        val target = readLine()!!
        val dp = IntArray(target.length + 1) { -1 }
        dp[0] = 0
        for (i in target.indices) {
            if (i + 2 <= target.length && target.substring(i, i + 2) in map.keys) {
                if (dp[i] != -1) {
                    dp[i + 2] = i
                }
            }
            if (i + 3 <= target.length && target.substring(i, i + 3) in map.keys) {
                if (dp[i] != -1) {
                    dp[i + 3] = i
                }
            }
        }

        if (dp.last() == -1) {
            println(-1)
        } else {
            val ans = ArrayList<Triple<Int, Int, Int>>()
            var left = dp.last()
            var right = target.length
            while (right != 0) {
                ans.add(map[target.substring(left, right)]!!)
                right = left
                left = dp[left]
            }
            println(ans.size)
            // 这里要注意... 输出多行要拼装一起输出，println放在for循环里会超时...
            val output = StringBuilder()
            ans.reversed().forEach {
                output.appendLine("${it.first} ${it.second} ${it.third}")
            }
            print(output)
        }
    }
}
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

# F. Interacdive Problem (opens new window)

非常有意思的题目，第一次做这种交互题。整体理解下来发现题目并不难，不过初次接触，感觉很新颖。

给一个数xx在[1,n−1][1, n-1]之间，然后我们可以命令这个值+c+ c，之后会返回这个值除以nn的结果。n的范围是[2,1000][2, 1000]，需要10次以内判断出当前的xx。通过数据很容易联想到210=10242^{10}=1024使用二分的思想进行处理。

最开始值的取值区间是[1,n−1][1, n - 1]，那么为了能让这个值除以n的结果能以中间值区分，则将中间值+c使其为n的倍数，则左半部分的返回值要比右半部分的返回值小1。循环执行该过程，直到二分区间为1，则当前结果就是我们所求。

还需要注意的是，+c的过程是不可逆的，题目要求我们返回的是当前的xx。所以在每次+c后，leftleft和rightright重新定义时也要将c的偏移量带上。

PLUS：flush之类的方法，使用Kotlin提交不需要调用，就普通的readLine println即可。

// 二分，每次将中值匹配到n的正整数倍上
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    var left = 1
    var right = n - 1
    while (left != right) {
        val mid = (left + right) / 2
        var diff = (n - mid - 1)
        while (diff < 0) diff += n
        println("+ $diff")
        val res = readLine()!!.toInt()
        if (res != left / n) {
            left = mid + 1 + diff
            right += diff
        } else {
            left += diff
            right = mid + diff
        }
    }
    println("! $left")
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# G. MinOr Tree (opens new window)

这道题有意思，根据题目能想到是要取或值的最小生成树，不过没想到如何利用并查集来处理。看题解才发现可以通过结果反推，从高位到低位，看该位若选取0（即权值该位为1的边都不选取）是否能保证联通，若能保证联通则不符合的边都舍弃，否则总结果的该位被设置为1。

有意思~涨知识！

// 权值取或的最小生成树
fun main() {
    val t = readLine()!!.trim().toInt()
    repeat(t) {
        readLine()
        // n个点，m条边
        val (n, m) = readLine()!!.split(" ").map { it.toInt() }
        var ans = 0
        val canSelect = BooleanArray(m) { true }
        val arr = ArrayList<IntArray>()
        repeat(m) {
            val tmp = readLine()!!.split(" ").map { it.toInt() }
            // 两个点及其权值
            arr.add(intArrayOf(tmp[0] - 1, tmp[1] - 1, tmp[2]))
        }
        // 从第29位一直判断到第0位，看是否高位是否可为0
        for (i in 29 downTo 0) {
            val ufs = UFS(n)
            // 假设结果中第i位为0
            for (j in arr.indices) {
                if (canSelect[j] && (arr[j][2] and (1 shl i) == 0)) {
                    ufs.union(arr[j][0], arr[j][1])
                }
            }
            // 是否所有点都联通，n个节点都是一组的
            if (ufs.sz[ufs.find(0)] == n) {
                // 这一位可为0，但一些边状态需要变成不可选
                for (k in arr.indices) {
                    if (arr[k][2] and (1 shl i) != 0) {
                        canSelect[k] = false
                    }
                }
            } else {
                // 这一位必须为1
                ans = ans or (1 shl i)
            }
        }
        println(ans)
    }
}
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