头像

小明_3




离线:17分钟前


最近来访(75)
用户头像
Bear_King
用户头像
向北
用户头像
ZhgDgE
用户头像
自律
用户头像
我要冷静思考
用户头像
ヅ天使ぺ嫙嵂
用户头像
RyanMoriarty
用户头像
菜狗一个
用户头像
海_5
用户头像
X-7D1C11010
用户头像
沄逸
用户头像
wssdl
用户头像
用户头像
滑稽先生
用户头像
不知_4
用户头像
2001f
用户头像
XUGUOHAO
用户头像
省四弱鸡
用户头像
DarksideCoder
用户头像
十二ya

活动打卡代码 AcWing 1216. 饮料换购

小明_3
17小时前
#include<iostream>
using namespace std;
const int N =1e4+10;
int main()
{
    int n;
    cin>>n;
    int res=n;
    while(n>=3)
    {
        res +=n/3;
        n = n%3+n/3;
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int  N= 1010;
int a[N][N];
int s[N][N];
int main()
{
    int n,m ,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
    while(q--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 795. 前缀和

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =1e5+10;
int s[N], a[N];
int main()
{
    int n ,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i] =s[i-1]+a[i];
        }   
    while(m--)
    {
        int l, r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    double x;
    cin>>x;
    double l=-1e4, r=1e4;
    while(r-l>1e-8)
    {
        double mid=(l+r)/2;
        if(mid*mid*mid>=x)  r=mid;
        else                l=mid;
    }
    printf("%.6lf",l);
    return 0;
 } 


活动打卡代码 AcWing 789. 数的范围

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =1e5+10;
int a[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)    cin>>a[i];
    while(m--)
    {
        int x;
        cin>>x;
        int l=0, r=n-1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(a[mid]>=x)   r=mid;
            else            l=mid+1; 
        }
        if(a[l]!=x) cout<<"-1 -1"<<endl;
        else
        {
            cout<<l<<" ";
            int l=0, r=n-1;
            while(l<r)
            {
                int mid=(l+r+1)/2;
                if(a[mid]<=x)   l=mid;
                else            r=mid-1;
            }
            cout<<l<<endl;
        }   
    }
    return 0;
}



#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =1010;
int f[N];
int a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        f[i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j])
                f[i]=max(f[i],f[j]+1);
        }
    }
    sort(f+1,f+1+n);
    cout<<f[n]<<endl;
    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =110;
int g[N][N];
int f[N][N];
int n,m;
int main()
{
    int T ;
    cin>>T;
    while(T--)
    {
        memset(f,0,sizeof f);
        memset(g,-0x3f3f,sizeof g);
        int n, m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>g[i][j];
        f[1][1]=g[1][1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(i>1) f[i][j]=max(f[i][j],f[i-1][j]+g[i][j]);
                if(j>1) f[i][j]=max(f[i][j],f[i][j-1]+g[i][j]);
            }
        cout<<f[n][m]<<endl;
     } 
     return 0;

}  


活动打卡代码 AcWing 2. 01背包问题

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =1010;
int w[N], v[N];
int f[N][N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(v[i]<=j)
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    cout<<f[n][m]<<endl;
    return 0;
} 



题目描述

这道题我们本来就是能用前缀和直接做出来 但是超时了 我们需要进行优化
实际上问题已经化简为有多少个当R已经定了 1到r-1的余数是和S[R]相等的

这里我们输入我们的信息 然后我们构造我们的前缀和数组

这里我们遍历我们前缀和数组 然后看r前面有多少个的前缀和与k的余数是等于我们的s[i]%k 即res+= 这个cnt
我们每次将我们的前缀和数组所取余的的数进行统计
Res是我们的答案 我们为什么将cnt[0]设置为1 这是因为当我们首次遇到s[i]%k的余数为零 此时的res就要加一 但是我们初始的时候cnt[0]为0 加不上 所以先将cnt[0]设置为1

本质上还是根据我们前缀和数组进行化简 得到我们的一个结论 即R确定的时候 以小于R为终点的前缀和对K的余数是等于S[R]
这里我们就可以进行想到cnt数组 进行保存之前前缀和对k取余的余数的个数
遍历到以Ri为右端点的时候 直接加上当前状态最新的cnt[s[i]%k]的个数 cnt就是保存前面取余等于k的总共的个数
而初始化cnt[0]=1保证了 我们当第一次遇到S[i]%k=0的时候 本身这个s[i]就是k的倍数了 所以预先使得cnt[0]=1

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll a[N],s[N],cnt[N];
int main()
{
    ll n, k;
    cin>>n>>k;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i] =s[i-1]+a[i];  
    }
    cnt[0]=1;
    ll res=0;
    for(ll i=1;i<=n;i++)
    {
        res += cnt[s[i]%k];
        cnt[s[i]%k]++;
    }
    cout<<res<<endl;
    return 0;

 } 


活动打卡代码 AcWing 1230. K倍区间

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll a[N],s[N],cnt[N];
int main()
{
    ll n, k;
    cin>>n>>k;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i] =s[i-1]+a[i];  
    }
    cnt[0]=1;
    ll res=0;
    for(ll i=1;i<=n;i++)
    {
        res += cnt[s[i]%k];
        cnt[s[i]%k]++;
    }
    cout<<res<<endl;
    return 0;

 }