zhanyeye's learning log

蒜头君生活的宇宙有 n 个星球，有 m 条虫洞。蒜头君发明了时光机，利用虫洞进行时光旅行。这 m 条虫洞，第 i条虫洞能实现星球 a_i 到 b_i 的单向旅行。蒜头君发明的时光机不稳定，通过第 i 条虫洞能够使得时间前进或者倒退 c_i（c_i≥0 表示前进，c_i < 0 表示倒退）。

如果通过时光机能够让时间无限倒退，那么将会掉进时间漩涡，从而实现穿越。那么蒜头君发明的时光机能否实现穿越（蒜头君可以从任何星球开始）。

蒜头君在玩一个很好玩的游戏，这个游戏一共有至多 100 个地图，其中地图 1 是起点，房间 n 是终点。有的地图是补给站，可以加 k_i 点体力，而有的地图里存在怪物，需要消耗 k_i 点体力，地图与地图之间存在一些单向通道连接。

蒜头君从 1 号地图出发，有 100 点初始体力。每进入一个地图的时候，需要扣除或者增加相应的体力值。这个过程持续到走到终点，或者体力值归零就会 Game Over。不过，他可以经过同个地图任意次，且每次都需要接受该地图的体力值。

蒜头君准备去参加骑车比赛，比赛在 n 个城市间进行，编号从 1 到 n。选手们都从城市 1 出发，终点在城市 n。

已知城市间有 m 条道路，每条道路连接两个城市，注意道路是双向的。现在蒜头君知道了他经过每条道路需要花费的时间，他想请你帮他计算一下，他这次比赛最少需要花多少时间完成。

圣诞节快到了，蒜头君准备做一棵大圣诞树。

这棵树被表示成一组被编号的结点和一些边的集合，树的结点从 1 到 n 编号，树的根永远是 1。每个结点都有一个自身特有的数值，称为它的权重，各个结点的权重可能不同。对于一棵做完的树来说，每条边都有一个价值 v_e，若设这条边 e 连接结点 i 和结点 j，且 i 为 j 的父结点（根是最老的祖先），则该边的价值 v_e = s_j × w_e，s_j表示结点 j 的所有子孙及它自己的权重之和，w_e 表示边 e 的权值。

现在蒜头君想造一棵树，他有 m 条边可以选择，使得树上所有边的总价值最小，并且所有的点都在树上，因为蒜头君喜欢大树。

蒜头君陷入了坐标系上的一个迷阵，迷阵上有 n 个点，编号从 1 到 n。蒜头君在编号为 1 的位置，他想到编号为 n 的位置上。蒜头君当然想尽快到达目的地，但是他觉得最短的路径可能有风险，所以他会选择第二短的路径。现在蒜头君知道了 n 个点的坐标，以及哪些点之间是相连的，他想知道第二短的路径长度是多少。

注意，每条路径上不能重复经过同一个点。

SQL介绍及MySQL安装

相关概念

1. 数据库和SQL概念
   数据库（Database）是按照数据结构来组织、存储和管理数据的仓库
   结构化查询语言(Structured Query Language)简称 SQL
   SQL 是一种数据库查询和程序设计语言，用于存取数据以及查询、更新和管理关系数据库系统，同时也是数据库脚本文件的扩展名
2. MySQL 介绍
   MySQL 是一个 DBMS（数据库管理系统）,关系型数据库管理系统,是建立在关系数据库模型基础上的数据库，借助于集合代数等概念和方法来处理数据库中的数据

两种次短路

对于一个带权图，求两个顶点之间的次短路。次短路表示除最短路以外长度最小的路径。

实际上我们遇到的次短路问题分成两种，第一种次短路中可以重复经过一个点，第二种次短路不能重复经过一个点的。而这一个区别会导致解法上的很大区别。

1. 对于第一种可以重复经过某个点的次短路，解法其实和求最短路相似，在进行 dijkstra 的过程中记录两个数组：dist0 和 dist1，分别表示最短路和次短路的答案。每次更新时需要依次判断是否可以更新次短路和最短路的值。由于需要计算次短路，所以调整后的 dijkstra 算法需要至少循环 2n−1 次才可以获得最终答案。
2. 对于第二种不可以重复经过点的次短路，解法也比较直观简单，枚举两个顶点之间最短路上的每条边，每次在去掉这条边的剩下的图中计算最短路，取其中最小的一个答案就是最终次短路的答案。

常用操作

设置git使用socks5代理

1
2
3
4
5
6
7
8
9
10
11

git config --global http.proxy socks5://127.0.0.1:1080
git config --global https.proxy socks5://127.0.0.1:1080

# 取消代理
git config --global --unset http.proxy
git config --global --unset https.proxy

# 只对github进行代理
git config --global http.https://github.com.proxy socks5://127.0.0.1:1080
git config --global https.https://github.com.proxy socks5://127.0.0.1:1080

Git 与 GitHub 简介

当我们在 GitHub 上创建一个仓库时，同时生成了仓库的默认主机名 origin，并创建了默认分支 master。GitHub 可以看成是免费的 Git 服务器，在 GitHub 上创建仓库，会自动生成一个仓库地址，主机就是指代这个仓库，主机名就等于这个仓库地址。克隆一个 GitHub 仓库（也叫远程仓库）到本地，本地仓库则会自动关联到这个远程仓库，执行 git remote -v 命令可以查看本地仓库所关联的远程仓库信息

Git 要求对本地仓库关联的每个远程主机都必须指定一个主机名（默认为 origin），用于本地仓库识别自己关联的主机，git remote 命令就用于管理本地仓库所关联的主机，一个本地仓库可以关联任意多个主机（即远程仓库）。

vim

Vim快速入门

典型例题

最大字段和

对于全是非正数的序列，答案明显就是其中的最大元素

对于有正数的序列，考虑以每一个点为结尾的最大字段和，这个子段一定满足前缀和均非负，因为如果有一个前缀是负的，那么去掉这个前缀对于这个点一定更优，并且这个子段要尽量往前延伸

所以我们可以只用一次扫描，记录目前统计的和sum 以及答案 ans. **当 sum 加上当前位置这个数还是正数的时候就继续累加sum, 否则就将sum 置为 0.**：这样就舍掉了所有前缀为负的情况，并且保证了这个子段尽可能的长，也就是说扫描中记录的sum就是以每个点为结尾的最大字段和，每一次如果sum比ans大就可以更新ans. 最后 ans就是整体的最大子段和。

时间复杂度 O(N)