头像

eric_fyq

$\href{https://cpp.sh/}{\huge\color{red}{我的编辑器}}$




离线:25分钟前


最近来访(148)
用户头像
空前
用户头像
鲸鱼不会飞
用户头像
Rywa
用户头像
梨绘小棠
用户头像
逍遥曹大仙
用户头像
Dark铭
用户头像
bwd
用户头像
今年拿省一
用户头像
半瓶可乐
用户头像
吴梦涵2022
用户头像
Jadore
用户头像
hudabi
用户头像
金陵笑笑生
用户头像
学会DP
用户头像
种花家的虎式坦克
用户头像
robben--10
用户头像
18910310021
用户头像
yxc的小迷妹
用户头像
reflectd
用户头像
Q_Chivalrous

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

eric_fyq
16小时前
#include <iostream>
using namespace std;
const int N = 110;

int n,w[N][N],f[N][N];
int x,y;
int main()
{
    cin>>n;
    while (n -- ){
        cin>>x>>y;
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                cin>>w[i][j];
            }
        }
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
            }
        }

        cout<<f[x][y]<<endl;
    }

    return 0;
}



eric_fyq
20小时前

1.动态规划法

#include <iostream>
using namespace std;

const int N = 1010;

int n,f[N],a[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 j=1;j<=i;j++)
        {
            if(a[j]<a[i])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);

    cout<<res<<endl;

    return 0;
}


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

eric_fyq
22小时前
#include <iostream>
using namespace std;
const int N = 1010;

int w[N],v[N];
int n,m;
int f[N][N];
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=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i-1][j-v[i]]+w[i],f[i][j]);
        }
    }

    cout<<f[n][m]<<endl;

    return 0;
}


活动打卡代码 AcWing 1211. 蚂蚁感冒

eric_fyq
22小时前
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n; 
int main()
{
    scanf("%d", &n);
    int pivot, left = 0, right = 0;
    scanf("%d", &pivot);

    for (int i = 1; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        //找到感冒蚂蚁左边边且向右走的
        if (abs(x) < abs(pivot) && x > 0) right++;
        //找到感冒蚂蚁右边且向左走的
        if (abs(x) > abs(pivot) && x < 0) left++;
    }
    //特殊情况
    if ((pivot < 0 && right == 0) || pivot > 0 && left == 0) puts("1");
    else printf("%d\n", left + right + 1);

    return 0;
}


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

eric_fyq
23小时前
#include <iostream>
using namespace std;
int main()
{
    int n,res;
    cin>>n;
    res=n;
    while(n>=3)
    {
        int x=n/3;
        res+=x;
        n-=x*3;
        n+=x;
    }
    cout<<res<<endl;

    return 0;
}


活动打卡代码 AcWing 1205. 买不到的数目

暴力打表找规律

#include <iostream>
#include <algorithm>

using namespace std;

bool dfs(int m,int p,int q)
{
    if(!m) return true;

    if(m>=p&&dfs(m-p,p,q)) return true;
    if(m>=q&&dfs(m-q,p,q)) return true;

    return false;
}
int main()
{
    int p,q;
    cin>>p>>q;
    int res=0;

    for(int i=1;i<=100;i++)
    {
        if(!dfs(i,p,q)) res=i;
    }
    cout<<res<<endl;

    return 0;
}

结论题代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <time.h>
using namespace std;
int main()
{
    int p,q;
    cin >> p >> q;
    cout << (p-1)*(q-1)-1<<endl;
    return 0;
}



#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <time.h>
using namespace std;
int main()
{
    clock_t start,finish;
    start=clock();
    //这里写测试代码


    finish=clock();
    cout<<double(finish-start)/CLOCKS_PER_SEC<<endl;

    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <climits>
using namespace std;

const int N = 1e5+10;

int n,m,x,y;
int w[N];

struct node{
    int l,r;
    int maxv;
}tr[N*4];

void pushup(int u)
{
    tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
}

void built(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,w[r]};
    else {
        tr[u]={l,r};
        int mid=l + r >> 1;
        built(u<<1,l,mid),built(u<<1|1,mid+1,r);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxv;
    int mid=tr[u].l+tr[u].r>>1;
    int maxv=INT_MIN;
    if(l<=mid) maxv=max(query(u<<1,l,r),maxv);
    if(r>mid) maxv=max(query(u<<1|1,l,r),maxv);
    return maxv;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    built(1,1,n);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",query(1,x,y));
    }
    return 0;
}


活动打卡代码 AcWing 1265. 数星星

线段树上线段果,线段树下我放火

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 32010;

int n;
int tr[N], level[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x)
{
    for (int i = x; i < N; i += lowbit(i)) tr[i] ++ ;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x ++ ;
        level[sum(x)] ++ ;//其实这个sum(x)返回的就是n的级别
        // cout<<sum(x)<<endl;
        add(x);
    }



    for (int i = 0; i < n; i ++ ) printf("%d\n", level[i]);

    return 0;
}




树状数组

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5+10;

int a[N],tri[N];
int n,m;

int lowbit(int x)
{
    return x & -x;
}

void add(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i)) tri[i]+=v;
}

int query(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tri[i];
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    for(int i=1;i<=n;i++) add(i,a[i]);

    while (m -- ){
        int k,x,y;
        cin>>k>>x>>y;
        if(k==0) printf("%d\n",query(y)-query(x-1));
        else add(x,y);
    }
    return 0;
}

线段树

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int n,m,w[N];

struct node{
    int l,r;
    int sum;
}tr[N*4];

//由子节点去更新父节点
void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
//建立以u为根节点的树,用到pushup()
void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,w[r]};
    else{
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
//查询操作
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    int mid=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=mid) sum+=query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);
    return sum;
}
//将给定的节点的值加上v
void modify(int u,int x,int v)
{
    if(tr[u].l==tr[u].r) tr[u].sum+=v;
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    build(1,1,n);

    int k,a,b;
    while (m -- ){
        scanf("%d%d%d",&k,&a,&b);
        if(k==0) printf("%d\n",query(1,a,b));
        else modify(1,a,b);
    }
    return 0;
}