ap325第三天

ap325第三天

一月 12, 2025

1-6最接近區間和

  • 假設陣列A[1..n]中存放著某些整數，另外給了一個整數K，請計算哪一個連續區
    段的和最接近K而不超過K。
    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
    #include <iostream>

    using namespace std;
    int K;

    int main()
    {
        int n;
        cin>>n>>K;
        int s[n];
        for(int i=0;i<n;i++){
            cin>>s[i];
        }
        int sum=0;
        int bestleft=0;
        int bestright;
        int bestans=1000;
        int right;
        int left=0;
        for(int i=0;i<n;i++){
            sum+=s[i];
            right=i;
            while(sum>K){
                sum-=s[left];
                left++;
            }
            if(abs(K-sum)<=abs(K-bestans)){
                bestans=sum;
                bestleft=left;
                bestright=right;
            }
        }
        cout<<bestleft<<' '<<bestright;
        return 0;
    }

1-7子集合乘積

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

  • 寫出這個答案的老師真的好厲害
    以下為暴力解，所以當測試資料過大時會TLE:
    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
    #include <iostream>

    using namespace std;

    int main()
    {
        int n;
        int P=10009; 
        int A[26]; //集合最大只有25個元素，因為0<n<26
        cin>>n;
        int sum=0;
        for(int i=0;i<n;i++){
            cin>>A[i];
        } 
        for(int i=1;i<(1<<n);i++){  // 1<<n的範圍就是2^n，所以這裡以binary i的數字1代表元素在內
            long long prod=1;       
            for(int j=0;j<n;j++){
                if(i & (1<<j)){         //如果binary i的第j位為一，則列進prod內
                    prod=(prod*A[j])%P; //先mod跟最後再mod根據公式結果一樣
                }
            }
            if(prod==1){
                sum++;
            }
        }
        cout<<sum;
        return 0;
    }

以下為遞迴解，時間複雜度較小，如果是迴圈解複雜度為O(2^n)遞迴解的話O(n*2^n)

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
#include <iostream>

using namespace std;
int P=10009;
int A[26];
int ans=0;
int prod=1;
int n;
void rec(int i,int prod){
    if(i>=n){
        if(prod==1) ans++;
        return;
    }
    rec(i+1,(prod*A[i])%P);
    rec(i+1,prod);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    rec(0,1);
    cout<<ans-1;
    return 0;
}

1-8子集合的和

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

  • 跟上面那題的解題思路大差不遠
    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
    #include <iostream>

    using namespace std;
    typedef long long LL;
    LL P;
    int A[26];
    int n;
    LL bestans=0;
    void rec(int i,LL sum){
        //cout<<i<<" i "<<bestans<<'\n';

        if(sum>P){
            return;
        }
        if(i>=n){
            if(P-sum<P-bestans){
                bestans=sum;

            }
            return;
        }

        rec(i+1,sum+A[i]);
        rec(i+1,sum);
    }
    int main()
    {
        cin>>n;
        cin>>P;
        for(int i=0;i<n;i++){
            cin>>A[i];
        }
        rec(0,0);
        cout<<bestans;
        return 0;
    }