T1
洛谷 P10564 Rubbish Sorting
发现长度很小，考虑二进制枚举所有非匹配位。一个给定的字符串会构成一些模板，比如 \(\texttt{abc}\) 能产生模板 \(\texttt{abc}, \texttt{a_c}, \texttt{ab_}, \texttt{_bc}, \texttt{a_}, \texttt{_b}, \texttt{a}, \texttt{_}\) 等。对于一个查询的串，实际上是找所有匹配它的模板里通配符最少且类型最小的。我们考虑把所有模板扔进一个类似 trie 的结构里，这是一棵完全 \(27\) 叉树，每个点向儿子连的边有 \(26\) 个英文字母与通配符。每个模板扔进来时在经过的结点上留下其类型。每个串查询的时候在经过的结点上寻找答案。由于此题中两个串匹配还需要其中至少一个是完整的长度，所以每个节点还要开两种值用来记录。
代码
#include <iostream>
#include <cassert>
using namespace std;
bool bg;
string Str;
int mxp, ans;
int T;
struct Trie {
int val[20000005][2];
void Insert(int x, int p) {
int b = (p == Str.size());
if (val[x][b] == 0)
val[x][b] = T;
else
val[x][b] = min(val[x][b], T);
if (p == Str.size())
return;
// assert(x <= 27 * 27 * 27 * 27 * 27);
int c = Str[p] - 'a' + 1;
Insert(x * 27 + c, p + 1);
Insert(x * 27 + 27, p + 1);
}
void Query(int x, int p, int cnt) {
int b = (p == Str.size());
if (p - cnt == mxp) {
if (val[x][1])
ans = min(val[x][1], ans);
if (b && val[x][0])
ans = min(ans, val[x][0]);
// cout << "getans " << ans << " " << b << " " << mxp << "\n";
} else if (p - cnt > mxp) {
int tmp = 2147483647;
if (val[x][1]) {
tmp = min(tmp, val[x][1]);
mxp = p - cnt;
}
if (b && val[x][0]) {
tmp = min(tmp, val[x][0]);
mxp = p - cnt;
}
if (tmp != 2147483647)
ans = tmp;
}
if (p == Str.size())
return;
int c = Str[p] - 'a' + 1;
// cout << c << "\n";
Query(x * 27 + c, p + 1, cnt);
// cout << "- " << c << "\n";
// cout << "_\n";
Query(x * 27 + 27, p + 1, cnt + 1);
// cout << "-_\n";
}
} trie;
bool ed;
int main() {
cerr << (&ed - &bg) / 1024.0 / 1024.0 << "\n";
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
int q;
cin >> q;
while (q--) {
int s;
cin >> s;
if (s == 1) {
cin >> Str >> T;
trie.Insert(0, 0);
} else {
cin >> Str;
mxp = -1, ans = 2147483647;
trie.Query(0, 0, 0);
cout << ans << "\n";
}
}
return 0;
}
T2
洛谷 P5572 Sirtet
考虑对于每个连通块标号。每个连通块向处在其直接上方的所有连通块连边，边权是这两个连通块有直接上下关系的最小距离。假设最下层也有一个连通块，以最下层的连通块为源点跑最短路，每个连通块代表的点的距离即为其在结束的时候下落的距离。于是可以求出最后的情况。
本质上是当所有连通块都没有接触地面时，每次每个连通块下落一格，在图上体现为所有与源点相连的边边权减少 \(1\)。当一个点与源点距离为 \(0\) 时，代表这个连通块落地，成为新的“源点”，然后以此类推，直到所有连通块落地。可以发现这样的情况下每个点停下时下落的距离就是源点到它的最短路。
代码
#include <iostream>
#include <string.h>
#include <queue>
#include <map>
using namespace std;
int n, m;
bool a[10000005];
int f(int x, int y) { return x * m + y; }
int v[10000005];
int ncnt;
void dfs(int x, int y, int id) {
if (!x || !y || x > n || y > m)
return;
v[f(x, y)] = id;
a[f(x, y)] = 0;
if (a[f(x - 1, y)])
dfs(x - 1, y, id);
if (a[f(x + 1, y)])
dfs(x + 1, y, id);
if (a[f(x, y - 1)])
dfs(x, y - 1, id);
if (a[f(x, y + 1)])
dfs(x, y + 1, id);
}
map<pair<int, int>, int> mp;
int head[10000005], nxt[20000005], to[20000005], ew[20000005], ecnt;
void add(int u, int v, int ww) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, ew[ecnt] = ww; };
int ans[10000005];
struct node {
int x, dis;
};
bool operator<(node a, node b) { return a.dis > b.dis; }
priority_queue<node> q;
int dist[10000005];
bool vis[10000005];
void dijkstra(int S) {
q.push((node) { S, 0 });
memset(dist, 63, sizeof dist);
dist[S] = 0;
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.x;
if (vis[x])
continue;
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (dist[v] > dist[x] + ew[i])
q.push((node) { v, dist[v] = dist[x] + ew[i] });
}
}
}
int main() {
// freopen("B.in", "r", stdin);
// freopen("B.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
for (int j = 1; j <= m; j++)
a[f(i, j)] = (str[j - 1] == '#');
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (a[f(i, j)] && !v[f(i, j)])
dfs(i, j, ++ncnt);
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++)
// cout << v[f(i, j)] << " ";
// cout << "\n";
// }
for (int j = 1; j <= m; j++) {
int lclr = -1, lpos = -1;
for (int i = 1; i <= n; i++) {
if (v[f(i, j)] != 0) {
int c = v[f(i, j)];
if (lclr != c && lclr != -1) {
pair<int, int> p = make_pair(c, lclr);
if (!mp.count(p))
mp[p] = i - lpos - 1;
else
mp[p] = min(mp[p], i - lpos - 1);
// cout << c << " " << lclr << " " << i - lpos - 1 << "\n";
}
lclr = c, lpos = i;
}
}
pair<int, int> p = make_pair(0, lclr);
if (!mp.count(p))
mp[p] = n - lpos;
else
mp[p] = min(mp[p], n - lpos);
// cout << 0 << " " << lclr << " " << n - lpos << "\n";
}
for (auto v : mp) {
// cout << v.first.first << " " << v.first.second << " " << v.second << "\n";
add(v.first.first, v.first.second, v.second);
}
dijkstra(0);
// for (int i = 1; i <= ncnt; i++) cout << dist[i] << "\n";
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (v[f(i, j)])
ans[f(i + dist[v[f(i, j)]], j)] = 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cout << (ans[f(i, j)] ? '#' : '.');
cout << "\n";
}
return 0;
}