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], บันทึกฉัน - 1 และ 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 การค้นหาในวงกว้างเป็นครั้งแรกเนื่องจากกราฟสามารถค้นหาเลเยอร์โดยเลเยอร์สามารถใช้เป็นวิธีในการค้นหาเส้นทางที่สั้นที่สุด แน่นอนว่ามันเป็นกราฟที่มีน้ำหนักเท่ากัน โดยทั่วไปจะมีอาร์เรย์เพื่อทำเครื่องหมายว่าจะเข้าถึงเพื่อป้องกันการเข้าถึงซ้ำ ๆ หรือไม่ แต่คำถามบางข้อจะเกิดขึ้นซ้ำ ๆ ขึ้นอยู่กับสถานการณ์ โดยทั่วไปมีเทมเพลตแบบครบวงจร ต้องคิวและบางครั้งคำถามก็จำเป็นต้องใช้คิวลำดับความสำคัญ
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
## ปัญหากระเป๋าเป้สะพายหลัง ### 01backpack 01backpack เป็นกระเป๋าเป้สะพายหลังประเภทพื้นฐานที่สุด: มีรายการ n และกระเป๋าเป้สะพายหลังที่มีความจุ V. ค่าใช้จ่ายของรายการ i-th คือ c [i] และค่าคือ w [i] แก้ไขรายการที่จะใส่ลงในกระเป๋าเป้สะพายหลังเพื่อเพิ่มผลรวมของค่าสูงสุด สมการของสถานะคือ: f [i] [v] = สูงสุด {f [i-1] [v], f [i-1] [vc [i]]+w [i]}
วิธีการแก้ปัญหาพื้นฐานคือการประมาณค่าย้อนกลับของความจุกระเป๋าเป้สะพายหลัง: สำหรับ i = 1..n สำหรับ v = v..cost f [v] = สูงสุด {f [v], f [vc [i]]+w [i]};
สำหรับคำถามโปรดดู HDU1203 && HDU2602 ### กระเป๋าเป้เต็มรูปแบบเป็นกระเป๋าเป้สะพายหลังที่สามารถวางครั้งนับไม่ถ้วนสำหรับแต่ละรายการ เนื่องจากสามารถวางครั้งนับครั้งไม่ถ้วนเราไม่จำเป็นต้องย้อนกลับอีกต่อไป ดังนั้นวิธีการแก้ปัญหาคือ: สำหรับ i = 1..N สำหรับ v = cost.v f [v] = สูงสุด {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 ตามลำดับ โซลูชันคือ: ขั้นตอน MultiplePack (ราคาน้ำหนักจำนวน)
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
