ap325第五天

ap325第五天

一月 14, 2025

1-10最多得分的皇后

https://judge.tcirc.tw/problem/d008

  • 延續第四天，然加上一個判斷要選哪幾列有皇后的排列就好(最佳得分並不一定是每一列皆有皇后)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    #include <iostream>

    using namespace std;
    int point[15][15];
    int best=0;
    void qr(int i,int K,int p[],int bound,int total){
        if(K>=bound){
            if(total>best){
                best=total;
            }
            return;
        }
        if(!(i & (1<<K))){
            qr(i,K+1,p,bound,total);
            return;
        }
        bool valid[bound];
        for(int j=0;j<bound;j++){
            valid[j]=true;
        }
        for(int j=0;j<K;j++){
            if(i& (1<<j) ){
                valid[p[j]]=false;
                int up=p[j]+K-j; //i=y軸數據+(當前x軸-x軸數據) 往左下
                if(up<bound){
                    valid[up]=false;
                }
                int down=p[j]-K+j; //往右上
                if(down>=0){
                    valid[down]=false;
                }

            }
        }
        for(int j=0;j<bound;j++){
            if(valid[j]){
                p[K]=j;
                qr(i,K+1,p,bound,total+point[j][K]);
            }
        }
    }
    int main()
    {
        int p[15];
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>point[i][j];
            }
        }
        for(int i=1;i<(1<<n);i++){ //將1向左移動
            int total=0;
            qr(i,0,p,n,total);
        }

        cout<<best;
        return 0;
    }

1-10刪除矩形邊界

https://judge.tcirc.tw/problem/d009

  • 有更快的dp寫法，不過這邊先用遞迴暴力解
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    #include <iostream>

    using namespace std;
    int s[13][13];
    int best=100000;
    void rec(int left_y,int left_x,int right_y,int right_x,int cost){
        if(abs(left_x-right_x)==0 || abs(left_y-right_y)==0){
            if(cost<best){
                best=cost;
            }
            return;
        }
        int one=0;
        int zero=0;
        int ans=0;
        for(int i=left_x;i<=right_x;i++){
            if(s[left_y][i]==1){
                one++;
            }else{
                zero++;
            }
            ans=min(one,zero);
        }
        rec(left_y+1,left_x,right_y,right_x,cost+ans); //1
        one=0;
        zero=0;
        for(int i=left_y;i<=right_y;i++){
            if(s[i][left_x]==1){
                one++;
            }else{
                zero++;
            }
            ans=min(one,zero);
        }
        rec(left_y,left_x+1,right_y,right_x,cost+ans); //2
        one=0;
        zero=0;
        for(int i=right_x;i>=left_x;i--){
            if(s[right_y][i]==1){
                one++;
            }else{
                zero++;
            }
            ans=min(one,zero);
        }
        rec(left_y,left_x,right_y-1,right_x,cost+ans); //3
        one=0;
        zero=0;
        for(int i=right_y;i>=left_y;i--){
            if(s[i][right_x]==1){
                one++;
            }else{
                zero++;
            }
            ans=min(one,zero);
        }
        rec(left_y,left_x,right_y,right_x-1,cost+ans); //4
    }
    int main()
    {
        int m,n;
        cin>>m>>n;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin>>s[i][j];
            }
        }
        rec(0,0,m-1,n-1,0);
        cout<<best;
        return 0;
    }

第二章 排序

  • sort
    sort()除了前兩個參數指定範圍之外，還可以傳入
    第三個參數，第三個參數是一個比較函數，這個函數負責告訴sort()排序的順序是什
    麼：比較函數必須傳入兩個參數，如果第一個參數要排在第二個的前面就回傳true，
    否則回傳false。
    簡單來說:
    1
    2
    3
    bool cmp(int j,int i){
        return j>i;
    }

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/?envType=daily-question&envId=2025-01-14

  • 心血來潮寫的leetcode每日一題
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
    public:
        vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
            int n=A.size();
            int m=n;
            int P_A[52]={};
            int P_B[52]={};
            int Aarr[52];
            int Barr[52];
            vector<int> ans; //寫成vector<int> ans(n,0)的話意思是大小為n，數據為0
            int num=0;
            for(int i=n-1;i>=0;i--){
                Aarr[i]=A.back();
                Barr[i]=B.back();
                A.pop_back();
                B.pop_back();
            }
            for(int i=0;i<n;i++){
                P_A[Aarr[i]]+=1;
                P_B[Barr[i]]+=1;
                if(P_A[Aarr[i]]>0 && P_B[Aarr[i]]>0){
                    num++;
                    P_A[Aarr[i]]--;
                    P_B[Aarr[i]]--;
                }
                if(P_A[Barr[i]]>0 && P_B[Barr[i]]>0){
                    num++;
                    P_A[Barr[i]]--;
                    P_B[Barr[i]]--;
                }
                ans.push_back(num);
            }
            return ans;
        }
    };

二分搜基本寫法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;
int bsearch(int a[],int left,int right,int x){
    while(left<=right){
        int mid=(left+right)/2;
        if(a[mid]==x){
            return mid;
        }
        if(a[mid]<x){
            left=mid+1;
        }
        if(a[mid]>x){
            right=mid-1;
        }


    }
    return -1;
}
int main()
{
    int p[100];
    for(int i=0;i<100;i++){
        p[i]=rand()%100; //random 保證數字1到99
    }
    sort(p,p+100);
    for(int i=0;i<100;i++){
        cout<<p[i]<<' ';
    }
    cout<<'\n';
    cout<<bsearch(p,0,100-1,p[7]);
    return 0;
}