本文主要是介绍BestCoder Round #20 解题报告 A.B.C.，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A题：who is the best?
题目地址：HDU 5123
水题。
哈希，然后枚举找最大的，从小的开始找。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL __int64
int a[102];
int main()
{int t, n, i, x, max1, y;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));scanf("%d",&n);max1=-1;for(i=0;i<n;i++){scanf("%d",&x);a[x]++;max1=max(max1,a[x]);}for(i=1;i<=100;i++){if(a[i]==max1){y=i;break;}}printf("%d\n",y);}return 0;
}B题：lines
题目地址：HDU 5124
离散化+扫描线
先将各点离散化，然后标记起点+1和终点-1，然后从左向右扫描找最大值。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL __int64
struct node
{int x, y;
}fei[300000];
int a[300000], c[300000], dp[300000], d[300000], cnt;
int bin_search(int x)
{int low=0, high=cnt-1, mid;while(low<=high){mid=low+high>>1;if(d[mid]>x) high=mid-1;else if(d[mid]==x) return mid;else low=mid+1;}
}
int main()
{int t, i, j, x, y, max1, s, n;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++){scanf("%d%d",&fei[i].x,&fei[i].y);c[i*2]=fei[i].x;c[i*2+1]=fei[i].y;}memset(a,0,sizeof(a));sort(c,c+2*n);cnt=0;d[cnt++]=c[0];for(i=0;i<2*n;i++){if(c[i]!=c[i-1])d[cnt++]=c[i];}memset(dp,0,sizeof(dp));for(i=0;i<n;i++){x=bin_search(fei[i].x);y=bin_search(fei[i].y);dp[x]++;dp[y+1]--;}max1=-1;s=0;for(i=0;i<cnt;i++){s+=dp[i];max1=max(max1,s);}printf("%d\n",max1);}return 0;
}C题：magic balls
题目地址：HDU 5125
线段树+DP
这题的DP思路很好想。就是找消耗当前能量下的最长上升序列的最大值，然后+1.这样复杂度是n*m*n，显然会超时，在这里可以注意到，最后的n是可以用线段树优化成logn的。于是就用m棵线段树来维护m个能量消耗下的DP信息。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define root 0, cnt-1, 1
struct node {int a, b;
} fei[1002];
int Maxdp[1002][8001], d[2001], c[2001], cnt, a[1001],b[1001];
void PushUp(int m, int rt)
{Maxdp[m][rt]=max(Maxdp[m][rt<<1],Maxdp[m][rt<<1|1]);
}
void Update(int m, int p, int x, int l, int r, int rt)
{if(l==r) {Maxdp[m][rt]=x;return ;}int mid=l+r>>1;if(p<=mid) Update(m,p,x,lson);else Update(m,p,x,rson);PushUp(m,rt);
}
int Query(int m, int ll, int rr, int l, int r, int rt)
{if(ll<=l&&rr>=r) {return Maxdp[m][rt];}int mid=l+r>>1;int ans=0;if(ll<=mid) ans=max(ans,Query(m,ll,rr,lson));if(rr>mid) ans=max(ans,Query(m,ll,rr,rson));return ans;
}
int bin_search(int x)
{int low=0, high=cnt-1, mid;while(low<=high) {mid=low+high>>1;if(c[mid]>x) high=mid-1;else if(c[mid]<x) low=mid+1;else return mid;}
}
int main()
{int t, i, j, n, k, f1, f2, m, maxv, ans, ans1, ans2;scanf("%d",&t);while(t--) {scanf("%d%d",&n,&m);for(i=0; i<n; i++) {scanf("%d%d",&fei[i].a,&fei[i].b);d[i<<1]=fei[i].a;d[i<<1|1]=fei[i].b;}sort(d,d+2*n);cnt=1;c[0]=d[0];for(i=1; i<n*2; i++) {if(d[i]!=d[i-1]) {c[cnt++]=d[i];}}memset(Maxdp,0,sizeof(Maxdp));maxv=0;for(i=0; i<n; i++) {f1=bin_search(fei[i].a);f2=bin_search(fei[i].b);ans=0;if(f1)ans=Query(0,0,f1-1,root);a[0]=ans+1;maxv=max(maxv,ans+1);for(j=1; j<=i+1&&j<=m; j++) {ans1=ans2=0;if(j!=i+1) {if(f1) ans1=Query(j,0,f1-1,root);//Update(j,f1,ans1+1,root);a[j]=ans1+1;}if(f2) ans2=Query(j-1,0,f2-1,root);//Update(j,f2,ans2+1,root);b[j]=ans2+1;ans=max(ans1,ans2);maxv=max(ans+1,maxv);}for(j=0; j<=i+1&&j<=m; j++) {if(j!=i+1) Update(j,f1,a[j],root);if(j) Update(j,f2,b[j],root);}}printf("%d\n",maxv);}return 0;
}
这篇关于BestCoder Round #20 解题报告 A.B.C.的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
