Practice for algorithm
1.0.0
Practice for algorithm
A tree used for dictionary search, the corresponding question is dictionary tree in the code using arrays to implement the corresponding question
The KMP algorithm is a string pattern matching algorithm that uses a NEXT array to perform high-speed matching of strings. The following is the KMP algorithm template:
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++;
}
}
}From Hdu 1027
The dictionary order output method is ready-made in STL. Next_permutation(a, a + 4) can obtain the next full permutation of the array with size 4. The non-recursive algorithm starts from the last bit, finds the first position of a[i - 1] < a[i], records i - 1, starts from i and then finds the last number greater than a[i - 1], records its position k, exchanges a[i - 1] and a[k], and then inverts the position i and gets the next full arrangement. From Hdu 1711
A binary idea
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;
}Use strings to add or subtract, without being restricted by the number of bits
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;
}
From Hdu 1002
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 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;
}
}From Hdu 1003
##Dynamic planning: Number of towers and towers are a typical dynamic planning problem. It can be imagined as starting from the vertex of the structure like the Yang Hui triangle, either left or right. The maximum value is required at the end. Using dynamic programming and bottom-up calculation, an optimal solution can be obtained.
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;
}From Hdu 1176
##BFS Broadness-first search Because the graph can be searched layer by layer, it can be used as a way to find the shortest path. Of course, it is a graph with equal weights. Generally, there will be an array to mark whether to access it to prevent repeated access, but some questions will be repeated, depending on the situation. Basically there is a unified template. Queues are required, and sometimes the question has the need to use priority queues.
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 " );
}From Hdu 1072
##DFS DFS is a traversal method of a graph that is completely different from the BFS method. It goes backwards on a route instead of searching layer by layer. It is often used to find feasible routes or explore maps. Whether you need to add map marks to see the question requirements. After a route is searched, you often need to cancel the mark step by step, so that other routes can walk at that point on the map again. I wrote the third maze of data structure question in DFS. The code is similar to the following:
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);
}
}
}
}From Hdu 1312
##Backpack Problem###01Backpack 01Backpack is the most basic type of backpack: there are N items and a backpack with a capacity of V. The cost of the i-th item is c[i] and the value is w[i]. Solve which items to put into a backpack to maximize the sum of the value. The equation of state is: f[i][v]=max{f[i-1][v],f[i-1][vc[i]]+w[i]}
The basic solution is the reverse estimation of backpack capacity: for i=1..N for v=V..cost f[v]=max{f[v],f[vc[i]]+w[i]};
For the question, please refer to Hdu1203&&Hdu2602 ###Full backpack is a type of backpack that can be placed countless times for each item. Because it can be placed countless times, we will no longer need to reverse the recursively. Therefore, its solution is: for i=1..N for v=cost..V f[v]=max{f[v],f[vc[i]]+w[i]}; It's just that there is a little difference between it and the 01 backpack###Multi-backpack multiple backpacks are relatively complicated. How to say it is that there is a limit on the quantity of items. When there are enough quantities, we still use the method of complete backpacking. When there are not enough quantities, we split the quantity and simplify it into 01 backpacks to solve it. The method is: divide the i-th item into several items, each item has a coefficient, and the cost and value of the item are both the original cost and value multiplied by this coefficient. Make these coefficients 1, 2, 4,..., 2^(k-1), n[i]-2^k+1, and k is the largest integer that satisfies n[i]-2^k+1>0. For example, if n[i] is 13, the item is divided into four items with coefficients of 1, 2, 4, 6, respectively. The solution is: procedure MultiplePack(cost, weight, amount)
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)
Title reference for complete backpack and multiple backpack Hdu 2159 Hdu 2191 Hdu 1171
