2020.11.12 模拟赛1 题解
T1 粉刷任务/task
题目描述
有(n)条木板，从上到下依次摆放，其中第(i)条木板的水平长度等于正整数(A_i)，高度等于(1)。这些木板按左端对齐，并且第i 条的下边界紧贴着第(i+1)条的上边界。
现在请你粉刷这(n)条的木板。你只有一个宽度为(1)的刷子，每次可以水平或者竖直地对连续的位置进行粉刷，但是刷子不能经过没有木板的位置。
现在允许同一个位置被多次粉刷。你希望通过最少的粉刷次数完成这(n)条木板的粉刷（即使得每块木板的每个位置都被刷到至少一次）。
这种情况下需要刷至少5下。
题解
全部横着刷最多需要(n)次，因此考虑用竖直刷来减少横着刷的次数。如果竖直刷，一定先考虑最左边的列。
如果一行被竖直操作完全覆盖，那就没有必要刷这一行了。
(f[i][j])表示染前(i)行，还有(j)个竖直操作可以往下延伸的最少操作次数（因为如果中间有短的一行那可能就有无法延伸的数值操作。复杂度(O(n^2))。
假设已经完成了(f[i][j])的计算，考虑(a[i+1])。
- (j<a[i+1])。即之前可以延伸的还没有完全能把这一行完全覆盖，因此后面的部分需要额外覆盖。可以使用一次横着或者全部竖直来覆盖这一部分。(f[i+1][a[i+1]]=f[i][j]+a[i+1]-j,f[i+1][j]=f[i+1][j]+1).
- (j=a[i+1])。那么就完全不需要额外覆盖，(f[i+1][j]=f[i][j])。
- (j>a[i+1])。那么就是说这一行阻断了竖直方向的覆盖，所以(f[i+1][a[i+1]]=f[i][j])。
T2
题目描述
你有(n)根火柴棍，并用它们摆出一个(k)位的正整数，且要求恰好把所有火柴棍都用完。这里(kge1)，且这个(k)位正整数不可以包含前导零。每个数字的形状如下图所示。
令(x_1,x_2,dots,x_m)表示所有可以摆出的(k)位正整数。给定非负整数(d)，你需要输出：
题解
(f[i][j])表示(i)个火柴表示(j)位数的(0)次方和；
(g[i][j])表示(i)个火柴表示(j)位数的(1)次方和；
(h[i][j])表示(i)个火柴表示(j)位数的(2)次方和。
对于(2)次方和每次多加一位时，只需要用完全平方展开即可转移。
用dp可以简单地解决。为了防止爆空间，可以考虑用滚动数组。
同时要关注首位非0的问题。
记数字(x)需要的火柴数为(d[x])，(t[i]=(i==0))，则有转移方程：
拓展：使用二次项展开可以拓展到(dle10)的情况。
T3
题目描述
有一个特殊的扑克游戏，算分规则是这样的：
• 先把(n)张牌放在桌上，每张牌编号(1sim n)。每张牌都有两面，一面点数为(A_i)，另一面点数为(B_i)，一开始写着(A_i)的面作为正面朝上。
• 接下来依次进行(K)轮操作，每次把所有朝上面点数(le T_j)的牌翻面。
• 所有操作完成后，计算所有牌朝上面点数之和(Sum)。
你需要输出最终的总分(Sum)。
题解
令较大的为(b[i])，较小的为(a[i])，即(forall iin[1,n])，有(a[i]le b[i])。
对于一个(T)，讨论三个情况：
- (T<a[i])。无论是哪面朝上，都不会有任何影响。
- (Tge b[i])。无论是哪面朝上，都会被翻转。
- (a[i]le T< b[i])。如果原来是(b[i])，不会被翻转；如果原来是(a[i])，一定被翻转。因此可以理解为翻转成为(b[i]).
因此，对于每张牌，找到最后一个第(3)类操作。然后从此往后寻找第(2)类操作的个数，如果是奇数次，则(a[i])朝上；反之(b[i])朝上。
可以考虑整个解题过程为两个步骤： - 对每个(i)，找到(max{j})，使得(a[i]le t[j]<b[i])。
- 找到(j')的个数，使得(j'>j)且(t[j']ge b[i])。
因此可以把原题转换为普通的数据结构题。
建立线段树(S)，对所有的(t[j])，在(t[j])的位置上插入(j)，每次在区间([a[i],b[i]-1])上查找最大的(j)。这样就完成了第一步的查询。（也可以用ST表）
等同于在平面直角坐标系中，对一个点，询问其右上角的点数有多少：二维偏序。
只要离线做法，因此依次扫描并加入一个BIT中，当询问时即回答已经计入BIT（即在其上方）的、位置在询问点右边的个数。