[BZOJ1789][BZOJ1830][Ahoi2008]Necklace Y型项链
试题描述
欢乐岛上众多新奇的游乐项目让小可可他们玩的非常开心。现在他们正在玩比赛串项链的游戏，谁串的最快就能得到优厚的奖品。这可不是普通的项链，而是一种Y型项链，项链的最中间有一颗大珍珠作为结合点，从大珍珠上连出来3条由各种宝石串起来的链子。比赛的规则是这样的：每次可以从三条链子中某一条的一端取下来一个宝石，或者安上去一个宝石，称为一次操作，经过若干次操作，最终使得三条链子完全相同。想要赢得比赛，那么只能使用尽量少的操作次数。假设每种宝石都有无数多个以供使用，且链子足够长。你能帮助小可可赢得比赛吗? 注：由于对Y型项链的宝石数没有特殊的要求，所以即使你把所有宝石都取下来，也是一个可以接受的方案(三根没有串宝石的绳子也是完全一样的)
输入
一共有3行，表示Y型项链的三条链子，每行开始有一个数字N，表示初始时这条链子上串有N个宝石(N<=50)，随后是一个空格，然后是N个'A'和'Z'之间的字符，表示这个链子上的宝石，每个字母表示一种不同的宝石，这个字符串最左边的字符表示的是离大珍珠最近的那个宝石，而最右边的表示的是在链子末端的宝石
输出
只有一个整数，表示所需要的最少的操作次数．
输入示例
CAT
TAC
CATCH
输出示例
数据规模及约定
见“输入”
题解
使劲贪心。建立 Trie 树，若有一个节点有三个儿子直接把三个分叉砍掉；若两个节点都有两个儿子，则深度大的节点的两个分叉都砍掉，深度小的把向“旁边”（自己理解一下）伸出的分叉砍掉再接上一段。。。大概就是这样。。。证明不难，意会一下就好了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; #define maxn 200
#define maxs 29
int ToT = 1, ch[maxn][maxs], cnb[maxn], dep[maxn], siz[maxn], ps[3], cnt; int idx(char c) { return c - 'A'; } int clo, L[maxn], R[maxn];
void build(int u) {
siz[u] = 1;
L[u] = ++clo;
for(int i = 0; i < maxs; i++) if(ch[u][i])
build(ch[u][i]), siz[u] += siz[ch[u][i]];
R[u] = ++clo;
return ;
} int main() {
char tc = getchar();
while(!isalpha(tc)) tc = getchar();
int u = 1, x;
while(isalpha(tc)) {
x = idx(tc);
if(!ch[u][x]) ch[u][x] = ++ToT, cnb[u]++, dep[ch[u][x]] = dep[u] + 1;
u = ch[u][x];
tc = getchar();
}
x = 26;
if(!ch[u][x]) ch[u][x] = ++ToT, cnb[u]++, dep[ch[u][x]] = dep[u] + 1;
while(!isalpha(tc)) tc = getchar();
u = 1;
while(isalpha(tc)) {
x = idx(tc);
if(!ch[u][x]) {
ch[u][x] = ++ToT; cnb[u]++; dep[ch[u][x]] = dep[u] + 1;
if(cnb[u] == 2) ps[++cnt] = u;
}
u = ch[u][x];
tc = getchar();
}
x = 27;
if(!ch[u][x]) {
ch[u][x] = ++ToT; cnb[u]++; dep[ch[u][x]] = dep[u] + 1;
if(cnb[u] == 2) ps[++cnt] = u;
}
while(!isalpha(tc)) tc = getchar();
u = 1;
while(isalpha(tc)) {
x = idx(tc);
if(!ch[u][x]) {
ch[u][x] = ++ToT; cnb[u]++; dep[ch[u][x]] = dep[u] + 1;
if(cnb[u] == 2) ps[++cnt] = u;
}
u = ch[u][x];
tc = getchar();
}
x = 28;
if(!ch[u][x]) {
ch[u][x] = ++ToT; cnb[u]++; dep[ch[u][x]] = dep[u] + 1;
if(cnb[u] == 2) ps[++cnt] = u;
}
build(1); if(cnt == 1) printf("%d\n", siz[ps[1]] - 4);
else {
int a = ps[1], b = ps[2], ans = 0;
if(dep[a] < dep[b]) swap(a, b);
for(int i = 0; i < maxs; i++) if(ch[b][i] && (L[ch[b][i]] > R[a] || L[a] > R[ch[b][i]])) {
ans += siz[ch[b][i]] + dep[a] - dep[b]; break;
}
ans += siz[a] - 1;
printf("%d\n", ans - 3);
} return 0;
}
/*
32 ABNXKSKDNSKGJSLKJSHSDJKHGJSXDJFS
21 ABNXKJSLKJSHSDJKHGJSX
32 ABNXKSKDNSKGJSLKJSHSDJKHGJSXDJFS 5 ABCBA
4 ABDB
5 ABCBA
*/