牛客算法周周练13 （A 水 B 换根dp C 水 D 水 E dp）ccsudeer-

题目链接

今天的题比较简单 人均40分钟ak

最小生成树

水题

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e5+10; int a[N],n; int main() {     n=read();          ll ans=0;     rep(i,1,n) a[i]=read(),ans+=a[i];     if(n==1){         puts("0");return 0;     }          sort(a+1,a+1+n);     ans+=1ll*(n-2)*a[1];     cout<<ans<<endl; } 

B-病毒感染

做法：树形dp+换根 dp[u] 代表u这个子树 子节点到u节点的距离之和，dp[u]+=dp[v]+sz[v]  然后随便换根一下就好了。

C-Shopping

做法：水题，记录 1 的个数num，然后前 min(num,m) 大的取一半 剩余的全部取就好了。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e3+10; int a[N],b[N],n,m; bool cmp(int x,int y) {     return x>y; } int main() {     int _=read();while(_--)     {         n=read(),m=read();         int num=0;         rep(i,1,n) {             a[i]=read(),b[i]=read();             num+=b[i];         }         num=min(num,m);         double ans=0;         sort(a+1,a+1+n,cmp );         for(int i=1;i<=num&&i<=n;++i){             ans+=1.0*a[i]/2;         }         for(int i=num+1;i<=n;++i) ans+=a[i];         printf("%.1fn",ans);     } } 

D-铺地毯

水题。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e4+10; struct node {     int x1,y1,x2,y2; }a[N]; int n,x,y; int main() {     n=read();     rep(i,1,n) {         a[i].x1=read(),a[i].y1=read(),a[i].x2=read(),a[i].y2=read();         a[i].x2+=a[i].x1;         a[i].y2+=a[i].y1;     }     x=read(),y=read();     int ans=-1;     rep(i,1,n)     {         if(a[i].x1<=x&&x<=a[i].x2&&a[i].y1<=y&&y<=a[i].y2) ans=i;     }     cout<<ans<<endl; } 

E-金币馅饼

做法：简单dp  考虑到走的方式比较奇特  先枚举列 再枚举行就好了。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=5e2; ll dp[N][N],a[N][N],n,m; int vis[N][N]; int main() {     n=read(),m=read();     rep(i,1,n) rep(j,1,m) a[i][j]=read();     dp[1][1]=a[1][1];     vis[1][1]=1;      for(int j=1;j<=m;++j){         for(int i=1;i<=n;++i){             if(vis[i][j]==0) continue;             vis[i-1][j+1]=1;             vis[i][j+1]=1;             vis[i+1][j+1]=1;              dp[i-1][j+1]=max(dp[i-1][j+1],dp[i][j]+a[i-1][j+1]);             dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a[i][j+1]);             dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+a[i+1][j+1]);         }     }     printf("%lldn",dp[n][m]); }