牛客练习赛131（未补）

A-小H学语文

题意：木板数量为m，想让m×m×h（min)最大，找出这几块木板

分析：让木板从大到小排序，找到最大的体积，将之前的木板按序列输出

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct A{ll x,idx;
}h[N];
struct AA{ll x,idx;
}b[N];
bool cmp(A xx,A yy){return xx.x>yy.x;
}
bool cmpp(AA xx,AA yy){return xx.idx<yy.idx;
}
void sol(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>h[i].x;h[i].idx=i;}sort(h+1,h+n+1,cmp);ll s=0;ll c=n;for(int i=1;i<=n;i++){if(s<h[i].x*i*i){s=h[i].x*i*i;c=i;}}cout<<c<<endl; for(int i=1;i<=c;i++){b[i].x=h[i].x;b[i].idx=h[i].idx;}sort(b+1,b+c+1,cmpp);for(int i=1;i<=c;i++)cout<<b[i].idx<<" ";
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;while(t--)sol();return 0;
}
​

B-小H学数学

题意：用双手可以有多少种方案凑出x，两只手可以直接表示一个1-10的范围的数，也能表示两个1-5范围的数，每个数都可以选择做加法或减法。一共有y+1个人

分析：dp[i]表示目标为i的方案数，b[i]表示上一个人目标为i的方案数，这个人要分两种情况,一只手和两只手，dp[1000]=1;答案：dp[x+1000];

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N=3e3+10;
const ll mod=1e9+7;
typedef long long ll;
ll x,y,dp[N],b[N];
void sol(){cin>>x>>y;dp[1000]=1;for(int i=1;i<=y+1;i++){//人 memset(b,0,sizeof(b));for(int j=0;j<=2e3;j++){for(int k=-10;k<=10;k++){//一只手 if(k!=0&&j+k>=0)b[j+k]=(dp[j]+b[j+k])%mod; }for(int l=-5;l<=5;l++){//两只手 for(int r=-5;r<=5;r++){if(l!=0&&r!=0&&(j+l+r>=0))b[j+l+r]=(b[j+l+r]+dp[j])%mod;}   }    }memcpy(dp,b,sizeof(dp));}cout<<dp[x+1000];
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;while(t--)sol();return 0;
}