574 解答
对着C怼了半天,结果错误原因是 %ld 不兼容 long long(是这样的= =)。决定以后输出全用cout了。

A. 学生吃菜

送分题。每个人想吃$a_i$,但是上菜必须成对,问多少人吃到了想吃的菜。

大概就是数奇数。

B. 学生吃糖

送分题。一个盒子,每次操作从里面拿一块糖吃掉,或者放进去比之前数目多1的糖。操作n次,剩下k块糖,问吃了几块。

嗯,就是+1+2+3...+l-1-1-1-1=k求解,其实是个一元二次方程。

注意9+8*k+8*n会超过int32,需要用long long存储。

C. 学生打篮球

两队人,选总高度最高的一部分人。不能连续选同一队伍的人,必须交替来。

1 2 10
9 1 1
# 最终选择9 10而不是9 2 1或1 1 10

简单的dp

 maxs[0][i] = max(maxs[0][i - 1] - h[0][i - 1], maxs[1][i - 1]) + h[0][i];
 maxs[1][i] = max(maxs[1][i - 1] - h[1][i - 1], maxs[0][i - 1]) + h[1][i];

maxs需要是long long

D. 求和

定义一个函数$f(a,b)$,$f(a_1 \dots a_p, b_1 \dots b_q) = a_1 a_2 \dots a_{p - q + 1} b_1 a_{p - q + 2} b_2 \dots a_{p - 1} b_{q - 1} a_p b_q$ 其中$a_i$ $b_i$是$a$ $b$ 的十进制写法各个位置的值。

给定数列,求$\sum_{i=1}^n\sum_{j=1}^nf(a_i,a_j)$

D1 所有$a_i$位数相同

一共n个数,每位相当于$11\times n\times \sum s$,这里的s是这一位的值,以输入 n=2 123 456为例,结果如下

112233
445566
142536
415263

所以就是每一位扩展成了100进制,其值就是前面提到的。

D2 位数不一定相同

位数不一定相同,以n=3 12 3 45为例

1122
  33
4455
 123
 132
 453
 435
1425
4152

需要计算并储存有k位的数的个数。对于第k位数字来说,超过k位的部分都需要改成$2\times n\times \sum s$

注意取模。

E. 地图

一个$n\times m$的地图,每个点上存储海拔高度。计算每个$a\times b$格子内最低点高度之和。

海拔高度由$g_i=(g_{i-1}\times x+y)\mod z$获得

就是一个构造问题。先构造行数$a$的每一列最小值矩阵$mn_{i,j}$(通过deque实现),然后在这个每一列最小值矩阵中同样求每一行宽度为$b$的最小值。最后求和。

deque实现

  • 添加数值:判断新数值是否小于尾部数值,小于直接添加,大于删掉尾部数值再添加。保证数列是单调递减的
  • 删除数值:判断删除量等于头部数值,等于就删除。

F. 地理

平面上由$n$个凸多边形,求第$i$到$j$个凸多边形的闵科夫斯基和($C = {a + b : a \in A, b \in B}$)的顶点数。

闵科夫斯基和可以直观理解为把图形$A$按照$B$的边平移最终得到的图形。最后的和是$A$和$B$所有边数目之和,其中所有平行(与x正半轴夹角相同)的边都算作一次。多个图形的和顶点数也是这样的。