数据结构期末考试资料代码.zip

# Special-2020级航类庆五一专题赛 LaTeX公式如果无法在线渲染，请下载查看。 所有的标题与题目描述均经过删改（**以防整个项目被github干掉**），**原始题面请前往OJ查看。** # `A` 时间限制：1000ms 内存限制：65536kb 通过率：456/498 `(91.57%) ` 正确率：456/965 `(47.25%)` ## 题目描述 ## 输入 无 ## 输出 输出下图中的文字 [插图敏感,请前往OJ查看] ## HINT 在使用输出函数直接输出**中文字符**时，平台会自动转为`UTF-8`编码进行输出。如果只输出ASCII码值，请确保你的码值对应`UTF-8`的编码。 ## 备注 本题由于政治敏感原因（**害怕这个项目直接被扬了**），请各位直接前往OJ平台对应题目查看输出要求。本项目上传的代码为纯UTF-8码输出的做法。 # `B` 猜拳擂台 时间限制：1000ms 内存限制：65536kb 通过率：167/243 `(68.72%) ` 正确率：167/732 `(22.81%)` ## 题目介绍 AAUB猜拳擂台来了！每位参加比赛的选手均有一个四位数的编号，第一位选手即是擂主。每轮比赛仅进行一局，获胜者成为新的擂主。请你输出最后的擂主。 ## 输入格式 本题中，大写字母`A, B, C`分别代表剪刀、石头、布。 第一行，一个数字，代表第一位选手的编号。 接下来不定行，每一行为一位打擂选的手编号，以及比赛情况。每行格式举例如下： `0001 A C`： 其中第一个数字打擂选手的编号，对于每一次猜拳，第一个字符为**擂主**的出拳，第二个字符为**打擂选手**的出拳。 例如：编号后第一个非空字符`A`代表**擂主**出了剪刀，第二个非空字符`C`代表**打擂选手**出了布。 请使用`EOF`判断输入结束。 ## 输出格式 输出最终擂主的编号，以及他总共参与的对局数，使用空格分隔。 ## 输入样例 ``` 1001 1002 A C 1003 A B 1004 B C ``` ## 输出样例 ``` 1004 1 ``` ## 数据范围 保证不会出现平局的情况。 ## HINT 需要注意：如果最终擂主为`0001`，必须原样输出其四位数编号`0001`。 注意选手可能重复上台哦。 不要问我最多有多少位选手，不想告诉你。 *AUTHOR: Xutian Jing* ## 思路分析 需要注意的是，如果一个人中间被挑战下去了，又重新登上了擂主席，那么他之前的博弈次数也要计算进去 # `C` cbj统计很多个班的成绩 时间限制：1000ms 内存限制：65536kb 通过率：80/111 `(72.07%) ` 正确率：80/322 `(24.84%)` ## 题目描述 ## 输入 若干行字符串 每一行字符串是空格分开的若干个整数，结尾可能有空格或者换行符`\r` 每个整数表示**姜老师**教授的一门课程的一位学生的期末考试成绩 本题字符串数量不确定，请使用`EOF`判断结尾。 ## 输出 对于每组数据,输出一行,格式如下(详见样例) 行号:学生人数 平均分(保留2位小数) ## 数据范围 保证每组输入字符串长度小于$5000$ 保证每个成绩为$[0,100]$的整数 ## 输入样例 ``` 1 1 2 11 45 1 41 91 98 10 ``` ## 输出样例 ``` 1:1 1.00 2:2 1.50 3:7 42.43 ``` ## HINT `姜老师`:可以参考课件 *author:cbj* ## 思路分析 一行的不定组输入，C语言要实现的话需要一定技巧 # `D` 合成OJ排行榜（青春版） 时间限制：1000ms 内存限制：65536kb 通过率：97/105 `(92.38%) ` 正确率：97/238 `(40.76%)` 试着做一个简单的OJ排行榜吧！ OJ排名的条件：分数高的排名在前，分数相同情况下用时少的同学在前，当分数，用时均相同时学号小的同学在前 ## 输入格式 第一行一个整数`n`，表示共`n`个同学，之后`n`行，每行包括： 同学的`id`(一个只由英文字母，`%`，数字组成的字符串，长度不超过`50`) 同学的学号（一个`int`范围内的正整数，任意两个同学不相同） 同学的分数（一个`float`范围内的实数） 同学的罚时（一个时间，格式为`%d:%d:%d`，分别代表时，分，秒，每个整数有且只有两位） 这四部分都用一个空格隔开，具体见输入样例 ## 输出格式 输出完整的排行榜，每个同学分数保留两位小数，其他信息与输入要求相同， ## 输入样例1 ``` 4 lzq 183741430 100 12:59:59 lzqpro 183741431 200 11:59:59 lzqpromax 183741432 200 00:12:01 lzqlite 18371433 0 12:59:59 ``` ## 输出样例1 ``` lzqpromax 183741432 200.00 00:12:01 lzqpro 183741431 200.00 11:59:59 lzq 183741430 100.00 12:59:59 lzqlite 18371433 0.00 12:59:59 ``` ## 输入样例2 ``` 3 a 1 1 00:00:01 b 2 1 00:00:01 c 3 1 00:00:00 ``` ## 输出样例2 ``` c 3 1.00 00:00:00 a 1 1.00 00:00:01 b 2 1.00 00:00:01 ``` ## 数据范围 $1≤n≤1000$ ## HINT 请用`%02d`控制时,分,秒的输出 `Author:`摸鱼的雒子清 # `E` 时间限制：128ms 内存限制：2048kb 通过率：101/124 `(81.45%) ` 正确率：101/332 `(30.42%)` ## 题目描述 一次行军中，有**一位**战士落单，没有回到终点。 每位战士有一个**编号**`id`，现在给出起点处登记的编号，终点处登记的编号，请输出没有回到终点的战士编号。 ## 输入格式 三行。 第一行输入从起点出发的战士人数`n` 第二行为起点处记录的`n`个编号，随机排列，用空格隔开。 第三行为终点处记录的`n-1`个编号，随机排列，用空格隔开。 ## 输出格式 一行，输出没有回到终点的战士编号 ## 输入样例 ``` 10 227 8 3 144 176 60 215 130 253 67 176 8 144 253 60 215 67 130 3 ``` ## 输出样例 ``` 227 ``` ## 数据范围 $0≤id≤2^{32}−1$ $1≤n≤10^5$ ## HINT 这么精彩的五一赛怎么能不出现位运算呢。 *Author:资深工具人孟大师* ## 思路 一看到时间空间限制，就要想到直接用异或和来解决这题 # `F` 众志成城 时间限制：300ms 内存限制：65536kb 通过率：25/53 `(47.17%) ` 正确率：25/162 `(15.43%)` ## 题目介绍 现在我们可以直观感受一下团结的力量，现在有$a,b,c$三个正整数，他们个人的力量可能是微小的，但是团结起来的力量却很大。你现在可以计算$a^{b^{c}}$的值来进行直观感受，因为团结的力量实在是太大了，因此请输出该数字对$100000007$（是一个质数）取模的结果。 ## 输入格式 多组输入，每行三个正整数$a,b,c$ ## 输入样例 ``` 7 4 9 8 9 1 2 6 7 9 1 2 11 1 9 77 8 7 ``` ## 输出样例 ``` 95820093 34217721 19401972 9 11 6308007 ``` ## 数据范围 $a,b,c$均是`int`范围内的正整数 ## HINT $a^{bc}$和$a^{b^{c}}$可不一样哦 了解一下费马小定理，当$p$为一个质数时，$ap−1≡1 (mod p)$ 如果TLE请使用更好的求幂方法 *AUTHOR：ZJD* ## 思路 费马小定理+快速幂/扩展欧拉引理+快速幂 # `G` 时间限制：1000ms 内存限制：65536kb 通过率：19/32 `(59.38%) ` 正确率：19/129 `(14.73%)` ## 题目描述 $$ 1→2→3→……→n−1→n $$ 我会对这个链进行m次调整，每一次的调整都会是如下**2种指令**之一： - 指令1 `1 x`，表示**将编号为x从链中删除**，他的前驱和后继直接进行传递； - 指令2 `2 x y`， 表示**将编号为y插入到编号为x后面**，即x向y传递，y向x原来的后继传递。（**保证x在链且y不在链中**） 所有的指令保证合法，且不存在当前链人数小于2人的情况。 现在请你输出经过m次调整之后的链。 ## 输入格式 输入共$m+1$行. 第$1$行，两个正整数$n,m$，含义如题面所示。 第$2$到$m+1$行，每行为一个指令，具体如下： - 指令1 `1 x` - 指令2 `2 x y` 指令的含义如题面所示，保证$1≤x,y≤n$，且当前操作合法。 ## 输出格式 一行，表示最终的链，每两个数用**一个空格**分开。 ## 输入样例 ``` 5 5 1 2 1 3 1 4 2 1