Stardust_AK的博客

原创 博客已搬迁

Rt.我不会删blog的，这个blog就留做纪念吧新blog

原创 最优贸易 题解

题目链接题目描述C 国有 nnn 个大城市和 mmm 条道路，每条道路连接这 nnn 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 mmm 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 111 条。C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决

原创 2020.10.08 模拟赛 题解

考试题解。。。

原创 牛客 2020.10.20 TG 前两题

NK TG系列

原创 2020.10.16 小球问题

原创 数论 初步

0x01 整除概念： 设 a,b∈Za, b \in \mathbb Za,b∈Z 且 a≠0a \neq 0a​=0，如果 ∃q∈Z\exists q \in \mathbb Z∃q∈Z，使得 a×q=ba \times q = ba×q=b，则 bbb 能被 aaa 整除，记为 a∣ba \mid ba∣b。性质：1. 传递性：如果 a∣ba \mid ba∣b 且 b∣cb \mid cb∣c，则 a∣ca \mid ca∣c。2. 若a∣ba \mid ba∣b 且 a∣ca \mid

原创 初赛知识点汇总（阶段性完结

持续更新。又是一篇互动贴，大家有些什么冷门知识可以留言我会整理。（注：初赛还有3天大家抓紧时间。part1 计算机史 Q1.1 第一台电子计算机的诞生 1946年2月14日：（情人节哦） ENIAC，世界上第一台数字式电子计算机， 同时也是电子管计算机。 Q1.2 第一台具有存储程序功能的计算机：EDVAC。由冯·诺依曼依据存储程序的工作原理设计。含有运算器、控制器、存储器、输入设备和输出设备五部分。同 ENIAC 相比，EDVAC 方案有两个重大改进：（1）采用了二进制。（2）首次提出

原创 飞行路线思路及代码

DP直接考虑 dpdpdp 。定义 dp[i][j]dp[i][j]dp[i][j] 表示到 iii 这个点用 jjj 次优惠的最短路径。对于 iii 这个点，只有用与不用优惠两种情况，由此可得状态转移方程：（其中 uuu 表示上一个点。int val = min(dp[u][j] + w, dp[u][j + 1]);dp[u][j] = min(dp[u][j], val);然后SPFA边跑边进行更新。但这样会超时，只有 909090 分（有人玄学Dijk在 potatopotatopo

原创 架设电话线 题解

题目描述原题来自：USACO 2008 Jan. Silver在郊区有 NNN 座通信基站，PPP 条双向电缆，第 iii 条电缆连接基站 AiA_iAi​ 和 BiB_iBi​。特别地，111 号基站是通信公司的总站，NNN 号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第 iii 条电缆需要花费 LiL_iLi​。电话公司正在举行优惠活动。农场主可以指定一条从 111 号基站到 NNN 号基站的路径，并指定路径上不超过 KKK 条电缆，由电话公司免费提供升级服务。农场主只需要支

原创 浅谈 LCA

lca(Lowest Common Ancestors)对于有根树 T 的两个结点 u、v，最近公共祖先 lca(u,v) 表示一个结点 x，满足 x 是 u 和 v 的祖先且 x 的深度尽可能大。显然，一个节点也可以是它自己的祖先。

原创 浅谈 Tarjan 算法之强连通分量（危

果然老师们都只看标签拉题。。。2020.8.19新初二的题集中出现了一道题目（现已除名），叫做Running In The Sky。OJ上叫绮丽的天空。发现需要处理环，然后通过一些神奇的渠道了解到有个东西叫缩点。紧接着搜了一下缩点，发现了 Tarjan 算法。然后又翻了翻算法竞赛，于是一去不复返……

原创 浅谈 拓扑排序

对一个有向无环图 $DAG$ $(Directed Acyclic Graph)$ 进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点 $u$ 和 $v$，若边 $<u,v>∈E(G)$，则 $u$ 在线性序列中出现在 $v$ 之前。通常，这样的线性序列称为满足拓扑次序 $(Topological Order)$ 的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

原创 关于动态规划

动态规划（Dynamic Programming，DP） 是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼 （R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

原创 欧几里得算法

欧几里得算法，模运算，费马小定理，乘法逆元，不定方程，模线性方程

原创 食物链 题解

题目描述动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述：第一种说法是 1 X Y，表示 X 和 Y 是同类。第二种说法是2 X Y，表示 X 吃 Y 。

原创 浅谈 线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

原创 浅谈 倍增

二分的逆用？不不不，兔子是oier的信仰

原创 Meetings S 题解

题目描述有两个牛棚位于一维数轴上的点 0 和 L 处。同时有 N头奶牛位于数轴上不同的位置（将牛棚和奶牛看作点）。每头奶牛 i 初始时位于某个位置 xi，并朝着正向或负向以一个单位每秒的速度移动，用一个等于 1 或 −1 的整数 di​ 表示。每头奶牛还拥有一个在范围 [1,10^3] 内的重量。所有奶牛始终以恒定的速度移动，直到以下事件之一发生：……

原创 QBXT 提高组储备营 2020.夏 游记

集中一点，登峰造极！

原创 排序模板

二路归并排序冒泡排序快速排序堆排序桶排序选择排序

原创 Huffman 树

命题描述对于一个字符串，我们需要将它的每一个字符进行二进制编码（同一个字符可能会在字符串中出现多次。我们规定：1）相同的字符二进制编码相同。2）且每一个字符的二进制编码不是其他的任意一个字符的二进制编码的前缀（eg.假设a的编码为10，则其他字符的编码前2位一定不为10。并找出最优的编码方式使整个字符串的二进制编码长度最短，求出这个最短长度。

原创 2020.7.31 模拟赛 题解

T1 营救T2 关系网络T3 寻找道路

原创 浅谈 最短路

最短路问题（short-path problem）：最短路问题是图论研究中的一个经典算法问题，指在寻找图（由结点和路径组成的）中两结点之间的最短路径。

原创 图论基础

突破极限，一旦放弃了就意味着结束，说不定身体里还隐藏着连自己都没有察觉到的力量，不要被所谓的极限所禁锢。

原创 2020.7.28 模拟赛 题解

心是人的原动力，心的强大是没有边际的，集中一点，登峰造极。

原创 树状数组 题目集合

T1 冒泡排序T2 校门外的树T3 数星星T4 加法

原创 浅谈 树状数组

树状数组，即 Binary Indexed Tree (B.I.T)， 通常用于解决区间查询，单点修改。

转载 2020.7.24 模拟赛 T4

T4 数三角

原创 2020.7.24 模拟赛

T1 字符串的展开T2 作业调度方案T3 火柴棒等式

原创 堆 题目集合

所有登峰造极之人最终都会抵达同一个终点，哪怕时代变迁，哪怕所经历的路途千差万别，他们最终都会抵达同样的终点。

原创 浅谈 STL

简介STL是Standard Template Library的简称，中文名标准模板库，从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL是C++的一部分，因此不用安装额外的库文件。---------来自《百度百科》

原创 2020.7.19 区间dp阶段测试

打崩了……事先说明，今天没有很在状态，所以题解就直接写在代码注释里的，非常抱歉

原创 求权值的积最小 题解

题目描述给定 nnn 个点的带权有向图，求从 111 到 nnn 的路径中边权之积最小的简单路径。

原创 飞行路线 题解

题目描述Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 nnn 个城市设有业务，设这些城市分别标记为 000 到 n−1n−1n−1，一共有 mmm 种航线，每种航线连接两个城市，并且航线有一定的价格。Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 kkk 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

原创 最佳牛围栏 题解

题目描述农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。输入格式第一行输入整数 N 和 F ，数据间用空格隔开。接下来 N 行，每行输出一个整数，第i+1行输出的整数代表，第i片区域内包含的牛的数目。输出格式

原创 乌龟棋 题解

题目描述原题目戳这里小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行 NNN 个格子，每个格子上一个分数（非负整数）。棋盘第 111 格是唯一的起点，第 NNN 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中 MMM 张爬行卡片，分成 444 种不同的类型（ MMM 张卡片中不一定包含所有 444 种类型的卡片，见样例），每种类型的卡片上分别标有 1,2,3,41, 2, 3, 41,2,3,4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数

原创 木棒 题解

直接上题。。。题目描述乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。输入格式输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。输出格式为每组数据，分别输出原始木棒的可

原创 浅谈 并查集

作者：曾经呢，我还是个蒟蒻现在也是，一不小心翻到了这个好像很高级的东西。于是，就学了。。。并查集首先，谁能告诉我这是个啥？？语文老师说，有个古文里的词不会的时候，可以尝试拆开组词。我们类比一下这个方法，并查集其实就是可以完成合并，查找操作的集合嘛。Emmmm……没懂？好叭，我去问问度娘。。。

原创 下一个序列 题解

题目描述对于这个问题，你要写一个程序，这个程序读入一个大于零的十进制的数字（这个数字可能非常的大），输出下一个比它大的一个序列（原数字各个位上的数字重新排列的序列，同样也是十进制），例如： 123->132 279134399742->279134423799有可能存在某数字不存在这样的下一个序列，例如： 987

原创 家庭作业 题解

小编：真是一道有趣的题