题解：CF1346E Magic Tricks

songge888 · 2025-03-26 16:52:17 · 题解

注意：此题只能用 Kotlin 语言提交。

所以这是一篇 Kotlin 的题解。

什么是 Kotlin？

Kotlin 是一种由 JetBrains 开发的现代编程语言，与 Java 兼容。

考虑到大部分人都用 C++ 写代码，这里主要将 Kotlin 和 C++ 作比较。

Kotlin 语法

1. 程序结构

fun main() {
    ...
}

也就是 main 函数。

2. 输入

使用 Java 的 Scanner 类从标准输入读取数据，并导入 java.util.Scanner。

在开头加上：

import java.util.Scanner

然后在 main 函数中初始化：

val scanner = Scanner(System.`in`)

之后读入 int 类型：

val a = scanner.nextInt()

其他类型同理，但字符串的读取方式略有不同：

val a = scanner.nextLine()

3. 输出

• print()：输出后不换行。
• println()：输出后换行。

4. 变量声明

• val：常量，相当于 C++ 中的 const，但如果 val 定义的是数组，内部元素仍然可以改变。
• var：变量。

不管是 val 还是 var，都可以自动识别类型。

5. 数组

val a: Array<Int> = Array(n + 1) { m + 1 }
val a = IntArray(n + 1) { m + 1 }

以上两种方式都代表创建一个大小为 n+1，初值全部为 m+1 的数组 a，支持下标访问，a[i] 表示数组 a 中的第 i 个元素。

其他的数据类型同理。

6. 判断

if (....) {
    ....
}

与 C++ 一致。

7. 循环

• for 循环

  for (i in a) {
    println(i)
  }

  类似于 C++ 中的 auto。

  for (i in 1..n) {
    println(a[i])
  }

  也可以通过 x..y 遍历。

• while 循环

  while (true) {
    if (...) {
        break
    }
  }

• repeat 循环

  repeat(m) {
    ...
  }

  表示循环执行 m 次括号内的语句。

8. 最大/最小值

val a = minOf(b,c)/maxOf(b,c)

基本与 C++ 一致。

下面来分析题目。

题意

给定 n 个球，其中一个是特殊球，初始位置为 k。有 m 次交换操作，每次交换两个位置上的球。你可以选择是否执行某些交换，以使特殊球最终到达某个位置。

要求计算每个位置 i，使特殊球到达该位置所需阻止交换次数，如果无法到达则输出 -1。

思路

考虑动态规划，定义 dp_{i,j} 表示前 i 个操作后，特殊球在 j 的最小代价。

假设第 i 次交换为 (u_i, v_i)，则状态转移方程为：

对于其他位置，dp 值不变。

由于 dp 只依赖于上一步的状态，因此可以使用滚动数组优化。

最终时间复杂度为 O(m)。

Code

import java.util.*

fun main(){
    val scanner=Scanner(System.`in`);
    val n=scanner.nextInt();
    val m=scanner.nextInt();
    val k=scanner.nextInt();
    val dp=IntArray(n+1){m+1};
    dp[k]=0;
    repeat(m){
        val a=scanner.nextInt();
        val b=scanner.nextInt();
        val aa=minOf(dp[a]+1,dp[b]);
        val bb=minOf(dp[b]+1,dp[a]);
        dp[a]=aa;
        dp[b]=bb;
    }
    for(j in 1..n){
        if(dp[j]>m){
            print(-1);
        }
        else{
            print(dp[j]);
        }
        print(" ");
    }
    println();
}