2015年百度之星程序设计大赛 – 初赛(1) 题解

【HDU5246(1001)】

贪心。首先对所有对手战斗力排序,然后先找出<=m的战斗力中最大的那个，如果没有<=m的战斗力那他必定不能战胜后面任何一个，然后尽量用最少的次数把自己的战斗力提升到>=max{a[i]};这样就能战胜所有人了，所以开始战力选择<=m中最大的那个，每次找到战力<=now+k(now是当前战力)中最大的值，然后必定要提升把now提升到那个值，这样最后只要能>=max{a[i]}就能感获胜；从左往右扫描一遍，再尽量往右升战力就好了，复杂度n*logn;

【AC CODE】514ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 10000+10;
LL a[MAXN], m,k;
int n;

bool sloved()
{
    sort(a,a+n);
    int st = -1;
    rep(i,0,n)
    {
        if(a[i] > m)
        {
            st = i;
            break;
        }
    }
    if(-1 == st) return true;
    if(0 == st) return false;
     LL now = a[st-1]+k;
    k--;
    int i = st;
    while(i < n)
    {
        int p = upper_bound(a+i,a+n,now)-a-1;
        if(p < i) return false;
        now = a[p]+k;
        i = p+1;
        if(k > 0)
            k--;
        else break;
    }
    return now+k >= a[n-1];
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t,count = 0;
    scanf("%d%*c", &t);
    while(t--)
    {
        scanf("%d %I64d %I64d%*c", &n, &m, &k);
        rep(i,0,n)
        {
            scanf("%I64d%*c", &a[i]);
        }
        printf("Case #%d:\n", ++count);
        if(sloved()) puts("why am I so diao?");
        else puts("madan!");
    }
    return 0;
}

 

【HDU5247(1002)】

询问的是连续的长度为k的区间；所以只要每次询问的时候扫描一边序列，进去右边的左边的出来(保持序列长度为k即可)，这样就能判断所有的连续k长子串，然后关键是判断子串中的所有数是不是连续的；这个只要判断子串的满足： 最大值-最小值==子串长度&&子串不重复 就可以；对于最值直接RMQ-ST预处理，可以做到O(1)查询；然后判断不重复需要先离散值，然后数组直接O(1)判；如果用set会超时，手写的HASH都超时了，所以还是乖乖离散吧。这样总复杂度n*m

【AC CODE】280ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 10000+10, MOD = 1000007;
int a[MAXN],mx[MAXN][20], mi[MAXN][20],cnt;
map<int,int> num;

void st_init(int n)
{
    repe(i,1,n) mx[i][0] = mi[i][0] = a[i];//下标从1开始的
    for(int j = 1; (1<<j) <= n; j++)
    {
        for(int i = 1; i+(1<<j)-1 <= n; i++)//下标从1开始的
        {
            mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
            mi[i][j] = min(mi[i][j-1], mi[i+(1<<(j-1))][j-1]);
        }
    }
}
void st(int x, int y, int &mxv, int &miv)
{
    int k = 0;
    while((1<<(k+1)) <= y-x+1) k++;
    mxv = max(mx[x][k], mx[y-(1<<k)+1][k]);
    miv = min(mi[x][k], mi[y-(1<<k)+1][k]);
}
int get_id(int v)
{
    if(num.find(v) == num.end())
    {
        num[v] = cnt++;
        return cnt-1;
    }
    return num[v];
}
int vis[MAXN];

int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int n,m;
    scanf("%d %d%*c", &n, &m);
    cnt = 0;
    repe(i,1,n) scanf("%d%*c", &a[i]);
    st_init(n);
    repe(i,1,n) a[i] = get_id(a[i]);
    puts("Case #1:");
    while(m--)
    {
        int k;
        scanf("%d%*c", &k);
        if(k > n)
        {
            puts("0");
            continue;
        }
        int ans = 0, sum = 0;
        clc(vis,0);
        rep(i,1,k)
        {
            if(!vis[a[i]]) sum++;
            vis[a[i]]++;
        }
        repe(i,k,n)
        {
            int mxv,miv;
            st(i-k+1,i,mxv,miv);
            int tmp = mxv-miv;
            if(!vis[a[i]]) sum++;
            vis[a[i]]++;
            if(k-1 == tmp && sum == k) ans++;
            if(!--vis[a[i-k+1]]) sum--;
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

【HDU5248(1003)】

二分答案即可，每次O(n)判断当前代价是否可行。复杂度n*logn

【AC CODE】374ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10;
int a[MAXN],n;

bool ok(int m)
{
    int st = a[0]-m, mi = st+1;
    rep(i,1,n)
    {
        if(a[i] < mi && mi-a[i] > m) return false;
        if(a[i] < mi) st = mi;
        else
        {
            st = max(mi,a[i]-m);
        }
        mi = st+1;
    }
    return true;
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t,count = 0;
    scanf("%d%*c", &t);
    while(t--)
    {
        scanf("%d%*c", &n);
        rep(i,0,n) scanf("%d%*c", &a[i]);
        int ans = INF, x = 0,y = 10000000;
        while(x <= y)
        {
            int m = (x+y)>>1;
            if(ok(m)) y = m-1, ans = m;
            else x = m+1;
        }
        printf("Case #%d:\n%d\n", ++count,ans);
    }
    return 0;
}

 【HDU5249(1004)】

很裸的平衡树题，我用的Treap，没什么的好说的吧。复杂度n*logn

【AC CODE】 421ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 10000+10;
queue<int> q;
struct NODE{
    NODE *ch[2];
    int r;//随机优先级
    int v;//键值
    int sum;//以当前节点为根的总结点数
    NODE(int a){
        v = a,ch[0] = ch[1] = NULL, r = rand(), sum = 1;
    }
    int cmp(int x){
        if(x == v) return -1;
        return x<v?0:1;
    }
    void push_up(){
        sum = 1;
        if(ch[0]) sum += ch[0]->sum;
        if(ch[1]) sum += ch[1]->sum;
    }
};
void clear(NODE* &u)//清空树
{
    if(!u) return;
    if(u->ch[0]) clear(u->ch[0]);
    if(u->ch[1]) clear(u->ch[1]);
    delete u;
    u = NULL;
}
void rotate(NODE* &u, int d)//旋转，d = 0左旋,d = 1右旋
{
    NODE *k = u->ch[d^1];
    u->ch[d^1] = k->ch[d], k->ch[d] = u;
    u->push_up(), k->push_up();  //更新sum,先更新u
    u = k;
}
void insert(NODE* &u, int v)//插入键值v(不需要保证v是否存在)
{
    if(!u) u = new NODE(v);
    else
    {
        int d = v < u->v?0:1;//不要使用cmp(),可能已经存在相同的v
        insert(u->ch[d], v);
        if(u->r < u->ch[d]->r) //如果儿子的r比当前大则需要旋转
            rotate(u,d^1);//左儿子则右旋，右儿子左旋
    }
    u->push_up();//更新sum
}
void del(NODE* &u, int v)//删除键值v
{
    int d = u->cmp(v);
    if(~d)//没找到继续往下找
        del(u->ch[d],v);
    else
    {
        NODE *o = u;
        if(u->ch[0] && u->ch[1])//左右儿子都存在
        {
            int d2 = u->ch[0]->r > u->ch[1]->r?1:0;//优先级大的儿子旋转为根
            rotate(u,d2);
            del(u->ch[d2],v);
        }
        else
        {
            if(!u->ch[0]) u = u->ch[1];//只有右儿子
            else u = u->ch[0];//只有左儿子
            delete o;
            //u = NULL;
        }
    }
    if(u) u->push_up();
}
int kth(NODE* u, int k)//寻找第k大键值
{
    if(!u || k <= 0 || k > u->sum) return 0;//不存在
    int d = k-(u->ch[0]?u->ch[0]->sum:0);
    if(d == 1) return u->v;//找到第k大值
    if(d <= 0) return kth(u->ch[0],k);
    return kth(u->ch[1],k-(u->ch[0]?u->ch[0]->sum:0)-1);
}
void pt(NODE *u)
{
    if(NULL == u) return;
    pt(u->ch[0]);
    printf("%d\n", u->v);
    pt(u->ch[1]);
}

int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int n,count = 0;
    while(~scanf("%d%*c", &n))
    {
        while(!q.empty()) q.pop();
        NODE *rt = NULL;
        printf("Case #%d:\n",++count);
        while(n--)
        {
            char op[21];
            scanf("%s", op);
            if('i' == op[0])
            {
                int v;
                scanf("%d%*c", &v);
                q.push(v);
                insert(rt,v);
            }
            else if('o' == op[0])
            {
                del(rt,q.front());
                q.pop();
            }
            else
            {
                int m = q.size();
                int pos = floor(m/2)+1;
                printf("%d\n",kth(rt,pos));
            }
        }
        clear(rt);
    }
    return 0;
}

 

 【HDU5250(1005)】

还没做；

【HDU5251(1006)】

最小矩形覆盖模版题。

【AC CODE】0ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
#define PR 1e-8
#define maxdouble 1e20
const int INF = 0x3f3f3f3f, MAXN = 1000*4+10;
struct TPoint
{
    double x,y;
};
struct TPolygon
{
    int n;
    TPoint p[MAXN];
}ply;
double MIN(double a,double b) {return a>b?b:a;}
int dblcmp(double a)
{
    if(fabs(a)<PR) return 0;
    return a>0?1:-1;
}
double dist(TPoint a,TPoint b)//距离
{
    double s1=a.x-b.x;
    double t1=a.y-b.y;
    return sqrt(s1*s1+t1*t1);
}
double cross(TPoint a,TPoint b,TPoint c)//叉积
{
    double s1=b.x-a.x;
    double t1=b.y-a.y;
    double s2=c.x-a.x;
    double t2=c.y-a.y;
    return s1*t2-s2*t1;
}
double dot(TPoint a,TPoint b,TPoint c)//点积
{
    double s1=b.x-a.x;
    double t1=b.y-a.y;
    double s2=c.x-a.x;
    double t2=c.y-a.y;
    return s1*s2+t1*t2;
}
bool cmop(TPoint a,TPoint b)//x、y排序
{
    if(fabs(a.x-b.x)<PR) return a.y<b.y;
    else return a.x<b.x;
}
bool cmp(TPoint a,TPoint b)//叉积内排序
{
    int d1=dblcmp(cross(ply.p[0],a,b));
    return d1>0||(d1==0&&dist(ply.p[0],a)<dist(ply.p[0],b));
}
TPolygon graham()//求凸包
{
    int i,top=2;
    for(i=2;i<ply.n;i++)
    {
        while(top>1&&(dblcmp(cross(ply.p[top-2],ply.p[i],ply.p[top-1])))>=0) top--;
        ply.p[top++]=ply.p[i];
    }
    ply.n=top;
    return ply;
}
double solve()
{
    int i,p=1,q=1,r;
    double minarea=maxdouble,area;
    ply.p[ply.n]=ply.p[0];
    for(i=0;i<ply.n;i++)
    {
        while(dblcmp(cross(ply.p[i],ply.p[i+1],ply.p[p+1])//最上一点
            -cross(ply.p[i],ply.p[i+1],ply.p[p]))>0)
            p=(p+1)%ply.n;
        while(dblcmp(dot(ply.p[i],ply.p[i+1],ply.p[q+1])//最右一点
            -dot(ply.p[i],ply.p[i+1],ply.p[q]))>0)
            q=(q+1)%ply.n;
        if(i==0) r=q;
        while(dblcmp(dot(ply.p[i],ply.p[i+1],ply.p[r+1])//最左一点
            -dot(ply.p[i],ply.p[i+1],ply.p[r]))<=0)
            r=(r+1)%ply.n;
        double d=dist(ply.p[i],ply.p[i+1])*dist(ply.p[i],ply.p[i+1]);
        area=cross(ply.p[i],ply.p[i+1],ply.p[p])*//求面积
            (dot(ply.p[i],ply.p[i+1],ply.p[q])-dot(ply.p[i],ply.p[i+1],ply.p[r]))/d;
        minarea=MIN(area,minarea);//更新
    }
    return minarea;
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t,count = 0;
    scanf("%d%*c", &t);
    while(t--)
    {
        scanf("%d",&ply.n);
        ply.n *= 4;
        int i;
        double area;
        for(i=0;i<ply.n;i++) scanf("%lf%lf",&ply.p[i].x,&ply.p[i].y);
        sort(ply.p,ply.p+ply.n,cmop);//排序
        sort(ply.p+1,ply.p+ply.n,cmp);
        ply=graham();//凸包
        if(ply.n<3) area=0;
        else area=solve();
        printf("Case #%d:\n%.0f\n",++count,area);
    }
    return 0;
}

总之这场很水。

dawxy

作者： dawxy

https://github.com/dawxy

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码