今天的题比较简单 人均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; }
做法：树形dp+换根 dp[u] 代表u这个子树 子节点到u节点的距离之和，dp[u]+=dp[v]+sz[v] 然后随便换根一下就好了。
做法：水题，记录 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("%.1f\n",ans); } }
水题。
#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; }
做法：简单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("%lld\n",dp[n][m]); }
