0 AK Monster

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 25w+

初赛知识点汇总(阶段性完结

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

2020-10-10 20:46:44

飞行路线思路及代码

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

2020-10-10 20:43:44

架设电话线 题解

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

2020-08-22 13:05:57

浅谈 LCA

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

2020-08-22 13:04:29

浅谈 Tarjan 算法之强连通分量(危

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

2020-08-22 13:02:27

浅谈 拓扑排序

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

2020-08-07 11:53:12

关于动态规划

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

2020-08-05 11:11:20

欧几里得算法

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

2020-08-03 11:21:22

食物链 题解

题目描述动物王国中有三类动物 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 。

2020-08-02 20:36:26

浅谈 线段树

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

2020-08-02 16:27:00

浅谈 倍增

二分的逆用?不不不,兔子是oier的信仰

2020-08-02 14:58:29

Meetings S 题解

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

2020-08-01 21:03:39

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

集中一点,登峰造极!

2020-08-01 18:48:37

排序模板

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

2020-08-01 18:46:36

Huffman 树

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

2020-08-01 16:53:40

2020.7.31 模拟赛 题解

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

2020-08-01 16:50:01

浅谈 最短路

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

2020-08-01 16:48:18

图论基础

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

2020-07-28 21:14:04

2020.7.28 模拟赛 题解

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

2020-07-28 19:27:12

树状数组 题目集合

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

2020-07-27 20:54:57

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。