T1
路径
注意到颜色出现的顺序并不重要，于是考虑状压，设 \(f_{x, S}\) 表示从 \(x\) 开始，经过的颜色集合为 \(S\) 的方案数。外层枚举路径上经过了几条路径，然后枚举点转移即可。
代码
#include <iostream>
#define int long long
using namespace std;
int n, m, K;
int clr[300005];
int head[300005], nxt[600005], to[600005], ecnt;
inline void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int f[300005][40];
signed main() {
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
cin >> n >> m >> K;
for (int i = 1; i <= n; i++) cin >> clr[i], f[i][1 << (clr[i] - 1)] = 1;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
int ans = 0;
for (int i = 2; i <= K; i++) {
for (int j = 1; j < (1 << K); j++) {
if (__builtin_popcountll(j) != i)
continue;
for (int k = 1; k <= n; k++) {
if (!(j & (1 << (clr[k] - 1))))
continue;
for (int a = head[k]; a; a = nxt[a]) {
int v = to[a];
f[k][j] += f[v][j ^ (1 << (clr[k] - 1))];
}
ans += f[k][j];
}
}
}
cout << ans << "\n";
return 0;
}
T2
二分的代价
首先容易想到一个区间 dp，\(dp_{l, r}\) 表示搞定这个区间的最小代价，直接做是三次方。但是发现这个 dp 单调，而且值域很小，只有 \(160\) 不到，于是考虑互换值域和定义域，变成 \(f_{l, x}\) 表示用 \(x\) 的代价，从 \(l\) 开始最多能做到什么地方。这个地方直接做是平方乘 \(160\)，但是发现本质不同的转移只有 \(9\) 种，而且这个 dp 也是单调的，于是可以通过枚举转移点的代价简单做到 \(9 \times 160 \times n\)。就能过了。
代码
#include <iostream>
using namespace std;
string str;
int n;
int dp[105][105];
int f[100005][165];
int X = 160;
int x[100005][11];
int main() {
freopen("cost.in", "r", stdin);
freopen("cost.out", "w", stdout);
cin >> str;
n = str.size();
str = ' ' + str;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 9; j++) x[i][j] = x[i - 1][j];
x[i][str[i] - '0'] = i;
}
for (int i = 0; i <= X; i++) f[n + 1][i] = n + 1;
for (int l = n; l; l--) {
f[l][0] = l;
for (int k = 1; k <= X; k++) {
f[l][k] = f[l][k - 1];
for (int c = 1; c <= 9; c++) {
int r = x[f[l][k - c]][c];
f[l][k] = max(f[l][k], f[r + 1][k - c]);
}
}
}
for (int i = 0; i <= X; i++) {
if (f[1][i] >= n + 1) {
cout << i << "\n";
break;
}
}
return 0;
}
T3
放假
字符串匹配，先考虑 AC 自动机。考虑一个双向无限序列在 AC 自动机上的形态，发现一定是一条以环开始，以环结束的路径。由于不能出现给定串，则不能经过所有匹配状态。如果要不是 \(-1\) 的话，首先不能有任何两个环交于点，其次不能存在一条路径经过三个环。这些都强连通缩点之后随便判一下。在不是 \(-1\) 的情况下，答案即为环的个数 加上 以环开始，以另一个环结束的路径数量。这个在缩点后的 DAG 上直接数即可。
代码
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#define int long long
using namespace std;
bool bg;
int K, n;
int son[2000005][10], ncnt1;
bool ep[2000005];
int rt;
void Insert(string str) {
int p = rt;
for (int i = 0; i < (int)str.size(); i++) {
int& t = son[p][str[i] - 'a'];
p = (!t ? (t = ++ncnt1) : t);
}
ep[p] = 1;
}
queue<int> q;
int fail[2000005];
void getfail() {
for (int i = 0; i < K; i++) {
if (son[rt][i])
fail[son[rt][i]] = 0, q.push(son[rt][i]);
}
while (!q.empty()) {
int p = q.front();
q.pop();
for (int i = 0; i < K; i++) {
if (son[p][i])
fail[son[p][i]] = son[fail[p]][i], ep[son[p][i]] |= ep[son[fail[p]][i]], q.push(son[p][i]);
else
son[p][i] = son[fail[p]][i];
}
}
// for (int i = 0; i <= ncnt1; i++) ep[i] |= ep[fail[i]];
}
vector<int> G[110005], G2[110005], G3[110005];
int clr[110005], ine[110005], ccnt;
int csz[110005];
string s;
int dfn[110005], low[110005], ncnt;
int stk[110005], sz;
bool vis[110005];
void tarjan(int x) {
stk[++sz] = x;
dfn[x] = low[x] = ++ncnt;
vis[x] = 1;
for (auto v : G[x]) {
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
} else if (vis[v])
low[x] = min(low[x], dfn[v]);
}
if (low[x] == dfn[x]) {
++ccnt;
int t;
do csz[clr[t = stk[sz--]] = ccnt]++, vis[t] = 0;
while (t != x);
}
}
bool isl[110005];
bool tol[110005], frl[110005];
void dfs2(int x) {
vis[x] = 1;
for (auto v : G2[x]) {
if (!vis[v])
dfs2(v);
tol[x] |= (tol[v] | ine[v]);
}
}
void dfs3(int x) {
vis[x] = 1;
for (auto v : G3[x]) {
if (!vis[v])
dfs3(v);
frl[x] |= (frl[v] | ine[v]);
}
}
int val[110005];
void dfs4(int x) {
vis[x] = 1;
for (auto v : G2[x]) {
if (!vis[v])
dfs4(v);
val[x] += val[v];
}
}
string str[10005];
bool ed;
signed main() {
// cerr << (&ed - &bg) / 1024.0 / 1024.0 << "\n";
cin >> K >> n;
if (!n)
return 0 * puts(K == 1 ? "1" : "-1");
for (int i = 1; i <= n; i++) cin >> str[i], Insert(str[i]);
getfail();
for (int i = 0; i <= ncnt1; i++) {
if (ep[i])
continue;
for (int j = 0; j < K; j++) {
if (!ep[son[i][j]])
G[i].emplace_back(son[i][j]);
}
}
for (int i = 0; i <= ncnt1; i++) {
if (!dfn[i])
tarjan(i);
}
for (int i = 0; i <= ncnt1; i++) {
for (auto v : G[i]) {
if (clr[v] == clr[i])
ine[clr[v]]++;
else {
G2[clr[i]].emplace_back(clr[v]);
G3[clr[v]].emplace_back(clr[i]);
}
}
}
for (int i = 1; i <= ccnt; i++) {
if (csz[i] != 1 && csz[i] != ine[i])
return 0 * puts("-1");
}
for (int i = 1; i <= ccnt; i++) (!vis[i]) ? dfs2(i) : void();
memset(vis, 0, sizeof vis);
for (int i = 1; i <= ccnt; i++) (!vis[i]) ? dfs3(i) : void();
for (int i = 1; i <= ccnt; i++) {
if (ine[i] && frl[i] && tol[i])
return 0 * puts("-1");
}
for (int i = 1; i <= ccnt; i++) val[i] = (ine[i] != 0);
int ans = 0;
memset(vis, 0, sizeof vis);
for (int i = 1; i <= ccnt; i++) {
if (ine[i])
dfs4(i), ans += val[i];
}
cout << ans << "\n";
return 0;
}
T4
普及组题
普及组题都不会做了。
标签：110005,int,20241102,++,son,vis,str From： https://www.cnblogs.com/forgotmyhandle/p/18526724