HNUOJ 50 题

ScaredQiu · 2024-12-12 11:33:09 · 算法·理论

免责声明

本文档不提供代码，仅提供简化题意或翻译题意以及题目解法描述，不违反学校与课程的相关规定。

本文档仅供参考，不保证信息的准确性、有效性、及时性和完整性，对于使用或未能使用本文档内容所导致的任何损害，作者不承担任何责任。

简介（必读）

文档同步发表在 我的博客，由于洛谷专栏有目录所以建议在洛谷专栏页面阅读。

前言：由于 HNU 的 ACM 课程平时成绩要求在 OJ 上刷 50 题，而 OJ 和上面的题目存在诸多问题，笔者被恶心得无以复加。为了同学们的心理健康，笔者在文档中整理了 OJ 上相对简单的 50 题帮助各位拿到课程平时分。

警告：由于 OJ 的部分题目存在极其荒谬的错误，例如有多组测试数据而不在题面和样例中声明、错误的测试数据以及极慢的评测机（已经使用约 20 年，某些情况下比洛谷评测机慢将近 500 倍），因此——请读者在做题前阅读本文档题目对应部分的警告。

须知：由于 OJ 长期无人维护，需要注意以下事项。

• 湖南大学 OJ 仅可使用湖南大学校园网访问。
• “万能头文件”bits\stdc++.h 不可用，会导致编译错误。
• 在 C++98 版本后加入的库以及函数、语法不可用，例如 std::string 类的 pop_back 函数，同样会导致编译错误。
• 评测机不支持 Python 语言。
• 评测机的反馈除了 Accepted、Wrong Answer、Compile Error、Time Limit Exceeded、Memory Limit Exceeded、Runtime Error 外还存在 Presentation Error（输出格式错误），这种情况一般是输出了多余的空格或换行符导致的。例如输出 3 个用空格隔开的数字 1、2、3，不换行。应当输出 1 2 3 而不是 1 2 3，数字 3 后面的多余空格可能导致评测机返回 Presentation Error，请注意并非每道题的输出格式要求都很严格，读者只有在出现 PE 结果时需要考虑输出格式问题。

对于有多组测试数据的题目，如果不给定测试数据数量，那么可以采用以下方式读入。例如，每组测试数据输入一个整数 n，保证 n 不超过 int 可表示的范围。

第一类实现

int main(){
    int n;
    while(cin>>n){
        //do something
    }
    return 0;
}

第二类实现

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        //do something
    }
    return 0;
}

本文档中如未特殊说明，数组、字符串等序列的下标一律从 1 开始。

第 1 题：A+B Problem

给定整数 a,b，输出它们的和。

题目链接

做法略。

第 2 题：A*B Problem

给定整数 a,b，输出它们的积。

题目链接

做法略。

第 3 题：A/B Problem

给定整数 a,b，输出它们的商向 0 舍入后的值（即 C++ 中 a/b 的值）。

题目链接

做法略。

第 4 题：谁拿了最多奖学金

本题和洛谷 P1051 完全相同，请读者自行学习并完成。

题目链接

做法略。

第 5 题：Recaman's Sequence

使用 a_i 表示 Recaman 序列的第 i 项，已知 a_0 = 0。

对于 i \geq 1 的整数 i，若 a_{i-1} - i \geq 0 且 a_{i-1} - i 这个数没有在 a_0 \sim a_{i-1} 出现过，那么 a_i = a_{i-1} - i，否则 a_i = a_{i-1} + i。

给定整数 k，求 a_k 的值，0 \leq k \leq 5 \times 10^5。

题目链接

使用数组 w 记录某个值是否在 a 中出现过，如果 w_x = 0 则 x 还没有在 a 中出现，否则 x 已经在 a 中出现过。

递推序列 a，若 a_{i-1} - i \geq 0 且 w_{a_{i-1} - i} = 0 则令 a_i = a_{i-1} - i，否则令 a_i = a_{i-1} + i。得到 a_i 的值之后令 w_{a_i} = 1，注意 a_i 的值可能比 5 \times 10^5 大，把 bool 类型数组 w 的大小开到 10^7 即可。

注意递推前先令 w_0 = 1。

第 6 题：Calendar

警告：本题容易导致高血压。

给定天数 n，求 2000 年 1 月 1 日起经过 n 天是几年几月几日星期几（包含 2000 年 1 月 1 日）。

题目链接

首先需要知道能被 400 整除或能被 4 整除但不能被 100 整除的年份是闰年。

预处理数组 w，数组的元素 w_x 表示从 2000 年 1 月 1 日到 x 年 1 月 1 日经过的天数。题目保证答案年份不超过 9999 所以数组 w 大小开到 10^4 即可。

猜测 k 为答案年份，如果 w_k \leq n 则 k 合法。二分得到的符合条件的最大的 k 即答案年份。暴力计算月份和具体日期。

利用 n 除以 7 的余数计算 n 天后是星期几（2000 年 1 月 1 日是星期六）。

预处理的时间复杂度为 O(V)，回答单次询问的时间复杂度为 O(\log V)，其中 V 为答案年份值域。

第 7 题：The Triangle

本题和洛谷 P1216 的区别只是有多组数据，请读者自行学习并完成。

题目链接

做法略。

第 8 题：Self Numbers

使用 d(x) 表示 x 加上 x 的各个位上的数字得到的值，例如 d(123)=123 + 1 + 2 + 3 = 129，d(6) = 6 + 6 =12。如果不存在满足 d(x) = N 的正整数 x 就称 N 为 Self Number，按照从小到大的顺序输出所有大于 0 小于 10^4 的 Self Number，用换行符分隔。

题目链接

由于满足 1 \leq x < 10^4 的 x 一定满足 d(x) > x，所以枚举 [1,10^4) 中的所有整数 i 并标记 d(i) 不是 Self Number 即可。标记用的数组大小最好不小于 10^4 + 36 以避免数组越界。

标记完毕后遍历 [1,10^4) 中的所有整数 i，如果 i 未被标记就将其输出。

第 9 题：幻方矩阵

警告：本题思维难度较大。

题目链接

令 ans_{i,j} 为幻方矩阵第 i 行第 j 列的数字，存在一种幻方的构造方法符合如下公式。

其中 \bmod 为取模运算，即 C++ 中的 % 运算符，其算术优先级与乘除法相同。

由于题目的空间限制不能开规模较大的数组，每次当场计算 ans_{i,j} 后输出即可。

时间复杂度 O(n^2)，空间复杂度 O(1)。

第 10 题：Lowest Bit

给定正整数 x，求 \operatorname{lowbit}(x) 的值。其中 \operatorname{lowbit}(N) 定义为 N 的二进制表示中最低位 1 转化为十进制后的值。例如 \operatorname{lowbit}(14) = 2，\operatorname{lowbit}(15) = 1，\operatorname{lowbit}(16) = 16。

题目链接

对于 int 类型变量 x，\operatorname{lowbit}(x) 的值为 x&-x，计算并输出即可。

第 11 题：Common permutation

给定长度不超过 10^3 的且仅包含小写字母的字符串 S_1,S_2，求长度最长的字符串 x，满足如下条件。

• 重新排列字符串 x 中的字母可以使 x 等于 S_1 的一个子序列。
• 重新排列字符串 x 中的字母可以使 x 等于 S_2 的一个子序列。
• 字符串 x 是所有满足以上条件的字符串中字典序最小的。

概念解释

• 子序列：定义一个字符串 H 是字符串 T 的子序列，当且仅当 H 能够由 T 删除若干字符后获得（可以一个字符都不删除，也可以全删除后得到空子序列）。
• 字典序：对于两个同样长度的字符串 s = s_1s_2\cdots s_L 和 t = t_1t_2 \cdots t_L，称字符串 s 字典序小于字符串 t，当且仅当以下条件成立：存在位置 i，在第 i 个字符之前 s 和 t 都相同，而且 s_i < t_i，即小写字母 s_i 在英文字母顺序中先于 t_i。

题目链接

对于字母 c，如果其在字符串 S_1 中的出现次数为 w_1，在字符串 S_2 中的出现次数为 w_2，那么其至多可以在字符串 x 中出现 \min(w_1,w_2) 次，对每种字母计算其最大出现次数，然后按照 \texttt{a} \sim \texttt{z} 的顺序输出相应数量的字母能够保证字典序最小。

第 12 题：IP Address

给定 n 组询问，每组询问给出一个长度为 32 的 \texttt{01} 串，其中每 8 个字符为一组，每组字符表示一个二进制数。

计算每个 \texttt{01} 串对应的 IP 地址。具体地，对于每组询问输出一行，令第 i 组字符表示的二进制数的十进制表示为 ans_i，按顺序输出 ans_1 \sim ans_4，用字符 . 分隔。

题目链接

读入字符串之后计算 ans_1 \sim ans_4 的值，然后按照指定格式输出。

不会计算 ans 的值的读者请自行学习进制转换相关内容。

第 13 题：Jolly Jumpers

对于一个长度为 n 的序列，如果序列中每一对相邻元素的差的绝对值能够构成一个 1 \sim n-1 的排列，就认为这个序列是 Jolly 的；否则这个序列是 Not jolly 的，给定若干个序列，判断每个序列是否是 Jolly 的。

题目链接

枚举每一对相邻元素，如果有一对元素的差的绝对值不属于 [1,n-1] 那么序列是 Not jolly 的。

再次枚举每一对相邻元素，使用 x_i 表示 |a_i - a_{i+1}| 的值。使用数组 w 的元素 w_j 记录是否存在 x_i = j。枚举所有 x_i 并令 w_{x_i} = 1，枚举完毕后若 w_1 \sim w_{n-1} 的值都为 1 那么序列是 Jolly 的，否则序列是 Not jolly 的。

第 14 题：Sum

对于正整数 n，可以通过将 1 \sim n 写出，然后选择一些数（可以选择任意多个数，也可以不选），在这些数前面添加负号，然后再将写出的所有数相加得到一些数。

例如，对于 n=7 的情况，首先写出 1 \sim 7 的所有数字。

选择一些数字，在前面加上负号。

求和。

因此，称 7 是可构造 12 的。给定正整数 S，求可构造 S 的最小的正整数 n，1 \leq S \leq 10^5。

题目链接

从小到大枚举自然数 n，如果 \sum\limits_{i=1}^{n} i < S，那么 i 必定无法构造 S。

否则，若 \sum\limits_{i=1}^{n} i - S 的值为偶数，当前的 n 就是最小的可构造 S 的正整数。

时间复杂度 O(S)。

第 15 题：Server

给定一个网址，输出其服务器。

例如 http://www.monkey.donkey.zebra.com 的服务器为 www，而 ftp://newton.cs.colorado.edu 的服务器为 newton。即按顺序输出所有在 // 与它之后的第一个 . 之间的字符。

输出前固定要有 server: 这些字符，注意其中包含的空格。

题目链接

做法略。

第 16 题：Faulty Odometer

有一种不包含数字 4 的计数规则，其只有 0,1,2,3,5,6,7,8,9 共 9 个数字。这种技术规则从 1 数到 15 是这样的，1,2,3,5,6,7,8,9,10,11,12,13,15，总共数了 13 下。

给定数字 n，求按照上面的计数规则从 1 数到 n 要数多少下。

题目链接

将 n 中的 5 替换为 4、6 替换为 5、7 替换为 6、8 替换为 7、9 替换为 8。

问题转化为求九进制数 n 的十进制表示。注意输出中包含的空格。

第 17 题：Sorting by Swapping

给定一个 1 \sim n 的排列 p，每次可以交换排列中的两个数字，求让排列满足 p_i = i 的最小交换次数。

概念解释

排列：包含 n 个数，并且包含 [1,n] 中每个整数恰好一次的序列是排列。

题目链接

枚举 p_1 \sim p_n，如果 p_i \neq i 就将满足 p_j = i 的 p_j 与 p_i 交换。

需要记录值 i 的位置 ex_i，每次交换实际上是交换 p_i 和 p_{ex_i}，交换之后更新数组 ex 中的值。

第 18 题：最大公约数

给定正整数 n,m 求 \gcd(n,m) 的值，其中 \gcd(n,m) 为 n 与 m 的最大公约数。

题目链接

做法略。

不会计算最大公约数的读者请自行学习数论相关内容。

第 19 题：2^x mod n = 1

给定正整数 n，求最小的满足 2^x \bmod n = 1 的正整数 x，或者判断不存在这样的正整数。

题目链接

如果 n 等于 1 或 n 是 2 的倍数，那么无解。

否则从 1 开始枚举 x 的值，第一个满足条件的 x 即答案。

时间复杂度 O(n)，因为 n 的范围小可以通过。

第 20 题：津津的储蓄计划

本题与洛谷 P1089 完全相同，请读者自行学习并完成。

题目链接

做法略。

第 21 题：简单的归并

给定两个非递减序列，将它们合并为一个非递减序列。

题目链接

每次比较两个序列的第一个元素，将更小的元素从其所在序列中删除并输出。

时间复杂度 O(n)。

第 22 题：Palindrome

给定若干个字符串，判断每个字符串是不是回文。

概念解释

回文：从左向右读和从右向左读得到的结果相同的字符串是回文。

题目链接

对于长度为 n 的字符串 s，若存在正整数 i 满足 s_i \neq s_{n-i+1} 那么 s 不为回文；否则 s 是回文。

第 23 题：进击的大学生

给定 a,b 求 a+b 的值，多测。

题目链接

做法略。

第 24 题：Annie's Bear

给定整数 n,m,k 判断 n+m \geq k 是否成立。

题目链接

做法略。

第 25 题：实验D——两个数的互素判定

给定正整数 a,b 判断 a,b 是否互质。

题目链接

若 \gcd(a,b) = 1 那么 a,b 互质。注意要开 long long 类型变量。

时间复杂度 O(\log V)，其中 V 为 a,b 的值域。

第 26 题：青姬の爱恋

警告：本题有多组测试数据并且未在题面中说明。

警告：本题有多组测试数据并且未在题面中说明。

警告：本题有多组测试数据并且未在题面中说明。

警告：本题有多组测试数据并且未在题面中说明。

警告：本题有多组测试数据并且未在题面中说明。

给定正整数 n，保证 n 是两个质数的乘积，找到这两个质数中较大的数。

题目链接

令这两个质数为 p,q（其中 p<q），那么必定有 p \leq \sqrt{n}，枚举 2 \sim \sqrt{n} 中的整数找到 p，通过 q = \dfrac{n}{p} 求出 q 的值。

时间复杂度 O(\sqrt{n})。

第 27 题：Fibonacci Number

斐波那契数列 f 的递推式如下。注意本题中数列下标从 0 开始。

给定非负整数 n，求 f_n 的值。

题目链接

做法略。

第 28 题：Word Reversal

给定字符串 s，输出将其左右翻转得到的字符串。

题目链接

做法略。

第 29 题：Palindromes

给定包含大写字母和小写字母的字符串 s，判断其是否是回文（大小写不敏感）。

题目链接

将 s 中的大写字母修改为对应的小写字母，然后套用第 22 题的做法。

第 30 题：Number lengths

给定正整数 n，求 n! 有多少个数位，1 \leq n < 10^6。

题目链接

预处理答案，开一个大于 10^6 的 double 类型数组 sum，初始化 sum_i = \log_{10} i，然后对 sum_1 \sim sum_{10^{6}} 做一遍前缀和。建议使用 cmath 头文件中的 log10 函数。

若 n=1 那么答案为 1；否则答案为 \left\lceil sum_n \right\rceil，向上取整建议使用 cmath 头文件中的 ceil 函数。

第 31 题：Recurrence Relations

给定下列递推式。

给定正整数 n，求 f_n 的值。

题目链接

做法略。

第 32 题：置换排列

给定长度为 n 的排列 p，判断其是否是置换排列。

如果排列 p 对于 [1,n] 中的每个整数 i 都满足 p_{p_i} = i，就认为 p 是一个置换排列。

题目链接

做法略。

第 33 题：Speed Limit

给定 n 条信息，每条信息包含两个正整数 a_i,b_i，计算 \sum\limits_{i=1}^{n} a_i (b_i - b_{i-1})，这里认为 b_0 = 0。

题目链接

做法略。

第 34 题：1, 10, 100, 1000...

有一个由 10 的正数次幂从左到右拼接而成的无限序列，它的前几项为 \texttt{110100100010000}，给定正整数 n，求序列的第 n 个数是 \texttt{0} 还是 \texttt{1}，1 \leq n < 2^{31}。

题目链接

序列第 i 个 \texttt{1} 的位置是 \dfrac{i(i-1)}{2} + 1，是 i^2 等级的。因此可以预先计算出所有位置小于 2^{31} 的 \texttt{1} 的位置并标记，建议使用 map 头文件中的 map<int,bool> 进行标记。

注意超出 2^{31} 的位置会爆 int，计算过程中要使用 long long 类型，而被标记的数必定小于 2^{31}，使用 int 类型足矣。

每次询问的 n 如果被标记则答案是 \texttt{1}；否则答案是 \texttt{0}。

预处理的时间复杂度为 O(\sqrt{n} \log n)，回答单次询问的时间复杂度为 O(\log n)。

第 35 题：Reduced ID Numbers

给定长度为 n 的序列 a，找到最小的正整数 m 使得 a_1 \sim a_n 对 m 取余的结果两两不同。