Practice for algorithm
1.0.0
アルゴリズムの練習
辞書検索に使用されるツリー、対応する質問は、配列を使用して対応する質問を実装するコードの辞書ツリーです
KMPアルゴリズムは、次の配列を使用して文字列の高速マッチングを実行する文字列パターンマッチングアルゴリズムです。以下は、KMPアルゴリズムテンプレートです。
void setNext (){
NEXT[ 0 ] = - 1 ;
int j = 0 , k = - 1 ;
while (j < par. length ()) {
if (k == - 1 || par[k] == par[j]) {
j++;
k++;
NEXT[j] = k;
}
else
k = NEXT[k];
}
}
void solve (){
int p = 0 , q = 0 ;
while (p < ori. length ()) {
if (q == - 1 || par[q] == ori[p]) {
q++;
p++;
}
else
q = NEXT[q];
if (q == par. length ()) {
ans++;
}
}
}HDU 1027から
辞書順序出力法は、STLで既製のものです。 Next_PerMutation（A、A + 4）は、サイズ4のアレイの次の完全な順列を取得できます。非再転用アルゴリズムは最後のビットから始まり、[I -1] <A [i]の最初の位置を見つけ、I -1を記録し、Iから始まり、[I -1]より大きい最後の数を見つけます。次のフルアレンジメント。 HDU 1711から
バイナリのアイデア
int quickMPow ( int a, int b){
if (b == 0 ) {
return 1 ;
}
int reslut = 1 ;
while (b) {
if (b & 1 ) {
reslut *= a;
}
a *= a;
b >>= 1 ;
}
return reslut;
}文字列を使用して、ビット数によって制限されることなく追加または減算します
void solve (){
int lenNum1 = strlen (num1), lenNum2 = strlen (num2), min = 0 , c = 0 , count = 0 ;
if (lenNum1 >= lenNum2) {
min = lenNum2;
} else {
min = lenNum1;
}
while (min) {
int temp;
temp = num1[lenNum1 - 1 ] + num2[lenNum2 - 1 ] - 96 ;
min--;
lenNum1--;
lenNum2--;
sum[count] = (temp % 10 + c) % 10 + 48 ;
count++;
if (temp % 10 + c >= 10 ){
c = 1 ;
}
else {
c = 0 ;
}
if (temp >= 10 ) {
c++;
}
}
while (lenNum1) {
sum[count] = (num1[lenNum1 - 1 ] - 48 + c) % 10 + 48 ;
count++;
if (num1[lenNum1 - 1 ] - 48 + c >= 10 ){
c = 1 ;
} else {
c = 0 ;
}
lenNum1--;
}
while (lenNum2) {
sum[count] = (num2[lenNum2 - 1 ] - 48 + c) % 10 + 48 ;
count++;
if (num2[lenNum2 - 1 ] - 48 + c >= 10 ){
c = 1 ;
} else {
c = 0 ;
}
lenNum2--;
}
if (c) {
sum[count] = ' 1 ' ;
count++;
}
count--;
for ( int i = 0 ; i <= count; i++) {
if (sum[i] != ' 0 ' )
break ;
if (i == count){
cout << ' 0 ' << endl;
return ;
}
}
while (count >= 0 ) {
cout << sum[count];
count--;
}
cout << endl;
}
HDU 1002から
シーケンスa [1]、a [2]、a [3] ...... a [n]が与えられると、あなたの仕事はサブシーケンスの最大合計を計算することです。たとえば、（6、-1,5,4、-7）が与えられた場合、このシーケンスの最大合計は6 +（-1） + 5 + 4 = 14です。
for ( int i = 0 ; i < T; i++) {
int count, start = 1 , end = 1 , max = - 1 << 31 , dp = 0 , temp = 1 ;
cin >> count;
for ( int k = 0 ; k < count; k++) {
int num;
cin >> num;
dp += num;
if (dp > max) {
max = dp;
start = temp;
end = k + 1 ;
}
if (dp < 0 ){
dp = 0 ;
temp = k + 2 ;
}
}
cout << " Case " << i + 1 << " : " << endl;
cout << max << " " << start << " " << end << endl;
if (i != T - 1 ) {
cout << endl;
}
}HDU 1003から
##ダイナミック計画：タワーとタワーの数は、典型的な動的計画の問題です。左または右のヤンフイの三角形のような構造の頂点から始まると想像できます。最後に最大値が必要です。動的プログラミングとボトムアップ計算を使用して、最適なソリューションを取得できます。
int H1176_Solve (){
for ( int i = maxTime - 1 ; i >= 0 ; i--) {
for ( int k = 0 ; k < 11 ; k++) {
int maxValue = arr[k][i + 1 ];
if (k - 1 >= 0 ) {
if (arr[k - 1 ][i + 1 ] > maxValue) {
maxValue = arr[k - 1 ][i + 1 ];
}
}
if (k + 1 <= 10 ){
if (arr[k + 1 ][i + 1 ] > maxValue) {
maxValue = arr[k + 1 ][i + 1 ];
}
}
arr[k][i] = arr[k][i] + maxValue;
}
}
int max = arr[ 4 ][ 1 ];
for ( int i = 4 ; i < 7 ; i++) {
if (arr[i][ 1 ] > max){
max = arr[i][ 1 ];
}
}
return max;
}HDU 1176から
## BFS Browness-First検索グラフはレイヤーごとに検索できるため、最短パスを見つける方法として使用できます。もちろん、それは等しい重みのグラフです。一般に、繰り返しアクセスを防ぐためにアクセスするかどうかをマークする配列がありますが、状況に応じていくつかの質問が繰り返されます。基本的に統一されたテンプレートがあります。キューが必要であり、時には質問に優先キューを使用する必要があります。
void solve (){
queue<Node> s;
memset (flag, 0 , sizeof (flag));
now. x = inx;
now. y = iny;
now. time = 6 ;
now. output = 0 ;
flag[inx][iny] = 6 ;
s. push (now);
while (!s. empty ()) {
now = s. front ();
s. pop ();
for ( int i = 0 ; i < 4 ; i++) {
nex = now;
nex. x = now. x + fx[i];
nex. y = now. y + fy[i];
if (nex. x >= 0 && nex. x < N && nex. y >= 0 && nex. y < M && flag[nex. x ][nex. y ] < now. time - 1 ){
if (mp[nex. x ][nex. y ] == 0 ) {
}
if (mp[nex. x ][nex. y ] == 3 ){
}
if (mp[nex. x ][nex. y ] == 1 ) {
}
if (mp[nex. x ][nex. y ] == 4 ) {
}
}
}
}
printf ( " -1 n " );
}HDU 1072から
## DFS DFSは、BFSメソッドとはまったく異なるグラフの横断方法です。レイヤーごとにレイヤーを検索する代わりに、ルートで後方に戻ります。多くの場合、実行可能なルートを見つけたり、マップを探索したりするために使用されます。質問要件を確認するためにマップマークを追加する必要があるかどうか。ルートが検索された後、多くの場合、マークを段階的にキャンセルする必要があります。これにより、他のルートがマップ上のその時点で再び歩くことができます。 DFSでデータ構造の質問の3番目の迷路を書きました。コードは以下に似ています。
int fx[ 4 ] = { 0 , 0 , 1 , - 1 };
int fy[ 4 ] = { 1 , - 1 , 0 , 0 };
void solve ( int x, int y){
if ((mp[x][y] == ' . ' || mp[x][y] == ' @ ' ) && vis[x][y] == 0 ){
num++;
vis[x][y] = 1 ;
for ( int i = 0 ; i < 4 ; i++) {
int nexX = x, nexY = y;
nexX += fx[i];
nexY += fy[i];
if (nexX >= 0 && nexX < N && nexY >= 0 && nexY < M) {
solve (nexX, nexY);
}
}
}
}HDU 1312から
##バックパックの問題### 01BackPack 01BackPackは最も基本的なタイプのバックパックです。Vの容量を持つnアイテムとバックパックがあります。i番目のアイテムのコストはc [i]で、値はw [i]です。値の合計を最大化するために、バックパックに配置するアイテムを解決します。状態の方程式は次のとおりです。f[i] [v] = max {f [i-1] [v]、f [i-1] [vc [i]]+w [i]}
基本的なソリューションは、バックパック容量の逆推定です。i= 1..n for v = v..cost f [v] = max {f [v]、f [vc [i]]+w [i]};
質問については、HDU1203 && HDU2602 ###を参照してください。フルバックパックは、各アイテムに数え切れない時間に配置できるバックパックの一種です。数え切れないほどに配置できるため、再帰的に逆転する必要はなくなります。したがって、その解決策は次のとおりです。i= 1..n for v = cost..v f [v] = max {f [v]、f [vc [i]]+w [i]};それは、それと01バックパック###マルチバックパックマルチバックパックの間に少し違いがあるということです。言い方は、アイテムの量に制限があるということです。十分な量がある場合でも、完全なバックパッキングの方法を使用します。十分な量がない場合は、量を分割し、01バックパックに単純化して解決します。方法は次のとおりです。i番目のアイテムをいくつかのアイテムに分割し、各アイテムには係数があり、アイテムのコストと値は、元のコストと値の両方にこの係数を掛けます。これらの係数を1、2、4、...、2^（k-1）、n [i] -2^k+1、およびkはn [i] -2^k+1> 0を満たす最大の整数です。たとえば、n [i]が13の場合、アイテムはそれぞれ1、2、4、6の係数を持つ4つのアイテムに分割されます。解決策は次のとおりです。手順倍数（コスト、重量、量）
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
完全なバックパックと複数のバックパックHDU 2159 HDU 2191 HDU 1171のタイトルリファレンス
