🚧施工中🚧

排序之间的比较

习题

有序的排序

(没好好看题全做错了)
对 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年
• 商标权可以续延长
• 商业秘密权保密期限不确定

普通

专业

数学符号

基本数学符号

希腊字母

微积分符号

集合论符号

逻辑符号

线性代数符号

矩阵和行列式

其他常见符号

上下标和分数

箭头

关系代数

参考

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

算了，寒假里做几道放几道呗

P8740 [蓝桥杯 2021 省 A] 填空问题

题目描述

试题 A：卡片

【问题描述】

小蓝有很多数字卡片，每张卡片上都是数字 到 。

小蓝准备用这些卡片来拼一些数，他想从 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。

小蓝想知道自己能从 拼到多少。

例如，当小蓝有 张卡片，其中 到 各 张，则小蓝可以拼出 到 ，但是拼 时卡片 已经只有一张了，不够拼出 。

现在小蓝手里有 到 的卡片各 张，共 张，请问小蓝可以从 拼到多少?

提示：建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 B：直线

【问题描述】

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。

给定平面上 个整点 ，即横坐标是 到 (包含 和 ) 之间的整数、纵坐标是 到 (包含 和 ) 之间的整数的点。这些点一共确定了 条不同的直线。

给定平面上 个整点 ，即横坐标是 到 (包含 和 ) 之间的整数、纵坐标是 到 (包含 和 ) 之间的整数的点。请问这些点一共确定了多少条不同的直线。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 C ：货物摆放

【问题描述】

小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、 宽、高。

小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆 的货物，满足 。

给定 ，请问有多少种堆放货物的方案满足要求。

例如，当 时，有以下 种方案： 、

请问，当 (注意有 位数字) 时，总共有多少种方案?

提示：建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 D：路径

【问题描述】

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由 个结点组成，依次编号 至 。

对于两个不同的结点 ，如果 和 的差的绝对值大于 ，则两个结点之间没有边相连; 如果 和 的差的绝对值小于等于 ，则两个点之间有一条长度为 和 的最小公倍数的无向边相连。

例如：结点 和结点 之间没有边相连; 结点 和结点 之间有一条无向边，长度为 ; 结点 和结点 之间有一条无向边，长度为 。

请计算，结点 和结点 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 E：回路计数

【问题描述】

蓝桥学院由 栋教学楼组成，教学楼编号 到 。对于两栋教学楼 和 ，当 和 互质时， 和 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路)，请问他有多少种不同的访问方案? 两个访问方案不同是指存在某个 ，小蓝在两个访问方法中访问完教学楼 后访问了不同的教学楼。

提示：建议使用计算机编程解决问题。

解法

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
using ll = long long;
using ull = unsigned long long;
//==================== 1 ====================
void solve1()
{
    int a[10];
    for (int i = 0; i <= 9; i++)
        a[i] = 2021;
    for (int i = 1;; i++)
    {
        for (int j = i; j; j /= 10)
        {
            if (a[j % 10] == 0)
            {
                cout << i - 1 << endl;
                return;
            }
            --a[j % 10];
        }
    }
}
//==================== 2 ====================
int gcd(int x, int y)
{
    return x % y == 0 ? y : gcd(y, x % y);
}
void solve2()
{
    int n = 20, m = 21;
    ull ans = 0ll; // row,col
    for (int a = 1; a < n; a++)
    {
        for (int b = 1; b < m; b++)
        {
            if (gcd(a, b) != 1)
                continue;
            ans += (n - a) * (m - b);
            if (a * 2 <= n && b * 2 <= n)
            {
                ans -= (n - 2 * a) * (m - 2 * b);
            }
        }
    }
    ans *= 2;
    ans += (n + m);
    cout << ans << endl;
}
//==================== 3 ====================
typedef pair<ull, ull> pp;
ull ans3 = 0;
map<pp, bool> mp;
vector<ull> yz; // 因子
void dfs3(pp p, int d)
{
    if (d == yz.size())
    {
        if (!mp[p])
        {
            mp[p] = true;
            ans3++;
        }
        return;
    }
    dfs3(pp(p.first, p.second), d + 1);
    dfs3(pp(p.first * yz[d], p.second), d + 1);
    dfs3(pp(p.first, p.second * yz[d]), d + 1);
}
void solve3()
{
    ull n = 2021041820210418;
    for (int i = 2; i <= n;)
    {
        if (n % i == 0)
        {
            // cout<<i<<',';
            yz.push_back(i);
            n /= i;
        }
        else
        {
            i++;
        }
    }
    // 2,3,3,3,17,131,2857,5882353
    dfs3(pp(1, 1), 0);
    cout << ans3 << endl;
}
//==================== 4 ====================
typedef pair<int, int> pint;
void solve4()
{
    int n = 2021;
    vector<vector<pint>> g(2022);
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= i + 21 && j <= n; j++)
        {
            int w = i * j / gcd(i, j);
            g[i].push_back(pint(w, j));
            g[j].push_back(pint(w, i));
        }
    }
    // dijsktra
    const int inf = INT_MAX;
    vector<int> dis(n + 1, inf);
    vector<bool> vis(n + 1, false);
    dis[1] = 0;
    priority_queue<pint, vector<pint>, greater<>> pq;
    pq.push(pint(0, 1));
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (!vis[u])
        {
            vis[u] = true;
            for (auto [w, v] : g[u])
            {
                if (dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    if (!vis[v])
                        pq.push(pint(dis[v], v));
                }
            }
        }
    }
    cout << dis[2021] << endl;
}
//==================== 5 ====================
ull ans5;
int ok;
bool have[22][22];
ull f[1 << 21][22]; // 走的序列,到下一个点
void solve5()
{
    for (int i = 1; i < 21; i++)
    {
        for (int j = i + 1; j <= 21; j++)
        {
            if (gcd(i, j) == 1)
            {
                have[i][j] = have[j][i] = true;
            }
        }
    }
    ok =(1 << 21)-1;// 2,097,151
    f[1][1]=1;
    for (int c = 1; c <= ok; c++)
    {
        for (int i = 1; i <= 21; i++)
        {
            if (c & (1 << (i - 1)))
                for (int j = 1; j <= 21; j++)
                {
                    if (!(c & (1 << (j - 1))) && have[i][j])
                        f[c | (1 << (j - 1))][j] += f[c][i];
                }
        }
    }
    for (int i = 1; i <= 21; i++)
    {
        ans5 += f[ok][i];
    }
    cout << ans5 << endl;
}
//==================== answer ====================
signed main()
{
    string ans[] = {
        "3181",                 // 双引号中替换为 A 题的答案
        "40257",                // 双引号中替换为 B 题的答案
        "2430",                 // 双引号中替换为 C 题的答案
        "10266837",             // 双引号中替换为 D 题的答案
        "881012367360", // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}

P8742 [蓝桥杯 2021 省 AB] 砝码称重

题目描述

你有一架天平和 个砝码, 这 个砝码重量依次是 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 。

第二行包含 个整数: 。

输出格式

输出一个整数代表答案。

输入输出样例 #1

输入 #1

1
2

3
1 4 6

输出 #1

1

10

说明/提示

【样例说明】

能称出的 10 种重量是: 。

【评测用例规模与约定】

对于 的评测用例, 。

对于所有评测用例, 个砝码总重不超过 。

蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。

解法

01背包

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

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int f[101][N];
signed main()
{
    int n, w, sum = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w);
        sum += w;
        for (int j = sum; j; j--)
            if (f[i - 1][j])
                f[i][j] = f[i][abs(j - w)] = f[i][j + w] = 1;
        f[i][w] = 1;
    }
    int ans = 0;
    for (int j = 1; j <= sum; j++)
        ans += f[n][j];
    printf("%d\n", ans);
    return 0;
}

P8743 [蓝桥杯 2021 省 A] 异或数列

题目描述

Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 和 , 有一个给定的长度为 的公共数列 。

Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种:

选项 1: 从数列中选一个 给 Alice 的数异或上, 或者说令 变为 。（其中 表示按位异或）

选项 2: 从数列中选一个 给 Bob 的数异或上，或者说令 变为 。

每个数 都只能用一次, 当所有 均被使用后（ 轮后）游戏结束。游戏结束时, 拥有的数比较大的一方获胜，如果双方数值相同，即为平手。

现在双方都足够聪明，都采用最优策略，请问谁能获胜?

输入格式

每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 ，表示询问数。

接下来 行每行包含一组询问。其中第 行的第一个整数 表示数列长度，随后 个整数 表示数列中的每个数。

输出格式

输出 行，依次对应每组询问的答案。

每行包含一个整数 、 或 分别表示 Alice 胜、平局或败。

输入输出样例 #1

输入 #1

1
2
3
4
5

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

输出 #1

1
2
3
4

1
0
1
1

说明/提示

对于所有评测用例, 。

蓝桥杯 2021 第一轮省赛 A 组 G 题。

解法

转换成二进制，对于某一位，如果它是1，则反转这一位答案。0对答案无影响。奇数个1异或得1，偶数个1异或得0

• 当1有偶数个时，偶数=偶数+偶数，这一位平手。
• 当1有奇数个时，奇数=奇数+偶数，两人都想办法获得奇数个1。
  • 只有一个1，Alice直接选，Alice win
  • 当0有偶数个，两人相抵，Alice win
  • 当0有奇数个，Bob选一个0，反转局面，Bob win

例:1 1 1 0 0 0
Alice:1
Bob:0(反转先手)
Alice:0
Bob:0
Alice:1(被迫)
Bob:Alice 1
Bob win

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
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int t, n, x, cnt[22];
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &x);
            for (int b = 0; x; b++)
            {
                if (x & 1)
                    cnt[b]++;
                x >>= 1;
            }
        }
        int win = 0;
        for (int i = 20; i >= 0; i--)
        {
            if (cnt[i] & 1)
            {
                if (cnt[i] == 1)
                    win = 1;
                else
                    win = n & 1 ? 1 : -1; // 偶数个0Alice win
                break;
            }
        }
        printf("%d\n", win);
    }
    return 0;
}
/*

*/