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_PERMTTATIGY (A ، A + 4) الحصول على التقليب الكامل التالي للمصفوفة بحجم 4. تبدأ الخوارزمية غير المثيرة للاشمئزاز من آخر شيء ، وتبدأ الموضع الأول من [I - 1] <A [A] ترتيب كامل. من 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) ، فإن Max Sum في هذا التسلسل هو 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
## التخطيط الديناميكي: عدد الأبراج والأبراج مشكلة تخطيط ديناميكية نموذجية. يمكن تخيله على أنه يبدأ من قمة الهيكل مثل مثلث Yang Hui ، إما اليسار أو اليمين. مطلوب الحد الأقصى للقيمة في النهاية. باستخدام البرمجة الديناميكية والحساب من أسفل إلى أعلى ، يمكن الحصول على حل الأمثل.
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 first-first Search لأنه يمكن البحث في الطبقة الرسم البياني حسب الطبقة ، يمكن استخدامه كوسيلة للعثور على أقصر مسار. بالطبع ، إنه رسم بياني ذو أوزان متساوية. بشكل عام ، سيكون هناك صفيف للاحتفال بما إذا كان سيتم الوصول إليه لمنع الوصول المتكرر ، ولكن سيتم تكرار بعض الأسئلة ، اعتمادًا على الموقف. أساسا هناك قالب موحد. قوائم الانتظار مطلوبة ، وأحيانًا يكون السؤال يحتاج إلى استخدام قوائم انتظار الأولوية.
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. الرمز مشابه لما يلي:
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
## Packpack Problem ### 01backpack 01backpack هو أبسط أنواع حقيبة الظهر: هناك عناصر n وحقيبة الظهر بسعة V. تكلفة العنصر I-th هي 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-TH إلى عدة عناصر ، كل عنصر له معامل ، وتكلفة وقيمة العنصر هي التكلفة الأصلية والقيمة المضروبين في هذا المعامل. اجعل هذه المعاملات 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 على التوالي. الحل هو: الإجراء المتعدد (التكلفة ، الوزن ، المبلغ)
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
