不定期更新蓝桥杯省赛赛题题解

一些关于数据范围的小Tips

有时候我们可以根据数据范围来确定算法

时间复杂度	常用算法
N<=30 =>指数级	dfs+剪枝 状态压缩dp
N<=100 => O(N3 )	floyd dp 高斯消元
N<=1000 => O(N2 ) O(N2logN )	dp 二分 朴素dijkstra 朴素Prim Bellman-Ford
N<=10000 => O(N * sqrt(N) )	块状链表 分块 莫队
N<=100000 => O(N * logN)	各种sort 线段树 树状数组 set/map heap 拓扑排序 堆优化dijkstra 堆优化Prim spfa 求凸包 半平面交 二分 CDQ分治 整体二分
N<=1000000 => O(N)或者常数较小的O(N * logN)	O(N): 单调队列 hash 双指针扫描 并查集 kmp AC自动机 小常数NlogN: sort 树状数组 heap dijkstra spfa
N<=1e8 => O(N)	双指针扫描 kmp AC自动机 线性筛素数
N<=1e9 => O(sqrt(N) )	判断素数
N<=1e18 => O(logN)	最大公约数 快速幂 二分
N<=1e1000 => O(k)	高精度加减乘除

2021C++A组

T8 左孩子右兄弟

树形 dp + dfs 太经典了！

基本思路就是递归找每个子节点的dp值

dp值为当前节点的兄弟数+子树的树高 维护最大值

// http://lx.lanqiao.cn/problem.page?gpid=T2898
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

vector<int> G[N];
int dp[N];
void dfs(int u) {
  dp[u] = G[u].size();
  int mx = 0;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    dfs(v);
    mx = max(mx, dp[v]);
  }
  dp[u] += mx;
}
int main() {
  int n;
  cin >> n;
  for (int i = 2; i <= n; i++) {
    int x;
    cin >> x;
    G[x].push_back(i);
  }
  dfs(1);
  cout << dp[1] << endl;
  return 0;
}

2020C++A组

T9 糖果

状压dp裸题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int dp[(1 << 21) + 1];
int tg[105];

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      int x;
      cin >> x;
      tg[i] |= (1 << (x - 1));
    }
  }
  memset(dp, 0x3f, sizeof(dp));
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < (1 << m); j++) {
      if (dp[j] > n)
        continue;
      dp[j | tg[i]] = min(dp[j | tg[i]], dp[j] + 1);
    }
  }
  if (dp[(1 << m) - 1] > n)
    puts("-1");
  else
    cout << dp[(1 << m) - 1] << endl;
  return 0;
}