最新要闻

广告

手机

小区建成老年活动室服务居民

小区建成老年活动室服务居民

 药康生物:财务总监焦晓杉辞职 将尽快完成新任财务总监选聘工作

药康生物:财务总监焦晓杉辞职 将尽快完成新任财务总监选聘工作

家电

  1. 首页
  2. 移动通信
  3. 内容

牛客练习赛 115 记录

来源：博客园


(资料图片)

牛客练习赛115

赛时 AC 题目

A. Mountain sequence

点击查看代码
/*1. 根据山峰数列的定义，用排列组合知识去计算即可。*/#include#define ll long longusing namespace std;const int maxn=1e5+5;int t,n;int a[maxn];ll ans;const int MOD=998244353;int main(){scanf("%d",&t);while(t--){scanf("%d",&n);ans=1ll;for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);int e=n;while(a[e]==a[n]) e--;int cnt=0,s=0;for(int i=1;i<=e;i++){if(a[s]!=a[i]){ans=(cnt+1)*ans%MOD;s=i,cnt=1;}else cnt++;}ans=(cnt+1)*ans%MOD;printf("%lld\n",ans);}}

B. Antiamuny wants to leaern binary search again

点击查看代码
/*1. 模拟+贪心的水题。*/#includeusing namespace std;int t,l,r,cnt;int main(){scanf("%d",&t);while(t--){scanf("%d%d%d",&l,&r,&cnt);int pos;while(cnt&&l<=r){pos=(l+r)>>1;if(r-pos>pos-l) l=pos+1;else r=pos-1;cnt--;}if(cnt) printf("-1\n");else printf("%d\n",pos);}return 0;}

C. Find the maximum slope

点击查看代码
/*1. 突破点在于发现，$\max\limits_{i\ne j}\{|\frac{a_i-a_j}{i-j}|\}$ 一定在当 $j=i+1$ 时取到（可以用**反证法**证明），故只需计算相邻元素的差的最大值。2. 对于 $a$ 的差分数组 $d$，要求满足**单点修改**和**求区间最大值**的操作。本题中，由于区间一直是 $[2,n]$，故可直接用 $L$ 维护区间最大值，然后每次修改 $d$ 数组时，更新 $L$。3. 代码中用了线段树，是因为当时没有注意到区间一直是 $[2,n]$（nt 了）。*/#include#define ld long double#define lson i<<1#define rson i<<1|1using namespace std;const int maxn=5e5+100;int n,q,a[maxn];struct ST{int mx,mi;}t[maxn<<2];void build(int i,int L,int R){if(L==R) {t[i].mx=t[i].mi=a[R+1]-a[R];return;}int mid=(L+R)>>1;build(i<<1,L,mid),build(i<<1|1,mid+1,R);t[i].mx=max(t[i<<1].mx,t[i<<1|1].mx);t[i].mi=min(t[i<<1].mi,t[i<<1|1].mi);return;}void merge(int i,int l,int r,int pos,int k){if(l==r&&l==pos){t[i].mx+=k,t[i].mi+=k;return;}int mid=(l+r)>>1;if(pos<=mid) merge(lson,l,mid,pos,k);else merge(rson,mid+1,r,pos,k);t[i].mx=max(t[i<<1].mx,t[i<<1|1].mx);t[i].mi=min(t[i<<1].mi,t[i<<1|1].mi);return;}int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n-1);printf("%lf\n",1.0*max(abs(t[1].mx),abs(t[1].mi)));while(q--){int l,r,k;scanf("%d%d%d",&l,&r,&k);if(l-1)merge(1,1,n-1,l-1,k);if(r

赛事未 AC 的题目（待补）

D.Genealogy in the trees

E. High contrast pattern

F. Jewel maximizing magic

关键词：