T1
树形DP，\(f_{u,1}\) 表示染了 \(k-1\) 种颜色，可以向上连边，\(f_{u,2}\) 表示染了 \(k\) 种颜色，转移式用优先队列维护即可。
一开始总想只用一维表示状态，后悔啊！这启示我们如果难处理的可以多记一维。
code
void dfs(int u, int p) {priority_queue<edge> q;for (edge &e : G[u]) {if (e.v == p) continue;dfs(e.v, u);q.push({e.v, dp[e.v][1] + e.w - dp[e.v][0]});}int cnt = 0;while (!q.empty()) {edge e = q.top(); q.pop();if (cnt < k && e.w > 0) dp[u][0] += e.w + dp[e.v][0];else dp[u][0] += dp[e.v][0];if (cnt < k - 1 && e.w > 0) dp[u][1] += e.w + dp[e.v][0];else dp[u][1] += dp[e.v][0];cnt++; }
}T2
一道概率题，我们发现我们只关心不同的颜色有多少种，以及他们的个数，我们并不在意他们是什么颜色，因为他们实质上是一样的。看到 \(k\) 这个数据范围想到矩阵乘法加速，于是考虑构建转移矩阵，具体看代码。
code
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define out() (cout << "sb\n")constexpr int mod = 1e9 + 7, M = 45;int n, k, cnt;
ll t;struct mat {ll m[M][M];mat() {memset(m, 0, sizeof(m));};void init() {for (int i = 1; i <= cnt; i++) m[i][i] = 1;}
}base, res;
mat operator * (const mat &a, const mat &b) {mat c;for (int i = 1; i <= cnt; i++) for (int k = 1; k <= cnt; k++) if (a.m[i][k])for (int j = 1; j <= cnt; j++)(c.m[i][j] += a.m[i][k] * b.m[k][j] % mod) %= mod;return c;
}
mat mpow(mat a, ll b) {mat ans; ans.init();for (; b; b >>= 1) {if (b & 1) ans = ans * a;a = a * a;}return ans;
}
ll qpow(ll a, ll b) {ll ans = 1;for (; b; b >>= 1) {if (b & 1) ans = ans * a % mod;a = a * a % mod;}return ans;
}
vector<int> temp, v[M];
void dfs(int now, int lst) {if (!now) {v[++cnt] = temp;return;} for (int i = lst; i <= now; i++) {temp.push_back(i);dfs(now - i, i);temp.pop_back();}
}
int main() {// system("fc paint.out temp.out");// freopen("paint.in", "r", stdin);// freopen("paint.out", "w", stdout);IOS;cin >> n >> t >> k;if (n == k) {cout << qpow(qpow(n, mod - 2), t) << "\n";return 0;} dfs(n, 1);for (int i = 1; i <= cnt; i++) {ll now = 0;for (int &j : v[i]) now += j * j;base.m[i][i] = now;for (int j = 0; j < v[i].size(); j++) {for (int k = 0; k < v[i].size(); k++) if (j != k) { //j->kvector<int> tem;for (int l = 0; l < v[i].size(); l++) if (l != j && l != k) tem.push_back(v[i][l]);if (v[i][j] != 1) tem.push_back(v[i][j] - 1);tem.push_back(v[i][k] + 1);sort(tem.begin(), tem.end());int pos = 1;while (v[pos] != tem) pos++;base.m[i][pos] += v[i][j] * v[i][k];}}}// for (int i = 1; i <= cnt; i++) // for (int j = 1; j <= cnt; j++) // cout << base.m[i][j] << " \n"[j == cnt]; res = mpow(base, t);ll ans = 0;for (int i = 1; i <= cnt; i++) if (v[i].size() >= k) ans = (ans + res.m[1][i]) % mod;// for (int i = 1; i <= cnt; i++) cout << res.m[1][i] << "\n";cout << ans * qpow(qpow(n * n, t), mod - 2) % mod << "\n";return 0;
}
T3
首先把字符串翻转，\(pre_i\)表示前缀，变成求最小长度 \(len\)使得 \(\forall 1\le i<j\le n\)，\(pre_i\) 和 \(pre_j\) 有长度为 \(len\) 的子序列不相同。
我们一次枚举每个 \(i\)，考虑用栈维护当前所选的以 \(i\) 为结尾子序列，记录的是位置。 \(last_{ch_i}\) 记录上一个 \(ch_i\) 出现的位置，我们发现如果当前栈顶的下一个位置 \(\ge last_{ch_i}\)，那么去掉栈顶，新的一定也是合法的，重复执行上述步骤，最后再加入 \(i\)，再统计答案。
这一段讲的有点抽象，一定要结合这代码看：
code
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define out() (cout << "sb\n")const int N = 3e6 + 5;string s;
int T, st[N], tp, lst[30], ans = 0;signed main() {cin >> T;while (T--) {cin >> s;int n = s.size();reverse(s.begin(), s.end());s = " " + s;// cout << s << "\n";for (int i = 1; i <= n; i++) {while (tp && st[tp - 1] >= lst[s[i] - 'a']) tp--; //找最小lst[s[i] - 'a'] = i;st[++tp] = i; //加入位置ans = max(ans, tp);// cout << tp << " ";}cout << ans << "\n";ans = tp = 0;for (int i = 0; i < 26; i++) lst[i] = 0;}return 0;
}
总结与展望
- T1 跟往常一样，试过很多假思路，要1h左右才能写过，往后还要加强快速切题能力。
- T2 是一道并不难的概率题，但我没怎么做过这种类型，矩阵乘法除了模板和斐波那契题几乎没写过，如果我冷静思考，感觉其实可以做出来，但是我从心底里畏惧去想去写，直接跳过去写 T3，心态这里让我说什么好呢？/wul
- T3 这道题初看被 \(O(n \log n)\) 的做法限死了，好在在江队的提醒下写出了 \(O(n)\) 做法，以后遇到 \(10^5\) 可不能只想带 \(\log\) 的了。