2020沈阳icpc复盘
和sigma姐姐vp这场icpc。
D. Journey to Un'Goro
这题是构造题,本来有思路了的,但是没敢提交。
题目描述
题目解析
就是说给定一个长度,你需要构造一个只有 r
和
b
字符的字符串,在字符串的子串中,如果有奇数个r
,这就是个好区间。问你一个这样长度的字符串最多有多少个好区间,并构造出最好的情况,按字典序输出,如果超过100个则输出前100个。
我们思考一下如何去计算最大值,就得先看看怎么去计数,首先暴力计数需要
\(n^2\)
就肯定不行。因为是奇数个,所以我们考虑转化成前缀和。那么我们看看,如果只有一个
r
其它全是 b
我们看哪些区间符合条件。这里我们不妨把 r
当成 1,把
b
当成 0。
1 | b b b b r r r b b b |
可以很容易发现,当前缀和相减之后为奇数时,区间是好区间。那么就是偶数匹配奇数其实,因为偶数减奇数或者奇数减偶数才有可能得到奇数,而前缀和要么是偶数要么是奇数。我们最终得到的结果就是 \(num=cnt_{odd}\times cnt_{even}\) 而我们很容易得到 \(cnt_{odd}+cnt_{even}=n\) ,根据基本不等式我们不难得到当 \(cnt_{odd}\) 与 \(cnt_{even}\) 接近的时候 \(num\) 得到最大值。
因为 \(n\) 可能是奇数,所以我这里说的是接近。那么奇数就是一个多一个一个少一个,偶数就是都一样就好了。
那么这个可以直接算出来的。
\(ans=\frac{n}{2}\times \frac{n+1}{2}\)
那么主要就是怎么构造了,也很简单,既然要字典序,我们就尽量构造
b
实在不行就构造
r
。什么叫实在不行呢?那就是前缀和奇数个数超过了
(n+1)/2
这个时候就肯定不行。
标程
1 |
|
F. Kobolds and Catacombs
题目描述
题目分析
就是要把一个序列划分,要尽可能地多划分,被划分的序列在一个内部进行排序,最后要求整个序列不递减。那么我们一开始是很容易想到如果元素 \(p_i\) 原本需要在 \(j\) 的位置上,那么 \(i-j\) 的位置上都应该被划分为一个集合。虽然想到了这点,但是其实还可以用这样一种方式做:前缀和!和排过序的前缀和做比较,当有一个位置前缀和相同则 +1,最后输出答案即可,这个思维一定要想到,是sigma姐姐想出来的,我根本没想到qwq。
标程
1 |
|
G. The Witchwood
题目描述
题目分析
签到,也没啥好说的,就是加出前k大的数。
标程
1 |
|
K.Scholomance Academy
题目描述
题目描述比较长,也不截全了。
题目分析
这题是题是题面巨长,但是答案巨简单的一题,讲的是一个机器学习的问题。我们只需要设置
θ
的值扫过去,然后积分算面积即可,没有用到啥算法。
标程
1 |
|
题意分析
题意: 一个时钟,时针走一圈就是一天,现在给定时针走一圈要 \(H\) 小时,分针走一圈要 \(M\) 分钟,设 \(α=\frac{2πA}{HM}\),求一天中时针和分针夹角小于等于 \(α\) 的时刻有几次。
这题首先有如下几个注意点: ①分针是按照刻度一格一格走的,因此不能将小数的分钟算入,必须是整的(即不能按照角度来求)。 ②两者成角度会有两种情况,分针在时针左边成角度 or 在时针右边成角度
切入点: 一般会最先想到用追及问题的角度去做,但是这样就有两个变量(涉及到分针和时针两个对象),所以我们可以选择将时针作为参照物 (参照物静止不动),运用相对速度只对分针这一个对象做分析。
两者绝对速度: \(v_{h绝对}= \frac{2π}{HM}\) ,$ v_{m绝对}=$
分针相对速度: \(v_{m相对}=v_{m绝对}-v_{h绝对}=\frac{2π}{HM}*(H-1)=(H-1)v_{h绝对}\)
即分针相对于时针以 \(H−1/min\) 的恒定速度运动。
要使两者之间夹角小于等于α,也就相当于追及问题中的两针“路程差”≤α,而此处因为时针作为参照物了,所以也就转化成了分针的“路程”\(≤α=\frac{2πA}{HM}=A*v_{h绝对}\)
因此我们可以写出一个关于时间 \(t∈[0,HM)\) 的不等式:
$t(H-1)v_{h绝对} mod HM ≤ |α|=|A∗ v h 绝 对 *v_{h绝对}∗v $
\(t\times (H-1)\ mod\ HM\le |A|\)
根据剩余系定理三: “若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(mod m)时,有a≡b(mod m)”
所以为了满足互质,可将不等式两边同除以 \(g =\gcd(H-1,HM)\) ,不等式可等价为:
\(t\times \frac{H-1}{g}\ mod\ \frac{HM}{g} \le |\frac{A}{g}|\)
\(\frac{-A}{g}\le t\times \frac{H-1}{g}\ mod\ \frac{HM}{g}\le \frac{A}{g}\)
------------注意:此处t的取值范围也同时从 \([ 0 , HM )\) 缩小到 \([ 0,\frac{HM}{g})\) ---------------
下面就只需求解出 t 的整数解的个数,即为满足条件的时刻的次数。我画在数轴上会比较直观。只需求出正半轴有几个整数解,然后个数 \(\times 2\)并且加上零解。
正半轴:因为要mod之后余数\(≤\frac{A}{g}\),因此一共有余数为$1,2,3… $ 的共计 \(\frac{A}{g}\) 个解,并且这些解中没有重复的,即t的值与余数取值一 一对应,下证:
令\(a=\frac{H-1}{g}\) ,$b= $
假设存在\(t_1\)和\(t_2\) 两个不同的值满足:\(t_1\times\ mod\ b ≡ t_2\times a\ mod\ b\) 且 \(t ∈ [ 0 , b ]\) 因此根据同余定义,易证\(t_1=t_2\) 与假设矛盾,因此每个t的解所对应的余数一定是各不相同的。
所以在 \(t∈[ 0 , \frac{HM}{g} )\) 的范围内一共有 \(2\times (\frac{A}{g})+1\)个不同整数解。把范围还原到 $ [ 0 , HM ) $,就共有 \(g\times[2\times(\frac{A}g)+1]\) 个不同的整数解,也就是本题答案之一。
有一种情况需要特判,就是当 \(A=\frac{HM}{2}\),这时 \(α=π\) ,\(t ∈ [ 0 , HM )\) 中的每个整数都满足条件,故答案为 \(HM\)
标程
然后标程就巨短
1 |
|
小结
希望能和sigma姐姐一起进步,争取下次能vp到铜首水平。