最後編輯時間: 2025/05/20

2025/05/20刷題心得整理

▌TF::OJ刷的題目

▌覺得有趣或值得紀錄的題目以及心得感想

  • 習題 Q-2-7. 互補團隊
    這題上一次解不出來,整體邏輯沒什麼太大的問題,不知道是原本設定的值有問題還是怎樣,會出錯,後面把陣列改成二進制,讓每個字母有單獨的值,確保字母相加不會相同,並使用map來存值,邊測邊+,最後就可以輸出正確答案了,我還使用set確保每次計算字母只計算一次。
  • 習題 Q-2-8. 模逆元 (*)
    這題題目不難,就是沒看懂公式,其實就是把公式套進去而已
  • 例題 P-2-9. 子集合乘積(折半枚舉) (@@)
    這題利用了將陣列分兩半,讓左相乘,右相乘,最後逆模抓出能兩邊相乘%p等於1的值,最後+一起就好了
  • 例題 Q-2-10. 子集合的和 (折半枚舉)
    這題跟上一題類似,就是把左邊算出來,右邊算出來,最後把左邊所有可能去查詢右邊是否有對應值,有就+
  • 例題 P-3-2. 括弧配對
    這題超級經典推疊提,總之就是把括號存著,只要後面括號沒辦法匹配到,這一個括號就是錯誤
  • 習題 Q-3-3. 加減乘除
    這題也是堆疊,如果是+或-直接壓入堆疊,如果是*或/就把上一個壓進去的值進行計算算完後壓回去
  • 例題 P-3-4. 最接近的高人
    這題利用單調堆疊,總之就是因為一直往後,如果後面的數值比前面的大,那對於更後面的值最高的高人就會是它,所以可以把前面比那個高人小的刪除,總之就這樣,我講得蠻抽象的

▌程式

    習題 Q-2-7. 互補團隊

				
					#include <bits/stdc++.h>
using namespace std;
int main(){
    int g[26]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,75536,151172,302344,604688,1209376,2418752,4837504,9675008,19350016,38700032};
    int m,n,ss=0,w=0;
    cin >> m >> n;
    for(int i=0;i<m;i++) w+=g[i];
    unordered_map<int,int> l;
    while(n--){
        int s=0;
        string a;
        cin >> a;
        unordered_set<char> b;
        for(char c:a){
            if(!b.count(c)){
                s += g[c-'A'];
                b.insert(c);
            }
        }
        l[s]++;
        ss += l[w-s];
    }
    cout << ss << endl;
}
				
			

     習題 Q-2-8. 模逆元 (*)

				
					#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p;
 LL ww(LL k,LL w){
    if(k==0) return 1;
    if(k%2==1) return (ww(k-1,w)*w)%p;
    LL q = ww(k/2,w);
    return (q * q)%p;
}
int main(){
    int n;cin >> n >> p;
    for(int i=0;i<n;i++){
            LL w;cin >> w;
        cout << ww(p-2,w) << " ";
    }
}
				
			

     例題 P-2-9. 子集合乘積(折半枚舉) (@@)

				
					#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,a[30],b[30],sa[300000]={},sb[300000]={},s=0,ss=0,n;
void aa(long long k, int e, bool selected) {
    if (e == n / 2) {
        if (selected) sa[s++] = k % p;
        return;
    }
    aa(k, e + 1, selected);
    aa(k * a[e] % p, e + 1, true);
}
void bb(ll k,int e,bool selected){
    if(e==n-n/2){
        if(selected) sb[ss++] = k%p;
        return;
    }
    bb(k%p,e+1,selected);
    bb(k*b[e]%p,e+1,true);
    return;
}
ll c(ll k,ll nn){
    if(nn==0) return 1;
    if(nn%2==1) return k * c(k,nn-1) % p;
    ll r = c(k,nn/2);
    return r * r % p;
}
int main(){
    cin >> n >> p;
    for(int i=0;i<n/2;i++){
        cin >> a[i];
    }
    for(int i=0;i<n-(n/2);i++){
        cin >> b[i];
    }
    aa(1,0,false);bb(1,0,false);
    unordered_map<int,int> v;
    for(int i=0;i<ss;i++){
        v[sb[i]]++;
    }
    ll w = 0;
    for(int i=0;i<s;i++){
        if(sa[i]==1) w++;
        w+=v[c(sa[i],p-2)];
    }
    cout << v[1]+w << endl;
}
				
			

     例題 Q-2-10. 子集合的和 (折半枚舉)

				
					#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll aa[38],bb[38],a[524288],b[524288],n,s=0,ss=0;
void aw(ll k,ll e){
    if(e==n/2){
        if(k!=0) a[s++] = k;
        return;
    }
    aw(k,e+1);aw(k+aa[e],e+1);
    return;
}
void bw(ll k,ll e){
    if(e==n-n/2){
        if(k!=0) b[ss++] = k;
        return;
    }
    bw(k,e+1);bw(k+bb[e],e+1);
    return;
}
int main(){
    ll m=0;
    ll p;cin >> n >> p;
    for(int i=0;i<n/2;i++) cin >> aa[i];
    for(int i=0;i<n-n/2;i++) cin >> bb[i];
    aw(0,0);bw(0,0);
    sort(a,a+s);sort(b,b+ss);
    ll da = upper_bound(a,a+s,p)-a;
    ll db = upper_bound(b,b+s,p)-b;
    if(a[da]<=p) {if(a[da]>m) m=a[da];}
    else {if(a[da-1]>m) m=a[da-1];}
    if(a[da]<=p) {if(b[db]>m) m=b[db];}
    else {if(b[db+1]>m) m=b[db+1];}
    for(int i=0;i<s;i++){
        if(a[i]<=p){
            ll w = p - a[i];
            ll t = upper_bound(b,b+ss,w)-b;
            if(b[t]<=w) {if(a[i]+b[t]>m) m=a[i]+b[t];}
            else {if(a[i]+b[t-1]>m) m=a[i]+b[t-1];}
        }
    }
    cout << m <<endl;
}
				
			

     例題 P-2-11. 最接近的區間和 (*)

				
					#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,p=0,m=0;cin >> n >> k;
    set<int> a({0});
    for(int i=0;i<n;i++){
        int w;cin >> w;
        p+=w;
        auto it=a.lower_bound(p-k);
        if(it!=a.end()) m = max(m,p-*it);
        a.insert(p);
    }
    cout << m <<endl;
    return 0;
}

				
			

     例題 P-3-2. 括弧配對

				
					#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a;char r[200];
    r[']']='[';r['}']='{';r[')']='(';
    while(cin >> a){
            stack<char> b;
            bool w = true;
            for(char c:a){
                if(c=='}'||c==')'||c==']'){
                    char s = (!b.empty())?b.top():'0';
                    if(r[(unsigned char)c]==s) b.pop();
                    else w=false;
                }else b.push(c);
            }
            if(w&&b.size()==0) cout << "yes" << endl;
            else cout << "no" << endl;
    }
    return 0;
}
				
			

     習題 Q-3-3. 加減乘除

				
					#include <bits/stdc++.h>
using namespace std;

int main() {
    string a;cin >> a;
    stack<int> b;b.push(a[0]-'0');
    for(int i=2;i<(int)a.size();i+=2){
        int t = b.top();
        int y = a[i]-'0';
        if(a[i-1]=='/'){
            b.pop();
            b.push(t/y);
        }else if(a[i-1]=='*'){
            b.pop();
            b.push(t*y);
        }else{
            if(a[i-1]=='-') b.push(0-y);
            else b.push(y);
        }
    }
    int s=0;
    while(!b.empty()){
        s+=b.top();
        b.pop();
    }
    cout << s <<endl;
    return 0;
}
				
			

     例題 P-3-4. 最接近的高人

				
					#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;cin >> n;
    stack<pair<int, int>> a;
    long long s = 0;
    for (int i = 1; i <= n; i++) {
        int w;cin >> w;
        while (!a.empty() && a.top().first <= w) a.pop();
        if (!a.empty()) s += i - a.top().second;
        else s += i;
        a.push({w, i});
    }
    cout << s << endl;
    return 0;
}
				
			

     習題 Q-3-5. 帶著板凳排雞排的高人

				
					#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;cin >> n;
    long long s = 0;
    vector<int> h(n),p(n),c;
    for(int i=0;i<n;i++) cin >> h[i];
    for(int i=0;i<n;i++) cin >> p[i];
    for(int i=0;i<n;i++){
        int ans = -1,left = 0,right = c.size()-1;
        int t = h[i] + p[i];
        while(left<=right){
            int ni = (right + left) / 2;
            if(h[c[ni]]&gt;t){
                ans = ni;
                left = ni + 1;
            }else right = ni - 1;
        }
        if(ans == -1) s+= i;
        else s+= i - c[ans] - 1;
        while(!c.empty()&&h[c.back()]<=h[i]) c.pop_back();
        c.push_back(i);
    }
    cout << s << endl;
}