Kotlin与竞技程序设计

发表于 更新于 分类于 阅读次数：

这里会在Codeforces上进行Kotlin语言的实践。

给出模板

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.*
import kotlin.math.*

fun readint()=readLine()!!.toInt()
fun readll()=readLine()!!.toLong()
fun readdb()=readLine()!!.toDouble()
fun readstring()=readLine()!!
fun readline_int()=(readLine()!!.split(" ").map{it.toInt()}).toIntArray()
fun readline_ll()=(readLine()!!.split(" ").map{it.toLong()}).toLongArray()
fun readline_db()=(readLine()!!.split(" ").map{it.toDouble()}).toDoubleArray()
fun main(args: Array<String>){go()}
/*
---------------c++->kotlin-------------------
swap(a,b)                    a=b.also{b=a}
for(i=0;i<n;i++)             for(i in 0 until n) / for(i in 0..n-1)
for(i=n-1;i>=0;i--)          for(i in n-1 downTo 0)
for(auto it:s)               for(it in s)
printf                       println("${ans}")
println(res)                 println(res.joinToString(" "))
ll a[n]                      var a=Array<Long>(n){}
int a[n+2][m+2]              var a=Array(n+2){Array<Int>(m+2){0}}
a&b                          a and b
a|b                          a or b
a^b                          a xor b
int gao(int a,int b)         fun gao(a:Int,b:Int):Int
---------sort---------
res.sortBy({it.fi})
res.sortWith({it.fi},{it.se})
--------vector--------
vector<int> res;             var res=mutableListOf<Int>()
res.push_back                res.add
vector<int> mp[n];           var mp=Array(n){mutableListOf<Int>()}
---------set----------
set<int> s;                  var s=TreeSet<Int>()
s.insert                     s.add
s.erase                      s.remove
s.count                      s.contains
s.begin                      s.first
s.rbegin                     s.last
set<pair<int,int>> s;        var s=TreeSet<Pair<Int,Int>>(compareBy({it.first},{it.second}))
-----unordered_map-----
unordered_map<int,int>       var mp:MutableMap<Int,Int> = mutableMapOf()
mp[x]++                      mp[x]=(mp[x]?:0)+1
sum+=mp[x]                   sum+=mp[x]?:0
-----priority_queue-----
struct node{int a;}          data class node(var a:Int)
priority_queue<node> q;      var q=PriorityQueue<node>(compareBy({it.a}))
q.top                        q.peek
q.pop                        q.poll
q.push                       q.add
---------deque----------
deque<int> dq;               var dq=ArrayDeque<Int>()
dq.push_front()              dq.offerFirst()
dq.front()                   dq.peekFirst()
dq.pop_front()               dq.pollFirst()
{dq.front(),dq.pop_front()}  dq.pollFirst()

dq.push_back()               dq.offerLast()
dq.back()                    dq.peekLast()
dq.pop_back()                dq.pollLast()
{dq.back(),dq.pop_back()}    dq.pollLast()
---------------------------------------------
 */
data class pair(var fi:Int,var se:Int,var id:Int)
/*using: xxx.sortWith(cmp)*/
val cmp: Comparator<pair> = Comparator{ a,b->
    if (a.fi==b.fi) a.se.compareTo(b.se)
    else a.fi.compareTo(b.fi)
}
val INF=0x3f3f3f3f
val LLINF=0x3f3f3f3f3f3f3f3fL
val MAX=200000+10
/*------------------------------------------------------------*/

fun go()
{
    //rewrite code here
}

正文

如何读入

由于 $java.util.Scanner$ 极其慢，所以放弃使用。

这里使用 $readLine()$ 方法，它返回一个可空类型 $String?$ ，迫使开发人员处理输入缺失的情况。

1
2
val n = readLine()?.toInt() // n可能为Int也可能为空，自行处理输入缺失。
val n: Int = readLine()!!.toInt() // n不可能为空，如不存在则抛出异常。

竞技程序设计中的输入格式向来都是精确指定的，并且实际输入不能偏离问题陈述中的输入规范。这基本上就是空断言操作符 !! 的行为—— 它断言输入的字符串存在，如不存在则抛出异常。

1
2
3
4
5
val str = readLine()!! // 读入一行字符串
val n = readLine()!!.toInt() // 一行单个整数
var (n, k) = readLine()!!.split(" ").map{it.toInt()} // 读入一行两个整数
val s = readLine()!!.split(" ")  // 字符串列表，List<String>类型
var a = readLine()!!.split(" ").map { it.toInt() } // 整数列表，相当于数组

可以定义为以下辅助函数，其他函数类似。

1
2
private fun readInt() = readLine()!!.toInt()
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }

如何输出

方法 $print()$ 和 $println()$ 分别在内部调用 $System.out.print()$ 和$System.out.println()$ 。

1
2
var x = mutableListOf<Int>()
println(x.joinToString(" ")) // x每个元素由空格隔开

数据存储

动态数组ArrayList

1
2
arr = ArrayList<Int>() 创建，可在括号内传一个Int指定容量
var x = mutableListOf<Int>()

HashMap与HashSet

$HashMap$ 类使用 $Hash$ 表实现 $MutableMap$ 接口。 它以键和值对的形式存储数据，表示为 $HashMap <key，value>$。

1
2
3
4
5
hashMap.get(key) 返回指定键的值，若没有指定键，则返回null。
hashMap.put(key, val) 在指定键处添加新值并替换旧值。
hashMap.containsKey(key) 若key存在返回true，否则返回false
hashMap.containsValue(val) 若val存在返回true，否则返回false
hashMap.clear() 清除所有数据

基础语法

循环

1
2
3
4
for (i in 1..5) print(i) // 12345
for (i in 1 until 5) print(i) // 1234
for (i in 5 downTo 1) print(i) // 从5开始反向，54321
for (i in 1..5 step 2) print(i) // 从5开始，步长为2，135

排序

1
2
3
4
a.sorted() // 自然升序
a.sortedDescending() // 自然降序
val lengthComparator = Comparator { str1: String, str2: String -> str1.length - str2.length } // 定义排序规则
a.sortedWith(lengthComparator) //自定义排序

实战:Kotlin Heroes: Practice 9

A. Spy Detected!

给定一个由 $n$ 个正整数组成的数组 $a$ ，保证其中只有一个元素是与其它元素不同的，输出这个元素的索引（从1开始）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fun main(args: Array<String>) {
    var t: Int = readLine()!!.toInt()
    while(t-- > 0) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(" ").map { it.toInt() }
        val mp = HashMap<Int, Int>()
        for(i in a.indices) {
            if(!mp.containsKey(a[i]))
                mp.put(a[i], 0)
            mp.put(a[i], mp.get(a[i])!!+1)
        }
        var ans: Int = 0
        for(i in a.indices) {
            if(mp.get(a[i]) == 1) {
                ans = i + 1
                break
            }
        }
        println(ans)
    }
}

B. Repeating Cipher

定义一个操作为“重复”，它会将第 i 个字符重复 i 次，给定“重复“操作后的字符，求初始字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun main(args: Array<String>) {
    val n: Int = readLine()!!.toInt()
    val s: String = readLine()!!
    var ans: String = ""
    var i = 0
    var len = 0
    while(i < n) {
        ans += s[i]
        //ans.plus(s[i])
        len++
        i += len
    }
    println(ans)
}

C. Teams Forming

$n$ 个数字，$n$ 为偶数，你要将他们分为 $\dfrac n2$ 个组，每组恰好两个数字。两个数字相同时才可以分到同一组，你可以每次对一个数进行+1操作，求能全部分组的最少操作次数。

思路

将这些数放到数轴上，会发现相近的两两连线即为最优方案，那么排序后做差求和即可。

代码

1
2
3
4
5
6
7
8
9
10
11
fun main(args: Array<String>) {
    val n: Int = readLine()!!.toInt()
    var a = readLine()!!.split(" ").map {it.toInt()}
    var ans: Int = 0
    a = a.sorted()
    //println(a)
    for(i in 0..n-1 step 2) {
        ans += a[i+1] - a[i]
    }
    println(ans)
}

D. Two Shuffled Sequences

一个数组能否打乱顺序后能否拆分为一个严格单调递减和严格单调递增的数组。

很明显有数字出现三次不可，否则必定有解。

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
fun main(args: Array<String>) {
    val n: Int = readLine()!!.toInt()
    var a = readLine()!!.split(" ").map {it.toInt()}
    val mp = HashMap<Int, Int>()
    var x = mutableListOf<Int>()
    var y = mutableListOf<Int>()
    var ok: Boolean = true
    for(i in a) {
        if(!mp.containsKey(i)) {
            mp.put(i, 0)
            x.add(i)
        } else if(mp.get(i) == 1) {
            y.add(i)
        } else {
            ok = false
            break
        }
        mp.put(i, mp.get(i)!!+1)
    }
    val cmp = Comparator { xx: Int, yy: Int -> xx - yy}
    x.sortWith(cmp)
    y.sortWith(cmp)
    y.reverse()
    if(ok) {
        println("YES")
        println(x.size)
        println(x.joinToString(" ")) 
        println(y.size)
        println(y.joinToString(" "))
    } else {
        println("NO")
    }
}

E. Powers Of Two

贪心拆分。

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import kotlin.math.log2
import kotlin.math.floor
import kotlin.math.pow
private fun readInt() = readLine()!!.toInt()
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }
fun main(args: Array<String>) {
    val (n, k) = readInts()
    //var ok: Boolean = true
    var tmp = n
    //var a = mutableListOf<Int>()
    var cnt: Int = 0 //让now变为k个
    var mp = Array<Int> (32) {0}
    while(tmp > 0) {
        var y = floor(log2(tmp.toDouble())).toInt()
        var now: Int = 2.0.pow(y).toInt()
        mp[y]++
        cnt++
        //a.add(now)
        tmp -= now
    }
    //println(a)
    if(n < k || k < cnt) // 最大拆分比k小，最小拆分比k大
        println("NO")
    else {
        println("YES")
        for(i in 31 downTo 0) {
            if(mp[i] >= k - cnt) {
                mp[i] -= k - cnt;
                mp[i-1] += (k - cnt) * 2
                cnt = k
                break
            }
            mp[i-1] += mp[i] * 2
            cnt += mp[i]
            mp[i] = 0
        }
        //println(mp.joinToString(" "))
        for(i in 0..31)
            for(j in 1..mp[i])
                print(2.0.pow(i).toInt().toString() + " ")
        // 不会倒序遍历hashmap所以放弃了
        /*val mp = HashMap<Int, Int>()
        for(i in a) {
            if(!mp.containsKey(i))
                mp.put(i, 0)
            mp.put(i, mp.get(i)!!+1)
        }
        var now: Int = a.size //让now变为k个
        for(it in mp) {
            if(it.value >= k - now) {//能够补足
                now = k
                mp.put(it.key, it.value - (k - now))
                if(!mp.containsKey(it.key/2))
                    mp.put(it.key/2, 0)
                mp.put(it.key/2, mp.get(it.key/2)!! + (k - now) * 2)
                break
            }
            now += it.value
            if(!mp.containsKey(it.key/2))
                mp.put(it.key/2, 0)
            mp.put(it.key/2, mp.get(it.key/2)!! + it.value * 2)
            mp.remove(it.key)
        }
        for(it in mp) {
            for(i in 1..it.value)
                print(it.key.toString() + " ")
        }*/
    }
}

F. Boxers

大概左右各扫一遍乱搞一下？

网络流可以秒……但是Kotlin不会写网络流。

推荐的Kotlin竞赛学习资料

Kotlin的开发者Roman Elizarov算法模板库

巧用Kotlin：内置函数let、also、with、run、apply大大提高你的开发效率！

语法糖

  • 类前面要加 open 关键字才能被继承。
  • 多用 when 关键字替代 if 。