寒假训练 2 题解

by lym

A - 一起回家

题目： https://codeforces.com/problemset/problem/1845/B

如果某个方向同时是两个人的最短路就朝这个方向走

cf 题解是另一种做法

提交记录： https://codeforces.com/contest/1845/submission/302530594

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
import kotlin.math.*

val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]


fun main() {
    repeat(readInts().first()) {
        val (xa, ya) = readInts()
        val (xb, yb) = readInts()
        val (xc, yc) = readInts()
        var ans = 0
        if (xa < min(xb, xc)) {
            ans += min(xb, xc) - xa
        }
        if (ya < min(yb, yc)) {
            ans += min(yb, yc) - ya
        }
        if (xa > max(xb, xc)) {
            ans += xa - max(xb, xc)
        }
        if (ya > max(yb, yc)) {
            ans += ya - max(yb, yc)
        }
        println(ans + 1)
    }
}

B - 最大区间

题目： https://codeforces.com/problemset/problem/1855/B

cf 题解做法

提交记录： https://codeforces.com/contest/1855/submission/302533225

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import kotlin.math.*

val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]


fun main() {
    repeat(readInts().first()) {
        val (n) = readLongs()
        val ans = (1..43).indexOfFirst { n % it != 0L }
        println(ans)
    }
}

C - 幸运元素

题目： https://codeforces.com/problemset/problem/1860/C

不能向左移动的位置是先手必胜的，题目要求先手必败的位置有多少

必胜的位置要么不能向左移动，要么可以移动到一个必败的位置

于是我们在从左到右扫描的过程中，
记录左边所有值的最小值用于判断能否向左移动，
记录左边所有必败位置的最小值用于判断当前位置是否可以移动到一个必败位置

提交记录： https://codeforces.com/problemset/submission/1860/302537469

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
import kotlin.math.*

val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]


fun main() {
    repeat(readInts().first()) {
        val (n) = readInts()
        var ans = 0
        var minV = n + 1
        var minLoss = n + 1
        readInts().forEach {
            if (it < minV || it > minLoss) {
                // win
            } else {
                ans++
                minLoss = min(minLoss, it)
            }
            minV = min(minV, it)
        }
        println(ans)
    }
}

D - 田忌赛马

题目： https://www.luogu.com.cn/problem/P1637

做法 1

考虑二元上升子序列的求法：从左到右扫一遍，过程中使用树状数组维护左边每个数的出现次数，在每个位置统计以这个位置结尾的二元组

可以把每个数的出现次数看成是以这个数为结尾的一元上升子序列数量，于是我们再维护一下每个数结尾的二元上升子序列数量，就可以得到本题的做法

同样的方法也可以用来计算四元上升子序列的数量

提交记录： https://www.luogu.com.cn/record/200061284

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
val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]

class Bit(n: Int) {
    val tree = MutableList(n + 1) { 0L }

    fun add(ii: Int, v: Long) {
        var i = ii
        while (i < tree.size) {
            tree[i] += v
            i += i and -i
        }
    }

    fun quary(ii: Int): Long {
        var s = 0L
        var i = ii
        while (i > 0) {
            s += tree[i]
            i -= i and -i
        }
        return s
    }

    fun rq(l: Int, r: Int) = quary(r) - quary(l - 1)
}

fun main() {
    val (n) = readInts()
    val a = readInts().map { it + 1 }
    val maxAi = 100001
    val f = Bit(maxAi)
    val g = Bit(maxAi)
    var ans = 0L
    a.forEach {
        val pair = f.quary(it - 1)
        val triple = g.quary(it - 1)
        f.add(it, 1)
        g.add(it, pair)
        ans += triple
    }
    println(ans)
}

做法 2

枚举中间的数，数据结构维护前面比它小的和后面比它大的，然后乘起来，参考洛谷题解。

或者直接 暴力也可以过

E - 数字游戏

题目： https://codeforces.com/problemset/problem/1749/C

Bob 的操作可以看成删掉一个数

Bob 的最优策略是删最小的数， Alice 的最优策略是选能选的最大的数

所以对于 ，Bob 会删掉最小的 个数， 如果接下来的 个数 Alice 可以选，那么这个 就是可行的

可以通过二分答案得到 的时间复杂度

提交记录： https://codeforces.com/contest/1749/submission/302546530

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
import kotlin.math.*

val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]


fun main() {
    repeat(readInts().first()) {
        val (n) = readInts()
        val a = readInts().sorted()
        val ans = (1..n).toList().binarySearch {
            if (it * 2 - 1 > n) return@binarySearch 1
            a.subList(it - 1, it * 2 - 1)
                .withIndex()
//                .also { println(it.toList()) }
                .all { (i, v) -> v <= i + 1 }
                .let { if (it) -1 else 1 }
        }.let { -it - 1 }
        println(ans)
    }
}

F - 拼图游戏

题目： https://www.luogu.com.cn/problem/P2532

卡特兰数

提交记录： https://www.luogu.com.cn/record/200122441

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import kotlin.math.*

val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]


fun main() {
    val (n) = readInts()
    val c = mutableListOf(1.toBigInteger())
    for (i in 1..n) {
        val ci = (c zip c.reversed()).sumOf { (a, b) -> a * b }
        c.add(ci)
    }
    println(c.last())
}

G - 染色游戏

题目： https://codeforces.com/problemset/problem/1876/B

从大到小枚举最大值取哪个数，之前枚举过的位置的因数不选，当前位置的因数选至少一个，剩下的随便选

提交记录： https://codeforces.com/contest/1876/submission/302553137

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
import kotlin.math.*

val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]


const val mod = 998_244_353L
infix fun Long.add(x: Long) = (this + x) % mod
infix fun Long.sub(x: Long) = (this - x) % mod
infix fun Long.mul(x: Long) = this * x % mod
fun Long.pow(n: Int) = this.toBigInteger().modPow(n.toBigInteger(), mod.toBigInteger()).toLong()
fun Long.mod() = (this % mod + mod) % mod

fun main() {
    val (n) = readInts()
    val div = List(n + 1) { mutableListOf<Int>() }
    for (i in 1..n) {
        for (j in i..n step i) {
            div[j] += i
        }
    }
    val a = readLongs()
        .mapIndexed { i, v -> Pair(i + 1, v) }
        .sortedBy { -it.second }
    var ans = 0L
    var unfix = n
    val free = MutableList(n + 1) { 1 }
//    println(a)
    a.forEach { (i, v) ->
        var p = 0
        div[i].forEach {
            p += free[it]
            unfix -= free[it]
            free[it] = 0
        }
        ans += (2L.pow(p)-1L) mul 2L.pow(unfix) mul v
    }
    println(ans.mod())
}

H - 安东和童话

题目： https://codeforces.com/problemset/problem/785/C

对于 的情况，从第 天开始时的状态可以等价为，谷仓的容量为 ，每天不再增加粮食，麻雀的攻击力重新从 开始增加

提交记录： https://codeforces.com/contest/785/submission/302559934

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
import kotlin.math.*

val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]


fun main() {
    val (n, m) = readLongs()
    if (n <= m) {
        println(n)
        return
    }
    val remain = n - m
    tailrec fun search(l: Long, r: Long): Long {
        // l: unknown
        // r: <= 0
        // return first  <= 0
        if (l == r) return l
        val mid = (l + r) / 2
        if (remain - mid * (mid + 1) / 2 > 0) {
            return search(mid + 1, r)
        } else {
            return search(l, mid)
        }
    }
    println(search(1, 2e9.toLong()) + m)
}

I - 完美数字

题目： https://codeforces.com/problemset/problem/300/C

枚举每种数字选几个，计算方案数，需要预处理组合数

提交记录： https://codeforces.com/contest/300/submission/302566364

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
import kotlin.math.*

val reader = System.`in`.bufferedReader()
fun readStrings() = reader.readLine().split(' ')
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
operator fun <E> List<E>.component6() = this[5]

const val mod = 1000_000_007L

fun Long.mod() = (this % mod + mod) % mod
infix fun Long.add(x: Long) = (this + x) % mod
infix fun Long.sub(x: Long) = (this - x) % mod
infix fun Long.mul(x: Long) = this * x % mod
fun Long.inve(): Long {
    var (a, b, u, v) = arrayOf(mod, this, 0, 1)
    while (b != 0L) {
        val t = a / b
        a -= t * b
        a = b.also { b = a }
        u -= t * v
        u = v.also { v = u }
    }
    assert(a == 1L)
    return u
}

fun main() {
    val (a, b, n) = readInts()
    tailrec fun ok(x: Int): Boolean =
        if (x == 0) true
        else if (x % 10 !in listOf(a, b)) false
        else ok(x / 10)

    val revfact = (n downTo 1).scan(1L) { acc, i -> acc mul i.toLong() }
    val inve = revfact.last().inve()
    fun c(r: Int) = inve mul revfact[r] mul revfact[n - r]
    val ans = (0..n)
        .filter { ok(it * a + (n - it) * b) }
        .sumOf { c(it) }
    println(ans.mod())
}