程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BestCoder Round #20 解題報告 A.B.C.

BestCoder Round #20 解題報告 A.B.C.

編輯：C++入門知識

BestCoder Round #20 解題報告 A.B.C.

A題：who is the best?

題目地址：HDU 5123

水題。

哈希，然後枚舉找最大的，從小的開始找。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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

B題：lines
題目地址：HDU 5124
離散化+掃描線
先將各點離散化，然後標記起點+1和終點-1，然後從左向右掃描找最大值。
代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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

C題：magic balls
題目地址：HDU 5125

線段樹+DP
這題的DP思路很好想。就是找消耗當前能量下的最長上升序列的最大值，然後+1.這樣復雜度是n*m*n，顯然會超時，在這裡可以注意到，最後的n是可以用線段樹優化成logn的。於是就用m棵線段樹來維護m個能量消耗下的DP信息。
代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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]