Ender's Blog

Kruskal 学习笔记 最小生成树 在无向图中，连通且无环的图称为树(Tree)。给定无向图G=(V,E)G=(V,E)G=(V,E)，连接GGG中所有点，且边集是EEE的子集的树称为GGG的生成树(Spanning Tree)，而权值最小的生成树称为最小生成树(Minimal Spanning Tree , MST)。s 例题:Luogu P3366 【模板】最小生成树 Kruskal 算法 ###介绍 Kruskal算法由Kruskal发明，用于构造MST，它易于编写，而且效率很高。该算法的基本思想是从大到小加入边，是个贪心算法。 证明 思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n−1n-1n−1 条边，即形成了一棵树。 证明：使用归纳法，证明任何时候 K 算法选择的边集都被某棵 MST 所包含。 基础：对于算法刚开始时，显然成立（最小生成树存在）。 归纳：假设某时刻成立，当前边集为 FFF ，令 TTT 为这棵 MST，考虑下一条加入的边 eee 。 如果 eee 属于 TTT ，那么成 ...

OI中的花样排序方法 排序算法多种多样 ，性质也大多不同。 选择排序 时间复杂度：O(n2)O(n^2)O(n2) ，不稳定排序 12345678910111213void selectionSort(int* a,int n){ //选择排序 for(int i = 1;i < n;i++){ //最后一位不用判断 int ith = i; //ith记录当前位置后最小数的位置 for(int j = i + 1;j <= n;j++){ if(a[j] < a[ith]) ith = j; //循环寻找当前位置后最小的数 } int t = a[i]; a[i] = a[ith]; a[ith] = t; //将第i个小的数与位置为i的数互换 }} 冒泡排序 时间复杂度：O(n2)O(n^2)O(n2) ，稳定排序 1234567891011121314void bubbleSort(int* a,int n){ //冒泡排序 bool flag = true; whil ...

线性代数(Linear Algebra)学习笔记 向量(Vectors) 在空间中，向量可以表示为一个有方向有长短的箭头。（数学中的向量为自由向量，是没有起点的。在线性代数中，通常使向量的起点为原点，此图以二维为例） 在运算时，因为线性代数中向量以原点为起点，所以用中括号扩起来的竖着写的坐标表示一个从原点指向终点(a,b)的向量。（以二维为例） [ab]\begin{bmatrix} a\\ b \end{bmatrix} [ab​] 这里的aaa与bbb也可以表示为从原点向xxx轴正方向移动aaa格，再向yyy轴正方向移动bbb格（多维向量同理）。 向量的基础运算 向量加法(Vector Addition) 两个向量之间的加法遵从三角形法则 ，即将一个向量u⃗\vec{u}u的起点移到另一个向量v⃗\vec{v}v的终点上。两向量只和的新向量的起点即为向量v⃗\vec{v}v的起点，新向量的终点即为向量u⃗\vec{u}u的终点，表示为u⃗\vec{u}u + v⃗\vec{v}v = w⃗\vec{w}w。（图中以二维为例） 或者，我们将u⃗\vec{u}u表示为[ab]\be ...

Java学习笔记-1 受Minecraft Java版的影响，一直想学Java。最近终于开始着手学习，在博客里记录下来学习历程。 安装编程环境 在官网下载安装jdk，配置环境变量，安装eclipse，汉化eclipse。 HelloWorld 1234567891011121314package xin.ender.helloworld; // 包名public class HelloWorld { // 定义公共类 public static void main(String[] args) { // main主函数 // public告知其他类可以访问这个函数 // static告知编译器这个函数是一个静态函数 // void表明main函数返回值为无类型 // String[] args定义一个字符串数组"args" System.out.print("HelloWorld"); //输出到控制台 }}

本文介绍博主在OI中常见代码风格，也用来规范自己。 本文内容自发稿开始保证实施 Ender’s Code Style for OI 概览 可以使用万能头文件#include<bits/stdc++.h> 使用using namespace std;时，应放在#include下一行。 结构体应放于所有函数之前，main函数应放于程序末尾。 缩进 所有同级命令均应为等长缩放长度，所有被包含的命令应使用4个空格或等长Tab缩进。 大括号 对于所有需要大括号的命令和函数，左大括号不应换行，左边必须有一个空格；右大括号与命令应为等长缩进,例： 123456789101112// 结构体struct Node { // do something...};// 其他,以if为例if(condition) { // do something...}else { // do something...} 对于所有几乎只包含一条return语句的函数，右大括号可以不换行，其余均应换行，例： 123456bool cmp ...

P1219八皇后学习笔记 问题描述 检查一个如下的6x6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。 上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：行号 1 2 3 4 5 6　列号 2 4 6 1 3 5 这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。 输入 一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。 输出 前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。 感想 这是一道经典回溯题，然而博主代码能力还是有点欠缺… 经过攻读紫书之后，终于弄会这道题了。 思路 我们不难发现，从左上到右下的对角线的横纵坐标的差是一样的，从右上到左下的对角线的横纵坐标的和是一样的。 所以可以定义一个二维数组vis[30][3]来记录哪些线不能放置皇后。int vis[30][3]判断条件：!v ...