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에서
## 동적 계획 : 타워와 타워 수는 일반적인 동적 계획 문제입니다. 양 히 트라이앵글 (Yang Hui Triangle)과 같은 구조의 정점에서 왼쪽 또는 오른쪽으로 시작하는 것으로 상상할 수 있습니다. 최대 값은 마지막에 필요합니다. 동적 프로그래밍 및 상향식 계산을 사용하면 최적의 솔루션을 얻을 수 있습니다.
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 Broadness-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에서 데이터 구조 질문의 세 번째 미로를 썼습니다. 코드는 다음과 유사합니다.
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-th 항목의 비용은 C [i]이고 값은 W [i]입니다. 값의 합을 최대화하기 위해 배낭에 넣을 항목을 해결하십시오. 상태 방정식은 다음과 같습니다. F [i] [v] = max {f [i-1] [v], f [i-1] [vc [i]]+w [i]}
기본 솔루션은 배낭 용량의 역 추정입니다. v = 1..n의 경우 v = v.
질문은 HDU1203 && hdu2602 ### 전체 배낭은 각 항목에 대해 수많은 시간을 배치 할 수있는 배낭의 한 유형을 참조하십시오. 수많은 시간을 배치 할 수 있기 때문에 더 이상 재귀 적으로 반전 할 필요가 없습니다. 따라서 솔루션은 다음과 같습니다. v = cost..v f [v] = max {f [v], f [vc [i]+w [i]}; 그것은 단지 그것과 01 배낭 ### multi-backpack 여러 배낭 사이에 약간의 차이가 있다는 것입니다. 말하는 방법은 품목의 수량에 제한이 있다는 것입니다. 수량이 충분하면 여전히 완전한 배낭 여행 방법을 사용합니다. 수량이 충분하지 않으면 수량을 분할하여 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의 계수를 가진 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에 대한 제목 참조
