ap325第二章剩下例題

ap325第二章剩下例題

一月 16, 2025

2-6set寫法

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

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
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int main()
{
    int m,n;
    LL k;
    cin>>m>>n>>k;
    set<LL>s;
    int A[m];
    LL x;
    for(int i=0;i<m;i++){
        cin>>A[i];
    }
    for(int i=0;i<n;i++){
        cin>>x;
        s.insert(x);
    }
    sort(A,A+m);
    int total=0;
    for(int i=0;i<m;i++){
        if(s.find(k-A[i])!=s.end()){ //s.find(k-A[i])會返回找到他的位置
            total++;
        }
    }
    cout<<total;
    return 0;
}

2-7互補團隊

https://judge.tcirc.tw/problem/d016
自己練習，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
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
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL total=0;
int n;
set<pair<int,int>> sss;
void recursion(string s[],int m,map<char,int> ma,int now,int deep){
    set<char> se;
    for(int i=0;i<s[now].size();i++){
        se.insert(s[now][i]);
    }
    for(auto k:se){
        ma[k]++;
    }
    if(deep==1){
        bool valid=true;
        for(char ch='A';ch<='A'+m-1 && ch<='Z';ch++){
            if(ma[ch]<=0|| ma[ch]>=2){
                valid=false;
                return;
            }
        }
        if(valid){
            total++;
            return;
        }
    }
    for(int i=0;i<n;i++){
        if(i!=now && sss.find({min(i,now),max(i,now)})==sss.end()){
            sss.insert({min(i,now),max(i,now)});
            recursion(s,m,ma,i,1);
        }
    }

}
int main()
{
    int m;
    cin>>m>>n;
    map<char,int> ma;
    for(char ch='A';ch<='Z' ;ch++){
        ma[ch]=0;
    }
    string str[n];
    for(int i=0;i<n;i++){
        cin>>str[i];
    }
    for(int i=0;i<n;i++){     
        recursion(str,m,ma,i,0);
    }
    cout<<total;
    return 0;   
}

看提示寫的:

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
#include <bits/stdc++.h>

using namespace std;
int k=1;
int m,n;
int main()
{

    cin>>m>>n;
    k=(1<<m)-1;
    //cout<<k<<'\n';
    string s[n];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }

    set<int> se;
    for(int i=0;i<n;i++){
        int team=0;
        for(int j=0;j<s[i].size();j++){
            /*if(s[i][j]=='A'){
                team|=1;
            }*/
            team |=(1<<(s[i][j]-'A'));
        }
        se.insert(team);
    }

    int total=0;

    for(auto t:se){
        if(se.find(k-t)!=se.end()){
            total++;
        }
    }
    cout<<total/2; //由這邊可以發現這題還可以優化，因為total被計算兩次
    return 0;
}

2-9子集合乘積(折半枚舉)

https://judge.hlhs.hlc.edu.tw/ShowProblem?problemid=e036
不足以通過這一題所有測資。這個程式的方法也很直接，我們逐一考慮每一個
元素，以一個map M1來記錄著目前所有可能的子集合乘積，相同的乘積只記錄一筆，
但記錄能產生此乘積的子集合個數。對於下一個元素a[i]，把原有的所有可能在乘上
此新元素，就是新的可能乘積。在計算過程，新的乘積不能直接加到原來的裡面，否則
無法分辨新舊。因此要利用一個 map M2 來暫存，當一個元素處理完畢後交換 M1 與
M2，以便下一個元素時再從M1計算到M2。
(我看不懂…)

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
// subset product = 1 mod P, slow method 
#include<bits/stdc++.h> 
using namespace std; 
typedef long long LL;
int main() { 
    int i, n; 
    LL p, a[50]; 
    scanf("%d%lld", &n, &p); 
    for (i=0;i<n;i++) 
        scanf("%lld", &a[i]); 
    map<LL,LL> M1; // (product, number) 
    M1[a[0]]=1; // The first element appear once 
    for (i=1;i<n;i++) { // for each element 
        // compute from M1 to M2 
        map<LL,LL> M2(M1); // copy M1 to M2 
        for (auto e:M1) { 
            LL t = (e.first*a[i])%p; 
            M2[t] = (M2[t] + e.second)%p; 
        } 
        M2[a[i]] = (M2[a[i]] + 1)%p; // for {a[i]} 
        M1.swap(M2); 
    } 
    printf("%lld\n", M1[1]); 
    return 0; 
}

接下來要來學折半枚舉