文字列とハッシュ・セット
114253 ワード
わが校OJ:テストアドレス図書セットOJ:テストアドレス
Descriptionは2つの文字列s 1,s 2(大文字のみ)を与え、s 1がs 2に何回現れるかを求める.例えば、s 1=「ABA」、s 2=「ABAABA」で、答えは2です.
解題構想:KMPアルゴリズムのテンプレートは、拡張KMPで解決することもできます.コードの例:
Description図書管理は非常に煩雑な仕事であり、図書館には毎日多くの新刊書が参加している.図書をより便利に管理するために(本を借りたいお客様が必要な本があるかどうかを迅速に検索するのを助けるために)、図書検索システムを設計する必要があります.このシステムでは、2つの操作をサポートする必要があります. add(s)は、sという本が新たに加わったことを示す. find(s)は、sという本があるかどうかを問い合わせる.
解題構想:この問題はhashで解決するつもりだったが、私はサボって直接mapを使った.のコードの例:
Descriptionでは、長さ≦10^6の文字列がいくつか与えられ、各文字列が最大何個の同じサブ文字列で繰り返し接続されているかを尋ねます.例えば、abababは最大3つのabが接続されている.解題構想:本題はループ節問題であり,文字列sがある長さxのサブストリングループから構成されると,必ずs[1,n−x]=s[x,n]があると結論した.一方,nex配列の定義によれば,nex[n]はs[x,n]の長さn−xである.したがって、この問題に解がある場合、n%(n-nex[n])は0であり、答えはn/(n-nex[n])である.コード例:
Descriptionで指定されたいくつかの文字列(これらの文字列の総長≦4)×10^5)は,各文字列において,接頭辞であり接尾辞であるすべてのサブ列長を求める.例えば、ababcabababcababは、接頭辞であり、接尾辞でもある:ab、ababab、abababcabab、ababcababababcabab.
解題の構想:依然としてKMPアルゴリズムの中のnex配列を利用して解く.まず、この列自体が最も長い「接頭辞であり接尾辞である」サブ列であり、次の条件を満たすサブ列はs[1,nex[n],次はs[1,nex[nex[n]],....
道理は簡単だが、思い出すと少し回りくどい.長さxのサブ列son「接頭辞であり接尾辞である」が存在する場合、s[1,x]=s[n-x,n]=sonがある場合、その長さはnex[n]を超えないのではないでしょうか.したがって、上記の方法は、すべての可能な長さ(すべてのサブストリングではない!)を大きくから小さくまで巡回することができる.
コードの例:
Descriptionには3人の親友が一緒にゲームをするのが好きで、A君は次の文字列Sを書いて、B君はそれをコピーしてTを得て、C君はTの任意の位置(首尾を含む)に1つの文字を挿入してUを得る.今あなたはUを手に入れました.Sを見つけてください.
解題の構想:本題はnexあるいはhashで解くならば、細部は少し多くて、もちろん細心の注意を払うのは書くことができるはずです.私の解題の構想はとても簡単で、O(N)複雑度、主に以下の基本的な推論に基づいています: nが偶数の場合、解はありません. 前のn/2+1文字が1文字削除され、後のn/2文字に等しくなる場合、マッチングは成功する. 後n/2+1文字が1文字削除され、前n/2文字と同等になる場合、マッチングは成功する. 2 2と3の両方が一致に成功し、2つの得られた元の列が異なる場合、解は一意ではないことを示す.
コードの例:
Descriptionは、小文字の英字からなる文字列Sを与え、Sのあるサブストリングの最短ループ節に答えるようにq個の質問を与える.文字列Bが文字列Aの循環節である場合、AはBによって何度も繰り返されて得られる.
問題を解く構想:これは最短サイクルの問題で、また本題カードは常に非常に厳しい.本論文では,迅速に解くために,線形ふるい,スクロールハッシュ最適化などの戦略も用いた.
まず、文字列ループの知識に基づいています.文字列sがあるサブストリングループから得られる場合、|s|=nのループセグメントの長さは、最短ループセグメントを含むlenの約数であるに違いない.したがって、1つの戦略は、nのすべての約数に対して、最短サイクルセグメントの長さであるか否かを1つずつ判断することであり、判断原理は以下の通りである.文字列sの最短サイクルセグメント長がxである場合、必然的にs[1,x]=s[n−x,n]がある.
ハッシュテクニックをスクロールすることによってO(1)時間で判断を完了することができる.では、現在主に費やされている時間は、nの約数を探すことであり、一般的なやり方O(n)O(sqrt n)O(n)であり、このやり方の総複雑度はO(q n)O(qsqrt n)O(qn)である.
しかし、このカードは常に深刻で、タイムアウトします.そこで素因数分解定理を用いてO(l o g 2 n)O(log_2^n)O(log 2 n)時間内に約数分解を完了し,総時間複雑度はO(q l o g 2 n)O(q log_2^n)O(qlog 2 n)である.
コードの例:
Description Zxlは一度ネックレスを作ることにしました.彼女はとても安い価格で鮮やかなサンゴのビーズを買いました.彼女は今も機械を持っています.このビーズをたくさんの塊(子串)に切ることができます.1枚にk(k>0)のビーズがあります.もしこのビーズの長さがkの倍数でなければ、最後の1枚がkより小さいものは引っ張らないでください.(ncはもったいない)、ビーズの長さが正の整数であることを保証します.Zxlは多様なネックレスが好きで、彼女のためにどのように数字kを選んでできるだけ多くの異なる子列を得るべきかに好奇心を持っていて、子列はすべて反転することができて、言い換えれば、子列(1,2,3)は(3,2,1)と同じです.Zxlに最適なkを決定し、最も異なるサブストリングを得るプログラムを書く.例えば、この一連のビーズは、(1,1,1,2,2,3,3,1,2,3,3,1,2,2,1,3,2,1,2,3,3,1,2,3,3,1,3,3,3,1,2,2,1,3,3,2,1,2,k=1のとき,3つの異なる子列:(1),(2),(3)k=2のとき,6つの異なる子列:(1,1),(1,2,2),(2,2,2),(2,2,2),(3,3),(3,1,1),(2,3,3)k=3のとき,5つの異なる子列:(1,1,1,1),(2,2,2,2,2),(3,2,2,2,3),(3,2,2,2,3),(3,1,2,2)k=4のとき,5つの異なる子列:(1,1,1,1,1,1,2),(2,2,2,3,3,(3,2,2,2,2,2,3),(3,2(3,1,2,2),(1,3,3,2)
解題構想:最初は時間複雑度の計算が間違っていたが,n+n/2+n/3+n/4+...+1は調和級数であり,時間複雑度は高くないため,2層サイクルにローリングハッシュO(1)を加えた判断は速やかに通過できる.
コードの例:
Descriptionは、01文字列について、この文字列0と1を逆にしてから、その文字列全体を元の文字列と逆にすると、「反対称」文字列と呼ばれます.例えば00001111と010101は反対で、1001はそうではありません.次に、Nの長さの01文字列を与え、どのくらいのサブ列が反対称であるかを求める.
解題構想:01列の問題は本当に変化が多いですね.この問題を解決するには、まずいくつかの推論を出す必要があります.「反対称」の列長は偶数に違いない. サブストリングが「反対称」である場合、それは必ず中軸線に関し、左右01は対応する(例えば0101). もし1つの列が「反対称」であれば、それと共中軸線のサブ列も「反対称」である.
そして,エコー列の性質と少し似ていることが分かったが,2点だけ異なるのは,エコー列の長さが奇抜であり,エコー列は逆ではなく中軸対称であることである.
では、Manacherアルゴリズムを利用することができますが、判決などを「逆」に変更すればいいだけです.もちろん、ワイルドカード「#」で埋めます.すべての「反対称」の列の長さは偶数でなければならないので、「#」で計算して、長さが偶数であることを保証します.
コードの例:
Description既知数列a n,a 0=1 a_n, a_0 = 1 an,a0=1, a i + 1 = ( a i ∗ A + a i m o d B ) m o d C a_{i+1}=(a_i*A+a_i:mod:B):mod:C ai+1=(ai
解題構想:mapは遅すぎるでしょう.私は読み込み出力をテストして、乗算と型取りをテストしました.mapを疑っていません.多くの時間を無駄にしました.手書きhash関数は,隣接テーブルを用いて衝突を解消し,これでかなり速くなった.
コードの例:
Descriptionの異なる雪は往々にして異なる形をしている.北の学生は雪を集めて、南方の学生たちにプレゼントしたいと思っています.全部でn個の時刻があり,各時刻に雪が降る形状を与え,異なる整数で異なる形状を表す.収集の過程で、学生たちは繰り返しの雪があることを望んでいない.任意のa時刻から、b時刻に停止することができます.aからbまでの間の雪も集められる.彼らは収集した雪が一番多いことを望んでいる.
解題の構想:これはhashで少し書きにくくて、ハッシュ表を空にするのは難しいです.私は離散化+ダブルポインタを使っています.左境界を維持するだけでいいです.現在の雪が2回目に現れると、前回の出現位置がv[p]であることがわかるので、まず現在の区間長で答えを更新し、左境界をv[p]+1に更新します.正確性証明書は書かないのは明らかだ.
コードの例:
A. Oulipo
Descriptionは2つの文字列s 1,s 2(大文字のみ)を与え、s 1がs 2に何回現れるかを求める.例えば、s 1=「ABA」、s 2=「ABAABA」で、答えは2です.
解題構想:KMPアルゴリズムのテンプレートは、拡張KMPで解決することもできます.コードの例:
#include
",solve());
}
return 0;
}
B.図書管理
Description図書管理は非常に煩雑な仕事であり、図書館には毎日多くの新刊書が参加している.図書をより便利に管理するために(本を借りたいお客様が必要な本があるかどうかを迅速に検索するのを助けるために)、図書検索システムを設計する必要があります.このシステムでは、2つの操作をサポートする必要があります.
解題構想:この問題はhashで解決するつもりだったが、私はサボって直接mapを使った.のコードの例:
#includeC. Power Strings
Descriptionでは、長さ≦10^6の文字列がいくつか与えられ、各文字列が最大何個の同じサブ文字列で繰り返し接続されているかを尋ねます.例えば、abababは最大3つのabが接続されている.解題構想:本題はループ節問題であり,文字列sがある長さxのサブストリングループから構成されると,必ずs[1,n−x]=s[x,n]があると結論した.一方,nex配列の定義によれば,nex[n]はs[x,n]の長さn−xである.したがって、この問題に解がある場合、n%(n-nex[n])は0であり、答えはn/(n-nex[n])である.コード例:
#include
",n/(n-nex[n]));
}
int main(){
while(scanf("%s",str+1) && str[1] != '.'){
str[0] = '*';
solve();
}
return 0;
}
D. Seek the Name, Seek the Fame
Descriptionで指定されたいくつかの文字列(これらの文字列の総長≦4)×10^5)は,各文字列において,接頭辞であり接尾辞であるすべてのサブ列長を求める.例えば、ababcabababcababは、接頭辞であり、接尾辞でもある:ab、ababab、abababcabab、ababcababababcabab.
解題の構想:依然としてKMPアルゴリズムの中のnex配列を利用して解く.まず、この列自体が最も長い「接頭辞であり接尾辞である」サブ列であり、次の条件を満たすサブ列はs[1,nex[n],次はs[1,nex[nex[n]],....
道理は簡単だが、思い出すと少し回りくどい.長さxのサブ列son「接頭辞であり接尾辞である」が存在する場合、s[1,x]=s[n-x,n]=sonがある場合、その長さはnex[n]を超えないのではないでしょうか.したがって、上記の方法は、すべての可能な長さ(すべてのサブストリングではない!)を大きくから小さくまで巡回することができる.
コードの例:
#include
",ans[1]);
}
int main(){
//freopen("123.txt","r",stdin);
while(~scanf("%s",str+1)){
str[0] = '#';
solve();
}
return 0;
}
E. friends
Descriptionには3人の親友が一緒にゲームをするのが好きで、A君は次の文字列Sを書いて、B君はそれをコピーしてTを得て、C君はTの任意の位置(首尾を含む)に1つの文字を挿入してUを得る.今あなたはUを手に入れました.Sを見つけてください.
解題の構想:本題はnexあるいはhashで解くならば、細部は少し多くて、もちろん細心の注意を払うのは書くことができるはずです.私の解題の構想はとても簡単で、O(N)複雑度、主に以下の基本的な推論に基づいています:
コードの例:
#includeF. A Horrible Poem
Descriptionは、小文字の英字からなる文字列Sを与え、Sのあるサブストリングの最短ループ節に答えるようにq個の質問を与える.文字列Bが文字列Aの循環節である場合、AはBによって何度も繰り返されて得られる.
問題を解く構想:これは最短サイクルの問題で、また本題カードは常に非常に厳しい.本論文では,迅速に解くために,線形ふるい,スクロールハッシュ最適化などの戦略も用いた.
まず、文字列ループの知識に基づいています.文字列sがあるサブストリングループから得られる場合、|s|=nのループセグメントの長さは、最短ループセグメントを含むlenの約数であるに違いない.したがって、1つの戦略は、nのすべての約数に対して、最短サイクルセグメントの長さであるか否かを1つずつ判断することであり、判断原理は以下の通りである.
ハッシュテクニックをスクロールすることによってO(1)時間で判断を完了することができる.では、現在主に費やされている時間は、nの約数を探すことであり、一般的なやり方O(n)O(sqrt n)O(n)であり、このやり方の総複雑度はO(q n)O(qsqrt n)O(qn)である.
しかし、このカードは常に深刻で、タイムアウトします.そこで素因数分解定理を用いてO(l o g 2 n)O(log_2^n)O(log 2 n)時間内に約数分解を完了し,総時間複雑度はO(q l o g 2 n)O(q log_2^n)O(qlog 2 n)である.
コードの例:
#include
",ans);
}
void solve(){
/* hash ,v */
getPri(); bse[0] = 1;
for(int i = 1;i <= n;i++){
hsh[i] = hsh[i-1]*b + str[i]-'a';
bse[i] = bse[i-1]*b;
}
}
inline int read() {
int x=0,f=1; char c=getchar();
while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); }
while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); }
return x*f;
}
int main(){
n = read();
scanf("%s",str+1); str[0] = '#';
q = read();
solve();
for(int i = 1,l,r;i <= q;i++){
l = read(); r = read();
ask(l,r);
}
return 0;
}
G. Beads
Description Zxlは一度ネックレスを作ることにしました.彼女はとても安い価格で鮮やかなサンゴのビーズを買いました.彼女は今も機械を持っています.このビーズをたくさんの塊(子串)に切ることができます.1枚にk(k>0)のビーズがあります.もしこのビーズの長さがkの倍数でなければ、最後の1枚がkより小さいものは引っ張らないでください.(ncはもったいない)、ビーズの長さが正の整数であることを保証します.Zxlは多様なネックレスが好きで、彼女のためにどのように数字kを選んでできるだけ多くの異なる子列を得るべきかに好奇心を持っていて、子列はすべて反転することができて、言い換えれば、子列(1,2,3)は(3,2,1)と同じです.Zxlに最適なkを決定し、最も異なるサブストリングを得るプログラムを書く.例えば、この一連のビーズは、(1,1,1,2,2,3,3,1,2,3,3,1,2,2,1,3,2,1,2,3,3,1,2,3,3,1,3,3,3,1,2,2,1,3,3,2,1,2,k=1のとき,3つの異なる子列:(1),(2),(3)k=2のとき,6つの異なる子列:(1,1),(1,2,2),(2,2,2),(2,2,2),(3,3),(3,1,1),(2,3,3)k=3のとき,5つの異なる子列:(1,1,1,1),(2,2,2,2,2),(3,2,2,2,3),(3,2,2,2,3),(3,1,2,2)k=4のとき,5つの異なる子列:(1,1,1,1,1,1,2),(2,2,2,3,3,(3,2,2,2,2,2,3),(3,2(3,1,2,2),(1,3,3,2)
解題構想:最初は時間複雑度の計算が間違っていたが,n+n/2+n/3+n/4+...+1は調和級数であり,時間複雑度は高くないため,2層サイクルにローリングハッシュO(1)を加えた判断は速やかに通過できる.
コードの例:
#include
",h1,h2);
}
//printf("%d %d
",cnt,mx);
if(cnt == mx) ans.push_back(i);
else if(cnt > mx) {
ans.clear(); ans.push_back(i); mx = cnt;
}
}
printf("%d %d
",mx,ans.size());
for(int i = 0;i < ans.size();i++) printf("%d ",ans[i]);
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",col+i);
solve();
return 0;
}
H. Antisymmetry
Descriptionは、01文字列について、この文字列0と1を逆にしてから、その文字列全体を元の文字列と逆にすると、「反対称」文字列と呼ばれます.例えば00001111と010101は反対で、1001はそうではありません.次に、Nの長さの01文字列を与え、どのくらいのサブ列が反対称であるかを求める.
解題構想:01列の問題は本当に変化が多いですね.この問題を解決するには、まずいくつかの推論を出す必要があります.
そして,エコー列の性質と少し似ていることが分かったが,2点だけ異なるのは,エコー列の長さが奇抜であり,エコー列は逆ではなく中軸対称であることである.
では、Manacherアルゴリズムを利用することができますが、判決などを「逆」に変更すればいいだけです.もちろん、ワイルドカード「#」で埋めます.すべての「反対称」の列の長さは偶数でなければならないので、「#」で計算して、長さが偶数であることを保証します.
コードの例:
#include
",ans);
}
int main(){
//freopen("123.txt","r",stdin);
scanf("%d",&n);
scanf("%s",str);
solve();
return 0;
}
I.チケット(tickets)
Description既知数列a n,a 0=1 a_n, a_0 = 1 an,a0=1, a i + 1 = ( a i ∗ A + a i m o d B ) m o d C a_{i+1}=(a_i*A+a_i:mod:B):mod:C ai+1=(ai
解題構想:mapは遅すぎるでしょう.私は読み込み出力をテストして、乗算と型取りをテストしました.mapを疑っていません.多くの時間を無駄にしました.手書きhash関数は,隣接テーブルを用いて衝突を解消し,これでかなり速くなった.
コードの例:
#include
",h,x);
Node* p = head[h].nex;
while(p != NULL){
//printf("%lld
",p->dat);
if(p->dat == x) return true;
p = p->nex;
}
return false;
}
void Add(ll x){
int h = x%N;
// printf("%d %lld
",h,x);
Node* p = head[h].nex;
Node *q = &head[h];
while(p != NULL) q = p,p = p->nex;
q->nex = new Node(x);
//printf("%lld
",p->dat);
}
void solve(){
ll res = 1; Add(res);
for(int i = 1;i < 2e6;i++){
res = (res*a+res%b)%c;
if(check(res)){
printf("%d
",i); return;
}
Add(res);
}
puts("-1");
return;
}
int main(){
//freopen("123.txt","r",stdin);
scanf("%lld%lld%lld",&a,&b,&c);
solve();
return 0;
}
J.雪花収集(snowflakes)
Descriptionの異なる雪は往々にして異なる形をしている.北の学生は雪を集めて、南方の学生たちにプレゼントしたいと思っています.全部でn個の時刻があり,各時刻に雪が降る形状を与え,異なる整数で異なる形状を表す.収集の過程で、学生たちは繰り返しの雪があることを望んでいない.任意のa時刻から、b時刻に停止することができます.aからbまでの間の雪も集められる.彼らは収集した雪が一番多いことを望んでいる.
解題の構想:これはhashで少し書きにくくて、ハッシュ表を空にするのは難しいです.私は離散化+ダブルポインタを使っています.左境界を維持するだけでいいです.現在の雪が2回目に現れると、前回の出現位置がv[p]であることがわかるので、まず現在の区間長で答えを更新し、左境界をv[p]+1に更新します.正確性証明書は書かないのは明らかだ.
コードの例:
#include
",ans);
return 0;
}