挑战程序设计竞赛

发表于 | 分类于 | |

挑战程序设计竞赛

初出茅庐——初级篇

搜索

DFS

从某个状态开始，不断地转移状态直至无法转移，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直至找到最终的解。

  • 部分和

    选出若干数，和恰好为k。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // 输入 
    int a[MAX_N]; int n, k;

    // 已经从前i项得到了和sum，然后对于i项之后的进行分支 
    bool dfs(int i, int sum) {
    	// 如果前n项都计算过了，则返回sum是否与k相等
      if (i == n) return sum == k;

    	// 不加上a[i]的情况
      if (dfs(i + 1, sum)) return true;

    	// 加上a[i]的情况
      if (dfs(i + 1, sum + a[i])) return true;

    	// 无论是否加上a[i]都不能凑成k就返回false 
      return false;
    }

    void solve() { 
      if (dfs(0, 0)) printf("Yes\n"); 
      else printf("No\n"); 
    }

  • Lake Counting (DFS一次就是消掉了一块积水)

    ​ 从任意的W开始，不停地把邻接的部分用’.’代替。1次DFS后与初始的这个W连接的所有W就都被替 换成了’.’，因此直到图中不再存在W为止，总共进行DFS的次数就是答案了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    // 输入 
    int N, M; 
    char field[MAX_N][MAX_M + 1]; // 园子

    // 现在位置(x,y) 
    void dfs(int x, int y) {
    	// 将现在所在位置替换为.
    	field[x][y] = '.';

    	// 循环遍历移动的8个方向 
      for (int dx = -1; dx <= 1; dx++) 
      { 
        for (int dy = -1; dy <= 1; dy++) 
         { 
          // 向x方向移动dx，向y方向移动dy，移动的结果为（nx,ny） 
          int nx = x + dx, ny = y + dy; 
          // 判断(nx,ny)是不是在园子内，以及是否有积水 
          if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W') 
            dfs(nx, ny); 
        } 
      } 
      return ;
    }

    void solve() {
    	int res = 0; 
      for (int i = 0; i < N; i++) 
      { 
        for (int j = 0; j < M; j++) 
        { 
          if (field[i][j] == 'W') 
          { 
            // 从有W的地方开始dfs 
            dfs(i, j); 
            res++; 
          } 
        }
    	}
      printf("%d\n", res);
    }

BFS

​ 与深度优先搜索的不同之处在于搜索的顺序，宽度优先搜索总是先搜索距离初始状态近的状态。 也就是说，它是按照开始状态→只需1次转移就可以到达的所有状态→只需2次转移就可以到达的所有状态→……

​ 深度优先用栈，宽度优先用队列

  • 迷宫最短路径

    ​ 宽度优先搜索按照距开始状态由近及远的顺序进行搜索，因此可以很容易地用来求最短路径、最少操作之类问题的答案。 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    const int INF = 100000000;

    // 使用pair表示状态时，使用typedef会更加方便一些 
    typedef pair<int, int> P;

    // 输入 
    char maze[MAX_N][MAX_M + 1]; // 表示迷宫的字符串的数组


    int N, M; 
    int sx, sy; // 起点坐标 
    int gx, gy; // 终点坐标

    int d[MAX_N][MAX_M]; // 到各个位置的最短距离的数组

    // 4个方向移动的向量
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

    // 求从(sx, sy)到(gx, gy)的最短距离 
    // 如果无法到达，则是INF
    int bfs() {
      queue<P> que; 
      // 把所有的位置都初始化为INF 
      for (int i = 0; i < N; i++) 
        for (int j = 0; j < M; j++) 
          d[i][j] = INF; 
      // 将起点加入队列，并把这一地点的距离设置为0 
      que.push(P(sx, sy)); 
      d[sx][sy] = 0;

    	// 不断循环直到队列的长度为0 
      while (que.size()) {
    	  // 从队列的最前端取出元素
        P p = que.front(); que.pop(); 
        // 如果取出的状态已经是终点，则结束搜索 
        if (p.first == gx && p.second == gy) break;

    		// 四个方向的循环 
        for (int i = 0; i < 4; i++) {

    			// 移动之后的位置记为(nx, ny) 
          int nx = p.first + dx[i], ny = p.second + dy[i];

    			// 判断是否可以移动以及是否已经访问过（d[nx][ny]!=INF即为已经访问过） 
          if (0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF) {
            // 可以移动的话，则加入到队列，并且到该位置的距离确定为到p的距离+1 
            que.push(P(nx, ny)); 
            d[nx][ny] = d[p.first][p.second] + 1; 
          }
    		}
    	} 
      return d[gx][gy];
    }

    void solve() { 
      int res = bfs();
      printf("%d\n", res); 
    }

贪心

  • 硬币问题

    优先使用面值大的硬币

    1
    2
    3
    4
    5
    6
    7
    8
    ……
    for(int i = 5; i >= 0; i--)
    {
      int t = min(A/V[i],C[i]);
      A-= t*V[i];
      ans+=t;
    }
    ……

  • 区间调度问题

    在可选的工作中，每次都去结束时间最早的工作

  • Fence Repair

    木板的长度*节点的深度 ==> 哈夫曼编码

动态规划

  • 01背包

    $memset(dp,-1,sizeof(dp))$ 按照1字节为单位对内存进行填充，-1每个二进制都为1。memset只能初始化为0或-1。

    状态 $dp[i][j]$ ：从第i个物品开始挑选总重小于j的部分

    递推

    $dp[n][j] = 0$

    $dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])$

  • 完全背包

    从01背包的选或不选转化为选多少件。

  • 多重部分和

    状态：$dp[i+1][j]$: 用前i种数加和得到j时第i种数最多剩余多少个（不能加和得到i的情况为-1）​

数据结构

优先队列和堆

堆得性质是儿子的值一定不小于父亲的值。

  1. 插入：首先在堆的末尾插入该数值，然后不断向上提升直到没有大小颠倒为止
  2. 删除：首先把堆得最后一个节点的数值复制到根节点上，删除最后一个节点，不断向下交换直到没有大小颠倒为止

  • Expedition

    trick：在到达加油站$i$时，就获得了一次在之后的任何时候都可以加$B_i$单位汽油的权利

    1. 在经过加油站时，往优先队列里加入$B_i$
    2. 当燃料空了时
      1. 如果优先队列也是空的，则无法到达终点
      2. 否则取出优先队列中的最大元素，并用来给卡车加油

二叉搜索树

删除

  1. 需要删除的节点没有左儿子，就把右儿子提上去
  2. 需要删除的节点的左儿子没有右儿子，把左儿子提上去
  3. 以上都不满足，就把左儿子子孙中最大的节点提到需要删除的节点上

图

  • 二分图判定

    dfs.

    从任意一个点出发，依次确定相邻顶点的颜色

    image-20190916155253357

最短路径

Bellman-Ford算法

$d[i] = min{d[j] + (j到i的边的权值)|e=(j,i)\in E }$

Dijkstra算法
  1. 找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离
  2. 此后不需要再关心1中的“最短距离已经确定的顶点”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct edge {int to, cost;};
typedef pair<int,int> P; //first 是最短距离，second是顶点的编号

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s)
{
  //通过指定greater<P>参数，堆按照first从小到大的顺序取出值
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d,d+V,INF);
  d[s] = 0;
  que.push(P(0,s));
  
  while(!que.empty())
  {
    P p = que.top(); que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(int i = 0; i<G[v].size();i++)
    {
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost)
      {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to],e.to));
      }
    }
  }
}
Floyd-Warshall算法

任意两点最短路径

image-20190916184235055

最小生成树

Prim算法

Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边的算法。

  1. 一颗只包含一个顶点v的树T
  2. 贪心地选取T和其他顶点之间相连的最小权值的边，并把它加入到T中
Kruskal算法
  1. 按照权值的顺序从小到大查看一遍
  2. 如果不产生圈，就把当前这条边加入到生成树中
  3. 判断是否产生圈：如果加入之前$u$和$v$不在同一连通分量里，那么加入也不会产生圈，可以使用并查集高效地判断是否属于同一个连通分量。

数学问题

辗转相除法

1
2
3
4
5
6
7
//a>b
int gcd(int a,int b)
{
	if(b==0)
    return a;
  return gcd(b, a%b);
}

素数判定

O($\sqrt n$)

素数的个数

埃氏筛法
  1. 首先，将2到范围n的所有整数写下来
  2. 其中最小的数字是2，将表中2的倍数都划去
  3. 再将表中所有3的倍数都划去
  4. ……
  5. 如果表中剩余的最小数字是m，m就是素数，将表中所有m的倍数都划去