2020.09.19【普及组】模拟赛C组总结_有n个小球排成一行,现在要对每个小球染一种颜色,一共有c 种颜色可供使用。若要求

总结

这一次考试没考好，原因有两个：

• 数学方法没做好
• 暴力打错

下一次不能犯同样的错误

T1蜈蚣（48）

题目大意：有$c$只$f$条腿的蜈蚣，还有$n$种颜色的袜子，每种多个，每只蜈蚣只能穿同样颜色袜子，求最少随机摸多少只袜子可以保证每只蜈蚣都有袜子。

这一题考试的时候想的是抽屉原理，只不过实现时是一个一个减的，所以错了。正确答案是先判断这种颜色是否能用，不能用就答案加上数量，否则减去 $(f-1)$ ，然后每次枚举最多数量的袜子，减去，判断是否足够，够就输出答案。

T2白板（100）

题目大意：告诉你三个矩阵，判断第一个矩阵是否被剩下两个矩阵覆盖。
这一题有两种做法，第一种是离散化，第二种是判断。考试时用的离散化，因为这和之前做的一道题特别像（那题数据更大 ）。
具体判断方法就是判断三种情况：

1. 一个包含另一个
2. 两个横着包含
3. 两个竖着包含

T3序列（30）

题目大意：给你一个无限长的序列：1,1,2,1,2,3,…,1,2,3,4,5,6,7,8,9,1,0,…，让你找规律，输出第$k$个位是什么数。
这一题考试的时候打了个离线加暴力，得了三十。听完课后知道70分做法是二分一个答案，判断满不满足，然后在那个答案上暴力。100分是二分套二分，就是把暴力改成等差数列计算，然后再二分。
具体如下：
1 | 1 2 | 1 2 3 | 1 2 3 4 |…
二分它在哪个区，然后套一个二分，求出那个区答案的位置。
第2个二分（禁止抄袭）：

//ef2(k,ef1(k));
LL ef2(LL c,LL x)//传参就自己理解好吧
{
	LL l=0,r=x+2,s=1,cc=c;
	c-=num2(x-1);//num2()求第1个分区到第x-1个分区的数字个数
	while(l+1<r)
	{
		LL mid=(l+r)/2;
		if(c>num(mid))l=mid;//num()求1~mid中数字个数
		else if(c==num(mid))return ______;//刚好够的判断
		else r=mid;s=mid;
	}
	return baoli(c-num(s-1),x,s);//baoli()是枚举，第三个参数为枚举起点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

T4游戏（0）

题目大意：有$n$个珠子，每个珠子有一种颜色$c_i(c_i$<=$20)$，然后让连续一段区间都为相同的颜色，且其他地方不再有。求最少相邻交换珠子的次数。
考试时打了个20分代码，可是没有注意要连续，其他地方不能有，于是WA 0分了。

1. 20分：判断1放在左边好还是右边好
2. 60分：枚举颜色的放置顺序，通过归并排序$nlogn$求出逆序对个数，取最小值
3. 100分：设$f_s$表示状态为$s$时，逆序对个数，再设$C_{i,j}$为颜色$i$在颜色$j$前面，逆序对个数。转移方程是枚举一个$i$是$s$中没出现的，$j$是$s$中出现的，然后转移。

完成情况

• T1蜈蚣
• T2白板
• T3序列
• T4游戏