数学符号

基本数学符号

希腊字母

微积分符号

集合论符号

逻辑符号

线性代数符号

矩阵和行列式

其他常见符号

上下标和分数

箭头

关系代数

参考

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;
}
/*

*/

P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟

题目描述

对于一棵多叉树，我们可以通过“左孩子右兄弟”表示法，将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。

给定一棵包含 个结点的多叉树，结点从 至 编号，其中 号结点是根，每个结点的父结点的编号比自己的编号小。请你计算其通过”左孩子右兄弟”表示法转化成的二叉树，高度最高是多少。（只有根结点这一个结点的树高度为 ）

例如如下的多叉树：

可能有以下 种 (这里只列出 种, 并不是全部) 不同的 “左孩子右兄弟” 表示:

其中最后一种高度最高, 为 。

输入格式

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

以下 行, 每行包含一个整数, 依次表示 至 号结点的父结点编号。

输出格式

输出一个整数表示答案。

输入输出样例 #1

输入 #1

1
2
3
4
5

5
1
1
1
2

输出 #1

1

4

说明/提示

对于 的评测用例，;

对于所有评测用例， 。

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

解法

dfs
最大答案=孩子数+孩子中的最大答案

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

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
vector<vector<int>> child(N);
int dfs(int u)
{
    int ret = 0;
    for (int v : child[u])
        ret = max(ret, dfs(v));
    return ret + child[u].size();
}
signed main()
{
    scanf("%d", &n);
    int r;
    for (int i = 2; i <= n; i++)
    {
        scanf("%d", &r);
        child[r].push_back(i);
    }
    printf("%d", dfs(1));
    return 0;
}

P8745 [蓝桥杯 2021 省 AB] 括号序列

题目描述

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。

例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()() 、()(())、(())()、(()()) 和 ((()))。

输入格式

输入一行包含一个字符串 ，表示给定的括号序列，序列中只有左括号和右括号。

输出格式

输出一个整数表示答案，答案可能很大，请输出答案除以 （即 ）的余数。

输入输出样例 #1

输入 #1

1

((()

输出 #1

1

5

说明/提示

对于 的评测用例，。

对于所有评测用例，。

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

解法

python生成代码

1
2
3
4
5
6
7
8

a=['(',')']
from random import randint
def f():
    l=randint(5,12)
    for i in range(l):
        print(a[randint(0,1)],end='')
    print()
f()

一雪2024的前耻，今年报销了300大洋报名费！慢慢复盘。

考时黑客不会优化，最后一题只写完了拖布，拓步，托……反正就是那个什么什么排序啦！目前黑客已经优化，最后三题还没复盘。

洛谷评测

注意事项

• 这里的题解偷懒了，实际上考试时不要用ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);，直接用scanf和printf最保险
• 注意数据范围，注意用long long或者unsigned long long的情况
• 一定记得return 0
• 注意devcpp开栈和c++版本
• 某些特殊的填空题可以用python写，改天新开一篇博文写
• 写一题交一题
• 拿不要死磕一道题，尽可能每道题都暴力骗到分。实在不行直接输出样例。

P12138 [蓝桥杯 2025 省 A] 寻找质数

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

如果一个正整数只能被 和它本身两个数整除，就称为一个质数。最小的几个质数依次是

请问，第 个质数是多少？

输入格式

无

输出格式

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

解法

get 5/5分
暴力就好

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

int cnt = 1, n = 1;
while (cnt < 2025)
{
    n += 2;
    bool prime = true;
    for (int i = 3; i < n; i += 2)
    {
        if (n % i == 0)
        {
            prime = false;
            break;
        }
    }
    if (prime)
    {
        ++cnt;
    }
}
cout << n << endl;

P12139 [蓝桥杯 2025 省 A] 黑白棋

题目描述

小蓝最近迷上了一款名为“黑白棋填充”的游戏。该游戏在一个方形网格棋盘上进行，其中部分格子已经填有黑色或白色的棋子，而其他格子为空，等待玩家填入棋子。

游戏规则是，玩家需要按照以下规则填满整个棋盘，才能算作胜利：

1. 黑白棋子数量均等：
   在每一行和每一列中，黑色棋子和白色棋子的数量必须相等。
2. 相邻棋子限制：
   在棋盘的任何一行或一列中，不能有超过两个相同颜色的棋子连续排列（即不允许出现“黑黑黑”或“白白白”的情况）。
3. 行列唯一性：
   每一行的棋子排列方式必须是唯一的，不能与棋盘中的任何其他行完全相同。
   每一列的棋子排列方式必须是唯一的，不能与棋盘中的任何其他列完全相同。
   行与列之间的棋子排列不作比较，即行可以与列相同，无需满足行列间的唯一性。

现在有一个 的棋盘，如上图所示，其中部分格子已填入棋子（黑色或白色），其余格子需要你填充，题目保证有唯一解。

请给出唯一的正确解，并按照以下格式输出答案：

• 黑色棋子用 表示，白色棋子用 表示。
• 从左到右、从上到下的顺序，依次遍历棋盘上的所有格子，并将这些值拼接成一个长度为 的字符串。

例如，假设最终填充完成后的棋盘如下（仅为示例，并非真实答案）：

1
2
3
4
5
6

1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 1 1 1 1

输入格式

无

输出格式

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

解法

get 5/5分
考试时第一反应是打excel表格，好吧。其实dfs稍微剪枝一下就可以。狠狠暴力！忘情地暴力！

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