rust-alg

复赛题目
背景：此次⼤赛不是考试，所以不搞LeetCode那套刷题的策略。希望通过⽐赛让⼤家习惯⽤Rust数据结构和算法来思考和解决问题。可以⽤AI或搜索引擎学习背景知识，但禁⽌使⽤AI来做题写代码，提交的代码会检测是否是通过AI完成的。分值已在题号后列出，满分150分。前10道题⽬会⾃动CI评分，最后⼀题无CI评分，会根据代码情况打分，后续再把分加上。即便有⾃动化CI，为防止作弊，保证比赛公平，所有题⽬的代码最后都会人工评审。

要求：代码用Rust实现，而且要多思考和设计使用的数据结构和算法，只解决问题还是刷LeetCode 的思路，不推荐。基础库可引⽤(如标准库、序列化库、数学处理库等)，但不能引⽤其他功能库。不许跨语⾔调⽤其他库，程序执行时不能联⽹查询。如果发现⼀些功能是需要实现成库的，那么就应该自己去实现，这也是比赛推荐的。部分题目看起来需要很多数据，似乎需要打表。这些题目，可以探索采用灵活的数据结构来处理。根据复赛成绩定是否增加限时赛，因为目前是开卷，还不能体现很多同学的水平，如果大家都表现得好，那就加限时赛。

赛题说明：
1.比赛是数据结构和算法学习赛，所以有算法题也有数据结构题，题目就是考这些。
2.偏算法的题优化算法，偏数据的题就考虑怎么合理组织数据，数组、队列、栈、树、图等结构，总有可以用上的。学习赛，就是看怎么组织数据，使用算法策略来计算并输出。
3.有的题是否一定要打个超大的表放在代码里？如果要准备表，是否需要更好地存储形式、转换、查询方法？
4.还有一些题目要求，看起来也需要打表，是否会有比较好的算法实现呢？
5.如果有的题，觉得能封装成库的，可以封装，这也是推荐的做法，这些题目里很多数据或算法目前还没有Rust实现。
6.题目背景都可以搜出来，有些题甚至有线上产品可用，可以思考下别人的产品怎么实现的。换一个思路，如果需要你基于这个需求推出一个同样的产品，技术上你怎么实现？这样就跳出做题了，变成了解决问题。现实中大部分问题都是这类，那种数据准备得很好，让人一上来就可以用的场景很少，可能就专门的竞赛是这种场景，其他的场景都会有很多费力活。
7.三周开卷考试，就是方便大家去思考、学习、组织、处理、解决。对于不熟悉的背景可以多了解，比如星期的定义，农历的定义，搞懂了就比较好开展后续工作了。

代码更新：请大家重新更新或重forkhttps://atomgit.com/rust/RustContest 库代码，按README 要求完成相关设置，保证代码库隐私和得分提交。

题目1 (5分)：

哥德巴赫曾经猜想，每个奇合数可以写成一个素数和一个平方的两倍之和。最终这个猜想被推翻了。试编码求出前两个不能写成一个素数和一个平方的两倍之和的奇合数之和是多少？无输入，直接输出结果。

题目2 (10)：

实现一个算法，计算输入的多个批次的城市群属于多少个省(含自治区、直辖市、港澳台)。输入数据 district.json 在题目对应目录下。
输入:
{
“1”: {
“成都”: [“宜宾”, “自贡”, “绵阳”, “泸州”],
“自贡”: [“成都”, “宜宾”, “泸州”],
“宜宾”: [“泸州”, “成都”, “自贡”, “绵阳”],
“绵阳”: [“成都”, “宜宾”, “自贡”, “宜宾”],
“东莞”: [“深圳”, “广州”, “佛山”],
“深圳”: [“广州”, “佛山”, “东莞”, “湛江”],
“湛江”: [“佛山”, “广州”, “深圳”],
“桃园”: [“台北”, “高雄”, “台中”],
“高雄”: [“台南”, “台北”, “台中”],
“台北”: [“台南”, “台中”, “桃园”],
“台南”: [“台中”, “高雄”, “台北”]
},
“2”: {
“东莞”: [“深圳”, “广州”, “佛山”],
“深圳”: [“广州”, “佛山”, “东莞”, “湛江”],
“桃园”: [“台北”, “高雄”, “台中”],
“台南”: [“台中”, “高雄”, “台北”]
},
…
}
输出：3,2

输入解释：城市主键对应的城市列表表示这个城市和这些城市有关联，看成一个省的
比如，湛江和佛山、广州、深圳是关联的，都属于广东省，其他几个城市分别属于四川和台湾省，所以第一个键对应省数量为3

题目3 (10)：

不使用时间库，自己实现一个时间计算器，输入年月日字符串，输出当前周是第几周，当年还剩多少天(不含当天)，距离过年(正月初一)还有多少天。结果用字符串，逗号隔开。（探索下农历是否有比较好的算法)
输入：2024-11-10
输出：45,51,79
输入：2024-11-18
输出：47,43,71

输出解释：2024-11-18是2024年第47周，2024年还剩下43天，离春节2025-01-29还有 71天

题目4 (10)：

实现一个拼音转换器，输入汉字，自动转为威妥玛表达式。请不要使用别人实现的库。（探索下数据怎么管理，有什么好的形式吗）
输入：北京
输出：Pei ching
输入：诸葛亮
输出：Chu ko liang
输入：上海
输出：Shang hai
输入：美国
输出：Mei kuo
输入：曹操
输出：Ts’ao ts’ao

题目5 (10)：

实现一个退休计算器，要求输入出生年月、人员类型，输出退休时间、退休年龄(精确到2位小数)和延迟退休月数。(请结合中央最新政策，后续延迟退休政策出台时，代码改动要小或无改动)。
输入：1971-04,原法定退休年龄55周岁女职工
输出：2026-08,55.33,4
输入：1995-12,原法定退休年龄50周岁女职工
输出：2050-12,55,60
输入：1995-12,男职工
输出：2058-12,63,36
输入：2000-12,原法定退休年龄55周岁女职工
输出：2058-12,58,36
输出解释：2058年12月退休，退休年龄58岁, 延迟退休36个月

思路：本质上都是从n年开始，每几个月延期一个月，上限是多少，原本是多久退休，将这个计算抽象出来作为计算函数，然后根据不同的输入参数调用这个函数，得到结果。

fn  uni_cal(year:i32,month:i32,start_year:i32,end_year:i32,max_add:i32,origin_year:i32,div:i32)->(i32,i32,f64,i32){
    let addtion_month = if year < start_year {
        0
    } else if year >= end_year {
        max_add
    } else {
        ((year - start_year) * 12 + month - 1) / div+1
    };

    let mut retire_year = year + origin_year+addtion_month/12;
    let mut retire_month = month  + addtion_month%12;

    // Correct month overflow
    if retire_month > 12 {
        retire_year += retire_month / 12;
        retire_month = retire_month % 12;
    }

    let retire_age = (origin_year as f64)+((addtion_month as f64) / 12.0);
    (retire_year,retire_month,retire_age,addtion_month)
}

题目6 (10)：

实现一个算法或程序，支持简繁互转换，模式可设定(s2t,t2s)。输入是繁体，输出是简体，输入简体，输出繁体。请不要使用别人实现的库。（多模式，简繁数据很多，是否一定要打表？）
输入：學習,t2s,
输出：学习
输入：电视,s2t
输出：電視
输入：中國,t2s
输出：中国
输入：龙的传人,s2t
输出：龍的傳人

思路：使用mediawiki-1.42.3中的ZhConversion.php导出csv文件，然后通过读取csv文件建立hash表，实现简繁互转换。

public static function exportZh2hansToCSV($filename){
		$file = fopen($filename, 'w');
		foreach (self::$zh2Hans as $key => $value) {
			fputcsv($file, [$key, $value]);
		}
		fclose($file);
	}

题目7 (10)：

实现一个身份证号码校验算法，用于校验身份证号。输入参数是身份证号，需要判断是否有效、性别、出生日期、输出其籍贯：省-市-区(县)。(下面是举例，号码是随机的，籍贯数据探索下如何高效管理)
输入：510399200012236015
输出：身份证号码错误
输入：370683198901117652
输出：身份证号码正确,男,1989年01月11日,山东省-烟台市-莱州市
输入：31010419900712232X
输出：身份证号码正确,女,1990年07月12日,上海市-市辖区-徐汇区

题目8 (10)：

设计一个高效的算法，用于找出正整数的最大素数因子，正整数可能非常大。
输入：53
输出：53
输入：12
输出：3
输入：33
输出：11
输出解释：11是能整除33的最大素数

题目9 (10)：

从1开始逆时针螺旋着摆放自然数，我们可以构造出一个边长为7的螺旋数阵。可以发现在所有对角线上一共有 8 个素数，比例达到 8/13≈628/13≈62。如果不断重复这个过程，求对角线上素数的比例第一次低于某个比例时，螺旋数阵的边长是多少，此时有多少个素数？(比例不会小于 7%)

输入： 50
输出： 11,10 # 输出逗号分割字符串
解释：对角线上素数占比小于50%时，边长至少为11, 此时有10个素数。

题目10 (15)：

随着信息技术的迅速发展，网络安全问题日益突出。为保护国家关键基础设施、重要信息系统和敏感数据的安全，需要有一套自主可控的密码算法体系。国密标准的制定就是为了确保在密码技术方面不受制于人。国密标准的制定始于2007年，并于2010年正式发布，包括：SM1、SM2、SM3、SM4、SM7、SM9、ZUC。其中ZUC(祖冲之算法)是一种流密码算法，主要用于3GPP LTE通信中的数据加密和完整性保护，请实现一个标准的Rust版的ZUC算法，大端处理，数据处理块大小为32位，若数据长度不够可用PKCS7填充。密钥和初始化向量分别是：[0u8; 16], [1u8; 16]。要求算法接收输入字符串并返回加密后的结果(Base64格式字符串)。
输入：Rust
输出：SPqRf7WauAI=
输入：依法治国
输出：/jF/7QILWrTdhHS/qnwkFA==
输入：love
输出：duCUbrWauAI=

题目11 (50):

内存分配器
【题目背景】
●动态内存分配器，又称为堆内存分配器，开发者通过动态内存分配（例如 Box::new、Vec::new 等）让程序在运行时获得内存。动态内存分配器管理一个虚拟内存区域，称为堆（heap）。分配器以块（block）为单位来维护堆，可以进行分配或者释放操作。在 Rust 中，内存管理主要通过所有权和生命周期规则来自动管理。但随着 Rust 在越来越多领域开始使用，涉及的场景越来越多样，如汽车、手机、AIOT、嵌入式、大数据等，有时也需要手动管理内存，特别是在实现自定义内存分配器时。常见的分配器有两种基本风格：
●显式分配器：需要开发者显式地分配或释放内存。例如 Box::new 和 drop。
●隐式分配器：在 Rust 中，隐式内存管理主要通过所有权和生命周期规则来实现，不需要手动释放内存。
【题目描述】
现代内存分配器需要平衡多个方面的需求，包括性能、安全、并发处理能力以及应用的具体需求。随着技术的发展，越来越多的内存分配器被用于支持那些依赖引用计数自动管理内存的语言，比如 Swift 和 Python。为此，我们介绍一种新的内存分配器——https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf。mimalloc 不仅在平衡这些需求方面表现优异，而且在性能上超越了许多现有的分配器，特别适用于那些将内存分配器作为引用计数机制后端的语言。
mimalloc 引入了几项创新特性。首先，它采用了每页三个本地分片的空闲列表，这提升了数据局部性，又减少了多线程下的竞争问题，同时还支持高效的分配和释放。此外，这些空闲列表还实现了时间节奏机制，使得分配器可以定期从快速路径中退出，进行必要的维护，如延迟释放内存、处理来自非本地线程的释放请求等。尽管 mimalloc 的设计受到了引用计数语言 Lean 和 Koka 的启发，但它在实际测试中展现出了比现代商业内存分配器（如 tcmalloc 和 jemalloc）更好的性能。例如，在 Redis 测试中，mimalloc 的速度分别比这两个竞品快了 7% 和 14%，并且在多种顺序和并发基准测试中持续领先。
mimalloc 已有C 语言版https://github.com/microsoft/mimalloc，但还无 Rust 版实现。 Rust 标准库没有提供类似 C 语言中 malloc、free 和 realloc 这样的函数，但通过 alloc 模块、智能指针等，你仍然可以实现类似的低级别内存管理功能。本题需要你完成一个 Rust 版的 mimalloc。
【参考链接】
●mimalloc 详情: https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf
●mimalloc C语言实现: https://github.com/microsoft/mimalloc

ฅ•ω•ฅ