#include <stdio.h>
#include <stdlib.h>

#define N 1010
#define ri register int

int n, v;
int weights[N], values[N], dp[N][N];

int main(const int argc, char** const argv) {
  scanf("%d %d", &n, &v);
  for (ri i = 1; i <= n; ++i)
    scanf("%d %d", weights + i, values + i);

  for (ri i = 1; i <= n; ++i)
    for (ri j = 1; j <= v; ++j) {
      if (weights[i] <= j) { // 01背包的核心, 状态转移方程
        dp[i][j] = fmax(dp[i - 1][j], values[i] + dp[i - 1][j - weights[i]]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
      // printf("%d%c", dp[i][j], j == v ? 10 : 32);
    }

  printf("%d", dp[n][v]);
  return 0;
}

据说是经典的树型DP

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ri register int
#define N 1000100
#define r() fast_read()

typedef long long int LL;

int head[N], cnt_edge;
struct Edge {
  int to, nxt;
} edges[N << 1]; // 无向图

void addEdge(int u, int v) {
  edges[++cnt_edge].to = v;
  edges[cnt_edge].nxt = head[u];
  head[u] = cnt_edge;
}

int fast_read() {
  int n = 0, sign = 1;
  char c = getchar();
  while (c < 48 || c > 57) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (c >= 48 && c <= 57) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

int n, sizes[N];
LL depths[N];

// Bottom-Up
void DFS1(int curr, int parent) {
  sizes[curr] = 1;
  for (int e = head[curr]; e; e = edges[e].nxt) {
    int child = edges[e].to;
    if (child == parent) continue;
    DFS1(child, curr);
    sizes[curr] += sizes[child];
    depths[curr] += sizes[child] + depths[child];
  }
} 

// Top Down
void DFS2(int curr, int parent) {
  if (parent)
    //depths[curr] += depths[parent] - depths[curr] + n - (sizes[curr] << 1);
    depths[curr] = depths[parent] + n - (sizes[curr] << 1);
  for (int e = head[curr]; e; e = edges[e].nxt) {
    int child = edges[e].to;
    if (child == parent) continue;
    DFS2(child, curr);
  }
}

int main(int argc, char const *argv[]) {
  n = r();
  // build the undirected graph
  for (int m = n - 1, u, v; m--; ) {
    u = r(), v = r();
    addEdge(u, v);
    addEdge(v, u);
  }

  DFS1(1, 0);
  DFS2(1, 0);

  int ans = 1;
  for (int u = 2; u <= n; u = -~u)
    if (depths[u] > depths[ans]) ans = u;

  return printf("%d", ans), 0;
}

DFS代码写起来简单

#include <iostream>
#include <vector>

using namespace std;

int n, m;

enum Color { UNKNOWN, BLUE, RED };

inline bool DFS(vector<vector<int>>& g, vector<Color>& colors, int curr, Color color) {
  colors[curr] = color;
  for (const auto& nxt : g[curr]) {
    if (colors[nxt] == color) return false; 
    if (colors[nxt] == UNKNOWN && !DFS(g, colors, nxt, color == BLUE ? RED : BLUE))
      return false;
  }
  return true;
}

int main(const int argc, const char** const argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> m;
  vector<vector<int>> g(n + 1);
  vector<Color> colors(n + 1, UNKNOWN);

  for (int u, v; m; --m) {
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  for (int i = 1; i <= n; ++i) {
    if (colors[i] == UNKNOWN && !DFS(g, colors, i, BLUE)) {
      cout << "No";
      return 0;
    }
  }

  cout << "Yes";
  return 0;
}

卡恩算法

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100005

int n, m;
int head[MAX_N], cnt_edges;
struct Edge {
  int to, nxt;
} edges[MAX_N];

int indegrees[MAX_N], ans[MAX_N], ansSize;

void addEdge(int u, int v) {
  edges[++cnt_edges].to = v;
  edges[cnt_edges].nxt = head[u];
  head[u] = cnt_edges;
}

int main(void) {
  scanf("%d %d", &n, &m);
  for (int u, v; m; --m) {
    scanf("%d %d", &u, &v);
    addEdge(u, v);
    ++indegrees[v];
  }

  int q[MAX_N], front = 0, rear = 0;
  for (int i = 1; i <= n; ++i)
    if (!indegrees[i]) q[rear++] = i;

  while (front < rear) {
    int curr = q[front++];
    ans[ansSize++] = curr;
    for (int e = head[curr]; e; e = edges[e].nxt) {
      int nei = edges[e].to;
      if (!--indegrees[nei]) q[rear++] = nei;
    }
  }

  if (ansSize < n) {
    puts("-1");
    return 0;
  }

  for (int i = 0; i < ansSize; ++i)
    printf("%d ", ans[i]);

  return 0;
}

暂时只会简单的证明，先背诵代码模版！

#include <iostream>
#include <vector>
#include <tuple>
#include <cstring>

using namespace std;

using T = tuple<int, int, int>;
const int oo = 0x3f3f3f3f;

int n, m, k;
vector<T> edges;

inline void bellman_ford(void) {
  int dists[n + 1], backup[n + 1];
  memset(dists, oo, sizeof dists);
  dists[1] = 0; // 源点到源点的距离为0

  int u, v, w;
  for (int i = 0; i < k; ++i) {
    memcpy(backup, dists, (n + 1) * sizeof(int));
    for (int j = 0; j < edges.size(); ++j) {
      u = get<0>(edges[j]), v = get<1>(edges[j]), w = get<2>(edges[j]);
      dists[v] = min(dists[v], backup[u] + w);
    }
  }

  cout << (dists[n] > oo >> 1 ? "impossible" : to_string(dists[n]));
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> m >> k;
  for (int u, v, w; m; --m) {
     cin >> u >> v >> w;
     edges.emplace_back(u, v, w);
  }

  bellman_ford(); 
  return 0;
}

暂时还不会双端BFS

#include <bits/stdc++.h>

using namespace std;

const string goal = "12345678x";

inline int bfs(const string& s) {
  queue<string> q{{s}};
  unordered_set<string> seen{s};

  const int dirs[] = { 0, -1, 0, 1, 0 };

  int steps = 0;
  while (not q.empty()) {
    size_t s = q.size();
    while (s--) {
      const auto curr = q.front(); q.pop();
      if (curr == goal) return steps;
      int p = curr.find('x');
      int x = p % 3, y = p / 3;
      for (int i = 0; i < 4; ++i) {
        int nx = x + dirs[i], ny = y + dirs[i + 1];
        if (nx < 0 || ny < 0 || nx == 3 || ny == 3)
          continue;
        string t(curr);
        swap(t[p], t[ny * 3 + nx]);
        if (seen.count(t)) continue;
        q.emplace(t);
        seen.emplace(t);
      }
    }
    ++steps;
  }

  return -1;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  string s;
  char x;
  for (int i = 0; i < 9; ++i) {
    cin >> x;
    s += x;
  }

  cout << bfs(s);
  return 0;
}

快速排序是一种不移定的排序。

理论上最好的时间复杂度为$O(NlogN)$, 最坏情况下时间复杂度退化到$O(N^2)$

#include <iostream>

using namespace std;

void qsort(int a[], int l, int r) {
  // recursion exit conditon (空集或只有一个元素)
  if (l >= r) return;
  int i = l, j = r, x = a[(l + r) >> 1]; // x 为哨兵
  do {
    while (a[i] < x) ++i;
    while (a[j] > x) --j;
    if (i <= j) swap(a[i++], a[j--]);
  } while (i <= j);
  qsort(a, l, j);
  qsort(a, i, r);
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n;

  int a[n];
  for (int i = 0; i < n; ++i) cin >> a[i];
  qsort(a, 0, n - 1);
  for (int i = 0; i < n; ++i) cout << a[i] << ' ';

  return 0;
}

DFS

#include <iostream>
#include <unordered_set>

#define N 55
#define r() fast_read()

int m, n, k;
int g[N][N];

int fast_read() {
  int n = 0, sign = 1;
  char c = getchar();
  while (c < 48 || c > 57) {
    if (sign == '-') sign = ~0;
    c = getchar();
  }
  while (c >= 48 && c <= 57) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

void print_grid(void) {
  int x, y;
  for (y= 0; y < m; ++y)
  for (x = 0; x < n; ++x)
  printf("%d%c", *(*(g + y) + x), x == n - 1 ? 10 : 32);
}

std::unordered_set<int> s;

void DFS(int x, int y, int k, int v) {
  static const int dirs[] = { 0, -1, 0, 1, 0 };
  if (x < 0 || y < 0 || x == n || y == m) return;
  v = v * 10 + *(*(g + y) + x);
  if (!k) {
    s.emplace(v);
    return;
  }
  for (int i = 0; i < 4; ++i)
    DFS(x + *(dirs + i), y + *(dirs + i + 1), k - 1, v);
}

int main(void) {
  m = r(), n = r(), k = r();
  int x, y;
  for (y= 0; y < m; ++y)
    for (x = 0; x < n; ++x)
      *(*(g + y) + x) = r();

  for (y = 0; y < m; ++y)
    for (x = 0; x < n; ++x) DFS(x, y, k, 0);

  return printf("%d", s.size()), 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 2010
#define M 10010

const int INF = 0x3f3f3f3f;

int head[N], cnt_edges;
struct Edge {
  int to, nxt, w;
} edges[M];

void addEdge(int u, int v, int w) {
  edges[cnt_edges].to = v;
  edges[cnt_edges].w = w;
  edges[cnt_edges].nxt = head[u];
  head[u] = cnt_edges++;
}

int n, m;

int spfa_algorithm() {
  int q[(int)5E6], front = 0, rear = 0;
  int cnts[N], exists[N], dists[N];

  memset(cnts, 0x0000, sizeof cnts);
  memset(exists, 0x0000, sizeof exists);
  memset(dists, INF, sizeof dists);

  for (int u = 1; u <= n; ++u) {
    q[rear++] = u;
    exists[u] = 1;
    dists[u] = 0;
  }
  int curr;
  while (front < rear) {
    curr = q[front++];
    exists[curr] = 0;
    for (int i = head[curr]; ~i; i = edges[i].nxt) {
      int v = edges[i].to, w = edges[i].w;
      if (dists[curr] + w < dists[v]) {
        dists[v] = dists[curr] + w;
        if (exists[v]) continue;
        q[rear++] = v;
        exists[v] = 1;
        ++cnts[v];
        if (cnts[v] == n) return 1;
      }
    }
  }

  return 0;
}

int main(const int argc, const char* const argv[]) {

  memset(head, -1, sizeof head);

  scanf("%d %d", &n, &m);

  int u, v, w;
  while (m--) {
    scanf("%d %d %d", &u, &v, &w);
    addEdge(u, v, w); // 有向图
  }

  puts(spfa_algorithm() ? "Yes" : "No");
  return 0;
}

#include <iostream>

using namespace std;

// s2 是不是s1 的子序列
bool is_subseqence(const string& s1, const string& s2) {
  int i = 0, j = 0;
  while (i < s1.length() && j < s2.length()) {
    if (s1[i] == s2[j]) ++j;
    ++i;
  }
  return j == s2.length();
}

int main(void) {
  string s;
  while (cin >> s)
    cout << (is_subseqence(s, "EASY") ? "easy" : "difficult") << endl;

  return 0;
}