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

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

#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;
}

出處:https://judge.tcirc.tw/ShowProblem?problemid=d022

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

擱置了半年,如今終於解開。與 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;
}

出處:https://judge.tcirc.tw/ShowProblem?problemid=d073

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;
}

以後都用這個啦(Highlighting code block),這樣就不用手動調色了。