Steven's Blog

[算法题]CSP 2023汇总

叠个盾：因为我也没针对算法比赛做过什么练习，并且还是Python选手，所以题解水平确实不高，很多解法时间开销较大....见谅

2023-08-28 14:00 Steven-Zhl

CCF CSP第29次、第30次、第31次认证的部分真题及解析

202303-1 田地丈量

• 时间限制: 1.0s
• 内存限制: 512.0MB

03-1问题描述

• 问题描述:
  • 西西艾弗岛上散落着$n$块田地。每块田地可视为平面直角坐标系下的一块矩形区域，由左下角坐标$(x_1,y_1)$和右上角坐标$(x_2,y_2)$唯一确定，且满足$x_1<x_2$、$y_1<y_2$。这$n$块田地中，任意两块的交集面积均为$0$，仅边界处可能有所重叠。
  • 最近，顿顿想要在南山脚下开垦出一块面积为$a\times b$矩形田地，其左下角坐标为$(0,0)$、右上角坐标为$(a,b)$。试计算顿顿选定区域内已经存在的田地面积。
• 输入格式:
  • 从标准输入读入数据。
  • 输入共$n+1$行。
  • 输入的第一行包含空格分隔的三个正整数$n、a、b$，分别表示西西艾弗岛上田地块数和顿顿选定区域的右上角坐标。
  • 接下来$n$行，每行包含空格分隔的四个整数$x_1$、$y_1$、$x_2$和$y_2$，表示一块田地的位置。
• 输出格式:
  • 输出到标准输出中。
  • 输出一个整数，表示顿顿选定区域内的田地面积。
• 子任务: 全部的测试数据满足$n\leq 100$，且所有输入坐标的绝对值均不超过$10^4$。

03-1样例输入

03-1样例输出

44

03-1样例说明

• 如图所示，选定区域内田地（绿色区域）面积为$44$。

附图

03-1分析

解题技巧嘛，有，但不多（毕竟是第1题）

• 其实就是求解重叠面积，唯一的难点在于不知道每次给出的$x_i,y_i$和$a,b$的相对大小关系，也就不便于计算面积。当然可以直接列一堆if，但毕竟不太美观。
• 我用了一个简单的数学算法来解决这个问题：先判断第$i$块地和$[0:a,0:b]$区域有没有重叠，有重叠再计算重叠面积。
• 在重叠的情况下，以$x$坐标举例，给$0,a,x_1,x_2$排序，则位于中间的两个必然分别来自第$i$块地和$[0:a,0:b]$区域，就可以轻松计算出$\Delta x$，同理计算出$\Delta y$，即可计算面积。

03-1解答

• Python版本

n, a, b = [int(i) for i in input().split(" ")]

area = 0
for idx in range(n):
    x1, y1, x2, y2 = [int(i) for i in input().split(" ")]
    if x1 >= a or x2 <= 0 or y1 >= b or y2 <= 0:
        continue
    else:
        tempX = [0, x1, x2, a]
        tempX.sort()
        deltaX = tempX[2] - tempX[1]
        tempY = [0, y1, y2, b]
        tempY.sort()
        deltaY = tempY[2] - tempY[1]
        area += deltaX * deltaY
print(area)

202303-2 垦田计划

• 时间限制: 1.0s
• 内存限制: 512.0MB

03-2问题描述

• 问题描述:
  • 顿顿总共选中了$n$块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第$i$块（$1\leq i\leq n$）区域的开垦耗时为$t_i$天。这$n$块区域可以同时开垦，所以总耗时$t_{Total}$取决于耗时最长的区域，即：
  • \[t_{Total}=\max\{ t_1,t_2,\cdots,t_n \}\]
  • 为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说：
    • 在第$i$块区域每投入$c_i$单位资源，便可将其开垦耗时缩短$1$天；
    • 耗时缩短天数以整数记，即第$i$块区域投入资源数量必须是$c_i$的整数倍；
    • 在第$i$块区域最多可投入$c_i\times (t_i-k)$单位资源，将其开垦耗时缩短为$k$天；
    • 这里的$k$表示开垦一块区域的最少天数，满足$0<k\leq \min{t_1,t_2,\cdots,t_n}$；换言之，如果无限制地投入资源，所有区域都可以用$k$天完成开垦。
  • 现在顿顿手中共有$m$单位资源可供使用，试计算开垦$n$块区域最少需要多少天？
• 输入格式:
  • 从标准输入读入数据。
  • 输入共$n+1$行。
  • 输入的第一行包含空格分隔的三个正整数$n$、$m$和$k$，分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。
  • 接下来$n$行，每行包含空格分隔的两个正整数$t_i$和$c_i$，分别表示第$i$块区域开垦耗时和将耗时缩短$1$天所需资源数量。
• 输出格式:
  • 输出到标准输出。
  • 输出一个整数，表示开垦$n$块区域的最少耗时。
• 子任务:
  • $70\%$的测试数据满足：$0<n,t_i,c_i\leq 100$且$0<m\leq 10^6$；
  • 全部的测试数据满足：$0<n,t_i,c_i\leq 10^5$且$0<m\leq 10^9$。

03-2样例输入1

03-2样例输出1

5

03-2样例解释1

• 如下表所示，投入$5$单位资源即可将总耗时缩短至$5$天。此时顿顿手中还剩余$4$单位资源，但无论如何安排，也无法使总耗时进一步缩短。

03-2样例输入2

03-2样例输出2

2

03-2样例解释2

• 投入$20$单位资源，恰好可将所有区域开垦耗时均缩短为$k=2$天；受限于$k$，剩余的$10$单位资源无法使耗时进一步缩短。

03-2分析

• 很典型的贪心法。思路大致可以概括为：迭代地向$n$个任务中时间最长的任务中投入资源，直至资源不足或所有任务的时间都等于$k$。
• 而且由于本题的“短板效应”，决定了这个题使用简单的贪心法即可（而不是dp）
• 不过不出意外的超时了

03-2解答

• Python版本

n, m, k = [int(i) for i in input().split(' ')]
t, c = [], []
for i in range(n):
    row = input().split(' ')
    t.append(int(row[0]))
    c.append(int(row[1]))

longest_time = max(t)  # 初始化最长时间
longest_index = t.index(longest_time)  # 最长时间的下标
while m >= 0:
    if m >= c[longest_index]:  # 可以减少1天
        if t[longest_index] > k:
            t[longest_index] = longest_time - 1
            m = m - c[longest_index]
            longest_time = max(t)
            longest_index = t.index(longest_time)
    else:  # 资源已经不足以让最长的项目-1，可以退出了
        break

print(longest_time)

202305-1 重复局面

• 时间限制: 1.0s
• 内存限制: 512.0MB

05-1问题描述

• 题目背景: 国际象棋在对局时，同一局面连续或间断出现3次或3次以上，可由任意一方提出和棋。
• 问题描述:
  • 国际象棋每一个局面可以用大小为$8\times 8$的字符数组来表示，其中每一位对应棋盘上的一个格子。六种棋子王、后、车、象、马、兵分别用字母 $k,q,r,b,n,p$ 表示，其中大写字母对应白方、小写字母对应黑方。棋盘上无棋子处用字符*表示。两个字符数组的每一位均相同则说明对应同一局面。
  • 现已按上述方式整理好了每步棋后的局面，试统计每个局面分别是第几次出现。
• 输入格式:
  • 从标准输入读入数据。
  • 输入的第一行包含一个正整数$n$，表示这盘棋总共有$n$步。
  • 接下来$8\times n$行，依次输入第$1$到第$n$步棋后的局面。具体来说每行包含一个长度为$8$的字符串，每$8$行字符串共$64$个字符对应一个局面。
• 输出格式:
  • 输出到标准输出中。
  • 输出共$n$行，每行一个整数，表示该局面是第几次出现。
• 子任务: 输入数据满足$n\leq 100$。
• 提示: 判断重复局面仅涉及字符串比较，无需考虑国际象棋实际行棋规则。

05-1样例输入

05-1样例输出

05-1样例说明

• 第$6$、$7$步后的局面分别与第$2$、$3$步后的局面相同。第$8$步后的局面与上图相对应。

05-1分析

• 没啥好说的，每$8$行截取，然后统计即可。

05-1解答

• Python版本

step = int(input())
map_list = []
for map_index in range(step):
    map_temp = "".join([input() for row in range(8)])
    map_list.append(map_temp)

for i in range(step):
    map = map_list[i]
    print(map_list[: i + 1].count(map))

202305-2 矩阵运算

• 时间限制: 5.0s
• 内存限制: 512.0MB

05-2问题描述

• 题目背景: $Softmax(\frac{Q\times K^T}{\sqrt{d}})\times V$是Transformer中注意力模块地核心算式，其中$Q、K、V$均是$n$行$d$列的矩阵，$K^T$表示矩阵$K$的转置，$\times$表示矩阵乘法。
• 问题描述:
  • 为了方便计算，顿顿同学将$Softmax$简化为了点乘一个大小为$n$的一维向量$W$：$(W\cdot(Q\times K^T))\times V$
  • 点乘即对应位相乘，记$W^{(i)}$为向量$W$的第$i$个元素，即将$(Q\times K^T)$第$i$行中的每个元素都与$W^{(i)}$相乘。
  • 现给出矩阵$Q、K、V$和向量$W$，试计算顿顿按简化的算式计算的结果。
• 输入格式:
  • 从标准输入读入数据。
  • 输入的第一行包含空格分隔的两个正整数$n$和$d$，表示矩阵的大小。
  • 接下来依次输入矩阵$Q、K、V$。每个矩阵输入$n$行，每行包含空格分隔的$d$个整数，其中第$i$行的第$j$个数对应矩阵的第$i$行、第$j$列。
  • 最后一行输入$n$个整数，表示向量$W$。
• 输出格式:
  • 输出到标准输出中。
  • 输出共$n$行，每行包含空格分隔的$d$个整数，表示计算的结果。
• 子任务:
  • $70\%$的测试数据满足：$n\leq 100$且$d\leq10$；输入矩阵、向量中的元素均为整数，且绝对值均不超过$30$。
  • 全部的测试数据满足：$n\leq 10^4$且$d\leq20$；输入矩阵、向量中的元素均为整数，且绝对值均不超过1000。
• 提示: 请谨慎评估矩阵乘法运算后的数值范围，并使用适当数据类型存储矩阵中的整数。

05-2样例输入

05-2样例输出

05-2分析

• 其实可以很明显的发现，这个题就是考矩阵乘法里的点乘和叉乘，直接用循环来模拟矩阵乘法过程是很简单直接的。
• 但题目中“$n\leq 10^4$且$d\leq20$”暗示了$n»d$，如果按照原式的计算顺序，在计算$Q\times K^T$时会出现$n\times n$的矩阵，运算量非常大，有超时风险（事实上这么做也确实会超时），所以需要利用矩阵乘法的性质，先计算$K^T\times V$出现$d\times d$矩阵，然后再计算$Q\times (K^T\times V)$和$W\times (Q\times (K^T\times V))$，以避免超时。

05-2解答

• Python版本

n, d = input().split(" ")
n, d = int(n), int(d)
Q = [[int(i) for i in input().split(" ")] for i in range(int(n))]
K = [[int(i) for i in input().split(" ")] for i in range(int(n))]
V = [[int(i) for i in input().split(" ")] for i in range(int(n))]
W = [int(i) for i in input().split(" ")]
# 计算K^T * V
temp = [[0 for j in range(d)] for i in range(d)]
for i in range(d):
    for j in range(d):
        for k in range(n):
            temp[i][j] = temp[i][j] + K[k][i] * V[k][j]
# 计算W(Q * (K^T * V))
ans = [[0 for j in range(d)] for i in range(n)]
for i in range(n):
    for j in range(d):
        for k in range(d):
            ans[i][j] += Q[i][k] * temp[k][j]
        ans[i][j] *= W[i]

for i in range(n):
    row = ans[i]
    print(" ".join([str(i) for i in row]))

202309-1 坐标变换（其一）

• 时间限制: 1.0s
• 内存限制: 512.0MB

09-1问题描述

• 问题描述:
  • 对于平面直角坐标系上的坐标$(x,y)$，小 P 定义了一个包含$n$个操作的序列$T=(t_1,t_2,…,t_n)$。其中每个操作$t_i(1\leq i\leq n)$包含两个参数$dx_i$和$dy_i$，表示将坐标$(x,y)$平移至$(x+dx_i,y+dy_i)$处。
  • 现给定$m$个初始坐标，试计算对每个坐标$(x_j,y_j),(1\leq j \leq m)$依次进行$T$中$n$个操作后的最终坐标。
• 输入格式:
  • 从标准输入读入数据。
  • 输入共$n+m+1$行。
  • 输入的第一行包含空格分隔的两个正整数$n$和$m$，分别表示操作和初始坐标个数。
  • 接下来$n$行依次输入$n$个操作，其中第$i(1\leq i\leq n)$行包含空格分隔的两个整数$dx_i$、$dy_i$。
  • 接下来$m$行依次输入$m$个坐标，其中第$j(1\leq j\leq m)$行包含空格分隔的两个整数$x_j$、$y_j$。
• 输出格式:
  • 输出到标准输出中。
  • 输出共$m$行，其中第$j(1\leq j \leq m)$行包含空格分隔的两个整数，表示初始坐标$(x_j,y_j)$经过$n$个操作后的位置。
• 评测用例规模与约定:
  • 全部的测试数据满足：$n,m \leq 100$，所有输入数据$(x,y,dx,dy)$均为整数且绝对值不超过$100000$。

09-1样例输入

09-1样例输出

09-1样例说明

• 第一个坐标$(1,-1)$经过三次操作后变为$(21,-11)$；第二个坐标$(0,0)$经过三次操作后变为$(20,-10)。

09-1分析

• 没有什么技巧，怎么要求怎么计算即可

09-1解答

• Python版本

n, m = [int(i) for i in input().split(" ")]  # 数据处理
x_movement, y_movement = 0, 0
# 读取移动
for i in range(n):
    info = input().split(" ")
    x_movement += int(info[0])
    y_movement += int(info[1])
for i in range(m):  # 读取m个点的坐标
    x, y = [int(i) for i in input().split(" ")]
    print(x + x_movement, y + y_movement)

202309-2 坐标变换（其二）

• 时间限制: 2.0s
• 内存限制: 512.0MB

09-2问题描述

• 问题描述:
  • 对于平面直角坐标系上的坐标$(x,y)$，小 P 定义了如下两种操作：
    1. 拉伸$k$倍：横坐标$x$变成$kx$，纵坐标$y$变成$ky$；
    2. 旋转$\theta$：将坐标$(x,y)$绕坐标原点$(0,0)$逆时针旋转$\theta$弧度$(1\leq i \leq j \leq n)$。易知旋转后的横坐标为$x\cos\theta-y\sin\theta$，纵坐标为$x\sin\theta+y\cos\theta$
  • 设定好了包含$n$个操作的序列$(t_1,t_2,…,t_n)$后，小P又定义了如下查询：
    • i j x y：坐标$(x,y)$经过操作$t_i,…,t_j(1 \leq i \leq j \leq n)$后的新坐标。
  • 对于给定的操作序列，试计算$m$各查询的结果。
• 输入格式:
  • 从标准输入读入数据。
  • 输入共$n+m+1$行。
  • 输入的第一行包含空格分隔的两个正整数$n$和$m$，分别表示操作和查询个数。
  • 接下来$n$行依次输入$n$个操作，每行包含空格分隔的一个整数（操作类型）和一个实数（$k$或$\theta$），形如$1k$（表示拉伸$k$倍）或$2\theta$（表示旋转$\theta$）。
  • 接下来$m$行依次输入$m$个查询，每行包含空格分隔的四个整数$i$、$j$、$x$和$y$，含义如前文所述。
• 输出格式:
  • 输出到标准输出中。
  • 输出共$m$行，每行包含空格分隔的两个实数，表示对应查询的结果。
• 评测用例规模与约定:
  • $80%$的数据满足：$n,m \leq 1000$；
  • 全部的测试数据满足：
    • $n,m \leq 100000$；
    • 输入的坐标均为整数且绝对值不超过$1000000$；
    • 单个拉伸操作的系数$k\in[0.5, 2]$；
    • 任意操作区间$t_i,…,t_j$（$1 \leq i \leq j \leq n$）内拉伸系数$k$的乘积在$[0.001, 1000]$范围内。
• 评分方式:
  • 如果你输出的浮点数与参考结果相比，满足绝对误差不大于$0.1$，则该测试点满分，否则不得分。
• 提示:
  • C/C++：建议使用double类型存储浮点数，并使用scanf("%lf", &x);进行输入，printf("%f", x);输出，也可以使用cin和cout输入输出浮点数；#include <math.h>后可使用三角函数cos()和sin()。
  • Python：直接使用print(x)即可输出浮点数x；from math import cos, sin后可使用相应三角函数。
  • Java：建议使用double类型存储浮点数，可以使用System.out.print(x);进行输出；可使用Math.cos()和Math.sin()调用三角函数。

09-2样例输入

09-2样例输出

09-2样例说明

• 第五个查询仅对输入坐标使用了操作八：拉伸$0.716$倍。
• 横坐标：$159430 \times 0.716 = 114151.88$
• 纵坐标：$-511187 \times 0.716 = -366009.892$
• 由于具体计算方式不同，程序输出结果可能与真实值有微小差异，样例输出仅保留了三位小数。

09-2分析

• 直接做也可以，就是先获取$m$和$n$，然后将预定义的$n$个操作暂存以备后用。然后在遍历$m$个操作序列时，用切片获取所需的操作部分，依次运算即可。
  • 但这么做的后果就是会超时，只能拿到80分，我们需要考虑一些简化思路。
• 我们首先剖析一下刚刚的计算过程：一共有$m$组，每组都包括$j-i$个运算。如果我们把拉伸运算定义为$f$，把旋转运算定义为$g$，那么运算实际上是$(j-i)$个$f,g$函数的嵌套运算。
• 既然$m$组大概是没法优化了，也许我们可以优化这个嵌套运算。这时候就考验观察能力了：
  • 如果连续$k$个$f(x,y)$嵌套，那么最终$(x,y)$将会变成$(\prod\limits_{i=1}^k k_i x,\prod\limits_{i=1}^k k_i y)$，emmm这好像没法优化。
  • 如果连续$k$个$g(x,y)$嵌套，那么最终$(x,y)$会变成什么呢？表达式比较难想，但如果从几何意义上来看，就是将$(x,y)$绕原点旋转了$\sum\limits_{i=1}^{k}\theta_i$度。虽然我不知道三角函数具体的运算复杂度，但应该不小，就算假定为不算很大的$O(\log n)$，连续$k$个三角运算的时间复杂度也达到了$O(k\log n)$，这下直接优化到$O(\log n)$了，效果是显而易见的。
  • 用这种思想(其实叫前缀和)优化后的代码，详见解答代码的第二版。但很可惜，我觉得这个算法没问题，在模拟考试时却总是提示错误…但在本地运行是没问题的QAQ

09-2解答

• Python版本

from math import sin, cos


def s(local: tuple, k) -> tuple:
    return local[0] * k, local[1] * k


def a(local: tuple, theta):
    x, y = local[0], local[1]
    return x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)


n, m = [int(i) for i in input().split(" ")]  # 读取数据

operation_list = [[float(i) for i in input().split(' ')] for i in range(n)]

for i in range(m):  # 读取每个点的坐标，以及操作序列
    i, j, x, y = [int(i) for i in input().split(" ")]
    operation_this = operation_list[i - 1:j]
    for op in operation_this:
        if op[0] == 1:
            x, y = s((x, y), op[1])
        else:
            x, y = a((x, y), op[1])
    print(round(x, 3), round(y, 3))

• Python版本(前缀和优化版)

from math import sin, cos


def s(local: tuple, k) -> tuple:
    return local[0] * k, local[1] * k


def a(local: tuple, theta):
    x, y = local[0], local[1]
    return x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)


n, m = [int(i) for i in input().split(" ")]  # 读取数据

operation_list = [[float(i) for i in input().split(' ')] for i in range(n)]

for _ in range(m):  # 读取每个点的坐标，以及操作序列
    i, j, x, y = [int(var) for var in input().split(" ")]
    operation_this = operation_list[i - 1:j]
    idx = 0
    while idx < len(operation_this):
        if operation_this[idx][0] == 1:  # 如果是拉伸，没什么好说的，直接算就是了
            x, y = s((x, y), operation_this[idx][1])
        elif operation_this[idx][0] == 2:  # 如果是旋转
            angle = 0
            for end_idx in range(idx, len(operation_this), 1):
                if operation_this[end_idx][0] == 2:
                    angle += operation_this[end_idx][1]
                    continue
                else:
                    idx = end_idx - 1
                    break
            x, y = a((x, y), angle)
        idx += 1
    print(round(x, 3), round(y, 3))