2020.10.24【普及组】模拟赛C组总结

TOP

这是一个好东西->作者主页

T1 match（100）

题目大意：让你构造一个3乘3的字母表，满足六个字符串都在里面。
思路：

1. 枚举每个字母放什么，剪枝后时间复杂度约为6³
2. 枚举每一行放哪个串，时间复杂度约为6³

T2 最佳裁判（10）

题目大意：多组数据，每个数据给你 n n n个小数，让你去除最大最小值后取平均值，求最接*均值的那个数的编号。
这一题很坑，一开始以为是水题，结果因为精度问题炸掉了QAQ。同上，也有两种方法：

1. 将每个输入的数乘10，这样就保证了是整数除整数，不会出现误差
2. 在判断时将差值加 0. 00 ⋅ ⋅ ⋅ 00 ⏟ 任 意 多 个 0 1 0. \underset{任意多个0}{\underbrace{00···00}}1 0.任意多个0 00⋅⋅⋅00​​1，仍然可以保证无误差

T3 临时工计划（100）

题目大意：给你一些线段，线段选择时不能重叠，且端点不能大于 m m m，每个线段都有一个起始点和终点，还有权值，求怎样选择可以使权值最大。
思路： d p dp dp。设 d p j dp_{j} dpj​表示时间到了 j j j的最大值。然后方程很好推，随便推推就行了。

T4 捉迷藏（10）

题目大意：给你一张图，告诉你起始点，让你 kill 另外两个位置。已知走一步耗费时间为1，求最少时间。

思路：宽搜。考虑以下处理：

1. 预处理出两个人能在哪个地方被看到
2. 因为标记的问题，设 b z x , y , z bz_{x,y,z} bzx,y,z​表示在( x , y x,y x,y)的点，状态为 z z z的情况有没有出现。共有4个状态：00(谁都没看见)，01(看见了大儿子)，10(看见了二儿子)，11(都看见了)
3. 循环队列。因为避免数组越界，可以使用循环队列避免越界。注意：是 L ! = R L!=R L!=R而不是 L < R L<R L<R

完成情况

• T1
• T2
• T3
• T4

题外话

推荐一个很棒的读入字符的函数：

char C()
{
	char ch=getchar();
	while(!(ch>=32&&ch<=126))ch=getchar();//字符是否合法
	return ch;
}