T1、小L的數列

給一個數列 \(\{f_i\}\)：
\[ f_i = \prod_{j = 1}^{j \leq k} f_{i - j}^{b_j}, \ (i > k) \]
現在給定數列的前 \(k \ (k \le 200)\) 項及 \({b_i}\)，求第 \(n\) 項。

\(Sol\)：
注意到數列的任意一項 \(f_i \ (i > k)\)，都是前 \(k\) 項若干次冪的乘積，只需分別計算每一項對第 \(n\) 項的貢獻。
記 \(dp_i\) 表示第 \(i\) 項的指數，則不難得出：
\[ dp_i = \sum_{j = i - k}^{j \leq i - 1} b_{i - j} \times dp_j \]

顯然可以用矩陣乘法來優化，因為要枚舉前 \(k\) 項，時間復雜度 \(O(k ^ 4 \ \log_2 n)\)。
每一項的轉移矩陣是一樣的，所以可以以 \(O(k ^3 \ \log_2 n)\) 的時間復雜度解決。

代碼如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {int x = 0; char c = getchar(); bool f = 0;while (c < '0' || c > '9')f |= c == '-', c = getchar();while (c >= '0' && c <= '9')x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }const int M = 205, mod = 998244353;
int n, m, f[205], y[205], a[205], b[205], res;struct matrix {int a[M][M];matrix(int t = 0) {memset(a, 0, sizeof(a));if (t > 0)for (int i = 1; i <= m; ++i)a[i][i] = t;}inline int* operator [] (int x) {return a[x];}inline matrix operator * (matrix &b) const {matrix ret;for (int k = 1; k <= m; ++k)for (int i = 1; i <= m; ++i)if (a[i][k])for (int j = 1; j <= m; ++j)if (b[k][j]) {ret[i][j] += 1ll * a[i][k] * b[k][j] % (mod - 1);if (ret[i][j] >= mod - 1)ret[i][j] -= mod - 1;}return ret;}
} ;matrix matrix_qpow(matrix base, int b) {matrix ret(1);for (; b; b >>= 1, base = base * base)if (b & 1)ret = ret * base;return ret;
}
int qpow(int base, int b, int ret = 1) {for (; b; b >>= 1, base = 1ll * base * base % mod)if (b & 1)ret = 1ll * ret * base % mod;return ret;
}int main() {//freopen("in", "r", stdin);freopen("seq.in", "r", stdin);freopen("seq.out", "w", stdout);matrix trans;n = in(), m = in();for (int i = 1; i <= m; ++i)y[i] = in();for (int i = 1; i <= m; ++i)f[i] = in();if (n <= m) {printf("%d\n", f[n]);return 0;}for (int i = 1; i <= m; ++i)trans[i][i - 1] = 1;for (int i = 1; i <= m; ++i)trans[i][m] = y[m - i + 1];res = 1;trans = matrix_qpow(trans, n - m);for (int i = 1; i <= m; ++i) {for (int j = 1; j <= m; ++j)b[j] = a[j] = 0;b[i] = 1;for (int k = 1; k <= m; ++k)for (int j = 1; j <= m; ++j) {a[j] += 1ll * b[k] * trans[k][j] % (mod - 1);if (a[j] >= mod - 1)a[j] -= mod - 1;}res = 1ll * res * qpow(f[i], a[m]) % mod;}printf("%d\n", res);return 0;
}

T2、夢境

數軸上給定 \(n\) 條線段 \(\{l_i,r_i\}\)，\(m\) 個點 \(\{t_i\}\)，每個線段選擇一個未匹配且包含于該線段的一個點進行匹配，求最大匹配數。

\(70pts\)：
線段樹優化建圖求二分圖最大匹配。

\(100pts\)：
\(Sol1\)：
點從小到大排序，線段按左端點從小到大排序；
從小到大枚舉所有點，把左端點在該點左邊的線段放入堆 (右端點為關鍵字的小根堆) 中；
檢查堆頂的右端點是否在當前枚舉到的點的右邊，若是，將改點與堆頂線段匹配；否則，重復上述過程，直至條件成立或堆為空。
對于第 \(i\) 個點，只有在它右邊的點會被影響，為了使右邊的點有更多線段可以選擇，所以選右端點最靠左的。
\(Sol2\)：
線段按右端點從小到大排序，點放入樹狀數組；
枚舉每一條線段，每條線段選擇盡量靠左的點。
和 \(Sol1\) 一樣。

代碼如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int in() {int x = 0; char c = getchar(); bool f = 0;while (c < '0' || c > '9')f |= c == '-', c = getchar();while (c >= '0' && c <= '9')x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }const int N = 2e5 + 5;
struct node {int l, r;inline bool operator < (const node &b) const {return this->r > b.r;}
} a[N];
int n, m, t[N];inline bool cmp(const node &i, const node &j) {return i.l < j.l;
}int main() {//freopen("in", "r", stdin);freopen("dream.in", "r", stdin);freopen("dream.out", "w", stdout);n = in(), m = in();for (int i = 1; i <= n; ++i)a[i] = (node){in(), in()};for (int i = 1; i <= m; ++i)t[i] = in();std::sort(a + 1, a + 1 + n, cmp);std::sort(t + 1, t + 1 + m);std::priority_queue <node> q;int pos = 1, res = 0;for (int i = 1; i <= m; ++i) {while (pos <= n && a[pos].l <= t[i]) {if (a[pos].r >= t[i])q.push(a[pos]);++pos;}while (!q.empty() && q.top().r < t[i])q.pop();if (!q.empty() && q.top().r >= t[i])++res, q.pop();}printf("%d\n", res);return 0;
}

T3、樹

一棵 \(n\) 個點的樹，給定 \(m \ (m \leq 10 ^ 5)\) 個點對(保證兩個點不同)，求不包含上述點對且點數大于一的簡單路徑。

\(Sol\)：
考慮求至少包含一組點對的路徑數量。
把一條路徑的端點放在二維平面上，一個點就可以代表一條路徑；
對于一個點對 \(u, v\)：
若兩點有祖先-后代關系(\(u\) 為 \(v\) 的祖先)，則可選的路徑兩端點范圍分別為 \(v\) 的子樹、除了 \(u\) 包含 \(v\) 的子樹的其它所有點。
若兩點沒有祖先-后代關系，則可選的路徑兩端點范圍分別為 \(u\) 的子樹、\(v\)的子樹。
按 \(dfs\) 序放在平面上，變成一個掃描線求矩形覆蓋面積的題，線段樹維護即可。
線段樹的維護：可以 \(push \_ down\) 也可以不用，前者可擴展性更強，由于掃描線刪除的線段一定加入過，所以并不用 \(push \_ down\)。

代碼如下：

//#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
int in() {int x = 0; char c = getchar(); bool f = 0;while (c < '0' || c > '9')f |= c == '-', c = getchar();while (c >= '0' && c <= '9')x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }const int N = 1e5 + 5;struct edge {int next, to;
} e[N << 1];
int ecnt = 1, head[N];inline void jb(const int u, const int v) {e[++ecnt] = (edge){head[u], v}, head[u] = ecnt;e[++ecnt] = (edge){head[v], u}, head[v] = ecnt;
}//heavy-light deposition begin
int siz[N], hson[N], fa[N], dep[N], fro[N], dfn[N];
void dfs_h(const int u) {siz[u] = 1;for (int i = head[u]; i; i = e[i].next) {int v = e[i].to;if (v == fa[u])continue;fa[v] = u, dep[v] = dep[u] + 1;dfs_h(v);siz[u] += siz[v];if (siz[v] > siz[hson[u]])hson[u] = v;}
}void dfs_f(const int u, const int tp) {dfn[u] = ++dfn[0], fro[u] = tp;if (hson[u])dfs_f(hson[u], tp);for (int i = head[u]; i; i = e[i].next)if (e[i].to != fa[u] && e[i].to != hson[u])dfs_f(e[i].to, e[i].to);
}
int lca(int u, int v) {while (fro[u] != fro[v]) {if (dep[fro[u]] > dep[fro[v]])std::swap(u, v);v = fa[fro[v]];}return dep[u] < dep[v] ? u : v;
}
int find_son(int u, int v) {while (fro[v] != fro[u]) {v = fro[v];if (fa[v] == u)return v;v = fa[v];}return hson[u];
}
//heavy-light deposition endint n, m;typedef std::pair<int, int> pii;
std::vector<pii> a[N][2];struct segment_tree {int sum[N << 2], cnt[N << 2];void push_up(int p, int tl, int tr) {if (cnt[p])sum[p] = tr - tl + 1;else if (tl == tr)sum[p] = 0;elsesum[p] = sum[p << 1] + sum[p << 1 | 1];}void modify(int l, int r, int k, int tl = 1, int tr = n, int p = 1) {if (l <= tl && tr <= r) {cnt[p] += k;push_up(p, tl, tr);return ;}int mid = (tl + tr) >> 1;if (mid >= l)modify(l, r, k, tl, mid, p << 1);if (mid < r)modify(l, r, k, mid + 1, tr, p << 1 | 1);push_up(p, tl, tr);}
} T;int main() {//freopen("in", "r", stdin);freopen("tree.in", "r", stdin);freopen("tree.out", "w", stdout);n = in(), m = in();for (int i = 1; i < n; ++i)jb(in(), in());dfs_h(3), dfs_f(3, 3);for (int i = 1, u, v, w; i <= m; ++i) {u = in(), v = in(), w = lca(u, v);if (dfn[u] > dfn[v])std::swap(u, v);if (w == u) {w = find_son(u, v);a[1][0].push_back(pii(dfn[v], dfn[v] + siz[v] - 1));a[dfn[w]][1].push_back(pii(dfn[v], dfn[v] + siz[v] - 1));a[dfn[v]][0].push_back(pii(dfn[w] + siz[w], n));a[dfn[v] + siz[v]][1].push_back(pii(dfn[w] + siz[w], n));} else {a[dfn[u]][0].push_back(pii(dfn[v], dfn[v] + siz[v] - 1));a[dfn[u] + siz[u]][1].push_back(pii(dfn[v], dfn[v] + siz[v] - 1));}}long long res = 1ll * n * (n - 1) / 2;for (int i = 1; i < n; ++i) {for (unsigned j = 0; j < a[i][0].size(); ++j)T.modify(a[i][0][j].first, a[i][0][j].second, 1);for (unsigned j = 0; j < a[i][1].size(); ++j)T.modify(a[i][1][j].first, a[i][1][j].second, -1);res -= T.sum[1];}printf("%lld\n", res);return 0;
}

轉載于:https://www.cnblogs.com/15owzLy1-yiylcy/p/11321993.html