牛客算法周周练13水题

Powered by:AB_IN 局外人

A 最小生成树

贪心算法，最小的数当父节点，其他数均为子节点。

n = int(input()) a = list(map(int,input().split())) a.sort() print(sum(a)+a[0]*(n-2))

C Shopping

依然是贪心，把获得半价的权力给价格高的即可。

#include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) typedef unsigned long long ull; typedef long long ll; ll a[1001],t,n,m,b; using namespace std; namespace IO{ char ibuf[1<<21],*ip=ibuf,*ip_=ibuf; char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21); inline char gc(){ if(ip!=ip_)return *ip++; ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin); return ip==ip_?EOF:*ip++; } inline void pc(char c){ if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf; *op++=c; } inline ll read(){ register ll x=0,ch=gc(),w=1; for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1; for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48; return w*x; } template<class I> inline void write(I x){ if(x<0)pc('-'),x=-x; if(x>9)write(x/10);pc(x%10+'0'); } class flusher_{ public: ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);} }IO_flusher; } using namespace IO; int main() { t=read(); while(t--){ n=read();m=read(); double sum=0; ll cnt=0; for(int i=1;i<=n;i++){ a[i]=read(); b=read(); sum+=a[i]; cnt+=b; } sort(a+1,a+1+n); ll j=min(cnt,m); for(int i=n;i>=n-j+1;i--) sum-=1.0*a[i]/2; printf("%.1lf\n",sum); } }

D 铺地毯

洛谷原题，以前写过，就直接把代码搬过来了。 思路就是：从头开始记下每个地毯的四个坐标，然后从尾开始判定点是不是在地毯里。

#include <bits/stdc++.h> using namespace std; const int N=1e5+1; int a[N][5],n,x,y,flag; int main() { while(cin>>n){ flag=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]==0; } } for(int i=1;i<=n;i++){ cin>>a[i][1]>>a[i][2]>>a[i][3]>>a[i][4]; a[i][3]=a[i][3]+a[i][1];//向右 a[i][4]=a[i][4]+a[i][2];//向上 } cin>>x>>y; for(int i=n;i>=1;i--){ if(x>=a[i][1]&&x<=a[i][3]&&y>=a[i][2]&&y<=a[i][4]){ cout<<i<<endl; flag=1; break; } } if(flag==0) cout<<"-1"; } return 0; }

E 金币馅饼

dp基础题。 一个点只能由它的，左上，正左，左下走来。（前一列的三个点） 所以要一列一列判断。 则状态转移方程： $$dp[i][j]=max(max(dp[i-1][j-1],dp[i][j-1]),dp[i+1][j-1])$$ 然而有些点可能无法到达，因为dp值为0，而金币数>0，所以判断一下: $$if(dp[i][j])dp[i][j]+=a[i][j];$$

#include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) #define rep(i,x,y) for (int i=(x);i<=(y);i++) typedef long long ll; ll a[120][120],n,m,dp[120][120]; using namespace std; namespace IO{ char ibuf[1<<21],*ip=ibuf,*ip_=ibuf; char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21); inline char gc(){ if(ip!=ip_)return *ip++; ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin); return ip==ip_?EOF:*ip++; } inline void pc(char c){ if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf; *op++=c; } inline ll read(){ register ll x=0,ch=gc(),w=1; for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1; for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48; return w*x; } template<class I> inline void write(I x){ if(x<0)pc('-'),x=-x; if(x>9)write(x/10);pc(x%10+'0'); } class flusher_{ public: ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);} }IO_flusher; } using namespace IO; int main() { n=read();m=read(); rep(i,1,n){ rep(j,1,m){ a[i][j]=read(); } } dp[1][1]=a[1][1]; rep(j,2,m){ rep(i,1,n){ dp[i][j]=max(max(dp[i-1][j-1],dp[i][j-1]),dp[i+1][j-1]); if(dp[i][j]) dp[i][j]+=a[i][j]; } } write(dp[n][m]); return 0; }

完结。