头像

不二_3




离线:7小时前



不二_3
11小时前

y总讲解
最长上升子序列.png

#include<iostream>
using namespace std;
const int N=1010;
int a[N],f[N];

int main()
{
    int n;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<<"\n";
}


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

不二_3
12小时前

y总讲解:
摘花生.png

/*摘花生   线性dp*/
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int f[N][N],w[N][N]; 
int main()
{
    int T;cin>>T;
    while(T--){
        int r,c;
        cin>>r>>c;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>w[i][j];
            }
        }
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
            }
        }
        cout<<f[r][c]<<"\n";

    }
    return 0;
}


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

不二_3
12小时前
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int f[N][N],v[N],w[N];

int main()
{
    int n,m;
    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][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    int res=f[n][m];
    cout<<res<<"\n";
    return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int f[N],v[N],w[N];
int main()
{
    int n,m;
    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=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<"\n";
    return 0;
}


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

不二_3
20小时前

```

include[HTML_REMOVED]

using namespace std;
int main()
{
int res=0;
int n;cin>>n;
if(n<3){cout<<n<<endl;return 0;}
int i=0;
while(n){
res;
n–;i
;
if(i==3)i=0,n++;
}

cout<<res<<endl;
return 0;

}
```



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

不二_3
20小时前
/*蚂蚁碰面掉头可以认为彼此穿过去了*/
#include<iostream>
#include<cmath>
const int N=55;
int x[N];
using namespace std;
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i];
    int tag=abs(x[1]);
    bool l=false,r=false;
    if(x[1]<0)l=true;
    else r=true; 

    int res=1;
    if(l){
        bool lr=false;
        for(int i=1;i<=n;i++){
            if(x[i]>0&&abs(x[i])<tag)res++,lr=true;
        }
        //右边还可能有向左边走的,他能被感染的前提是母体向左走的时候感染了向右走的蚂蚁
        for(int i=1;i<=n;i++){
            if(lr&&x[i]<0&&abs(x[i])>tag)res++;
        }
    }
    if(r){
        bool rl=false;
        for(int i=1;i<=n;i++){
            if(x[i]<0&&abs(x[i])>tag)res++,rl=true;
        }
        for(int i=1;i<=n;i++){
            if(rl&&x[i]>0&&abs(x[i])<tag)res++;
        }
    }
    cout<<res<<"\n";
    return 0;
 } 


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

不二_3
20小时前
#include<iostream>
#include<cstdio>
#define MAX 1000000
using namespace std;
bool dfs(int num,int x,int y)
{//给定一个数 num,能否用正整数x,y凑出来
    if(num==0)return true;

    if(num>=x&&dfs(num-x,x,y))return true;
    if(num>=y&&dfs(num-y,x,y))return true;

    return false; 

}
int main()
{
    int n,m;
    int res;
    cin>>n>>m;
    /*int _max=n;
    if(n<m) _max=m;
    for(int i=_max;i<=1100;i++){
        if(!dfs(i,n,m))res=i;
    }*/
    res=n*m-m-n;
    printf("%d",res);

    return 0;
 } 


活动打卡代码 AcWing 1219. 移动距离

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e4+10;

int main()
{
    int w,m,n;
    cin>>w>>m>>n;
    //m--,n--;/*从1开始计算行号*/
    int x1,y1,x2,y2;

    y1=m%w;
    if(y1==0)x1=m/w;else x1=m/w+1;
    if(x1%2==0){
        if(y1==0)y1=1;
        else y1=w-y1+1;
    }
    else {
        if(y1==0)y1=w;
    }
    y2=n%w;
    if(y2==0)x2=n/w;else x2=n/w+1;
    if(x2%2==0){
        if(y2==0)y2=1;
        else y2=w-y2+1;
    }
    else {
        if(y2==0)y2=w;
    }

    int res=abs(x1-x2)+abs(y1-y2);

    cout<<res<<"\n";

    return 0;
}


活动打卡代码 AcWing 1245. 特别数的和

枚举每个数,对每个数分解位数判断即可

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

using namespace std;
bool judge(int n){
    int dig;
    while(n){
        dig=n%10;
        n/=10;
        if(dig==2||dig==0||dig==1||dig==9)return true;
    }
    return false;
}
int main()
{
    int n;cin>>n;
    long long res=0;
    for(int i=1;i<=n;i++){
        if(judge(i))
            res+=i;
    } 
    printf("%lld\n",res);

    return 0;
}



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

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

using namespace std;
const int N=32009;//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>0;i-=lowbit(i))res+=tr[i];
    return res;
}
int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        x++;
        level[sum(x)]++;
        add(x);
    } 
    for(int i=0;i<n;i++)printf("%d\n",level[i]);

    return 0;
}




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

using namespace std;
const int N=1e5+10;
int n,m;
int A[N],tr[N];
int lowbit(int x){
    return x&-x;
}
void add(int x,int v){
    //x位置的元素+v ,修改树状数组 
    for(int i=x;i<=n;i+=lowbit(i))
        tr[i]+=v; 
}
int query(int x){
    //求Sx
    int res=0; 
    for(int i=x;i>0;i-=lowbit(i))
        res+=tr[i];
    return res; 
}
int main()
{
    cin>>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,a,b;
        scanf("%d%d%d",&k,&a,&b);
        if(k==0)printf("%d\n",query(b)-query(a-1));
        else add(a,b);
    }
    return 0;
}