\(\color{black}\texttt{A. 序列}\)

题目描述

给定 \(N\) 个数，每个数均可写成 \(pq(p,q\in\mathbb{P},p<q)\) 的形式，问最长能找到多长的子序列使得任意相邻两项 \(x_i=p_1q_1,x_{i+1}=p_2q_2(p_1,q_1,p_2,q_2\in\mathbb{P},p_1<q_1,p_2<q_2)\) 满足 \(q_1=p_2\) ？

思路

按照 \(p\) 排序并 dp 即可。

代码

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int MAXN = 50001;

struct Num {
  int p, q;
}a[MAXN];

int n, Max[MAXN], ans;

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1, x; i <= n; ++i) {
    cin >> x;
    for(int j = 2; j * j <= x; ++j) {
      if(x % j == 0) {
        a[i] = {j, x / j};
        break;
      }
    }
  }
  sort(a + 1, a + n + 1, [](const Num &x, const Num &y) { return x.p < y.p || (x.p == y.p && x.q < y.q); });
  for(int i = 1; i <= n; ++i) {
    ans = max(ans, Max[a[i].p] + 1);
    Max[a[i].q] = max(Max[a[i].q], Max[a[i].p] + 1);
  }
  cout << ans;
  return 0;
}

\(\color{black}\texttt{B. 生成最小树}\)

题目描述

给定一张图和其中的一棵树，每次操作可以将一条边的边权 \(-1\)，求最少需要多少次操作才能使这棵树变成最小生成树？

思路

因为每一条非树边必须 \(\ge\) 边两个端点树上路径的每一条边，不然这条边一定比树边更优，所以使用树链剖分求出每条边的限制即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 10001, MAXM = 100001;

struct Edge {
  int u, v, w;
}g[MAXM];

struct Segment_Tree {
  int l[4 * MAXN], r[4 * MAXN], dfn[MAXN], W[MAXN], Min[4 * MAXN], lazy[4 * MAXN];
  void build(int u, int s, int t) {
    l[u] = s, r[u] = t, lazy[u] = INT_MAX;
    if(s == t) {
      Min[u] = W[dfn[s]];
      return;
    }
    int mid = (s + t) >> 1;
    build(2 * u, s, mid), build(2 * u + 1, mid + 1, t);
    Min[u] = min(Min[2 * u], Min[2 * u + 1]);
  }
  void tag(int u, int x) {
    Min[u] = min(Min[u], x), lazy[u] = min(lazy[u], x);
  }
  void pushdown(int u) {
    tag(2 * u, lazy[u]), tag(2 * u + 1, lazy[u]), lazy[u] = INT_MAX;
  }
  void update(int u, int s, int t, int x) {
    if(l[u] >= s && r[u] <= t) {
      tag(u, x);
      return;
    }
    pushdown(u);
    if(s <= r[2 * u]) {
      update(2 * u, s, t, x);
    }
    if(t >= l[2 * u + 1]) {
      update(2 * u + 1, s, t, x);
    }
    Min[u] = min(Min[2 * u], Min[2 * u + 1]);
  }
  int Get(int u, int p) {
    if(l[u] == r[u]) {
      return Min[u];
    }
    pushdown(u);
    return (p <= r[2 * u] ? Get(2 * u, p) : Get(2 * u + 1, p));
  }
}tr;

int n, m, sz[MAXN], f[MAXN], son[MAXN], dfn[MAXN], tot, top[MAXN];
ll ans;
vector<pii> e[MAXN];
map<pii, bool> vis;
map<pii, int> _W;

void dfs(int u, int fa) {
  f[u] = fa, sz[u] = 1;
  for(auto [v, w] : e[u]) {
    if(v != fa) {
      tr.W[v] = w;
      dfs(v, u);
      sz[u] += sz[v];
      if(sz[v] > sz[son[u]]) {
        son[u] = v;
      }
    }
  }
}

void DFS(int u, int fa) {
  dfn[u] = ++tot, tr.dfn[tot] = u;
  if(son[u]) {
    top[son[u]] = top[u], DFS(son[u], u);
  }
  for(auto [v, w] : e[u]) {
    if(v != fa && v != son[u]) {
      top[v] = v, DFS(v, u);
    }
  }
}

void changepath(int u, int v, int w) {
  for(; top[u] != top[v]; ) {
    if(dfn[u] > dfn[v]) {
      tr.update(1, dfn[top[u]], dfn[u], w);
      u = f[top[u]];
    }else {
      tr.update(1, dfn[top[v]], dfn[v], w);
      v = f[top[v]];
    }
  }
  if(min(dfn[u], dfn[v]) + 1 <= max(dfn[u], dfn[v])) {
    tr.update(1, min(dfn[u], dfn[v]) + 1, max(dfn[u], dfn[v]), w);
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= m; ++i) {
    cin >> g[i].u >> g[i].v >> g[i].w;
    _W[{g[i].u, g[i].v}] = _W[{g[i].v, g[i].u}] = g[i].w;
  }
  for(int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    e[u].push_back({v, _W[{u, v}]});
    e[v].push_back({u, _W[{u, v}]});
    vis[{u, v}] = vis[{v, u}] = 1;
  }
  dfs(1, 0);
  top[1] = 1;
  DFS(1, 0);
  tr.build(1, 1, n);
  for(int i = 1; i <= m; ++i) {
    if(!vis.count({g[i].u, g[i].v})) {
      changepath(g[i].u, g[i].v, g[i].w);
    }
  }
  for(int i = 2; i <= n; ++i) {
    ans += max(0, _W[{f[i], i}] - tr.Get(1, dfn[i]));
  }
  cout << ans;
  return 0;
}

\(\color{black}\texttt{C. 互质序列}\)

题目描述

给定 \(l,r\)，求有多少个序列满足以下条件：

• 序列单调递增。
• 序列中的数 \(\in[l,r]\)。
• 序列中的数两两互质。

思路

因为 \(r-l+1\le 100\)，所以出现超过两次的质数一定 \(\le 100\)，所以状压 dp 即可。

但是这样可能会 \(\texttt{TLE}\)，所以要先预处理出所有出现超过一次的质数。

令 \(V=25\)，空间复杂度 \(O(2^V)\)，时间复杂度 \(O((r-l)2^V)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

ll a, b, dp[1 << 25], ans;
vector<int> v;

void FileIO(const string &s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  FileIO("rlprime");
  cin >> a >> b;
  for(int i = 1; i <= 25; ++i) {
    int cnt = 0;
    for(ll j = a; j <= b; ++j) {
      cnt += (j % prime[i] == 0);
    }
    if(cnt > 1) {
      v.push_back(prime[i]);
    }
  }
  dp[0] = 1;
  for(ll i = a; i <= b; ++i) {
    int res = 0;
    for(int j = 0; j < int(v.size()); ++j) {
      if(i % v[j] == 0) {
        res |= (1 << j);
      }
    }
    for(int j = (1 << int(v.size())) - 1; j >= 0; --j) {
      if(!(j & res)) {
        dp[j | res] += dp[j];
      }
    }
  }
  for(int i = 0; i < (1 << int(v.size())); ++i) {
    ans += dp[i];
  }
  cout << ans - 1;
  return 0;
}