红鲤鱼与绿鲤鱼与驴

今天把昨天学的二分和快速幂的练习做了一下

1、题意：n块木头切成等长的k段，求小段木头最长可以为多少。

2、思路：比较基础 正常做就行

3、代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
long long n,k;
long long a[100005];
int judge(long long m){
    long long cnt=0;
    for(int i=1;i<=n;i++){
        cnt=cnt+a[i]/m;
        if(cnt>=k)
            return 1;
    }
    return 0;
}
int main() {
    long long ans=0;
    cin>>n>>k;
    long long maxx=-1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>maxx)
            maxx=a[i];
    }
    long long l=0,r=maxx;
    while(l<r-1){
        long long mid=(l+r)/2;
        if(judge(mid)){
            ans=mid;
            l=mid;
        }else
            r=mid;
    }
    cout<<ans;
    return 0;
}

1、题意：给定正整数数列A，求一个平均数最大、长度不小于f的连续子段

2、思路：如果把数列中每个数都减去二分值，就把为问题转化为求是否存在一个长度不小于f的子段且字段和非负；

图片说明

每次只会有一个新的取值进入min{sum_j}的候选集合，所以只需要用一个变量记录当前最小值，跟sum_(i-f)进行比较取小的就可以了

3、代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
double a[100005],b[100005],sum[100005];
int main() {
    int n,f;
    cin>>n>>f;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    double eps=1e-4;
    double left=-1e6,right=1e6;
    while(right-left>eps){
        double mid=(right+left)/2;
        for(int i=1;i<=n;i++)
            b[i]=a[i]-mid;
        for(int i=1;i<=n;i++)
            sum[i]=sum[i-1]+b[i];
        double ans=-1e10;
        double min_val=1e10;
        for(int i=f;i<=n;i++){
            min_val=min(min_val,sum[i-f]);
            ans=max(ans,sum[i]-min_val);
        }
        if(ans>=0)
            left=mid;
        else
            right=mid;
    }
    cout<<(int)(right*1000);
    return 0;
}

1、题意：已知数列 a1=a2=a3=1 a_x=a_(x-1)+a_(x-3) (x>=4) 求第n项 (mod 1e9+7)

2、思路：
A [ 4 ] = A [ 3 ] * 1 + A [ 2 ] * 0 + A [ 1 ] * 1
A [ 3 ] = A [ 3 ] * 1 + A [ 2 ] * 0 + A [ 1 ] * 0
A [ 2 ] = A [ 3 ] * 0 + A [ 2 ] * 1 + A [ 1 ] * 0

图片说明

可得如下矩阵式：

图片说明
3、代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+7;
struct Mat{
    long long m[5][5];
}ans,a;
Mat Mul(Mat a,Mat b,int n){
    Mat c;
    memset(c.m,0,sizeof(c.m));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j])%mod)%mod;            
    return c;
}
int main() {
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        if(n<4){
            cout<<"1"<<endl;
            continue;
        }
        n-=3;
        memset(ans.m,0,sizeof(ans.m));
        memset(a.m,0,sizeof(a.m));
        ans.m[1][1]=ans.m[1][2]=ans.m[1][3]=1;
        a.m[1][1]=a.m[1][2]=a.m[2][3]=a.m[3][1]=1;
        while(n){
            if(n&1)
                ans=Mul(ans,a,1);
            a=Mul(a,a,3);
            n>>=1;
        }
        cout<<ans.m[1][1]<<endl;
    }
    return 0;
}

自言自语Part：
昨天果然鸽了 不过这样的节奏也挺好的
今天没有 “ Good Luck ! ” 可以迟到但别缺席呀 拜托拜托