注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2000(hnoi2010)取石子游戏  

2013-02-21 22:57:41|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

二试的题几乎就没有可做的,除了绵羊……

就在几分钟前,vfleaking大神还在感慨:这贪心怎么想得到啊

大神真相了!!

那个神贪心的大概思路就是把题目当成0或1或2个栈与若干个双端队列来看待

然后两个结论:

①如果栈底比栈底的上一个元素大,那么谁都不愿意去那个元素,于是那个元素就被拖到了最后,可以直接根据奇偶性判断是谁拿

②如果双端队列中,存在连续的三个数A,B,C,然后A<B<C,那么在能不拿A,C的情况下大家都不会拿,而当有人拿的时候对方就肯定得赶快拿B了所以就把这个给看成是A+C-B

最后就一定具有单调性了,然后再快排一下就可以根据奇偶性取了

然后再看一遍……嘛我自己都没看懂我在写什么了

看题解吧……

果然讲不清,纯当我在扯淡吧

友情提示:注意long long

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1000010
using namespace std;
typedef long long LL;
int pre[MAXN],next[MAXN],head,tail;
int n,cnt;
LL sum1,sum2,digit[MAXN];
bool mark[MAXN];
void Read(int &digit)
{
    digit=0;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void Delete(int p)
{
    mark[p]=false;
    if(head==p)  head=next[p];
    if(tail==p)  tail=pre[p];
    pre[next[p]]=pre[p],next[pre[p]]=next[p];
}
void read()
{
    Read(n);
    for(int i=1;i<=n;i++)
    {
        int x;
        Read(x),digit[i]=x;
        sum1+=digit[i],cnt+=(digit[i]!=0);
        if(digit[i]!=0)  mark[i]=true;
    }
    head=1,tail=n;
    for(int i=1;i<=n;i++)
        pre[i]=i-1,next[i]=i+1;
}
void work()
{
    while(1)
    {
        bool flag=false;
        while(mark[head]&&mark[next[head]]&&digit[head]>=digit[next[head]])
        {
            if(cnt&1)  sum2=sum2+digit[head]-digit[next[head]];
            else  sum2=sum2+digit[next[head]]-digit[head];
            flag=true,Delete(head),Delete(head);
        }
        while(mark[tail]&&mark[pre[tail]]&&digit[tail]>=digit[pre[tail]])
        {
            if(cnt&1)  sum2=sum2+digit[tail]-digit[pre[tail]];
            else  sum2=sum2+digit[pre[tail]]-digit[tail];
            flag=true,Delete(tail),Delete(tail);
        }
        for(int i=next[head];i<tail;i=next[i])
            if(mark[i]&&mark[pre[i]]&&mark[next[i]])
                if(digit[i]>=digit[pre[i]]&&digit[i]>=digit[next[i]])
                {
                   flag=true,digit[i]=digit[pre[i]]+digit[next[i]]-digit[i];
                   Delete(pre[i]),Delete(next[i]);
                }
        if(flag==falsebreak;
    }
}
void print()
{
    static int s=0;
    static LL ans[MAXN];
    for(int i=head;i<=tail;i=next[i])
        if(mark[i])
            ans[++s]=digit[i];
    sort(ans+1,ans+s+1),reverse(ans+1,ans+s+1);
    for(int i=1;i<=s;i++)
        sum2=sum2+ans[i]*(i&1?1:-1);
    cout<< (sum1+sum2)/2 << " " << (sum1-sum2)/2 <<endl;
}
int main()
{
    read();
    work();
    print();
    return 0;
}


  评论这张
 
阅读(495)| 评论(6)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017