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正半轴夹角相同)的边都算作一次。多个图形的和顶点数也是这样的。