CSP – S/J 2019 第一轮 游记

0 序

又开始了啊,新的一轮

大家或多或少的开始了新的旅程了呢

这两天和一位内地的 CSPer 聊了一些和 CSP 无关的东西,感觉想通了不少事情

今年到考场都跟咸鱼一样了

依稀记得去年监考老师不讲理过了 3min 还不发卷子

「老师,已经过去了三分钟了,怎么还不发卷子」 xqmmcqs 大佬突然站起来询问道

感觉自己就是从这个时候开始,老师这个概念已经从我心中的神坛跌了下去

我只会去尊重有理有据教育我们的老师的

或许是 Oi 学久了,某些思想竟以变得如此激进了

前文说的有点杂了,还是开始正题吧

注:为了笔者和大家的习惯,下文统称 CSPer 和 Oier 为 Oier

注:文中出现人物多使用其常见 id 称呼,没有或我不知道常见 id 的使用姓名拼音首字母简称,您可以在评论去提出更改或者匿名请求,请求处理完后会删除相应评论

Continue reading “CSP – S/J 2019 第一轮 游记”

平面向量学习笔记(大概?)

这篇文章咕了好久了,鬼知道为什么

本篇文章的目的只是为了更方便的学习 P2742 【模板】二维凸包 这道题目,如果有不详细或者错误之处,往各位大佬们多多指出

1 定义

向量:有大小,有方向 的量是向量,然而数学中研究的向量通常是 自由向量,即起点终点并不重要

向量的模:向量的长度被称为向量的模

零向量:模为 $0$ 的向量,零向量方向任意,记为 $\vec 0$ 或 $\mathbf 0$

单位向量:模为 $1$ 的向量是其在该方向的单位向量

Continue reading “平面向量学习笔记(大概?)”

中山纪念中学 Day 21 2019.08.21 解题报告 & 题解

T1 数字 Number

1 记录

考场上疯狂肝这道题目,结果少个特判

2 Solution

很明显,$n$ 只有三种情况

  1. $n$ 就是结尾
  2. 中间有一段是一个数字,这个情况 $O(\log^3(n))$ 枚举即可
  3. 中间切一刀,左边是一个不完整的数字,右边也是一个不完整的数字,枚举中间即可

所以直接暴力即可

所以这是一道毒瘤模拟题目

Continue reading “中山纪念中学 Day 21 2019.08.21 解题报告 & 题解”

中山纪念中学 Day 10 2019.08.10 解题报告 & 题解

T1 数学题 Math

1 记录

真就数学题目呗

考场企图推正解,结果最后只推出了 60 分的,哭了

正解参见 欧几里得算法的应用.pdf

这是真的类欧几里得算法

Continue reading “中山纪念中学 Day 10 2019.08.10 解题报告 & 题解”

中山纪念中学 Day 4 2019.08.04 解题报告 & 题解

T1 锻造 Forging

1 记录

考场上的时候总觉得题目非常的奇妙

因为一直循环下去不就完了吗?

直到后来我的同桌给我指点,原来把 DP 式子当方程解可以了

还是太菜啊

Continue reading “中山纪念中学 Day 4 2019.08.04 解题报告 & 题解”

Kruskal 重构树入门 – 「NOI 2018」 归程

Kruskal 重构树

Kruskal 最小/大生成树 — Luogu P1967 货车运输 一文中,介绍了 Kruskal 算法是如何生成最小生成树的

如果将两个联通块联通的不是边而是点呢?

这就是 Kruskal 重构树

具体来说就是,我们原来是通过一条边将两个联通块相连接的,现在我们新建立一个点,将这两个联通块的根节点连接到这个点上,原来的边权就是这个新建节点的点权,这样执行下来,我们会得到一棵新的树,这个树有以下两个特征

  • 没有 边权
  • 保证是一个堆
    • 大根堆还是小根堆要看 原来 生成的是最小还是最大生成树
    • 因为我们保证边权的单调性,故后期新建节点的点权也是单调的,故新树是一个堆
Continue reading “Kruskal 重构树入门 – 「NOI 2018」 归程”

Kruskal 最小/大生成树 — Luogu P1967 货车运输

1 最小生成树

1.1 生成树

无向图 $G$ 的生成树,就是具有图 $G$ 的所有顶点,但是边数最小的联通子图

更加详细的定义: Wikipedia – 生成树

1.2 最小生成树

带权联通无向图的总权值最小的生成树

更加详细的定义: Wikipedia – 最小生成树

1.3 求解算法

  • Kruskal 算法
  • Prim 算法
Continue reading “Kruskal 最小/大生成树 — Luogu P1967 货车运输”