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_permution (a, a + 4) может получить следующую полную перестановку массива с размером 4. Нерекурсивный алгоритм начинается с последнего бита, находит первую позицию [i - 1] <a [i], записи I - 1, начинается с i, а затем находит последнее число больше, чем a [i - 1], записывает его позицию, обмену a, и [I - 1, а затем и [k] и [k], а затем и в точке, а затем и в точке. Полная договоренность. От 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] = max {f [i-1] [v], f [i-1] [vc [i]]+w [i]}
Основным решением является обратная оценка емкости рюкзака: для i = 1..n для v = v..cost f [v] = max {f [v], f [vc [i]]+w [i]};
Для вопроса, пожалуйста, обратитесь к HDU1203 && HDU2602 ### Полный рюкзак - это тип рюкзака, который можно размещать бесчисленное количество раз для каждого элемента. Поскольку это может быть размещено бесчисленное количество раз, нам больше не нужно рекурсивно. Следовательно, его решение: для i = 1..n для v = stord..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
