Бодлогын өгүүлбэрийг ЭНД дарж Монголоор уншина уу.
Trie:
Энэ нь бусад модтой адил төрлийн өгөгдөлийн бүтэц. Хоёртын хайлтын мод нь модны орой бүр 2 хүүтэй байдаг бол Траэй нь орой бүр тухайн бодлогоосоо шалтгаалаад хэдэн ч хүү-оройтой байж болно. Бидний бодлогын хувьд жижиг латин цагаан толгойн үсэгнүүд байж болох тул орой бүр 26-н хүүтэй. Траэй модны үндэс нь ганцаараа хоосон байна. Доор зургаар дэлгэрэнгүй тайлбарлая.
TREE
TRIE
ALL
ALSO
ALGO
ASSOC
Эдгээр үгнүүд хэрхэн Траэй модонд нэмэгдсэн байгааг харж байгаа байх. Траэй модонд үг нэмэх, хасах, хайх үйлдэл бүгд шугаман буюу O(N) байхыг хялбархан харж болно.
Бодлогоруугаа эргээд оръё. Бидний зорилго бүх үгийг хэвлэх, хэвлэхдээ хамгийн цөөн үйлдлээр. Мөн хамгийн сүүлд хэвлэсэн үгний дараа устгах үйлдэл хийлгүй шууд програм зогсох ёстой. Тэгвэл бидэнд гарч ирэх асуудлууд:
үсэг хэвлэх машин дээр тавина гэдэг юу гэсэн үг вэ?
хэвлэх машин дээрх үсэгнүүдийг хэвлэнэ гэдэг маань юу гэсэн үг вэ?
хэвлэх машинаас үсэг устгах нь юу гэсэн үг вэ?
Эдгээр асуултуудын хариултыг Траэй модны үндсэн үйлдэлүүд л хариулчихна. Модондоо гүний нэвтрэлт хийе. Нэвтрэлт хийн тухайн түвшинээс нэг түвшин доошлоно гэдэг нь хэвлэх машин дээр тухайн үсгийг тавьж байна, гүний нэвтрэлт буцалтаа хийх буюу тухайн түвшингийн дээр байрлах эцэг орой руу очино гэдэг нь хэвлэх машинаас үсэг устгахтай адил '-' команд. Харин үсэгүүдийг хэвлэнэ гэдэг нь нэг бүтэн үг олсон эсвэл модны навч дээр очсон тохиолдолд 'P' команд биелэгдэнэ. Бидний гол асуудал хамгийн цөөн үйлдэлээр бүх үгийг хэвлэх. Траэй модондоо гүний нэвтрэлт хийгээд, хэвлээд хамгийн сүүлд хэвлэгдсэн үгний дараа буцаад устгах шаардлага байхгүй.
Тэгвэл хамгийн сүүлд ямар үгийг хэвлэх ёстой вэ? Хариулт мэдээж хамгийн урт үгийг. Хамгийн урт үгийг хамгийн сүүлд хэвлэсэн л бол өмнөх үгнүүдийг ямар ч дарааллаар хэвлэсэн бодлогын хариуг өөрчилж чадахгүй. Яагаад? Энэ нь биднарт хамгийн урт үгнээс бусад бүх үгнүүдийг санаа зоволтгүй гүний нэвтрэлт хийгээд хэвлэх боломж олгоно.
Бид мод дээр үйлдэл хийж байгаа, хамгийн урт үгэнд орж байгаа үсэгнүүдээс бусад үсэг бүгд яг 2 удаа ашиглагдана, хэвлэх машин дээр өрөх мөн хэвлэх машинаас устгах. Тэгвэл одоо гарч ирэх асуудал хэрхэн хамгийн урт үгээ Траэй модноос ялгаж хамгийн сүүлд хэвлэх вэ?
Гүний нэвтрэлт хийгээд хамгийн урт үгээ олж байгаад хамгийн урт үгэнд орж байгаа оройнуудыг тэмдэглэчихэж болно. Тэгээд Траэй хэвлэх үйлдэлдээ нэмэлт ганц нөхцөл нэмээд, энэ нөхцөл нь мэдээж тэмдэглэгдээгүй орой байх. Хамгийн урт үгийг бүтэн модондоо гүний нэвтрэлт хийснээс, өгөгдөлөө уншихдаа хамгийн урт үгийг олж байгаад мөн бүх үгнүүд модонд тэмдэглэгдсэний дараа хайлт хийж тэмдэглэсэн нь хамаагүй хурдан. Яагаад?
Үг нэмэхдээ анхаарах зүйл бол ямар нэгэн бүтэн үг нэмсэн л бол тухайн үгний сүүлийн үсгийг бүтэн үг эсвэл навч гэдэгийг тэмдэглэх ёстой. Ингэснээр бид хэвлэх командаа төвөггүйхэн хийж чадна. Жишээ нь доорх өгөгдлийг бодоод үзээрэй.
2
aabc
aabcde
Энэ үед хариу нь:
8
a
a
b
c
P
d
e
P
Мөн энэ жишээнээс би яагаад шууд дан ганц навч гээд хэлчихээгүй харах байх. C++ дээрх кодыг тавьлаа, гэхдээ энэ удаад өгөгдөлийн бүтэц, санах ойтой харьцаж байгаа тул арай доод түвшний код байх болно, гэхдээ хурдхан шиг аль болох учирыг нь олж сурах хэрэгтэй.
//Trie
//IOI 2008 Type Printer.
//by Baska.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#define mp make_pair
#define pb push_back
using namespace std;
long long toint(string s) { istringstream in(s); long long x; in>>x; return x; }
template<class T> string tostring(T x) { ostringstream out; out<<x; return out.str();}
inline int convertIn(char ch){ return ch-'a'; }
inline char convertOut(int v){ return v+'a'; }
int total;
struct trie{
bool isLast;
bool isLeaf;
trie *next[26];
trie(){
for(int i=0; i<26; i++)
next[i] = NULL;
isLast = 0;
isLeaf = 0;
}
};
inline void insert(trie* root, char *str, int len){
for(int k, i=0; i<len; i++){
k = convertIn(str[i]);
if(root->next[k]==NULL){
root->next[k] = new trie();
total += 2;
}
root = root->next[k];
}
root->isLeaf = 1;
}
inline void printTrie(trie *root){
for(int i=0; i<26; i++){
if(root->next[i]!=NULL&&!root->next[i]->isLast){
printf("%c\n", convertOut(i));
if(root->next[i]->isLeaf)
printf("P\n");
printTrie(root->next[i]);
printf("-\n");
}
}
}
inline void searchAndMark(trie *root, char *word){
for(int i=0, len = strlen(word); i<len; i++){
int k = convertIn(word[i]);
root->next[k]->isLast = 1;
root = root->next[k];
}
}
int main(int argc, char *argv[]){
int n;
char longestWord[22];
scanf("%d", &n);
total = n;
trie *root = new trie();
while(n--){
char word[22];
scanf("%s", word);
if(strlen(word)>strlen(longestWord))
strcpy(longestWord, word);
insert(root, word, strlen(word));
}
searchAndMark(root, longestWord);
printf("%d\n", total-strlen(longestWord));
printTrie(root);
for(int i=0, len = strlen(longestWord); i<len; i++){
printf("%c\n", longestWord[i]);
int k = convertIn(longestWord[i]);
printTrie(root->next[k]);
if(root->next[k]->isLeaf)
printf("P\n");
root = root->next[k];
}
return 0;
}
Арлууд бодлогын Монгол өгүүлбэрийг ЭНД дарж уншина уу.
Бидэнд чиглэлгүй жинтэй граф комфонентууд өгөгдсөн. Компонент бүр хамгийн ихдээ ганц цикл агуулна. Тэгвэл компонент бүрийн диаметрүүдийн нийлбэрийг ол гэсэн бодлого.
Бодлого энгийн хоёр тохиолдолтой. Комфонент цикл агуулсан, агуулаагүй.
Цикл агуулаагүй комфонент нь мод байна. Модны диаметрийг олохдоо дурын А оройноос нэвтрэлт хийн, гүний, түвшний аль нь ч болно, хамгийн хол орших оройг В гэе, В оройгоос дахин нэвтрэлт хийн хамгийн хол С орой дээр ирсэн гэж үзвел сүүлийн С-ээс В хүртлэх жин нь тухайн модны диаметр болно.
Цикл агуулсан үед:
Тухайн N оройтой компонент яг N ширхэг ирмэгтэй байна гэсэн үг, яагаад? ямар нэгэн ирмэгийг хасая, N-1 ирмэгтэй мод үүсгэн, энэ модны диаметрийг дээрх аргаар олж болно O(N)-д. Тэгвэл бүх ирмэгийг хасаж үзээд хагийн урт диаметртэй модыг сонгох замаар бодвол бодолт O(N^2) болно. Энэ бодолт 40% тэст давна.
Арай хурдан бодолт олох гэж үзье.
Тухайн компонент дахь цикл нь С урттай мөн V1, V2, V3,...,Vc гэсэн оройнуудтай байг.
Тэгвэл тухайн цикл-д харьялагдаж байгаа орой бүрийг ямар нэгэн мондын үндэс болгоё. Гэхдээ анхаарах зүйл энэ үндэс нь тухайн цикл-д агуулагдаж байгаа аль ч оройг өөрийн хүү болгон авах ёсгүй. Тэгвэл зарим тохиолдолд зөвхөн ганцхан оройтой, үндэстэй, мод үүсэж болно. Дээрх жишээнд V3, V4, V6, V7-оос бусад нь бүгд ганцхан үндэстэй мод болох нь. Бид эдгээр моднуудын уртыг олчиж чадна, энэ удаад хоёр нэвтрэлт хийх хэрэггүй, яагаад гэвэл зөвхөн Vi-дээр энэ модны орой байгаа учир бид энэ оройгоос хамгийн хол орших оройн хоорондахь жинг л сонирхож байгаа, үүнийг модны өндөр ч гэж нэрлэж болно, энэ өндөрийг Ki гэе, Vi дээр оройтой модны өндөр. Яг ийм компоненттэй үед бодлогын хариу маань ямар нэгэн хоёр модны жингүүдийн мөн тухайн хоёр модны, энэ хоёр модны үндэс нь цикл дээр байраа, үндэснүүдийн хоорондах зайн нийлбэрийг максимумчилна.
Одоо тэгвэл тухайн хоёр модны үндэсний хоорондахь зай хэрхэн гарж болохыг харъя.
Vi, Vj ( i < j ) гэе. Vi-ээс Vj-рүү хоёр янзаар очиж болно.
1: Vi, Vi+1, Vi+2, .. , Vj-1, Vj.
2: Vi, Vi-1, Vi-2, .. , Vc, Vc-1, .. , Vj+1, Vj. Яагаад?
Wi-ээр Vi-ээс Vi+1-р оройн хоорондахь жинг тэмдэглэвэл дээрх хоёр замын жин маань:
1: Wi + Wi1 + , .., Wj-1,
2: Wi-1 + Wi-2 + , .., Wc-1 + ,.., Wj = Wj + Wj+1 + .. + Wc + .. + Wi-1.
Тухайн циклийхаа жинг Wc гэвэл дээрх хоёр замын жингийн нийлбэр Wc байна. Яагаад?. Мөн цикл дээрх дурын хоёр оройн хоорондахь жин нь циклийхаа жинг хэсэгчилж байгааг харж байгаа байх. Si-ээр Vi хүртлэх жингүүдийн нийлбэрийг дараах байдлаар тодорхойлоё. S1 = 0, Si = S(i-1) + Wi. Тэгвэл дээрх хоёр нийлбэр маань дараах нийлбэртэй тэнцүү:
(1) = Sj - Si.
(2) = Wc - (Sj-Si). Энд мэдээж циклийн оройнууд дээр ярьж байгаа ба i < j байна.
Тэгвэл бид дараах хариуг л олох гээд байгаа юм: max{Ki+Kj+max(Sj‐Si,S‐(Sj‐Si))} ( i < j ).
Үүнийг бүх хосуудаас максимумыг олох замаар үзвэл O(C^2) бодолт болох ба кодоо хэрхэн цэвэх бичсэнээс шалтгаалт нийт онооны 60-80%-г авч чадна. Бүтэн бодолт O(C)-д хийх ёстой, үүнийг бэлтгэл хийж байгаа хүүхдүүд, мөн сонирхон бодож байгаа хүмүүст өөрсөд нь үлдээе.
