牛客练习赛114

A.最后有0得数肯定是10得倍数，然后直接排序即可

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10,mod=1e9+7;
int n;
void solve(){cin>>n;vector<int> a(n);for(auto&i:a) cin>>i;sort(a.begin(),a.end(),greater<>());if(a.back()!=0) cout<<"-1";else{for(auto x:a) cout<<x;}
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;// cin>>t;while(t--) solve();return 0;
}

C.首先把每个递增的区间处理出来，然后问题就变成了，用最少的区间个数去覆盖1到m这条线段即可

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;int n,m;
int a[N],b[N];
void solve(){cin>>n>>m;int st=1,ed=m;for(int i=1;i<=n;i++) cin>>a[i];vector<PII> b;for(int i=1;i<=n;i++){int j=i;while(j+1<=n&&a[j]==a[j+1]-1){j++;}if(j!=i){b.emplace_back(a[i],a[j]);i=j-1;}else b.emplace_back(a[i],a[i]);}sort(b.begin(),b.end());//for(auto[l,r]:b) cout<<l<<" "<<r<<"\n";int res=0;bool success=false;m=b.size();int l=1,r=1;for(int i=0;i<m;i++){int j=i;while(j<m&&b[j].first<=l){r=max(r,b[j].second);j++;}res++;if(r>=ed) break;l=r+1;if(j>i+1) i=j-1; }if(r<ed) res=-1;cout<<res<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();return 0;
}

D.首先我们要么从最大一个数开始往前，要么从最小的一个数开始往后

首先想个问题假设从最大的数往前枚举

 

假设a[n]的个数小于a[n-1]那么直接false，a[n-1]无法支撑全部的a[n]连续，所以我们要尽可能减少a[j]让a[i]<=a[j]

 假设从n一直往前拿，什么时候一定要停止呢，

a[i]<a[j]一定要停止拿了，拿完a[j]就别拿a[i]的意思

假设我a[i]和a[j]都拿了，那么同样陷入了a[i]不足以支撑全部a[j]连续,所以这个时候我只能靠

a[j] a[j+1] a[j+2] a[j+3] a[j+4].... 把这个多的a[j]拿走，我才有可能处理a[j]的个数

假设a[i]==a[j]，倒是无所谓

a[i]>a[j]，就继续拿a[i]，方便后面处理k<i<j
a[k]>a[i]<a[j]，这个情况拿完a[i]可以继续拿a[k]，不影响a[k]后面的决策

a[k]<a[i]<a[j],由于a[i]>a[k]我们不会拿a[k]，此时a[i]减少，更有利拿完

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;int n,m;
int a[N],b[N];
void solve(){cin>>n;vector<int> cnt(n+1,0);for(int i=1;i<=n;i++){cin>>a[i];cnt[a[i]]++;}for(int i=n;i>=1;i--){while(cnt[i]){int cnt0=0;for(int j=i;j>=1;j--){cnt[j]--;cnt0++;if(cnt[j-1]<cnt[j]+1) break;}if(cnt0<5) {cout<<"NO\n";return ;}}}cout<<"YES\n";
}
signed main(){// cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();return 0;
}

 

E.

每个人得到得物品个数概率都是同样的，所以只要计算出一个人获得物品个数的概率最后乘上n即可

dp：方程就变成前i轮，已经连续j次没中奖的物品个数概率

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;int n,m,k,d;
int a[N],b[N];
int fact[N],infact[N];int qmi(int a,int k,int p){int res=1;while(k){if(k&1) res=(LL) res*a%p;a=(LL)a*a%p;k>>=1;}return res;
}
void init(){fact[0]=infact[0]=1;for(int i=1;i<N;i++){fact[i]=(LL)fact[i-1]*i%mod;infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;}
}
int C(int a,int b){if(b<0||b>a) return 0;return ((LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
void solve(){cin>>n>>m>>k>>d;//n选手选k个人，参加m轮，连续dint t1=k*qmi(n,mod-2,mod)%mod;int t2=(n-k)*qmi(n,mod-2,mod)%mod;vector<vector<int>> f(m+10,vector<int>(d+10,-1));std::function<int(int,int)> dfs=[&](int i,int j)->int{//前 i轮，连续j次没中if(i == m+1)return 0;auto &res = f[i][j];if(res!=-1)return res;res = 0;if(j+1==d){res=(dfs(i+1,0)+1)*t1%mod+(dfs(i+1,0)+1)*t2%mod;}else{res=dfs(i+1,j+1)*t2%mod+(dfs(i+1,0)+1)*t1%mod;}res%=mod;return res;};int res=dfs(1,0)*n%mod;cout<<(res%mod+mod)%mod<<"\n";
}
signed main(){// cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;init();while(t--) solve();return 0;
}

F.

首先这个答案图像最后一定是一个山峰或者单调递增的线，如图，它可以左右往返跳跃

从最高点开始，那么我们枚举每个位置i，那么最优解肯定是当前i右边最高的点，然后这个最高的点再单调递减的一个图，我们预处理出当前位置

为啥要处理无重复元素呢，因为他是严格小于的，假设右边往下的线中有一个和左边重复的元素，那么他是重复的，他是不能走的，而又由于我们枚举的i位置是在左边，一定要用到当前i，所以如果左边和右边元素重叠我们要选择左边的，因为如果选择右边的话，左边这个一直存在，那么我永远选不到i了，因为题目说得紧邻左侧或右侧，i右边那个点都没选完，我i根本没可能选得到