二模01day1解题报告

时间:2023-12-25 10:46:01

T1.音量调节(changingsounds)

有n个物品的背包(有点不一样,每个物品必须取),给出初始价值,物品价值可正可负(就是两种选择嘛),求可能的最大价值,不可能(<0或>maxsound)输出-1。

很简单的,f[i][j]表示的是到第i首歌时音量为j是否可能。

f[i][j]=f[i-1][j-c[i]]||f[i-1][j+c[i]]  (j-c[i]>=0,j+c[i]<=maxsound)

不贴代码啦。

T2.旅行(journey)

有n*m的矩阵由’.’和’X’组成,X为障碍物’.’为可以通行。求地图上任意两点间的曼哈顿距离之和/空格数的平方 (曼哈顿距离两点对调算不同的)。

一开始想不到怎么解,于是就想拿个50分吧。于是就坑了好久想一个公式啊。经过一番苦解终于解出了n*m的矩阵左上角的点到各点的距离之和为二模01day1解题报告(哈哈哈哈哈)。然而不甘心的我又加了一个四重循环坑坑看后5个点。。。不过最终还是50分

那么怎么AC呢?

二模01day1解题报告

可以发现,如果有这样的点阵,那么蓝点到红点都必须绕过一个X,也就是说蓝点到红点的曼哈顿距离比原来多了二,但是到黄点就不用了。

那么如果要解决X的问题,就可以计算出需要加2的点就可以了。可以用x[],y[]数组来记录每列和每行的X(最早的)位置,然后枚举,向两边寻找更小的x[],y[],再用乘法计算增加的数量。

我们可以先假设X是可穿过的,那么就有了

二模01day1解题报告

这样子的一段处理代码,可以解决无X的情况。

再配合上面的计算方法就可以解决含X的计算了。

这个可以有代码吧。。。

二模01day1解题报告

这一段是处理X的(列上的,行上的自行脑补,稍稍改动一下就好了)

T3.舞蹈课(dancinglessons)

有n个人,每个人有不同价值,每次取相邻的且价值差最小的男女出列,求总数和出列顺序。

打了一个煞笔模拟,每次直接枚举计算最小差然后输出。(总对数直接输出男女中较小的总数)

本来呢,我是想到优先队列来着,但是偏偏想着怎么把不存在的节点取出来而没想到我已经标记过了。。。。QAQ我的天。。。。

那么正解就是优先队列,把每对的差值都算出来存到优先队列里,(要改成小根堆),然后每次取堆顶元素,查看是否标记(直到都没被标记为止),然后在标记,输出,找到左边和右边第一个没被标记的人,查看是否异性,是则入队。如此循环直到队列为空。