因为很喜欢我的伪代码所以备份一下

条件

• 全部都是直线段
• 没有重合的线段
• 线段端点不重合
• 没有三条及以上线段在同一点相交

基本算法思路

1. 事件点优先队列Q
   将所有线段的端点作为事件点，分为起点和终点，按x坐标排序，若x坐标相同则按y坐标排序。使用一个红黑树存储点指针。
2. 扫描线状态活动集S
   使用一个平衡二叉搜索树来维护当前扫描线与线段，按线段在扫描线上的y坐标排序。每当扫描线经过一个事件点时，更新树的状态。

   由于std::set底层不支持动态更新key值，所以自己实现了平衡搜索树。

3. 处理事件点

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

   //处理事件点伪代码 while(Q非空) { 弹出事件点p; switch(p的类型) { case 起点: p的关联线段l插入到S; if(l的上邻居与l相交) 计算交点并插入Q; if(l的下邻居与l相交) 计算交点并插入Q; break; case 终点: if(l的上邻居与l的下邻居相交) 计算交点并插入Q; l从S中删除; break; case 交点: 交点关联的两条线段为l1和l2; 交换l1和l2在S中的位置;//设定交换后l1在上，l2在下 if(l1的上邻居与l1相交) 计算交点并插入Q; if(l2的下邻居与l2相交) 计算交点并插入Q; break; } }

4. 拆分线段
   记录每个线段对应的事件点指针。如果数量大于2，将线段删除并拆分成多个线段，重新插入到原链表中。

剩下的是付费内容（）

前言

众所周知，二叉搜索树的性质是，节点的左子树键值都比节点的小，右子树键值都比节点的大。当单调增加或减少的值一一插入时，插入等时间复杂度严重退化成线性。所以我们要控制左右子树的高度差，作为平衡因子，将一次操作的时间复杂度控制在对数级内。

在实习的应用场景中，我想将一个时间复杂度高达 的算法，降到 ，以便于给后面的 算法腾出点儿时间（划掉）。查询资料，我选择了 Avl 树作为底层数据结构。接下来，我将写一个针对那个问题的c++模板类，以便于后续的更改。

（以后要不要来点酸爽的红黑树呢？）

实现

时间复杂度测试

%%%
计算机系统结构的GCD法引发的深思

求模与求余的区别

这是我们小学二年级就会的除法运算。

$
\begin{aligned}
5\div3&=1\cdots2\\
(-5)\div3&=(-1)\cdots(-2)\\
(-5)\div(-3)&=1\cdots(-2)\\
5\div(-3)&=(-1)\cdots2
\end{aligned}
$

好吧，我是平凡而随处可见的小学生，没学过负数……

数学定义

求模和求余的主要区别在于处理负数的方式。
首先，商的符号永远由被除数和除数一起决定。

• 求余操作 (a % b)：
  • 余数的符号与被除数相同
  • 商 = abs(a)/abs(b)*sign(a)*sign(b)
  • 余数 = a-b*商 = abs(a)%abs(b)*sign(a)
• 求模操作 (a mod b)：
  • 模的符号与除数相同
  • 商 = abs(a)/abs(b)-(sign(a)*sign(b)==1?0:abs(b))
  • 模 = a-b*商 = abs(abs(a)%abs(b)-(sign(a)*sign(b)==1?0:abs(b))*sign(b)

其中sign(a)为取a的正负符号,正为1，负为-1，0为0

实际对比

对于正数，两者结果相同：
对于负数，结果可能不同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include<bits/stdc++.h>
using namespace std;
int main() {
    //求余
    int a[]={5,-5,-5,5},b[]={3,3,-3,-3};
    for(int i=0;i<4;++i){
        cout<<a[i]<<" div "<<b[i]<<" = "<<a[i]/b[i]<<"···"<<a[i]%b[i]<<endl;
    }
    return 0;
}
//result
5 div 3 = 1···2
-5 div 3 = -1···-2
-5 div -3 = 1···-2
5 div -3 = -1···2

1
2
3
4
5
6
7
8
9
10
11

# 求模
a=[5,-5,-5,5]
b=[3,3,-3,-3]
for i in range(4):
    print(f'{a[i]} div {b[i]} = {a[i]//b[i]}···{a[i]%b[i]}')

# result
5 div 3 = 1···2
-5 div 3 = -2···1
-5 div -3 = 1···-2
5 div -3 = -2···-1

表格对比

转换公式

默认求模的程序语言：Python, Ruby
默认求余的程序语言：C, C++, Java, JavaScript

如果想在求余的语言中实现求模：

1
2
3
4

int mod(int a, int b) {
    int r = a % b;
    return r < 0 ? r + abs(b) : r;
}

如果想在求模的语言中实现求余：

1
2
3
4
5

def remainder(a, b):
    r = a % b
    if (a < 0 and b > 0) or (a > 0 and b < 0):
        return r - b
    return r

模意义下的加减乘除

$
(a+b)\bmod c=((a\bmod c)+(b\bmod c))\bmod c\\
(a-b)\bmod c=((a\bmod c)-(b\bmod c))\bmod c\\
(a\times b)\bmod c=((a\bmod c)\times (b\bmod c))\bmod c
$

但是注意，除法就不是这样的了

$
(a\div b)\bmod c=(a\times b^{-1})\bmod c=((a\bmod c)\times (b^{-1}\bmod c))\bmod c
$

$b^{-1}$是逆元

🚧施工中🚧

排序之间的比较

习题

有序的排序

(没好好看题全做错了)
对 n 个基本有序的整数进行排序：

1. 若采用插入排序算法，则时间和空间复杂度分别为（ ）；
2. 若采用快速排序算法，则时间和空间复杂度分别为（ ）。

正确答案

1. 插入排序：时间复杂度 ，空间复杂度 .
2. 快速排序：时间复杂度 ，空间复杂度 .

解析

1. 插入排序：

   • 时间复杂度：当数据基本有序时，插入排序只需进行少量的比较和移动操作，因此时间复杂度为
   • 空间复杂度：插入排序只需常数级的额外空间（如临时变量等），因此空间复杂度为 .

2. 快速排序：

   • 时间复杂度：快速排序在最坏情况下（如数据已完全有序），每次划分只能将数组分成一个元素和 个元素的两部分，此时递归深度为 ，时间复杂度为 .
   • 空间复杂度：快速排序主要是在原数组上进行操作，无需额外的存储空间，因此空间复杂度为 .

这不是某大学期末考试考的东西，不要背。

信息安全

信息的特性：

密码体制和加密算法

• 对称加密/共享密钥
  • 加密密钥与解密密钥都是用相同密钥
  • 对大量明文加密时，考虑效率，一般采用对称加密
  • 常用算法：AES、DES、3DES、RC-5
• 非对称加密/公钥加密
  • 使用不同的加密密钥与解密密钥。公钥加密，私钥解密
  • 常见算法：RSA、ECC、EIGamma、背包算法
• 流加密
  • 加密和解密双方使用相同伪随机加密数据流作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流
  • 常见算法：RC4、ORYX、SEAL
• 分组加密
  • 将明文分为等长的模块，使用确定的算法和对称密钥对每组分别加密解密
  • 常见算法：DES、AES
• 数字摘要/消息摘要算法
  • 一个唯一对应一个消息或文本的固定长度的值
  • 单向Hash加密函数
  • 常见算法：MD5、SHA、MAC

X.509数字证书推荐使用的密码算法：RSA
国密SM2数字证书采用的密码算法：ECC

数字签名与数字证书

数字签名

• 功能 ：保证信息的完整性和不可否认性。确保信息在传输过程中未被篡改，同时让接收方确认消息确实来自发送方且发送方无法否认其发送过该消息。
• 密钥使用 ：发送方使用自己的私钥对信息生成数字签名，接收方用发送方的公钥验证签名，验证通过则确认信息完整性和身份。

数字证书

• 功能 ：用于证明身份和确保公钥可信度。就像网络上的身份证，由权威机构颁发，验证持有者身份及公钥归属。
• 密钥使用 ：证书中包含公钥，证书颁发机构用自己的私钥对证书签名。接收方收到证书后，用颁发机构公钥验证证书合法性，验证通过则可安全使用证书中的公钥。

防火墙

防火墙

• 控制进出网络的数据包和数据流向
• 提供流量信息的日志和审计
• 隐藏内部IP以及为网络结构细节
• 记录访问工程、包过滤、代理

在出口防火墙上配置ACL（Access Control List，访问控制列表）功能可以组织外部未授权用户访问内部网络。

防火墙三个区域，受保护程度：外网<DMZ<内网
通常把Web服务器置于DMZ区（隔离区、非军事化区）

包过滤防火墙对网络层

一些网络协议

IPsec
工作在网络层，主要用于在两台设备之间建立加密连接，保护数据传输不被窃听和篡改。常用于虚拟专用网络（VPN），让远程办公人员安全访问公司内部网络。

PPP（点对点协议）
位于数据链路层，用于在点对点链路上传输数据，比如拨号上网。它负责建立和维护连接，进行数据封装等，为上层协议提供服务。
PPP的安全协议是CHAP，密文采用MD5加密。

HTTPS
是加密版的 HTTP，在应用层工作。通过加密和身份验证，保护用户访问网站时的数据安全，比如网上购物、银行转账等场景，防止信息泄露。

TLS（传输层安全协议）
工作在传输层，是 HTTPS 的基础安全协议。用于在互联网通信中提供加密和身份验证，确保数据传输的机密性和完整性，广泛应用于各种网络应用。

未分类知识

有效防止SQL注入的手段：

• 对用户输入做关键字过滤
• Web应用防火墙
• 定期扫描系统漏洞并及时修复

入侵检测技术有：专家系统、模型检测、简单匹配

知识产权的分类：

知识产权的特点：

• 无形性
• 双重性
• 确定性
• 独占性
• 地域性
  • 本国法律保护
• 时间性

《计算机软件保护条例》保护对象：

• 软件程序
  • 源程序
  • 目标程序
• 文档

软件著作权无明确规定，由开发者所有。

同样的发明只能授予一项专利

专利权：谁先申请就给谁；同时申请则商量
商标权：谁先申请就给谁；同时申请，谁先使用就给谁；均未使用或者无法证明，先协商；协商不了则抽签

烟草必须注册商标

著作权时间期限

• 永久保护：
  • 普通著作权作品的署名权、修改权、保护作品完整权
  • 软件著作权的署名权、修改权
• 其他作品保护期限是作者终身及其死后50年
• 商标权可以续延长
• 商业秘密权保密期限不确定

普通

专业

数学符号

基本数学符号

希腊字母

微积分符号

集合论符号

逻辑符号

线性代数符号

矩阵和行列式

其中示例中的...为a & b \\ c & d，即

1. &为换列
2. \\为换行

示例：

1
2
3
4
5
6

\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{bmatrix}

其他常见符号

上下标和分数

修饰符号与上下划线

常用组合示例：

• 向量表示： (\vec{v}) 或 (\mathbf{v})
• 平均值： (\bar{x}) 或 (\overline{X})
• 估计值： (\hat{\theta})
• 有向线段： (\overrightarrow{AB})

箭头

关系代数

参考

Not just for exam.

参考：林子雨老师的《数据库系统原理》，以及《软件设计师教程》

写在前面：刻在DNA里的学生选课数据库

本章的所有实例都以学生选课数据库为基础，该数据库包括5个表：

1. 学生表Student(Sno, Sname, Ssex, Sage, Sdept);
2. 课程表Course(Cno, Cname, Cpno, Ccredit);
3. 学生选课表SC(Sno, Cno, Grade);
4. 教师表Teacher(Tno, Tname, Tsex, Tage);
5. 授课表TC(Tno, Cno)。

每一个表的第一列都是主码。

Student

Course

SC

Teacher

TC

数据库概述

关系数据库

关系运算

逻辑表达式

八种关系运算

1. 并（Union）：

   • 符号：
   • 作用：合并两个关系中的元组，去除重复的元组。
   • 表示：，表示关系R和关系S的并集。

2. 交（Intersection）：

   • 符号：
   • 作用：找出两个关系中共有的元组。
   • 表示：，表示关系R和关系S的交集。

3. 差（Difference）：

   • 符号：
   • 作用：从第一个关系中移除与第二个关系中相同的元组。
   • 表示：，表示关系R中不在关系S中的元组。

4. 选择（Selection）：

   • 符号：
   • 作用：从关系中选择满足特定条件的元组（行）。
   • 表示：，表示从关系R中选择满足条件的元组。

5. 投影（Projection）：

   • 符号：
   • 作用：从关系中选择特定的属性列。
   • 表示：，表示从关系R中选择指定的属性列。

6. 连接（Join）：

   • 符号：
   • 作用：将两个关系中满足特定条件的元组合并成一个新的关系。
   • 表示：，表示关系R和关系S的自然连接。
     • 条件连接（θ-连接）：，其中是连接条件，可以是、、等比较运算符，表示基于这些条件的连接。
     • 外连接（Outer Join）：当两个关系中没有完全匹配的元组时，外连接可以返回其中一个关系的所有元组，以及另一个关系中匹配的元组。如果另一个关系中没有匹配的元组，则结果中对应的字段为NULL。
       • 左外连接（Left Outer Join）：返回左关系（R）的所有元组，即使在右关系（S）中没有匹配的元组。如果右关系中没有匹配的元组，则结果中右关系的部分为NULL。
         • 表示： 或者
       • 右外连接（Right Outer Join）：返回右关系（S）的所有元组，即使在左关系（R）中没有匹配的元组。如果左关系中没有匹配的元组，则结果中左关系的部分为NULL。
         • 表示： 或者
       • 全外连接（Full Outer Join）：返回两个关系中任一关系的所有元组，无论另一个关系中是否有匹配的元组。如果另一个关系中没有匹配的元组，则结果中对应的字段为NULL。
         • 表示： 或者

7. 笛卡尔积（Cartesian Product）：

   • 符号：×
   • 作用：将两个关系中的每个元组与另一个关系中的每个元组配对，形成所有可能的组合。
   • 表示：R × S，表示关系R和关系S的笛卡尔积。

8. 除（Division）：

   • 符号：÷
   • 作用：找出能够与第二个关系中所有元组配对的第一个关系中的元组。
   • 表示：R ÷ S，表示关系R中能够与关系S中所有元组配对的元组。

简单理解：

• 选择是取行，投影是取列。
• 自然连接中，如果两个表有相同的列名，那两个表相同列名的列，具体值也要相同，才能配对。所以左右表都有可能会删去一些不匹配的行。
• 左外连接中，左边表的所有行都会被保留，即使右边表中没有匹配的行，此时右边表对应的位置会用NULL填充。
• 右外连接同理。
• 全外连接中，左右两边表的所有行都会被保留，无论是不是匹配，当有一边没有匹配时，那一边对应的位置会用NULL填充。
• 笛卡尔积就是两个表直接不由分说地连， 大小的表A和 大小的的表B，笛卡尔积得到的表C，与连接不同。
• 除如图：

关系运算的sql表示

1. 并（Union）

   1 2 3

   SELECT column_name(s) FROM table1 UNION SELECT column_name(s) FROM table2;

2. 交（Intersection）

   1 2 3

   SELECT column_name(s) FROM table1 INTERSECT SELECT column_name(s) FROM table2;

3. 差（Difference）

   1 2 3

   SELECT column_name(s) FROM table1 EXCEPT SELECT column_name(s) FROM table2;

4. 选择（Selection）

   1 2	SELECT * FROM table WHERE condition;

5. 投影（Projection）

   1	SELECT column_names FROM table;

1. 连接（Join）

• 自然连接（Natural Join）

  1 2	SELECT * FROM table1 NATURAL JOIN table2;

• 条件连接（θ-连接）

  1 2	SELECT * FROM table1 JOIN table2 ON condition;

• 外连接（Outer Join）

  • 左外连接（Left Outer Join）

    1 2	SELECT * FROM table1 LEFT JOIN table2 ON condition;

  • 右外连接（Right Outer Join）

    1 2	SELECT * FROM table1 RIGHT JOIN table2 ON condition;

  • 全外连接（Full Outer Join）

    1 2	SELECT * FROM table1 FULL JOIN table2 ON condition;

1. 笛卡尔积（Cartesian Product）

   1	SELECT * FROM table1, table2;

2. 除（Division）

   1 2 3 4 5

   SELECT column_names FROM table1 WHERE NOT EXISTS ( SELECT * FROM table2 WHERE table1.column = table2.column );

习题

学生数据库

已知数据库

1. 学生表S(Sno, Sname, Ssex, Sage, Sdept);
2. 课程表C(Cno, Cname, Cpno, Ccredit);
3. 学生选课表SC(Sno, Cno, Grade);

完成：

1. 检索选修课程名为“数学”的学生的学号和姓名。
2. 检索至少选修了课程号为 1 和 3 的学生的学号。
3. 检索选修了“操作系统”或“数据库”课程的学生的学号和姓名。
4. 检索年龄在 18～20 之间（含 18 和 20）的女生的学号、姓名及年龄。
5. 检索选修了“数据库”课程的学生的学号、姓名及成绩。
6. 检索选修了全部课程的学生的姓名所在系。
7. 检索选修课程包括 1042 学生所学课程的学生的学号。
8. 检索不选修 2 课程的学生的姓名和所在系。

My answer：
打latex也太难了吧，我直接开始歪歪地手写

关系数据库标准语言SQL

视图在数据字典中保存的是视图定义

关系数据库编程

关系数据库安全和保护

关系数据库的规范化理论

关系模式中可能存在的冗余和异常问题

1. 数据冗余
2. 不一致性
3. 插入异常
4. 删除异常

   函数依赖

   定义

5. 函数依赖：设 为任一给定关系，如果对于 中属性 的每一个值， 中的属性 只有唯一值与之对应，则称 函数决定 ，或 函数依赖于 X，记作 。其中，X 称为决定因素。反之，对于关系 中的属性 和 ，若 不能函数决定 Y，则其符号记作 。
6. 平凡的函数依赖：设 是一个函数依赖，若 ，则称 是一个平凡的函数依赖。
7. 完全函数依赖：设 是一个函数依赖，并且对于任何 ， 都不成立，则称 是一个完全函数依赖，记作。
8. 部分函数依赖：设 是一个函数依赖，但不是完全函数依赖，则称 是一个部分函数依赖，记作。
9. 传递函数依赖：设 是一个关系模式，，，，如果 ，，且 ，，，则称 传递函数依赖于 ，。
10. 候选码：设 为任一给定关系模式， 为其所含的全部属性集合， 为 的子集，若有完全函数依赖 ，则 为 的一个候选码。
11. 主属性和非主属性：包含在任何一个候选码中的属性为主属性，否则为非主属性。

理解

1. 普通函数依赖（X→Y）
   想象你的身份证号码（X）就像一把万能钥匙，它能直接确定你的姓名（Y）、性别、出生地。只要知道身份证号，其他信息都能唯一确定。
   例如：学号→姓名，就像每个学号对应唯一的学生。

2. 平凡依赖 vs 非平凡依赖

   • 平凡就像「已知父亲名字，自然知道家族姓氏」（因为姓氏已经是父亲名字的一部分）
   • 非平凡像「快递单号与包裹信息」，单号能唯一确定收件人的电话（例如单号 SF123456 对应电话 13800001111），但电话不是单号的子集，这也是​​非平凡函数依赖

3. 完全依赖 vs 部分依赖
   完全依赖就像「用完整钥匙开锁」：

   • 成绩完全依赖（学号+课程号）组合，单独学号或课程号都不够

   部分依赖像「用半截钥匙就能开锁」：

   • 如果课程名称只依赖课程号（而课程号是主键的一部分），就是部分依赖

4. 传递依赖（连锁反应）
   学号→系号→系主任，系主任像被「间接遥控」确定。这会导致数据冗余（多个学生重复存储系主任信息）

• 候选码就像「能开所有锁的最小钥匙组合」：

  • 比如（学号+课程号）组合才能确定成绩，单独一个都不行

• 主属性是所有候选码中的零件：

  • 如果候选码是学号，那么学号就是主属性；如果候选码是（学号+身份证号），两者都是主属性

范式

第一范式（1NF）

如果关系模式 的每一个 属性对应的域值都是不可再分的，称模式 属于第一范式，记作 。若数据库模式 中的每个关系模式都是 ，则数据库模式 。

最基本的要求，就是表中的每个属性都不可再分。例如，学生信息表中，每个学生的姓名、年龄、性别等都是不可再分的。

第二范式（2NF）

如果关系模式 ，并且每个非主属性都完全函数依赖于 的码，则 。

不能有部分依赖。例如，在选课表中，学生成绩应该依赖于学号和课程号的组合，而不是单独依赖学号或课程号。

第三范式（3NF）

关系模式 R 中若不存在这样的码 、属性组 及非主属性 ，使得 、 和 成立，则称 。

例如，学生表中的成绩不能依赖于学生的姓名，因为姓名不是码。

Boyce-Codd范式(BCNF)

若 ，而且R中没有任何属性传递函数依赖于R中的码，则关系模式 。

第四范式（4NF）

了解一下就可以了。

第五范式（5NF）

了解一下就可以了。

理解

1. 1NF（基础版）
   要求：每个字段都是最小单元，不能拆。
   错误示范：把「联系电话」写成 “13800001111,13800002222”（应拆分成多行）

2. 2NF（消灭半吊子依赖）
   必须消灭部分依赖。比如选课表中：

   • 错误：把课程名称和成绩都放在同一张表（课程名称只依赖课程号，不依赖学号）

   • 正确：拆分成「选课表（学号+课程号+成绩）」和「课程表（课程号+课程名称）」

3. 3NF（斩断连锁依赖）
   禁止传递依赖。比如学生表里直接存系主任名字：
   • 错误：学生表包含系号→系主任
   • 正确：拆分成「学生表（学号+系号）」和「院系表（系号+系主任）」
4. BCNF（加强版3NF）
   连主属性都不能有传递依赖。举个极端例子：
   • 假设每个老师只教一门课，每门课有多个老师
   • 错误表：（老师ID，课程）主键是老师ID，但课程→教室（课程不是主键）
   • 正确：拆分成「老师-课程表」和「课程-教室表」

举个综合例子（学生选课系统）：
原始混乱表
| 学号 | 姓名 | 课程号 | 课程名 | 成绩 | 系名 | 系主任 |
|—-|—-|—-|—-|—-|—-|—-|
| 001 | 张三 | C01 | 数学 | 90 | 计算机系 | 李主任 |

问题分析：

1. 课程名只依赖课程号（违反2NF）
2. 系主任依赖系名，系名依赖学号（传递依赖，违反3NF）

规范化后：

• 学生表（学号，姓名，系名）3NF

• 课程表（课程号，课程名）2NF

• 选课表（学号，课程号，成绩）2NF

• 院系表（系名，系主任）3NF

这样修改后，更新系主任信息只需要修改院系表中的一个位置，避免了数据冗余和更新异常。

模式分解

习题

2021上半年软考 42题

给定关系R（U,F），其中U={A,B,C,D,E,H}，F={(A→B,B→DH,A→H,C→E)}。关系有（ ），F中（ ）。

问题1：

• [ ] A. 1个候选码A
• [ ] B. 2个候选码A、B
• [x] C. 1个候选码AC
• [ ] D. 2个候选码A、C

问题2：

• [ ] A. 不存在传递依赖，但存在冗余函数依赖
• [ ] B. 既不存在传递依赖，也不存在冗余函数依赖
• [ ] C. 存在传递依赖A→D和A→H，但不存在冗余函数依赖
• [x] D. 存在传递依赖A→D和A→H，并且还存在冗余函数依赖

算法

日期题: datetime

日期差值填空

众所周知，2025 年是完全平方年，因为 。
定义一个年份 是完全平方年当且仅当存在一个正整数 使得 。
今天是 2025 年 3 月 29 日，现在我们想知道距离下一个完全平方年的 1 月 1 日还有几天（即从 2025 年 3 月 29 日 0 时到下次完全平方年的 1 月 1 日 0 时，例如：从 3 月 29 日 0 时到 3 月 30 日 0 时算 1 天）。

1
2
3
4

from datetime import datetime as dt
a=dt(2025,3,29,0,0,0)
b=dt(46**2,1,1,0,0,0)
print((b-a).days)

P10385 [蓝桥杯 2024 省 A] 艺术与篮球

小蓝决定根据日期的笔画数来安排自己的练习。首先，他会将当天的日期按照 YYYYMMDD 的格式
转换成一个 位数，然后将这 位数对应到汉字上，计算这些汉字的总笔画数。如果总笔画数超过 ，他就去练习篮球；如果总笔画数不超过 ，他就去练习书法。
例如，在 年 月 日这天，日期可表示为一个 位数字 ，其转换为汉字是“二零二四零一零一”。日期的总笔画数为 ，因此在这天，小蓝会去练习书法。
以下是汉字的笔画数对照表：

现在，请你帮助小蓝统计一下，在 年 月 日到 年 月 日
这段时间内，小蓝有多少天是在练习篮球？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

from datetime import datetime,timedelta
a=datetime(2000,1,1,0,0,0)
b=datetime(2024,4,13,0,0,0)
c=a
d=timedelta(days=1)
bh=[13,1,2,3,5,4,4,2,2,2]
s=0
def cnt(x,n):
    ret=0
    for i in range(n):
        ret+=bh[x%10]
        x//=10 # 注意python除法
    return ret

while c<=b:
    s+=1 if cnt(c.year,4)+cnt(c.month,2)+cnt(c.day,2)>50 else 0
    c+=d

print(s)

大数/高精度题: decimal

最高位之和

对于正整数 ，设 为 在十进制下的最高非零位的值， 为 在十进制下的最高非零位的值，求所有可能的作为 的值的和。相同的值只计算一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from decimal import Decimal
two=Decimal('2')
five=Decimal('5')
s=set()
def high(x):
    while x>9:
        x//=10
    return x

for i in range(50000):
    try:
        s.add(high(two)*high(five))
        two*=2
        five*=5
        # print(two,five)
    except Exception as e:
        # print(str(e))
        break
res=0
for i in s:
    res+=i
print(res)

对拍

待测程序

待测程序test.cpp

1
2
3
4
5
6
7
8
9

#include<bits/stdc++.h>
using namespace std;
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    //待测程序
    return 0;
}

对拍程序

对拍程序bl.cpp

1
2
3
4
5
6
7
8
9

#include<bits/stdc++.h>
using namespace std;
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output2.txt","w",stdout);
    //待测程序
    return 0;
}

Python简易评测机

没用过，先放一个在这儿
python简易对拍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import os
import random
import subprocess
import time
import filecmp

def test():
    with open("input.txt", "w") as f:
        '''
        生成随机数据，例
        n = random.randint(1, 100)
        f.write(f"{n}\n")
        for _ in range(n):
            l = random.randint(1, 100)
            r = random.randint(1, 100)
            f.write(f"{l} {r}\n")
        '''
    start_time=time.time()
    subprocess.run(["test.exe"], shell=True) # 测试
    print(f"用时{time.time()-start_time:.3f}s")
    subprocess.run(["bl.exe"], shell=True) # 对拍
    return filecmp.cmp("output1.txt", "output2.txt")

random.seed(time.time())
for i in range(100): # 测试数量
    print(f"运行测试例 {i}...")
    if not test():
        print("测试例 {i} 失败")
        exit(0)
print("通过")

参考：https://blog.csdn.net/Mibbp/article/details/124012372