2.8k 字 3 分钟

对于规模较大的题目，有的时候，普通 DijkstraDijkstraDijkstra 可能因为时间复杂度太高而被卡成 TLETLETLE 此时就需要使用优先队列优化的 DijkstraDijkstraDijkstra 算法来解决 对于单到多的最短路径，跑一遍 DijkstraDijkstraDijkstra 可以出来，但是如果是反向的呢？ 不妨转变一下思路，多到单的最短路径，不就相当于将单向图的所有边的方向 reversereversereverse 一下，反向建图之后跑一遍单到多的 DijkstraDijkstraDijkstra 嘛，由此可以提出反向建图的思想 # 例题 #...
2.9k 字 3 分钟

# 基础 Dijkstra 算法 # 题目背景 给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 # 输入格式 第一行包含三个整数 n,m,sn,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。 接下来 mmm 行每行包含三个整数 u,v,wu,v,wu,v,w，表示一条 u→vu \to vu→v 的，长度为 www 的边。 # 输出格式 输出一行 nnn 个整数，第 iii 个表示 sss 到第 iii 个点的最短路径，若不能到达则输出 231−12^{31}-1231−1。 # 数据范围 对于 100%100\%100% 的数据：1≤n≤5001...
553 字 1 分钟

# 同余 两个整数 a,ba, ba,b，如果(a−b)%m=0(a - b) \% m = 0(a−b)%m=0，则称 a、ba、ba、b 对于模 mmm 同余，记作 a≡b(mod m)a ≡ b(mod~m)a≡b(mod m)，读作：aaa 同余于 bbb 模 mmm a≡b(moda ≡ b(moda≡b(mod m)m)m) →\to→ (a−b)(a - b)(a−b) %\%% m==0m == 0m==0 # 何谓 "逆元"？ 在取模的条件下，除以一个数等于乘以这个数的乘法逆元 x/2%107≡x∗54%107x /...
414 字 1 分钟

# 题目描述 给定 nnn 组 ai,bi,pia_i,b_i,p_iai​,bi​,pi​，对于每组数据，求出 aibia_i ^ {b_i}aibi​​ modmodmod pip_ipi​ 的值 # 算法思路 对于数 aibia_i ^ {b_i}aibi​​ modmodmod pip_ipi​ 有，bib_ibi​ 可以拆成二进制表示 以 454^545 modmodmod 101010 为例 555 的二进制表示为 101101101 45=420∗422\Large\color{red}{4^5 = 4^{2^0} *...
3.7k 字 3 分钟

# 小苯的计算器 (B 组、C 组) 水题 给你两个数 aaa，bbb，输出 a=k*b+c python123456789t = int(input())while True: if t == 0: break (a, b) = list(map(int, input().split())) print("{}={}*{}+{}".format(a, a // b, b, a - a // b * b)) t -=...
1.8k 字 2 分钟

参考连接传送门 # 什么是树状数组？ 结构为树形结构的数组，与二叉树结构有些类似 二叉树结构示意图： 树状数组结构示意图： # 可以解决的问题 可以解决大部分区间修改以及查询问题 单点修改，单点查询 区间修改，单点查询 区间查询，区间修改 # 相较线段树，树状数组的优缺点 优点：修改和查询操作复杂度于线段树一样都是 logNlogNlogN，但是常数比线段树小，并且实现简单 缺点：扩展性弱，线段树能解决的问题，树状数组不一定能解决 # 前置知识 - lowbit (x) 运算 如何计算一个非负整数 nnn 在二进制下的最低为 111 及其后面的 000...
2k 字 2 分钟

# B # 题意 对于给定方程 (d + x) % q[t] == r[t] ，已知 d,qt,rtd,q_t,r_td,qt​,rt​，求 d+xd+xd+x # 题解 方程等价于： d + x = k * q[t] + r[t] x = k * q[t] + r[t] - d 因为 x≥0x \ge 0x≥0，所以可以得到 k⋅q[t]+r[t]−d≥0k · q[t] + r[t] - d \ge 0 k⋅q[t]+r[t]−d≥0 等价于 k≥d−r[t]q[t]m,minn(k)=⌈d−r[t]q[t]⌉k \ge \frac{d -...
1.7k 字 2 分钟

# 关系模型的数据结构 # 关系 关系模型的数据结构是规范化的二维表，亦称关系 每个表（关系）有唯一的名字。 关系数据库是表的集合，即关系的集合 # 关系代数 # 域 一组具有相同数据类型的值的集合 空值是所有可能的域的一个取值 # 笛卡尔积 例如：D1={′A′,′B′},D2={′a′,′b′}D_1= \{ 'A', 'B' \},D_2= \{ 'a','b'...