期末测试补题报告

2024-06-10 21:36
文章标签 测试 期末 报告 补题

本文主要是介绍期末测试补题报告,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1. 游戏机
  • 2. 序列操作
  • 3. 划分区间
  • 4. 数字匹配
  • 5. 地图移动

1. 游戏机

  • 赛时

    Accepted 100 \color{green}\texttt{Accepted 100} Accepted 100

  • 题目描述

    在一个长条形的区域里有 n n n 个格子,人物角色可以从任意一个格子出生,如果格子上是 L,则往左走一格;如果是 R,往右走一格。当角色走出区域时,即为获胜。

    求有多少个格子可以使角色一出生就能直接获胜。

  • 题解

    如果从左边走出区域,那么从这个格子(包括这个格子)一直到最左边的格子都是 L

    如果从右边走出区域,那么从这个格子(包括这个格子)一直到最右边的格子都是 R

  • 代码

    #include <bits/stdc++.h>
    #define endl '\n'
    using namespace std;
    int n;
    string s;
    int main() {CLOSE;while (cin >> n && n) {cin >> s;int ans = 0;for (int i = 0; i < s.size() && s[i] == 'L'; i++)ans++;for (int i = s.size() - 1; i >= 0 && s[i] == 'R'; i--)ans++;cout << ans << endl;}return 0;
    }
    

2. 序列操作

  • 赛时

    Accepted 100 \color{green}\texttt{Accepted 100} Accepted 100

  • 题目描述

    给定一个长度为 n n n 的序列 a a a,然后进行 q q q 次操作 ,然后打印 q q q 次操作后序列最小值的位置。

    • 操作一:输入方式为1 l r,表示将序列 [ l , r ] [l,r] [l,r] 区间的全部元素全部升序排列。

    • 操作二:输入方式为2 l r,表示将序列 [ l , r ] [l,r] [l,r] 区间的全部元素全部降序排列。

    • 操作三:输入方式为3 l r,表示将序列 [ l , r ] [l,r] [l,r] 区间的全部元素进行翻转。

    • 操作四:输入方式为4 l r k,表示将序列 [ l , r ] [l,r] [l,r] 区间的全部元素按照swap(a[i],a[i+k])规则进行交换。

  • 题解

    题目要求操作后最小值的位置,所以我们只需要跟踪最小值的位置 t t t 即可,其他的元素我们并不关心。

    • 操作一:显然,升序排列后最小值在最前面, t = l t=l t=l

    • 操作二:同理, t = r t=r t=r

    • 操作三:易得, t = l + r − t t=l+r-t t=l+rt

    • 操作四:找规律得
      t = { t − k ( l + k ≤ t ≤ r + k ) t + ⌊ r − t k + 1 ⌋ k ( l ≤ t < l + k ) t= \begin{cases} t - k &(l+k\le t\le r + k)\\ t+\lfloor\frac{r-t}{k}+1\rfloor k &(l\le t< l + k) \end{cases} t={tkt+krt+1k(l+ktr+k)(lt<l+k)

  • 代码

    #include <bits/stdc++.h>
    #define endl '\n'
    using namespace std;
    const int N = 2e5 + 10;
    int n, T, q, a[N];
    int main() {CLOSE;cin >> T;while (T--) {cin >> n >> q;int maxn = INT_MAX, t;for (int i = 1; i <= n; i++) {cin >> a[i];if (maxn > a[i]) {maxn = a[i];it = i;}}while (q--) {int k, l, r, op;cin >> op >> l >> r;if (op == 4)cin >> k;if (t >= l && t <= r) {if (op == 1) {t = l;} else if (op == 2) {t = r;} else if (op == 3) {t = l + r - t;}}if (op == 4) {if (t >= l && t <= r + k) {if (t >= l + k)t -= k;else t += ((r - t) / k + 1) * k;}}}cout << t << endl;}return 0;
    }
    

3. 划分区间

  • 赛时

    Wrong Answer 0 \color{red}{\texttt{Wrong Answer 0}} Wrong Answer 0

  • 题目描述

    给定一个包含 n n n 个区间的集合 S S S,请你将 S S S 划分为一个或多个区间,每个区间属于且仅属于一个区间组内, 同一个区间组内的任意两个区间不相交(区间相交指两个区间无重叠部分)。

    请问集合 S S S 最少可以划分为多少区间组?

  • 题解

    贪心。要想让一个区间组尽可能地放更多的区间,就要让区间之间的空隙尽可能地小。现有若干个区间组,要把当前区间组接到一个右端点离它左端点最近的区间组,这样可以使空隙变小。如果现有的区间组右端点都不小于当前区间的左端点,那么把当前区间独立成一个新的区间组。

    所以,不妨先把所有区间按照左端点排序,这样可以使区间右端点尽可能靠前,然后依次考虑每一个区间,每次找右端点最靠前的区间组,如果能放进去,就改变右端点;反之,就加入一个新的区间组。

  • AC代码

    #include <bits/stdc++.h>
    #define endl '\n'
    using namespace std;
    const int N = 1e5 + 10;
    int n;
    struct node{int l, r;bool operator<(const node& x) const {return l < x.l;}
    }a[N];
    priority_queue<int, vector<int>, greater<int>> q;  //小根堆,找最小右端点
    int main() {CLOSE;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;sort (a + 1, a + n + 1);  //左端点排序for (int i = 1; i <= n; i++) {if (!q.empty() && q.top() < a[i].l) q.pop();q.push(a[i].r);}cout << q.size();return 0;
    }
    

4. 数字匹配

  • 赛时

    Runtime Error 30 \color{red}{\texttt{Runtime Error 30}} Runtime Error 30

  • 题目描述

    给定由 m m m 个长度都为 n n n ,仅包含 01 的字符串组成的集合 S S S,再给定 n n n 个整数组成的序列 w w w

    对于字符串 s s s 和字符串 t t t 的匹配收益定义为:
    ∑ i = 1 ∣ s i = t i n w i \sum_{i=1|s_i=t_i}^{n}w_i i=1∣si=tinwi
    进行 q q q 次询问,每次询问给定一个字符串 t t t 和一个整数 k k k,问集合 S S S 中有多少个字符串和 t t t 的匹配收益不多于 k k k

  • 题解

    数据范围太大,枚举必定超时。字符串仅包含 01 ,且 n n n 很小( n ≤ 12 n\le 12 n12),考虑状态压缩,把字符串看作一个二进制数,转换成十进制保存。

    对于两个字符串的匹配,如果对应位相同记为 0,不同记为 1,则可以得到一个“匹配串”,它的十进制是原来两个字符串十进制的异或值。通过异或值,我们可以把匹配受益求出来。

    如果在每次询问时都求一遍异或值,依然超时。考虑 n n n 很小,所以不妨预处理,把所有可能的询问字符串 t t t 和集合中的字符串 s s s 都两两匹配求一下匹配收益,然后使用数组f[t][k]求出当询问字符串为 t t t 时,匹配收益不大于 k k k 的集合中字符串 s s s 的个数。

    易得,数组 f[][] 满足:
    f ( t , k ) = f ( t , k ) + f ( t , k − 1 ) f(t, k) = f(t,k)+f(t,k-1) f(t,k)=f(t,k)+f(t,k1)

  • AC代码

    #include <bits/stdc++.h>
    #define endl '\n'
    using namespace std;
    const int N = 5e5 + 10;
    int n, m, q, w[N], bin[N], f[5000][200];
    string s[N];
    int getbin(string s) {int res = 0;for (int i = 0; i < n; i++)res = res * 2 + (s[i] - '0');return res;
    }
    int main() {CLOSE;cin >> n >> m >> q;for (int i = 1; i <= n; i++)cin >> w[i];for (int i = 1; i <= m; i++)cin >> s[i], bin[getbin(s[i])]++;  //记录s[i]的十进制int len = 1 << n;for (int i = 0; i < len; i++) {if (!bin[i]) continue;for (int j = 0; j < len; j++) {int x = i ^ j, cnt = 0;for (int l = n; l >= 1; l--) {  //求匹配效益cnt += (x % 2 == 0) * w[l];x /= 2;}if (cnt > 100) continue;f[j][cnt] += bin[i]; }}for (int i = 0; i < len; i++) for (int j = 1; j <= 100; j++) f[i][j] += f[i][j - 1];while (q--) {string t;int k;cin >> t >> k;int check = getbin(t);cout << f[check][k] << endl;}return 0;
    }
    

5. 地图移动

  • 赛时

    Runtime Error 0 \color{red}{\texttt{Runtime Error 0}} Runtime Error 0

  • 题目描述

    给定一个 h × w h\times w h×w 的矩阵地图,在地图上有些点是山或者其他障碍物,不可以通过,除此之外所有点都可以走。每次只能向下走或者向右走一步。

    计算,从左上角走到右下角总共有多少种移动方法。

  • 题解

    ( 1 , 1 ) (1,1) (1,1) ( x , y ) (x,y) (x,y) 的路径数为 C x + y − 2 y − 1 C_{x+y-2}^{y-1} Cx+y2y1

    不妨求出路径总数,再减去不能走的路径数。

    障碍点 ( i , j ) (i,j) (i,j) 到起点的路径数时 C i + j − 2 j − 1 C_{i+j-2}^{j-1} Ci+j2j1。但是,在实际计算不能走的路径数时有重复,比如存在路径同时经过两个或多个障碍点。因此,实际计算通过障碍点 ( i , j ) (i,j) (i,j) 的路径数时,应当减去重复的。

    先将障碍点按从左上到右下的顺序排序。

    f ( k ) f(k) f(k) 表示第 k k k 个障碍点, x x x y y y 表示行和列, n u m num num 表示障碍点 k k k 左上方的障碍点个数,则有:
    f ( k ) = C x k + y k − 2 y k − 1 − ∑ i = 1 n u m f ( i ) × C x k + y k − x i − y i y k − y i f(k)=C_{x_k+y_k-2}^{y_k-1}-\sum_{i=1}^{num}f(i)\times C_{x_k+y_k-x_i-y_i}^{y_k-y_i} f(k)=Cxk+yk2yk1i=1numf(i)×Cxk+ykxiyiykyi
    最后,终点的 f ( e n d ) f(end) f(end) 就是答案。

这篇关于期末测试补题报告的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1049334

相关文章

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

【测试】输入正确用户名和密码,点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题: 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定,导致点击后无法触发登录操作。 页面可能存在

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

Python:豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】

**爬取豆瓣电影信息,分析近年电影行业的发展情况** 本文是完整的数据分析展现,代码有完整版,包含豆瓣电影爬取的具体方式【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】   最近MBA在学习《商业数据分析》,大实训作业给了数据要进行数据分析,所以先拿豆瓣电影练练手,网络上爬取豆瓣电影TOP250较多,但对于豆瓣电影全数据的爬取教程很少,所以我自己做一版。 目

开题报告中的研究方法设计:AI能帮你做什么?

AIPaperGPT,论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗?研究方法部分是不是已经让你头疼到抓狂? 别急,这可是大多数人都会遇到的难题!尤其是研究方法设计这一块,选定性还是定量,怎么搞才能符合老师的要求? 每次到这儿,头脑一片空白。 好消息是,现在AI工具火得一塌糊涂,比如ChatGPT,居然能帮你在研究方法这块儿上出点主意。是不

Verybot之OpenCV应用一:安装与图像采集测试

在Verybot上安装OpenCV是很简单的,只需要执行:         sudo apt-get update         sudo apt-get install libopencv-dev         sudo apt-get install python-opencv         下面就对安装好的OpenCV进行一下测试,编写一个通过USB摄像头采

【干货分享】基于SSM的体育场管理系统的开题报告(附源码下载地址)

中秋送好礼 中秋佳节将至,祝福大家中秋快乐,阖家幸福。本期免费分享毕业设计作品:《基于SSM的体育场管理系统》。 基于SSM的体育场管理系统的开题报告 一、课题背景与意义 随着全民健身理念的深入人心,体育场已成为广大师生和社区居民进行体育锻炼的重要场所。然而,传统的体育场管理方式存在诸多问题,如资源分配不均、预约流程繁琐、数据统计不准确等,严重影响了体育场的使用效率和用户体验。