题意:大 模 拟
题解:题目比较长,理清逻辑关系即可,没什么好说的……
题意:给定一个只由1 2 3组成的字符串,问取该字符串的一段连续字串,至少要取多长的字串才能满足子串中既有1也有2还有3。
题解:首先判断是否三个数都出现了,若没有都出现,直接就可以判定不成立。然后,最不动脑经的做法,就是从第一个开始模拟,找出每一段连续的且同为一个字符的串,观察该串开头的左边和末尾的右边的字符是否为同一个,若不是则为一种情况。复杂度O(n)
题意:给一个边长全部都为1的正2*n边形,这里n取偶数,要求一个正方形完全盖住这个正2*n边形,问最小边长是什么。
题解:如果n是偶数我们能够比较容易的看出合法的情况为下图
则很容易得出答案为 $\frac{1}{\tan\frac{\pi}{2n}}$
题意:将上述题的n改成奇数
题解:如图
利用对称性,发现当n是奇数时我们可以发现当正多边形在旋转时具有一个对称性,我们旋转$\frac{\pi}{2n}$时,图形会变为原来的状态。则我们不难发现当旋转为一半,即为$\frac{\pi}{4n}$,可以达到最大,那么我们有几何关系可以得到答案为$\frac{\cos\frac{\pi}{4n}}{\sin\frac{\pi}{2n}}$
题意:给一系列数,每个数都满足小于等于n,每次可能进行两个操作,一种操作为将k插入序列,第二种操作为将第k个数消去。问k个操作后是否还有数。
题解:注意一下空间限制,这个限制不能用平衡树,不然死的很惨……,可以利用权值线段树,空间复杂度0(2n),可以满足。