2020沈阳icpc复盘
和sigma姐姐vp这场icpc。
D. Journey to Un’Goro这题是构造题，本来有思路了的，但是没敢提交。
题目描述
题目解析就是说给定一个长度，你需要构造一个只有 r 和 b 字符的字符串，在字符串的子串中，如果有奇数个r，这就是个好区间。问你一个这样长度的字符串最多有多少个好区间，并构造出最好的情况，按字典序输出，如果超过100个则输出前100个。
我们思考一下如何去计算最大值，就得先看看怎么去计数，首先暴力计数需要 $n^2$ 就肯定不行。因为是奇数个，所以我们考虑转化成前缀和。那么我们看看，如果只有一个 r 其它全是 b 我们看哪些区间符合条件。这里我们不妨把 r 当成 1，把 b 当成 0。
12b b b b r r r b b b0 0 0 0 1 2 3 3 3 3
可以很容易发现，当前缀和相减之后为奇数时，区间是好区间。那么就是偶数匹配奇数其实，因为偶数减奇数或者奇数减偶数才有可能得到奇数，而前缀和要么是偶数要么是奇数。我们最终得到的结果就是 $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 这个时候就肯定不行。
标程123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include F. Kobolds and Catacombs题目描述 题目分析就是要把一个序列划分，要尽可能地多划分，被划分的序列在一个内部进行排序，最后要求整个序列不递减。那么我们一开始是很容易想到如果元素 $p_i$ 原本需要在 $j$ 的位置上，那么 $i-j$ 的位置上都应该被划分为一个集合。虽然想到了这点，但是其实还可以用这样一种方式做：前缀和！和排过序的前缀和做比较，当有一个位置前缀和相同则 +1，最后输出答案即可，这个思维一定要想到，是sigma姐姐想出来的，我根本没想到qwq。 标程12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include G. The Witchwood题目描述 题目分析签到，也没啥好说的，就是加出前k大的数。 标程1234567891011121314151617181920#include K.Scholomance Academy题目描述 题目描述比较长，也不截全了。 题目分析这题是题是题面巨长，但是答案巨简单的一题，讲的是一个机器学习的问题。我们只需要设置 θ 的值扫过去，然后积分算面积即可，没有用到啥算法。 标程1234567891011121314151617181920212223242526272829303132333435363738394041#include 题意分析题意： 一个时钟，时针走一圈就是一天，现在给定时针走一圈要 $H$ 小时，分针走一圈要 $M$ 分钟，设 $α=\frac{2πA}{HM}$，求一天中时针和分针夹角小于等于 $α$ 的时刻有几次。 这题首先有如下几个注意点：①分针是按照刻度一格一格走的，因此不能将小数的分钟算入，必须是整的（即不能按照角度来求）。②两者成角度会有两种情况，分针在时针左边成角度 or 在时针右边成角度 切入点： 一般会最先想到用追及问题的角度去做，但是这样就有两个变量（涉及到分针和时针两个对象），所以我们可以选择将时针作为参照物 （参照物静止不动），运用相对速度只对分针这一个对象做分析。 两者绝对速度： $v_{h绝对}= \frac{2π}{HM}$ ，$ v_{m绝对}=\frac{2π}{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\times (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} $ 的共计 $\frac{A}{g}$ 个解，并且这些解中没有重复的，即t的值与余数取值一 一对应，下证： 令$a=\frac{H-1}{g}$ ，$b=\frac{HM}{g} $ 假设存在$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$ 标程然后标程就巨短 123456789101112#include 小结希望能和sigma姐姐一起进步，争取下次能vp到铜首水平。