2020 ICPC 小米网络选拔赛 热身赛 题解

2020 ICPC 小米网络选拔赛 热身赛 题解

更好的阅读体验？
blog链接:https://www.cnblogs.com/Creed-qwq/p/13961455.html

比赛链接

https://ac.nowcoder.com/acm/contest/8409

A题

Pro：
https://ac.nowcoder.com/acm/contest/8409/A

Sol：
https://www.cnblogs.com/Creed-qwq/p/13961365.html

B题

Pro：
https://ac.nowcoder.com/acm/contest/8409/B
给定一个长度为n的序列
一个区间的贡献为其中不同数字的个数
计算所有区间的贡献和

Sol：
只需要考虑每一种不同数字的贡献，计算贡献时用一个简单的容斥即可

C题

Pro：
https://ac.nowcoder.com/acm/contest/8409/C

Sol：
https://www.cnblogs.com/Creed-qwq/p/13961468.html

D题

Pro：
https://ac.nowcoder.com/acm/contest/8409/D
给定一个大小为的矩阵
计算该矩阵中的极大全1矩阵个数

Sol：
队友写的
听说是什么悬线法板子题
有空补一下这个坑

E题

Pro：
https://ac.nowcoder.com/acm/contest/8409/E
给定一张图
要求从1号点出发到达n号点
开始时选择一个权值
每条边都有一个限制
表示只有在初始的权值在这个区间内才能使用这条边
问有多少个可行的初始权值

Sol：
比较显然的线段树分治题
当然LCT也可以
注意一下不能离散化即可(离散化会导致间距变小从而使得答案错误)
因此动态开点即可

F题

Pro：
https://ac.nowcoder.com/acm/contest/8409/F
给定两个分数和
比较它们大小

Sol：
考虑先比较整数部分
这个之间除法就能实现
如果整数部分相同则可以把问题转化为比较两个真分数
这个时候由于直接开longlong乘起来比较即可

G题

Pro：
https://ac.nowcoder.com/acm/contest/8409/G
给定一个长度为n的字符串
对其进行一系列操作
每次操作可以选择三个连续且相等的字符删掉
问最短可以删到多短

Sol：
算是一个挺经典的题？
直接用一个栈来操作
当时弹栈即可

H题

Pro：
https://ac.nowcoder.com/acm/contest/8409/H
Sol：
https://www.cnblogs.com/Creed-qwq/p/13961468.html

I题

Pro：
https://ac.nowcoder.com/acm/contest/8409/I

Sol：

J题

Pro：
https://ac.nowcoder.com/acm/contest/8409/J

Sol：
https://www.cnblogs.com/Creed-qwq/p/13961885.html

K题

Pro：
https://ac.nowcoder.com/acm/contest/8409/K
给定一个三角形
在其内部随机选一点
求

Sol：
首先可以猜到答案只和面积S有关
看到输出的要求很容易猜到答案的分母是36的约数
因此手动模拟加大力爆OJ即可得到
后续应该会补一下严格证明