用途： 用于求图中指定两点之间的最短路径，或者是指定一点到其它所有点之间的最短路径。实质上是贪心算法。

基本思想：
1.将图上的初始点看作一个集合S，其它点看作另一个集合
2.根据初始点，求出其它点到初始点的距离d[i] （若相邻，则d[i]为边权值；若不相邻，则d[i]为无限大）
3.选取最小的d[i]（记为d[x]），并将此d[i]边对应的点（记为x）加入集合S （实际上，加入集合的这个点的d[x]值就是它到初始点的最短距离）
4.再根据x，更新跟 x 相邻点 y 的d[y]值：d[y] = min{ d[y], d[x] + 边权值w[x][y] }，因为可能把距离调小，所以这个更新操作叫做松弛操作。 （仔细想想，为啥只更新跟x相邻点的d[y]，而不是更新所有跟集合 s 相邻点的 d 值？ 因为第三步只更新并确定了x点到初始点的最短距离，集合内其它点是之前加入的，也经历过第 4 步，所以与 x 没有相邻的点的 d 值是已经更新过的了，不会受到影响）
5.重复3，4两步，直到目标点也加入了集合，此时目标点所对应的d[i]即为最短路径长度。 （注：重复第三步的时候，应该从所有的d[i]中寻找最小值，而不是只从与x点相邻的点中寻找。想想为什么？） 原理：这里不进行严格证明，Dijkstra的大致思想就是，根据初始点，挨个的把离初始点最近的点一个一个找到并加入集合，集合中所有的点的d[i]都是该点到初始点最短路径长度，由于后加入的点是根据集合S中的点为基础拓展的，所以也能找到最短路径。

伪代码：

清除所有点的标号;
设d[0]=0，其他d[i]=INF;//INF是一个很大的值，用来替代正无穷
循环n次 { 
在所有未标号结点中，选出d值最小的结点x;
给结点x标记;
对于从x出发的所有边(x,y)，更新d[y] = min{d[y], d[x]+w(x,y)} 
}

实现代码：（C++） 以下算法用于求所有点到初始点的最短距离（保存在d[i]中），n是节点数，m是边的数量。

memset(v, 0, sizeof(v)); 
for(int i = 0; i < n; i++) d[i] = (i==0 ? 0 : INF); 
for(int i = 0; i < n; i++) {  
  int x, m = INF;  
  //3.如果y没有被加入集合，且d[y]是最小的，则把y加入集合且x = y
  for(int y = 0; y < n; y++) 
    if(!v[y] && d[y] <= m) m = d[y], x = y; 
  v[x] = 1;  //新的点加入集合(这是更新之后的新x）
  //4.更新x相邻的点的d[i]，实际上这里更新的是所有点，但是与x未相邻的w[x][y]值是无穷大，不可能被更新
  for(int y = 0; y < n; y++) d[y] = min(d[y], d[x] + w[x][y]); 
}

· 稍微修改一下，便可以把路径存储起来（将当前点y的前一个点x存储在p[y]中），之后就方便递归打印了。

将d[y] = min(d[y], d[x] + w[x][y])改成：

if(d[x] + w[x][y] < d[y]) {
 d[y] = d[x] + w[x][y];
 p[y] = x;

· 类似于d[y] = min(d[y], d[x] + w[x][y])这种操作，它每次都可能把距离更新成更小的值，所以这类操作又叫作”松弛操作“。

优化方法（vector & 邻接表） 上述代码的复杂度为$O(n^2)$，这里可以用邻接表将其优化为$O(m \log n)$，之所以为优化，是因为m往往远小于$n^2$。为了方便，我们把边封装在结构体中：

struct Edge {
  int from, to, dist;
  Edge(int u, int v, int d):from(u),to(v),dist(d) {}
}

` 又因为Dijkstra算法中，每次循环需要提取出最小$d_i$对应的点，所以这里可以用到优先队列 priority_queue，队列内部是根据d值进行排序的，又需要d值对应的点的信息（u），所以这里可以用另一个结构体存储放在优先队列里的元素（d相当于d[i]，u相当于i）。

struct DistNode {
  int d, u;
  bool operator  rhs.d; //这样一来，队列中在最顶层的是最小值
  }
}

接下来我们再建立一个统一的邻接表数据结构，用于接收数据并构造邻接表，并能Dijkstra。

struct Dijkstra {
  int n, m;
  vector edges;//相当于数组r[i],用于存储每条边
  vector G[maxn];//邻接表，只需存储边的标号即可
  book done[maxn];//用于判断是否已经处理过该节点
  int d[maxn];距离
  int p[maxn];上一条弧
  //清除垃圾数据，初始化邻接表和deges
  void setn(int n) {
    this->n = n;
    for(int i = 1; i <= n; i++) G[i].clear();
    edges.clear();
  }
  //添加一条边
  void addedge(int from, int to , int dist) {
    edges.push_back(Edge(from, to, dist));
    m = edges.size();
    G[from].push_back(m - 1);
  }
  //Dijkstra
  void dijkstra(int s) {
  }
}
   · 接下来实现dijkstra函数:

void dijkstra(int s) {
  priority_queue Q;
  Q.push_back(DistNode{0, s});
  for(int i = 1; i <= n; i++) d[i] = INF;//把d[i]都设置为最大值
  d[s] = 0;
  memset(done, 0, sizeof(done));
  while(!Q.empty()) {
    DistNode x = Q.top(); Q.pop();
    int u = x.u;
    if(done[u]) continue;//如果这个点已经被提出过了，直接抛弃（适用于那种松弛之后重复放入队列的点）
    done[u] = true;
    for(int i = 0; i < Q[u].size(); i++) 
      Edge& e = edges(Q[u][i]);
      if(e.dist + d[u] < d[e.to] && d[u] < INF) {
        d[e.to] = e.dist + d[u];
        p[e.to] = G[u][i];
        Q.push_back(Edge(d[e.to], e.to));//把松弛过后点的d值重新放入队列
      }
    }
  }
}

前言：我是GD选手，而GD的CSP/NOIP考场环境都是Windows系统+Linux虚拟机，所以写一下常用的指令，考前复习用

cmd常用指令

1.打开cmd

本文以WIN10系统为例

在开始菜单中打开

Step 1:在开始(按钮) 上左键单击

Step 2:鼠标滚轮向下滚动(在"启动"中)

Step 3:在Windows系统文件夹，已折叠 (列表项目) 上左键单击(在"启动"中)

Step 4:在命令提示符 (列表项目) 上左键单击(在"启动"中)

用“启动”打开

Step 1: 在键盘上输入[Win+R]

Step 2:在"打开(O): (编辑)"上键盘输入“cmd”(在"运行"中)

Step 3: 在"确定 (按钮)"上左键单击(在"运行"中)

常用指令大全

1.help指令

2.cd指令

3.打开各种程序

GDB常用命令

打开gdb

Windows环境

打开cmd，输入gdb或按[Win+R]，输入gdb

Linux环境

在终端输入$gdb

GDB命令

感觉成了炮灰。。。

DAY1

三天中最简单的一天了，但因为我的手残，挂了很多分。。。

割

题目全是使用数学语言描述的，但理解没有问题

题目大意

有一个无向图，将点分成两部分（就像二分图），并且要求两部分之间连的边要是原来的$\frac{1}{2}$以上

思路

因为最终的图要像二分图一样，所以可以考虑删边，将一个点放入一个集合中，并删除与该集合连接的边，显然是加入连的边较多的一个集合更优，而题目保证有解，所以$O(n)$跑一边贪心即可，但考试时打挂了。。。

忙碌的出题人

直接$O(n^2)$硬上，有人用线段树和ST表复杂度反而更大

回文

10%

$O(n^3)$暴力

30%

manacher暴力

100%

manacher预处理+DP

东方永夜抄

Subtask1

暴力枚举

100%

奇奇怪怪的多项式

DAY2

游戏

思路

明显是期望DP

$p_i$指胜率($\frac{x_i}{y_i}$)，设$f_i$表示从$i-1$颗星打到$i$期望对局的次数，那么

$$f_i=(f_i+f_{i-1})\times (1-p_i)$$

但方程中仍有$f_i$,所以转化为

$f_i=\frac{f_{i-1}\times (1-p_i)+1}{p_i}$,$f_1=\frac{1}{p_1}$

接着就可以$O(n)$转移了

答案为$\sum_{i=1}^nf_i$.

群岛

线段树乱搞即可

抄写

manacher预处理回文

堆

使用$O(n\log n)$的堆构造方法即可

DAY3

？？？