C++ 基礎題 Q-2-13 無理數的快速冪

題目連結:d024. Q_2_13 無理數的快速冪 (108高中全國賽, simplifed) – JMJudge

實做好無理數的乘法後就簡單了

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

const int p=1000000009;
struct number{
    long long x,y;
};
number operator*(number a,number b){
    number c;
    c.x=((a.x*b.x%p)+(2*a.y*b.y%p))%p;
    c.y=((a.x*b.y%p)+(a.y*b.x%p))%p;
    return c;
}

number powerNum(number x,int n){
    if(n==1) return x;
    if(n&1) return x*powerNum(x,n-1);
    number t=powerNum(x,n/2);
    return t*t;
}

int main(){
    int n;
    number a;
    cin>>a.x>>a.y>>n;
    number ans=powerNum(a,n);
    cout<<ans.x<<" "<<ans.y;
    return 0;
}

C++ 基礎題 Q-6-5 二維最大子矩陣

題目連結:d074. Q_6_5 二維最大子矩陣 – JMJudge

擱置了半年,如今終於解開。與 Q-2-12有異曲同工之妙,但複雜度變O(n2m)。

#include<bits/stdc++.h>
using namespace std;
#define r first
#define c second
#define INF 100000000000
typedef long long ll;

ll a[205][205],p[205][205];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            p[i][j]=p[i-1][j]+a[i][j];
        }
    }

    ll ans=0;
    for(int i=0;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ll psum=0;
            for(int k=0;k<m;k++){
                psum+=p[j][k]-p[i][k];
                if(psum<0) psum=0;
                ans=max(psum,ans);
            }
        }
    }
    cout<<ans;
    return 0;
}

C++ APCS325 Q-2-12 最接近的子矩陣和

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

int main(){
    int k,m,n;
    cin>>k>>m>>n;
    vector<int> a[55],ps[55];

    for(int i=0;i<n;i++) ps[0].push_back(0);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            int tmp;cin>>tmp;
            a[i].push_back(tmp);
            ps[i].push_back(tmp);
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<n;j++){
            ps[i][j]+=ps[i-1][j];
        }
    }

    int best=0;
    for(int i=0;i<m;i++){
        for(int j=i+1;j<=m;j++){
            set<int> s({0});
            int psum=0;
            for(int o=0;o<n;o++){
                psum+=(ps[j][o]-ps[i][o]);
                auto it=s.lower_bound(psum-k);
                if(it!=s.end()){
                    best=max(best,psum-(*it));
                }
                s.insert(psum);
            }
        }
    }
    cout<<best<<"\n";
    return 0;
}

APCS 325 習題Q-4-8. 先到先服務

題目連結:d050. Q_4_8 先到先服務 (* – JMJudge

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

int main(){
    ios::sync_with_stdio(false);

    ll n,m,worst;
    cin>>n>>m;
    priority_queue<ll> bars;
    for(int i=0;i<m;i++){
        bars.push(0);
    }
    for(int i=0;i<n;i++){
        ll total=bars.top();
        bars.pop();
        int ipt=0; cin>>ipt;
        total-=ipt;
        worst=max(-(total),worst);
        bars.push(total);
    }
    cout<<worst;
    return 0;
}

APCS 325 習題Q-3-13 X差值範圍內的最大Y差值

題目連結:d041. Q_3_13 X差值範圍內的最大Y差值 – JMJudge

#include<iostream>
#include<algorithm>
#include<cmath> 
#include<deque>
#include<fstream>
using namespace std;

struct posion{
    int x,y;
};

bool cmp(posion a,posion b){
    return a.x<b.x;
}

posion seq[200010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,L;
    cin>>n>>L;
    for(int i=0;i<n;i++){
        cin>>seq[i].x;
    }
    for(int i=0;i<n;i++){
        cin>>seq[i].y;
    }
    sort(seq,seq+n,cmp);

    int best=0;
    deque<int> max,min;
    for(int i=0,j=0;i<n;i++){
        while(!max.empty() && seq[i].x-seq[max.back()].x>L)
            max.pop_back();
        while(!min.empty() && seq[i].x-seq[min.back()].x>L)
            min.pop_back();
        while(!max.empty() && seq[i].y>seq[max.back()].y)
            max.pop_front();
        while(!min.empty() && seq[i].y<seq[min.back()].y)
            min.pop_front();
        max.push_front(i);
        min.push_front(i);

        if(!max.empty() && !min.empty() && 
            abs(seq[max.back()].y-seq[min.back()].y)>best){
                best=abs(seq[max.back()].y-seq[min.back()].y);
            }
    }
    cout<<best;
    return 0;
}