锐客网

  1. 首页 > it技术 > >

牛客|牛客练习赛3

牛客个人训练计划

比赛链接
A题 求最初要携带的最少能量，其实可以假设最初为0，走一遍全过程，其中的最小负数的相反数即答案。
A题代码

#include #include using namespace std; int main() { int n; int i; int maxx=0; cin>>n; for(i=0; i>x; maxx=max(maxx,x+i); } cout<

B题 给你一段序列，让你把这个序列按原顺序拆分成两个序列，两个序列必须完全相同。问是否可行
本题为51nod1400原题 链接
由于数据范围只有50，所以只要dfs+剪枝就好了。
用两个变量l,r表示两个数组分别进行到什么位置，当前元素没出现过时，一定要加到第一个数组，如果出现过就有两种选择，要么加到第一个，要么加到第二个，当搜到最后一个元素而且 l = r l=r l=r时，代表搜索成功。
B题代码
#include #include #include #include using namespace std; const int maxn = 55; int a[maxn]; int q[maxn]; int flag; int n; void dfs(int u,int l,int r) { if(flag==1) return ; if(u==n+1) { if(l==r) flag=1; return ; } if(l==r) { q[r]=a[u]; dfs(u+1,l,r+1); } else { if(a[u]==q[l]) { q[r]=a[u]; dfs(u+1,l,r+1); dfs(u+1,l+1,r); } else { q[r]=a[u]; dfs(u+1,l,r+1); } } } int main() { int t; scanf("%d",&t); while(t--) { flag=0; memset(q,0,sizeof(q)); scanf("%d",&n); for(int i=1; i<=n; ++i) { scanf("%d",&a[i]); } dfs(1,0,0); if(flag) printf("Frederica Bernkastel\n"); else printf("Furude Rika\n"); } return 0; }

D题 给你三种图的类型，求给定图是哪一种类型，按照题找出没种图不同的特性，例如每个点的度，每种度的点的个数。
D题代码
#include #include #include #include using namespace std; const int maxn = 505; int d[maxn]; int cnt[5]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); d[x]++; d[y]++; } for(int i=1; i<=n; i++) { if(d[i]<=4) cnt[d[i]]++; } //cout<

E题 给你一个长度为n的数组，最多删除k个元素，求最长相同连续子序列。
0 < = k < = n < = 1 ? 1 0 5 1 < = a [ i ] < = 1 ? 1 0 9 0< =k< =n< =1*10^{5} \quad \quad 1< =a[i]< =1*10^{9} 0<=k<=n<=1?1051<=a[i]<=1?109
本题由于数据范围是1e5,所以肯定是 n l o g n nlogn nlogn的做法，考虑到最长相同子序列肯定是同一种元素构成的，所以我们可以对每个元素检验可构成的最长连续子序列。我们可以枚举右端点，然后二分左端点，如果删除k个点能达到长度为 l l l，删除k个点肯定能达到 l ′ < l l' < l l′=(r?l+1).
E题代码
#include #include #include #include #include using namespace std; const int maxn = 1e5+5; #define dbg(x) cout<<#x<<" :"< > mm; map pre; map【牛客|牛客练习赛3】,int> sum; int main() { int n,k; int ans=0; scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) scanf("%d",&a[i]); for(int i=1; i<=n; i++) mm[a[i]].push_back(i); for(int i=1; i<=n; i++) { sum[pair(a[i],i)]=sum[pair(a[i],pre[a[i]])]+1; pre[a[i]]=i; } map >::iterator it; for(it=mm.begin(); it!=mm.end(); ++it) { int tmp=it->first; int sz=(it->second).size(); if(sz<=1) continue; for(int i=0; i>1; if((rr-mm[tmp][mid]+1)-(sum[pair(tmp,rr)]-sum[pair(tmp,mm[tmp][mid])]+1)<=k) r=mid-1; else l=mid+1; } ans=max(ans,sum[pair(tmp,mm[tmp][i])]-sum[pair(tmp,mm[tmp][l])]+1); } } printf("%d\n",ans); return 0; }

    推荐阅读


    上一篇：【leetcode】28. 实现strStr() 【字符串】

    下一篇：Codeforces|【Codeforces Round #531 (Div. 3) E. Monotonic Renumeration】思维题