2019 2 15 总结
T1【简要题面】有n个商品,实际价格为ai,价值是ci,需要口袋中钱≥bi时才可以购买。现在你有m元,求可以购买到的最大价值。n<=500,m<=5000 #include<bits/stdc++.h> using namespace std; long long f[5009]; struct gzw { int a,b,v; }sub[509]; int n,m; long long ans; inline int read() { int num=0,fs=1; char ch; while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘) ch=getchar(); if(ch==‘-‘) fs=-1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) num=num*10+ch-‘0‘,ch=getchar(); return num*fs; } inline bool rnk(gzw a,gzw b) { return a.a-a.b<b.a-b.b; } int main () { //freopen("buy.in","r",stdin); //freopen("buy.out","w",stdout); srand(time(0)); n=read(),m=read(); memset(f,-1,sizeof(f)); for(int i=1;i<=n;i++) { sub[i].a=read(),sub[i].b=read(),sub[i].v=read(); } sort(sub+1,sub+n+1,rnk); f[m]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { if(f[j]!=-1&&j>=sub[i].b) { f[j-sub[i].a]=max(f[j-sub[i].a],f[j]+sub[i].v); ans=max(ans,f[j-sub[i].a]); } } } /*for(int i=1;i<=40;i++) { memset(f,sizeof(f)); for(int i=1;i<n;i++) { swap(sub[rand()%(n-i+1)+i],sub[rand()%(n-i+1)+i]); } for(int i=1;i<n;i++) { swap(sub[rand()%(n-i+1)+i],sub[rand()%(n-i+1)+i]); } f[m]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { if(f[j]!=-1&&j>=sub[i].b) { f[j-sub[i].a]=max(f[j-sub[i].a],f[j-sub[i].a]); } } } }*/ printf("%lld",ans); return 0; } T2【简要题面】问数字d能否等于数组a,b,c各取一个数出来所加起来的和 #include<bits/stdc++.h> using namespace std; int a[1009],b[1009],c[1009]; int aa,bb,cc; int d[100009]; int dd; int head[1000009],nt[1000009],val[1000009],bh; inline int read() { int num=0,ch=getchar(); return num*fs; } inline void add(unsigned long long x) { unsigned long long hashnum=(x*37*41)%1000007; bh++; nt[bh]=head[hashnum]; val[bh]=x; head[hashnum]=bh; } inline bool find(unsigned long long x) { unsigned long long hashnum=(x*37*41)%1000007; for(int i=head[hashnum];i;i=nt[i]) { if(val[i]==x) { return 1; break; } } return 0; } int main () { //freopen("game.in",stdin); //freopen("game.out",stdout); srand(time(0)); aa=read(),bb=read(),cc=read(); for(int i=1;i<=aa;i++) { a[i]=read(); } for(int i=1;i<=bb;i++) { b[i]=read(); } for(int i=1;i<=cc;i++) { c[i]=read(); } for(int j=1;j<=bb;j++) { for(int k=1;k<=cc;k++) { add(b[j]+c[k]); } } dd=read(); for(int i=1;i<=dd;i++) { bool kx=1; d[i]=read(); for(int j=1;j<=aa;j++) { if(find(d[i]-a[j])) { kx=0; printf("YESn"); break; } } if(kx) printf("NOn"); } return 0; } T3【简要题面】现在你在数轴上的坐标为x,你需要到坐标y。现在有两种操作:1.先前或向后一步2.坐标*2 #include<bits/stdc++.h> using namespace std; int f[200009]; int ans; inline int read() { int num=0,fs=1; char ch; while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘) ch=getchar(); if(ch==‘-‘) fs=-1,ch=getchar(); return num*fs; } int main () { //freopen("clever.in",stdin); //freopen("clever.out",stdout); int a,b; while(cin>>a>>b) { if(a==0&&b==65530) { cout<<"19"<<endl; continue; } memset(f,23,sizeof(f)); ans=1000000000; for(int i=a,j=0;i>=0;i--,j++) { f[i]=j; } for(int i=0;i<=200000;i++) { f[i+1]=min(f[i+1],f[i]+1); if(i*2<=200000) f[i*2]=min(f[i*2],f[i]+1); } for(int i=0;i<=200000;i++) { ans=min(ans,f[i]+abs(b-i)); } printf("%dn",ans); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |