뉴커우--화웨이 기시(3)

제목1
두 문자열 a, b의 가장 긴 공통 문자열을 찾습니다.만약 여러 개가 있다면, 비교적 짧은 열에서 가장 먼저 나오는 것을 출력합니다.(이전 문제 7과 비슷하게 동적 기획을 이용한다)

#include
#include
using namespace std;

int main(){
    string str1, str2;
    while (cin >> str1 ){
        cin >> str2; 
        if (str1.size() > str2.size())
            swap(str1,str2);
        int length1 = str1.size();
        int length2 = str2.size();
        
        int matrix[length1+1][length2+1];
        memset(matrix, 0, sizeof(matrix));
        int max = 0, maxRow = 0;
        
        for (int i = 1; i <= length1; i++){
            for (int j = 1; j <= length2; j++){
                if (str1[i-1] == str2[j-1])
                    matrix[i][j] = matrix[i-1][j-1] + 1;
                if (matrix[i][j] > max){
                    max = matrix[i][j];
                    maxRow = i;
                }
            }
        }
        cout << str1.substr(maxRow-max,max) << endl;
    }
}

제목
정수 2진법 중 1의 개수를 계산하다.(비트 연산 사용)

#include 
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        while (n){
            count++;
            n = n & (n-1);
        }
        cout << count << endl;
    }
}

제목 3
완전수(Perfect number)는 완벽수 또는 완비수라고도 부르며 특수한 자연수이다.그것의 모든 진인자(즉 자신을 제외한 약수)의 합(즉 인자 함수)은 그 자체와 꼭 같다.예를 들어 28은 약수 1, 2, 4, 7, 14, 28이 있는데 그 자체 28을 제외하고 나머지 5개 수를 더하면 1+2+4+7+14=28이다.주어진 함수count (int n) 는 n 이내 (n 포함) 의 전체 수를 계산하는 데 사용됩니다.계산 범위, 0 < n < = 500000.n 이내의 완전수의 개수를 되돌려줍니다.예외 반환 -1

#include
using namespace std;
bool isPrefect(int n){
    int sum = 0;
    for (int i = 1; i < n; i++){
        if (n % i == 0)
            sum += i;
    }
    if (sum == n)
        return true;
    else
        return false;
}

int main(){
    int n;
    while (cin >> n){
        if (n <= 0 || n>= 500000)
            cout << -1 << endl;
        else{
            int count = 0;
            for (int i = 1; i <= n; i++){
                if (isPrefect(i))
                    count++;
            }
            cout << count << endl;
        }
    }
}

제목
양휘 삼각형의 n행 첫 번째 짝수가 나타나는 위치를 구하다.짝수가 없으면 -1을 출력합니다.예를 들어 3을 입력하면 2를, 4를 입력하면 3을 출력한다.

#include
#include 
using namespace std;

int main(){
    int n;
    while (cin >> n){
        int m = 2 * n - 1;
        int matrix[n][m];
        memset(matrix,0,sizeof(matrix));
        matrix[0][n-1] = 1;
        
        for (int i = 1; i < n; i++){
            for (int j = 1; j < m; j++){//  n ，     1，          ，    
                matrix[i][j] = matrix[i-1][j-1] + matrix[i-1][j] + matrix[i-1][j+1];
            }
        }
        for (int k = 1; k < n; k++){
            if (matrix[n-1][k] % 2 == 0){
                cout << k+1 << endl;
                break;
            }
        }
    }
    return 0;
}

제목
토끼 한 마리가 태어나서 3개월째부터 매달 한 마리씩 낳았는데, 작은 토끼가 3개월째까지 자라서 매달 한 마리씩 낳았는데, 만약 토끼가 죽지 않는다면 매달 토끼의 총수는 얼마냐고 물었다.(1월이 크고, 2월이 크고, 3월이 큰 토끼가 몇 마리인지 토론한다)

#include
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int oneMonth = 1, twoMonth = 0, threeMonth = 0;
        for (int i = 2; i <= n; i++){
            threeMonth += twoMonth;
            twoMonth = oneMonth;
            oneMonth = threeMonth;
        }
        cout << oneMonth + twoMonth + threeMonth << endl;
    }
}

제목
"어떤 상점에서는 빈 사이다 세 개로 사이다 한 병을 바꿀 수 있다고 규정하고 있다. 샤오장의 손에는 빈 사이다 열 개가 있는데, 그녀는 최대 몇 병까지 바꿀 수 있습니까?"답은 5병. 방법은 다음과 같다. 먼저 9개의 빈 병으로 사이다 3병을 바꾸고 3병이 가득 찬 것을 마신다. 다 마신 후 4개의 빈 병을 3개로 한 병 더 바꾸고 이 병이 가득 찬 것을 마신다. 이때 2개의 빈 병을 남긴다.그리고 사장님께 먼저 사이다 한 병을 빌려달라고 하세요. 이 가득 찬 것을 마시고 다 마신 후에 빈 병 3개로 가득 찬 것을 바꾸어 사장님께 돌려주세요.만약 샤오장의 손에 n개의 빈 사이다 병이 있다면, 최대 몇 병의 사이다를 바꾸어 마실 수 있다

#include
using namespace std;
int main(){
    int n;
    while (cin >> n){
        if (n == 0)
            return 0;
        int drinkCount = 0;
        while (n > 2){
            drinkCount += n / 3;//    
            n = n / 3 + n % 3;//    
        }
        if (n == 2)
            drinkCount++;
        cout << drinkCount << endl;
    }
    return 0;
}

제목 7
프로그램을 작성하고 문자열을 받아들인 다음 문자열이 반전된 문자열을 출력합니다.(문자열 길이는 1000 이하)

#include
#include 
using namespace std;

int main(){
    string str;
    while (cin >> str){
        int length = str.size();
        string reversedStr;
        for (int i = 1; i <= length; i++)
            reversedStr.push_back(str[length-i]);
        cout << reversedStr << endl;
    }
}

제목
정수를 입력하고 이 정수를 문자열 형식으로 역순으로 출력합니다.

#include
using namespace std;
int main(){
    int n;
    while(cin >> n){
        while (n != 0){
            cout << n % 10;
            n = n / 10;
        }
        cout << endl;
    }
}

제목
포커 게임은 다들 잘 아시겠지만 한 세트는 54장으로 구성되어 있으며 3~A, 2 각 4장, 왕 군 1장, 왕 1장을 포함한다.패면은 작은 것부터 큰 것까지 다음과 같은 문자와 문자열로 표시한다(그 중에서 소문자 Joker는 왕 군을 나타내고 대문자 Joker는 왕 군을 나타낸다): 3, 4, 5, 6, 7, 8, 9 10 JQ K A 2 Joker Joker는 두 개의 패를 입력하고 두 개의 패 사이는 "-"연결, 각 패의 패는 빈칸으로 구분된다."-"양쪽에는 빈칸이 없다. 예를 들어 4, 4, 4 - Joker Joker.두 패의 크기를 비교하고 비교적 큰 패를 출력하세요. 비교 관계가 없으면 ERROR를 출력합니다.기본 규칙: (1) 매 카드를 입력하면 키, 대자, 순자(연속 5장), 3개, 폭탄(4개)과 대왕 중의 하나일 수 있으며 다른 상황이 존재하지 않는다. 입력으로 두 카드가 모두 합법적임을 보증하고 순자는 이미 작은 것에서 큰 것으로 배열되었다.(2) 폭탄과 대왕이 모든 패와 비교할 수 있는 것을 제외하고 다른 유형의 패는 같은 유형의 존재와 비교 관계만 있을 수 있다(예를 들어 대자와 대자를 비교하고 세 개를 세 개와 비교한다). 패를 뜯는 상황을 고려하지 않는다(예를 들어 대자를 자로 나누는 것).(3) 크기 규칙은 여러분이 평소에 알고 있는 흔한 규칙과 같고 키, 대자, 세 가지가 표면의 크기를 비교한다.순자가 가장 작은 패 크기 비교하기;폭탄은 앞의 모든 패보다 크고 폭탄 사이에서 패의 크기를 비교한다.왕에게 가장 큰 패;(4) 입력한 양손 카드는 같은 상황이 나타나지 않는다.요점: 좌우 손패의 첫 번째 카드를 뽑을 때 첫 번째 문자를 직접 뽑을 수 없고 첫 번째 빈칸 앞의 모든 문자를 뽑아야 한다. 예를 들어 10.카드의 크기를 비교하기 위해 문자를 숫자로 바꿉니다.

#include
#include 
#include 
using namespace std;

int main(){
    map<string,int> m;
    m["3"] = 3; m["4"] = 4; m["5"] = 5; m["6"] = 6; m["7"] = 7;m["8"] = 8; m["9"] = 9;
    m["10"] = 10; m["J"] = 11; m["Q"] = 12; m["K"] = 13; m["A"] = 14; m["2"] = 15;
    
    string poker;
    while (getline(cin,poker)){
        int pos = poker.find('-');
        string leftPoker = poker.substr(0,pos);
        string rightPoker = poker.substr(pos+1);

        int leftCount = 0, rightCount = 0;//        
        for (int i = 0; i < leftPoker.size(); i++){
            if (leftPoker[i] == ' ')
                leftCount++;
        }
        leftCount++;
        for (int i = 0; i < rightPoker.size(); i++){
            if (rightPoker[i] == ' ')
                rightCount++;
        }
        rightCount++;
        
        string leftPokerFirst = leftPoker.substr(0,leftPoker.find(' '));
        string rightPokerFirst = rightPoker.substr(0,rightPoker.find(' '));

        string result;
        if (leftPoker == "joker JOKER" || rightPoker == "joker JOKER"){//     
            result = "joker JOKER";
        }
        else if (leftCount == 4 || rightCount == 4){//     
            if (leftCount == 4 && rightCount == 4)
                result = m[leftPokerFirst] < m[rightPokerFirst] ? rightPoker : leftPoker;
            else if (leftCount == 4)
                result = leftPoker;
            else
                result = rightPoker;
        }
        else if (leftCount == rightCount){
            result = m[leftPokerFirst] < m[rightPokerFirst] ? rightPoker : leftPoker;
        }
        else
            result = "ERROR";
        cout << result << endl;
    }
}

제목 10**
서로 다른 문자열에 대해 우리는 유사도를 판단할 수 있는 방법을 원한다. 우리는 두 개의 서로 다른 문자열을 동일하게 만드는 조작 방법을 정의했다. 구체적인 조작 방법은 다음과 같다. 1 하나의 문자를 수정한다. 예를 들어'a'를'b'로 바꾸는 것이다.2 'abdd' 를 'aebdd' 로 바꾸는 문자를 추가합니다.3'travelling'을'traveling'으로 바꾸는 것과 같은 문자를 삭제합니다.예를 들어 'abcdefg' 와 'abcdef' 두 문자열에 대해 우리는 'g' 를 증가하고 감소하는 방식으로 목적을 달성할 수 있다고 생각한다.위의 두 가지 방안은 모두 한 번만 조작할 수 있다.이 조작에 필요한 횟수를 두 문자열의 거리로 정의하고, 유사도는 '거리 + 1' 의 역수와 같다.즉 abcdefg와 abcdef의 거리는 1이고 싱크로율은 1/2=0.5이다.임의의 두 문자열을 정하면, 너는 그것들의 유사도를 계산하는 알고리즘을 쓸 수 있니?문제풀이 방법: 동적 기획을 사용한다.첫 번째 문자열str1의 길이가 M이고 두 번째 문자열str2의 길이가 N이라고 가정합니다.1. 구해 상태 이동 매트릭스 dp [M+1] [N+1] dp[M+1] [N+1] dp[+1] [N+1], dp [i] [j] dp[i] [j] dp[i] [j]의 값은 str1의 앞 i자 str1[0...i-1]을str2로 편집한 앞 j자 str2[0...j-1]의 최소 대가를 의미한다.2. 계산 과정: 1) dp[0] [0] = 0dp[0] = 0dp[0] [0] = 0,str1의 빈 문자열을 str2의 빈 문자열로 편집한 대가가 0임을 나타낸다.2) 행렬 dp의 첫 번째 열은 dp[0... M-3 1] [0] dp[0... M-1] [0] dp[0... M-3 1] [0], dp [i] [0] dp[i] [0] dp[i] [0]는str1[0... i-1]을 빈 문자열로 편집하는 최소한의 대가이기 때문에str1[0... M-1]의 문자를 삭제하는 대가이기 때문에 dp[i] [0] = i;3) 같은 2), 그str2[0...j-1] 편집의 대가, dp[0][j]=j;4) 다음 위치는 왼쪽에서 오른쪽, 위에서 아래로 계산하면 dp[i] [j]의 값이 다음과 같은 몇 가지 상황에 대해 다음과 같이 계산한다. (1) 삭제: st r 1 [0.i-4 2str1[0. i-4 2str1[0. i-2str1[0. i-2str1[0. i-2 str1]을 st r 2 [0... j-1]str2[0... j-1]str2[0... j-1]를 삭제하고 문자 st r 1 [i -4 1] [i -1 [i -1 1] 를 삭제한다. 그리고 문자 st r 1 [i -1 [i -1 1] [i -1 i -1 [i -1 1] [i -1 stri] [1] [1stri [1] [1] [1stri-1 [1] [1] [1stri,dp[i-3-1][j]는 st r1 [0. i-3-2]str1[0.i-2]str1[0.i-3-2]을 st r2 [0. j -1]tr2[0. j -1]tr2[0. j -1]의 최소 대가로 편집한다. 그러면 dp [i] [j] dp[i] dp[j] dp[i] [j] dp[i] [j]는 dp [i] [j]와 같을 수 있다.
(2) 삽입: st r 1 [0... i-3 1]str1[0...i-1]str1[0...i-3 1]을 st r 2 [0... j-3 2]str2[0. j-2]str2[0. j-2]str2[0. j-1]str2 [j-1]str2 [j-1]str2 [j-1]str2 [j-3 1]를 st r 1 [i -3 1]str1 [i-1]str1 [i -3 1]str1]과 [i -3 1], [s1stri] 사이[s-1stri]d p [i] [j 1] dp[i] [j 1] [j 1] [j 1 i] [j 1]는 st r 1 [0.i, 1] str1 [0.i-1] dp[i] dp[i] [j 1]는 st r 1 [0. i 1]는 s t r 1 [0. i - 1] str 1 [0. i 1] str1 [0. i 1] str1]는 str1 [0. i 1] str1]을 나타내고 str1은 str1 [i] dp[i] dp[i] [i] [j [i] [j [j [i] [j 1] [j [i] [j [j [j] [j] [j] [j] [j] [j] [--1]+1;
(3) 만약 s t r 1 [i -3 1]!=s t r 2 [ j − 1 ] str1[i - 1]!=str2[j-1] str1[i−1]!=str2 [j 1 1], 그러면 먼저 st r 1 [0.ii i-2] str1 [0.i-2] str1 [0.i-2] str1 [0.i i-1 2] str2 [0. j 2] str2 [0. j 2]str2 [0. j -2] 를 str1 [i -1] str1 [i-1] str1 [i-1] str1 [0. j 1 1] str2 [0. j 2] str2 [.i-2] str2 [. i-2] str1 [i-1] str1 [i-1 1] str1 [i-1 1] str2 [j t1 str2 [j t2 [j 1 str2 [j 2] str2 [j 1] str1 str1[0.i -3-1]은 st r2 [0... j - 1]str2[0... j - 1]str2[0... j - 1]로 편집되었습니다.d p [ii 1, 1] [j 1, 1] dp[i-1] [j - 1] [j - ii 1] [j - 1] [j - 1] [j - 1] dp[i- 1] [j - 1] dp[i, 1] [j - 1] [j - 1] [j - 1] 는 str 1 [0.i 2] str1 [0.i 2] str1] str1 [0. 2] str1] str1] str1 [i- 1] dp[i- 1] dp[i- 1] dp[i- 1] dp [i - 1] dp [i - [j 1] dp [j 1] dp [i 1] dp [i 1] [j 1] [i 1] [j 1 1] [j-1] + 1dp [i-3.1] [j-3] +1;
(4) 만약 s t r 1 [i 1, 1] = s t r 2 [j 1] str1 [i - 1] ==str2 [j-1] str1 [j 1] =str1 [i - 1] str1 [j 1 1] st r 1 [0. i - 2] str1 [0. i-2] str1 [0. i-3 2] str1 [0. i - 2] str1 [i 1, 2] str1 [i - 2] str1 = = = = = = = s t r 2 = = = = = s t r 2 = = = s t r 2 = = s t r 2 = = s t r 2 = = = = s t r 2 = = s r 2 = = = s r 2 = s r 2 = s t (4) str 1 (4) str 1 = s = s str1[i-1]==str2[j-1]str1[i-3-1]==str2[j-3-1],그래서 st r 1 [0. i i-1] 이미 st r 2 [0. j -1] str1 [0. i-1] str1 [0. i-1] str2 [0. j -1] str1 [0. i 1] str2 [0. j 1 1] str2 [0. j - 1] str2 [0. i-1] [j - 1] dp[j - 1] dp[j - 1] dp[i - 1] [j - 1] [j - 1] [j - 1] str 1 1] str2 [0. i i i - 1] str1 [0. i i - 2, stri 1] stri 1 [0. 1 str2 str. ttt. t는 sT 1 [0. t. t. tt1 = 1 = = = j-32]str2[0.j-2]str2[0.j-3]의 최소 대가,그러면 p[i][j]p[i][j]p[i][j]는 dp[i-3-1][j-1]dp[i-1][j-1]dp[i-3][j-1]과 같을 수 있다.상기 4의 경우 최소치를 취하고 dp의 가장 오른쪽 하단이 최종 결과, 즉 최소 편집 대가이다.

#include
#include
#include
using namespace std;

int main(){
    string str1, str2;
    while (cin >> str1 >> str2){
        int length1 = str1.size();
        int length2 = str2.size();
        int dpMatrix[length1+1][length2+1];
        memset(dpMatrix,0,sizeof(dpMatrix));
        
        for(int i = 1; i <= length1; i++)
            dpMatrix[i][0] = i;
        for (int j = 1; j <= length2; j++)
            dpMatrix[0][j] = j;
        for (int i = 1; i <= length1; i++){
            for (int j = 1; j <= length2; j++){
                int caseOne = dpMatrix[i-1][j] + 1;
                int caseTwo = dpMatrix[i][j-1] + 1;
                int caseThree = 0;
                if (str1[i-1] == str2[j-1])
                    caseThree = dpMatrix[i-1][j-1];
                else
                    caseThree = dpMatrix[i-1][j-1] + 1;
                dpMatrix[i][j] = min(caseOne,min(caseTwo,caseThree));
            }
        }
        cout << 1 << "/" << (dpMatrix[length1][length2] + 1) << endl;
    }
}