专栏文章

题解：CF1346E Magic Tricks

ssongge888
CF1346E题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipszvkh
此快照首次捕获于
2025/12/03 17:27
3 个月前
此快照最后确认于
2025/12/03 17:27
3 个月前
查看原文
注意：此题只能用 Kotlin 语言提交。
所以这是一篇 Kotlin 的题解。

什么是 Kotlin？

Kotlin 是一种由 JetBrains 开发的现代编程语言，与 Java 兼容。
考虑到大部分人都用 C++ 写代码，这里主要将 Kotlin 和 C++ 作比较。

Kotlin 语法

1. 程序结构

KOTLIN
fun main() {
	...
}
也就是 main 函数。

2. 输入

使用 Java 的 Scanner 类从标准输入读取数据，并导入 java.util.Scanner。
在开头加上：
KOTLIN
import java.util.Scanner
然后在 main 函数中初始化：
KOTLIN
val scanner = Scanner(System.`in`)
之后读入 int 类型：
KOTLIN
val a = scanner.nextInt()
其他类型同理，但字符串的读取方式略有不同：
KOTLIN
val a = scanner.nextLine()

3. 输出

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

4. 变量声明

  • val：常量，相当于 C++ 中的 const，但如果 val 定义的是数组，内部元素仍然可以改变。
  • var：变量。
不管是 val 还是 var，都可以自动识别类型。

5. 数组

KOTLIN
val a: Array<Int> = Array(n + 1) { m + 1 }
val a = IntArray(n + 1) { m + 1 }
以上两种方式都代表创建一个大小为 n+1n+1，初值全部为 m+1m+1 的数组 aa，支持下标访问，a[i] 表示数组 aa 中的第 ii 个元素。
其他的数据类型同理。

6. 判断

KOTLIN
if (....) {
    ....
}
与 C++ 一致。

7. 循环

  • for 循环
    KOTLIN
    for (i in a) {
    println(i)
}
    类似于 C++ 中的 auto。
    KOTLIN
    for (i in 1..n) {
    println(a[i])
}
    也可以通过 x..y 遍历。
  • while 循环
    KOTLIN
    while (true) {
    if (...) {
        break
    }
}
  • repeat 循环
    KOTLIN
    repeat(m) {
    ...
}
    表示循环执行 mm 次括号内的语句。

8. 最大/最小值

KOTLIN
val a = minOf(b,c)/maxOf(b,c)
基本与 C++ 一致。
下面来分析题目。

题意

给定 nn 个球，其中一个是特殊球，初始位置为 kk。有 mm 次交换操作，每次交换两个位置上的球。你可以选择是否执行某些交换，以使特殊球最终到达某个位置。
要求计算每个位置 ii，使特殊球到达该位置所需阻止交换次数，如果无法到达则输出 −1-1。

思路

考虑动态规划，定义 dpi,jdp_{i,j} 表示前 ii 个操作后，特殊球在 jj 的最小代价。
假设第 ii 次交换为 (ui,vi)(u_i, v_i)，则状态转移方程为：
dpi,ui=min(dpi−1,vi,dpi−1,ui+1)dpi,vi=min(dpi−1,ui,dpi−1,vi+1)dp_{i,{u_i}}=min(dp_{i-1,{v_i}},dp_{{i-1},{u_i}}+1)\\ dp_{i,{v_i}}=min(dp_{i-1,{u_i}},dp_{{i-1},{v_i}}+1)
对于其他位置，dpdp 值不变。
由于 dpdp 只依赖于上一步的状态，因此可以使用滚动数组优化。
最终时间复杂度为 O(m)O(m)。

Code

KOTLIN
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();
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...