[算法题]CSP 2022汇总

搜索结果

显示上限: 10

[算法题]CSP 2022汇总

2023-08-29 14:10 Steven-Zhl

CCF CSP第28次认证的真题及解析

202212-1 现值计算

时间限制: 1.0s

内存限制: 512.0MB

12-1问题描述

问题描述:

评估一个长期项目的投资收益，资金的时间价值是一个必须要考虑到的因素。简单来说，假设银行的年利率为$5\%$，那么当前的$100$ 元一年后就会变成$105$元，两年后变成$110.25$元。因此，现在收到$100$元比两年后收到$100$元收益更多，两年后再支出$100$元会比立刻支出$100$元更加划算。

基于上述分析，我们使用如下的模型来衡量时间价值：假设银行的年利率为$i$，当前（第$0$年）的$x$元就等价于第$k$年的$x\times(1+i)^k$元；相应的，第$k$年的$x$元的当前价值实际为$x\times(1+i)^{-k}$元。

现给出某项目未来$n$年的预计收入支出情况，在将所有款项转换为当前价值后，试计算该项目的总收益。

输入格式:

从标准输入读入数据。

输入的第一行包含空格分隔的一个正整数$n$和一个实数$i$，分别表示年数和银行年利率。

输入的第二行包含空格分隔的$n+1$个整数，依次表示该项目第$0,1,\cdots,n$年的预计收入（正数）或支出（负数）。

输出格式:

输出到标准输出中。

输出一个实数，表示该项目在当前价值标准下的总盈利或亏损。

子任务:

全部的测试数据满足$0<n\leq 50,0<i<1$，且$i$的有效数字不多于$3$位，每年预计收入（正数）或支出（负数）的绝对值不大于$1000$。

提示:

C/C++：建议使用double类型存储浮点数，并使用scanf("%lf", &x);进行输入，printf("%f", x);进行输出。

Python：直接使用print(x)进行输出即可。

Java：建议使用double类型存储浮点数，可以使用System.out.print(x);进行输出。

12-1样例输入

2 0.05
-200 100 100

12-1样例输出

-14.059

12-3样例说明

该项目当前支出$200$元，在接下来两年每年收入$100$元。虽然表面看起来收支相抵，但计算当前价值可知总共亏损了约$14.059$元。

12-3分析

第一题，只需要按照题义一步步实现即可。
这题的重点反而是看题，注意题目说的第$0,1,\cdots,n$年的预计收入，而要计算的是“当前价值标准下的”，也就是说知道未来的数据，计算现在(第0年)的价值。这一点看明白后就直接套公式就好了。

12-3解答

Python版本

n, i = input().split(" ")
n, i = int(n), float(i)
nums = [int(j) for j in input().split(" ")]  # 获取数据

sum = 0

for j in range(len(nums)):
    sum += nums[j] * pow(1 + i, -j)
print(sum)

C11版本

#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    double i, sum = 0;
    scanf("%d", &n);
    scanf("%lf", &i);
    for (int j = 0; j <= n; j++)
    {
        int temp;
        scanf("%d", &temp);
        sum += temp * pow(1 + i, -j);
    }
    printf("%f", sum);
    return 0;
}

Java版本

import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double sum = 0;
        int n = sc.nextInt();
        double i = sc.nextDouble();
        List<Integer> nums = new ArrayList<Integer>();
        for (int j = 0; j <= n; j++) {
            nums.add(sc.nextInt());
        }
        sc.close();
        for (int j = 0; j < nums.size(); j++) {
            sum += nums.get(j) * Math.pow(1 + i, -j);
        }
        System.out.println(sum);
    }
}

代码长度	编程语言	评测结果	得分	时间使用	空间使用
195B	PYTHON	正确	100	31ms	8.035MB
295B	CPP11	正确	100	15ms	2.687MB
584B	JAVA	正确	100	109ms	23.72MB

202212-3 JPEG解码

时间限制: 1.0s

内存限制: 512.0MB

12-3问题描述

问题背景:

四年一度的世界杯即将画上尾声。在本次的世界杯比赛中，视频助理裁判（Video Assistant Referee, VAR）的应用可谓是大放异彩。VAR 使用视频回放技术帮助主裁判作出正确判罚决定。西西艾弗岛足球联赛的赛场上也引入了一套 VAR 设备。作为技术供应商的技术主管小C，需要存储和编码 VAR 产生的图像数据。小 C 分析比较发现，JPEG 编码算法可以达到较好的压缩效果，并且质量损失是可以接受的。因此，小 C 决定使用 JPEG 编码算法来存储和传输图像数据。JPEG 是一种常用的图片有损压缩算法，它的压缩率高，但是压缩后的图片质量下降较多。JPEG 图片的压缩率一般在 10:1 到 20:1 之间，一般用于存储照片等图片质量要求不高的场景。

为了简化问题，我们以灰度图片为例，介绍 JPEG 编码算法的过程。一张灰度图片，可以被视为由多个像素点组成。每个像素点对应一个 0 到 255 之间的数值，用于表示像素点的亮度。JPEG 编码算法将图片分割为$8\times8$的小块，每个小块被称作一个最小编码单元。对每个小块进行如下的计算：

将每个像素点的数值减去 128，使得每个像素点的数值都在 -128 到 127 之间。

将每个小块的像素点排成一个$8\times8$的矩阵，并对矩阵进行离散余弦变换（DCT）。进行离散余弦变换后，仍然得到一个$8\times8$的矩阵，矩阵中的每个元素都是实数，并且所得矩阵的左上方的数字的绝对值较大，右下方的数字的绝对值较小，甚至接近 0。

对矩阵进行量化操作。量化操作是指将矩阵中的每个元素都除以一个数字，并取整数。量化操作的目的是为了减少矩阵中的数据，从而减少编码后的文件大小。量化操作的数字越大，矩阵中的数据就越少，但是压缩后的图片质量也会越差。

对矩阵进行 Z 字形扫描。Z 字形扫描是指从左上角开始，沿着 Z 字形的路径扫描矩阵中的元素，将扫描到的元素依次排成一个数组，由于 Z 字形扫描的路径是从左上角到右下角，数组结尾处可能存在着连续的 0，为了节省空间，可以不存储这些连续的 0。得到的数据被称为扫描数据。

最后，将得到的各个小块的扫描数据采用哈夫曼编码进行压缩，并置于必要的数据结构中，就能得到一张 JPEG 图片了。

问题描述:

在本题中，你需要实现一个能够解码 JPEG 图片的一个最小编码单元的程序。解码的步骤与上述编码的步骤相反，具体的步骤是：

读入量化矩阵$Q_{i,j}$，其中$i,j$的取值范围为$0-7$。

初始化一个$8\times8$的矩阵$M$，令$M_{i,j}=0$。

读入扫描数据，将扫描数据按照这样的顺序写入矩阵$M$：从左上角$M_{0,0}$开始，接下来填充它的右侧相邻的元素$M_{0,1}$，然后依次向左下方填充直至$M_{1,0}$，接下来从它下侧相邻的元素$M_{2,0}$开始，依次向右上方填充直至$M_{0,2}$，依次类推，循环往复，直至填充满整个矩阵或用尽所有扫描数据，如图所示。

将矩阵$M$中的每个元素都乘以量化矩阵$Q$中的对应元素。

对矩阵$M$进行离散余弦逆变换，得到一个$8\times8$的矩阵$M’$。其中，逆变换的公式如下：

\[M'_{ij}=\frac{1}{4}\sum^7_{u=0}\sum^7_{v=0}\alpha(u)\alpha(v)M_{u,v}cos(\frac{\pi}{8}(i+\frac{1}{2})u)cos(\frac{\pi}{8}(j+\frac{1}{2})v)\] \[\alpha(u)=\begin{cases}\sqrt{\frac{1}{2}} & u=0\\1 & u\neq0\end{cases}\]

将矩阵$M’$中的每个元素都加上$128$，并取最接近的整数（四舍五入）。如果得到的整数大于$255$，则取$255$；如果得到的整数小于$0$，则取$0$。得到的矩阵即为解码后的图片。

输入格式:

从标准输入读入数据。

输入的前 8 行，每行有空格分隔 8 个正整数，是量化矩阵。

接下来的 1 行是 1 个正整数$n$，表示扫描数据的个数。

接下来的 1 行是 1 个数字$T$，取值为 0、1 或 2，表示要进行的任务。

接下来的 1 行，有空格分隔的$n$各整数，是扫描数据。

输出格式:

输出到标准输出中。

输出共 8 行，每行有 8 个空格分隔的整数，表示一个图像矩阵。

当$T$取 0 时，输出填充（步骤 3）后的图像矩阵；当$T$取 1 时，输出量化（步骤 4）后的图像矩阵；当$T$取 2 时，输出最终的解码结果。

子任务:

对于 20% 的数据，有$T=0$；

对于 40% 的数据，有$T=0$或$1$；

对于 100% 的数据，有$T\in {0,1,2}$，且$n\in[0,64]$，并且量化矩阵中的各个元素$q_{i,j}$满足$0<q_{i,j}<256$，扫描序列中的各个元素$m_i$满足$-256<m_i<256$。

提示:

在 C/C++ 语言中，可以通过包含 math.h（C 语言）或 cmath（C++ 语言）来使用数学函数。$\pi$的值可以通过表达式 acos(-1) 获得。

在 Python 语言中，可以通过 from math import pi 引入$\pi$。

在 Java 语言中，可以使用 Math.PI 来获取$\pi$的值。

12-3样例输入

样例输入

16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
26
2
-26 -3 0 -3 -2 -6 2 -4 1 -3 1 1 5 1 2 -1 1 -1 2 0 0 0 0 0 -1 -1

12-3样例输出

样例输出

62 65 57 60 72 63 60 82
57 55 56 82 108 87 62 71
58 50 60 111 148 114 67 65
65 55 66 120 155 114 68 70
70 63 67 101 122 88 60 78
71 71 64 70 80 62 56 81
75 82 67 54 63 65 66 83
81 94 75 54 68 81 81 87

12-3样例说明

本组样例即为题目描述中的样例。

12-3分析

嘛，我只会暴力求解了….

12-3解答

Python版本

from math import pi, cos, sqrt


def calcAlpha(u):
    return sqrt(0.5) if u == 0 else 1


# 处理输入数据
Q = []
for i in range(8):
    Q.append([int(i) for i in input().split(" ")])
n, T = int(input()), int(input())
scanData = [int(i) for i in input().split(" ")]
# 计算M
M = [[0 for _ in range(8)] for _ in range(8)]  # 初始化M
i, j = 0, 0
# 填充数据
down = False
while scanData and i < 8 and j < 8:
    M[i][j] = scanData.pop(0)
    if down:
        if j == 0:  # 说明已经在down方向上到了最后一列，该换方向了
            down = False
            i += 1
        else:  # 还没到最后一行，继续向下
            i += 1
            j -= 1
    else:
        if i == 0:  # 说明已经在up方向上到了第一行，该换方向了
            down = True
            j += 1
        else:  # 还没到第一行，继续向上
            i -= 1
            j += 1
# 计算M.*Q
M2 = [[M[i][j] * Q[i][j] for j in range(8)] for i in range(8)]
# 离散余弦逆变换+第6步变换
M3 = [[0 for _ in range(8)] for _ in range(8)]  # 初始化M3
for i in range(8):
    for j in range(8):
        temp = 0
        for u in range(8):
            for v in range(8):
                temp += (calcAlpha(u) * calcAlpha(v) * M2[u][v] * cos(pi / 8 * (i + 0.5) * u) * cos(
                    pi / 8 * (j + 0.5) * v)) / 4
        temp2 = round(temp + 128)
        if temp2 > 255:
            temp2 = 255
        elif temp2 < 0:
            temp2 = 0
        M3[i][j] = temp2

# 输出结果
if T == 0:
    for row in M:
        print(" ".join([str(i) for i in row]))
elif T == 1:
    for row in M2:
        print(" ".join([str(i) for i in row]))
elif T == 2:
    for row in M3:
        print(" ".join([str(i) for i in row]))

C11版本

#include <stdio.h>
#include <math.h>
#include <string.h>

/*
 * 注：该解法逻辑上应该是没问题的，因为精度原因过不去
 */
double calcAlpha(double u) {
    if (u < 1e-6) {
        return sqrt(0.5);
    } else {
        return (double) 1.0;
    }
}

int main() {
    int Q[8][8];
    double M[8][8], M2[8][8], M3[8][8];
    int scanData[64];
    int n, T;
    // 处理输入数据
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            scanf("%d", &Q[i][j]);
    scanf("%d%d", &n, &T);
    for (int i = 0; i < n; i++)
        scanf("%d", &scanData[i]);
    // 计算M
    memset(M, 0, sizeof(M));
    int i = 0, j = 0, down = 0, scanData_cursor = 0;
    // 填充数据
    while (scanData_cursor < n && i < 8 && j < 8) {
        M[i][j] = scanData[scanData_cursor];
        scanData_cursor++;
        if (down) {
            if (j == 0) {
                i++;
                down = 0;
            } else {
                i++;
                j--;
            }
        } else {
            if (i == 0) {
                j++;
                down = 1;
            } else {
                i--;
                j++;
            }
        }
    }
    // 计算M.*Q
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            M2[i][j] = M[i][j] * Q[i][j];
    // 离散余弦逆变换+第6步变换
    memset(M3, 0, sizeof(M3));
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            double temp = 0, temp2;
            for (int u = 0; u < 8; u++) {
                for (int v = 0; v < 8; v++) {
                    temp += (calcAlpha(u) * calcAlpha(v) * M2[u][v] * cos(acos(-1) / 4.0 * (i + 0.5) * u) *
                             cos(acos(-1) / 4.0 * (j + 0.5) * v)) / 4.0;
                }
            }
            temp2 = round(temp + 128);
            if (temp2 > 255) temp2 = 255;
            else if (temp2 < 0) temp2 = 0;
            M3[i][j] = temp2;
        }
    }
    // 输出结果
    if (T == 0) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; i < 8; i++) {
                printf("%d ", (int) M[i][j]);
            }
            printf("\n");
        }
    } else if (T == 1) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; i < 8; i++) {
                printf("%d ", (int) M2[i][j]);
            }
            printf("\n");
        }
    } else if (T == 2) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; i < 8; i++) {
                printf("%d ", (int) M3[i][j]);
            }
            printf("\n");
        }
    }
}

代码长度	编程语言	评测结果	得分	时间使用	空间使用
1.720KB	PYTHON	运行超时	40	运行超时	8.007MB
4.520KB	CPP11	错误	40	15ms	3.023MB

202212-4 光线追踪

时间限制: 2.0s

内存限制: 512.0MB

12-4问题描述

问题描述:

光线追踪是计算机图形学领域的一个重要算法，其原理是追踪一束从光源发出的光，经过不同的反射面，最终到达摄像机处的过程。

在这道问题中，你需要实现一段程序来处理一个简易的光线追踪模型。

在平面中有一些反射面，为方便起见，我们设这些反射面都是线段，与坐标轴成$45$度角摆放，且两个端点的坐标均为整数。为进一步简化问题，我们假设所有的反射表面都是镜面反射。任何一束光线照射到反射面上（为避免讨论，假设反射面不含端点）时，都会改变方向为相应的镜面反射方向。注意，反射面的两侧都可以反射光线。

平面中还有一些激光光源，每个光源位于一个坐标为整数的点上，会向某个水平或竖直的方向发射一定强度的激光。

所有的反射面都不是完美的，每个反射面有一个折损系数$a$，当强度为$I$的光线照射上去时，反射光线的强度会变成$aI$。为了便于处理，你可以认为所有反射面的材质均不算太好也不算太糟，因此所有的$a$均在$0.2\sim 0.8$的范围内。

在一些超高速摄影问题中，有时甚至连光速都要考虑在内。在这个问题中，我们不妨假设激光在$1$单位时间内恰好移动$1$单位距离。然而，超高速摄影带来的往往是采样精度的损失，因此对于一束激光，最终采样到的光线强度都是向下取整后的数值。特别地，当一束激光的强度小于$1$时，认为其已经完全耗散。

问题的最开始，平面上没有反射面也没有光源。接下来你需要处理若干个操作，每个操作形如：

$x_1$ $y_1$ $x_2$ $y_2$ $a$：在平面上插入一个分别以$(x_1,y_1)$和$(x_2,y_2)$为端点，反射系数为$a$的反射面，保证反射面与坐标轴成$45$度角摆放，且不与先前已经存在、且还没有被删除的反射面在非端点处相交；另外受到渲染效率的影响，问题中的所有反射面的总长度（可以理解为所有的$|x_4-x_2|$之和）不会太大。

$k$：删除第$k$个操作插入的反射面，保证第$k$个操作发生在当前操作之前且为一个插入操作，且这个反射面还没有被删除；

$x$ $y$ $d$ $I$ $t$：在$(x,y)$位置放置一个光源，发射光线的方向为$d$，强度为$I$，求其所经$t$时刻后光线到达的坐标以及采样得到的光线强度。其中$d$的含义为：$d=0$表示沿$x$坐标增加的方向，$d=1$表示沿$y$坐标增加的方向，$d=2$表示沿$x$坐标减小的方向，$d=3$表示沿$y$坐标减小的方向。另外，保证光源不位于当前存在的某个反射面（不含端点）上。注意：如果$t$时刻后光线刚好到达某个反射面，则其强度取反射后的强度。

输入格式:

从标准输入读入数据。

第$1$行，一个正整数$m$表示操作的总数量。

接下来$m$行，每行描述一个操作，格式如题目描述。

其中，除了所有的$a$和$I$以外的输入均为绝对值不超过$10^9$的整数，其中$k$和$t$为正整数；$a$和$I$均为小数点后不超过$6$位的正实数，其中$a$在$0.2\sim 0.8$之间，$I\leq 10^9$。

输出格式:

输出到标准输出中。

对于每个查询操作输出一行，$3$个整数，形如 $x$ $y$ $I$ 表示激光最终到达的位置为$(x,y)$，采样得到的光线强度为$I$。特别地，如果采样到的光线强度为$0$（即光线已耗散），你也就无需关心最终到达的坐标，而只需要输出0 0 0即可。

题目数据保证，你可以在计算时直接使用$64$位浮点数的运算和取整操作，而无需担心可能的精度误差问题。

数据范围:

测试点编号 $m\leq$ 特殊性质

$1\sim 3$ $1000$ 所有光线$t\leq 1000$，所有输入坐标的绝对值$\leq 1000$

$4\sim 7$ $1000$ 无

$8\sim 10$ $10^5$ 所有光线的$t\leq 10$

$11\sim 13$ $10^5$ 所有$1$操作在所有$3$操作之前，且无$2$操作

$14\sim 16$ $10^5$ 所有光线的$I=1$

$17\sim 20$ $10^5$ 无

对于$100\%$的数据，保证$m\leq 10^5$，所有反射面的$|x_1-x_2|$之和不超过$3\times 10^5$

测试点编号	$m\leq$	特殊性质
$1\sim 3$	$1000$	所有光线$t\leq 1000$，所有输入坐标的绝对值$\leq 1000$
$4\sim 7$	$1000$	无
$8\sim 10$	$10^5$	所有光线的$t\leq 10$
$11\sim 13$	$10^5$	所有$1$操作在所有$3$操作之前，且无$2$操作
$14\sim 16$	$10^5$	所有光线的$I=1$
$17\sim 20$	$10^5$	无

12-4样例输入

样例输入

7
1 0 4 2 2 0.4
1 2 2 0 0 0.45
3 -1 3 0 6 5
3 1 5 3 2.4 5
3 0 2 0 3 4
2 1
3 1 5 3 2.4 5

12-4样例输出

样例输出

0 1 1
0 0 0
4 2 3
0 1 1

12-4分析

12-4解答

Python版本

# 未完待续...

代码长度	编程语言	评测结果	得分	时间使用	空间使用
	PYTHON

Steven's Blog

搜索结果

目录

菜单

归档

关于

搜索结果