头像

liyx19




离线:4小时前


活动打卡代码 AcWing 1163. 纪念品

liyx19
4小时前
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=10005;
int v[N],w[N],f[N],t[N];
int T,n,m;
void bag(){//完全背包
    memset(f,0,sizeof f);
    for(int i=1;i<=n;i++){
        if(w[i]<0) continue;
        for(int j=v[i];j<=m;j++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    m+=f[m];
}
int main(){
    cin>>T>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);//第一天全部输进
    for(int i=2;i<=T;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&t[j]);//输入当日价格
            w[j]=t[j]-v[j];
        }
        bag();
        for(int j=1;j<=n;j++){
            v[j]=t[j];
        }
    }
    cout<<m;
}


活动打卡代码 AcWing 9. 分组背包问题

liyx19
1天前
#include<iostream>
using namespace std;
const int N=105;
int f[N];
int v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int s;
        cin>>s;
        for(int j=1;j<=s;j++){
            cin>>v[j]>>w[j];
        }
        for(int j=m;j>=0;j--){
            for(int k=1;k<=s;k++){
                if(j>=v[k]) f[j]=max(f[j],f[j-v[k]]+w[k]);
            }
        }
    }
    cout<<f[m];
}


活动打卡代码 AcWing 4. 多重背包问题

liyx19
4天前
#include<iostream>
using namespace std;
const int N=5e5;
int v[N],w[N];
int f[N];
int main(){
    int n,m,l=0;
    cin>>n>>m;
    int vv,ww,ss;
    for(int i=1;i<=n;i++){
        cin>>vv>>ww>>ss;
        int k=1;
        while(ss>k){
            v[++l]=k*vv;
            w[l]=k*ww;
            ss-=k;
            k*=2;
        }
        v[++l]=ss*vv;
        w[l]=ss*ww;
    }
    for(int i=1;i<=l;i++){
        for(int j=m;j>=v[i];j--) 
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
}


活动打卡代码 AcWing 5. 多重背包问题 II

liyx19
4天前
#include<iostream>
using namespace std;
const int N=5e5;
int v[N],w[N];
int f[N];
int main(){
    int n,m,l=0;
    cin>>n>>m;
    int vv,ww,ss;
    for(int i=1;i<=n;i++){
        cin>>vv>>ww>>ss;
        int k=1;
        while(ss>k){
            v[++l]=k*vv;
            w[l]=k*ww;
            ss-=k;
            k*=2;
        }
        v[++l]=ss*vv;
        w[l]=ss*ww;
    }
    for(int i=1;i<=l;i++){
        for(int j=m;j>=v[i];j--) 
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
}


活动打卡代码 AcWing 450. 寻宝

liyx19
4天前
#include<iostream>#include<cstdio>using namespace std;const int N=10005,mod=20123,M=105;int st[N][M],x[N][M];int main(){    int n,m;    scanf("%d%d",&n,&m);    for(int i=0;i<n;i++)        for(int j=0;j<m;j++) scanf("%d%d",&st[i][j],&x[i][j]);    int res=0;    int k;    scanf("%d",&k);    for(int i=0;i<n;i++){        int s=0;        for(int j=0;j<m;j++) s+=st[i][j];        int t=x[i][k];        res=(res+t)%mod;        t%=s;        if(!t) t=s;        for(int j=k; ;j=(j+1)%m){            if(st[i][j]){                if(--t==0){                    k=j;                    break;                }            }        }    }    cout<<res<<endl;}




liyx19
4天前

算法1

(简单的模拟) O(n)

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N=5005;
struct AC{
int k,s;
}a[N];
int cmp(AC a,AC b){//香的一批的cmp
if(a.s==b.s) return a.k[HTML_REMOVED]b.s;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i){
cin>>a[i].k>>a[i].s;
}
sort(a+1,a+n+1,cmp);
m=(int)(m*1.5);
cout<[HTML_REMOVED]=a[m].s) cnt
;
}
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++){
cout<<a[i].k<<” “<<a[i].s<<endl;
}
}



活动打卡代码 AcWing 438. 分数线划定

liyx19
4天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5005;
struct AC{
    int k,s;
}a[N];
int cmp(AC a,AC b){
    if(a.s==b.s) return a.k<b.k;
    return a.s>b.s; 
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].k>>a[i].s;
    }
    sort(a+1,a+n+1,cmp);
    m=(int)(m*1.5);
    cout<<a[m].s<<" ";
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i].s>=a[m].s) cnt++; 
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++){
        cout<<a[i].k<<" "<<a[i].s<<endl;
    }
}



liyx19
4天前

算法1

(模拟) O(n)

include[HTML_REMOVED]//无需任何脑筋,依题意模拟的去就OK了

include[HTML_REMOVED]

using namespace std;
int main(){
int n;
cin>>n;
for(int i=n;i>=0;i–){
int k;//不需要数组
cin>>k;
if(k==0) continue;//系数为0
if(k>0 && i!=n) cout<<”+”; //依题意先输出符号
if(k<0) cout<<”-“;
k=abs(k);//取绝对值
if(k==1){//系数为1要特判
if(i>1) cout<<”x^”<[HTML_REMOVED]1) cout<<”x^”<<i;
if(i==1) cout<<”x”;
if(i==0) break;
}
}
}



活动打卡代码 AcWing 437. 多项式输出

liyx19
4天前
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=n;i>=0;i--){
        int k;
        cin>>k;
        if(k==0) continue;//系数为0
        if(k>0 && i!=n) cout<<"+"; 
        if(k<0) cout<<"-";
        k=abs(k);
        //cout<<k;
        if(k==1){
            if(i>1) cout<<"x^"<<i;
            if(i==1) cout<<"x";
            if(i==0){
                cout<<k;
                break;
            } 
        }
        else{
            cout<<k;
            if(i>1) cout<<"x^"<<i;
            if(i==1) cout<<"x";
            if(i==0) break;
        }
    }
}


活动打卡代码 AcWing 463. 求和

liyx19
4天前
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5,mod=10007;
int color[N],sum[N][2],w[N],cnt[N][2];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&color[i]);
        sum[color[i]][i%2]=(sum[color[i]][i%2]+w[i])%mod;
        cnt[color[i]][i%2]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+(i*((cnt[color[i]][i%2]-2)*w[i]%mod+sum[color[i]][i%2])%mod)%mod)%mod;
    }
    cout<<(ans+mod)%mod;
}