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

ydc的博客

 
 
 

日志

 
 

bzoj 3010  

2013-02-05 13:22:44|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

学校的考试题考了下usaco,然后考了这套题,现在把题目改完了。



对于第二问,做法是贪心,每次找剩余牛最多的团队跑进去

对于第三问,方法跟字典序最小的最小割集似乎有点像?就是usaco上的什么milk几去了。

枚举这一位是多少,如果把它丢进去之后再做一遍第二问,结果等于答案,那么就把它丢进去。

由于第二问做法每次要找最大值,所以用个priority_queue

结果在bzoj上用时还是倒数第一

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 110
using namespace std;
struct node
{
    int num,value;
    node() {}
    node(int num,int value): num(num),value(value) {}
    friend bool operator < (const node &a,const node b){  return a.value<b.value;  }
};
int remain,n,m,cow,s,gangs[MAXN];
priority_queue<node>sum;
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d",&gangs[i]);
}
void Go(int p)
{
    if(s==0)  cow=p,s++;
    else if(cow==p)  s++;
    else if(s==1)  cow=0,s=0;
    else s--;
}
int calc()
{
    while(!sum.empty())  sum.pop();
    for(int i=2;i<=m;i++)
        if(gangs[i])
            sum.push(node(i,gangs[i]));
    while(!sum.empty())
    {
        Go(sum.top().num);
        if(sum.top().value!=1)  sum.push(node(sum.top().num,sum.top().value-1));
        sum.pop();
    }
    for(int i=1;i<=gangs[1];i++)
        Go(1);
    if(cow!=1)  return 0;
    return s;
}
int main()
{
    read();
    remain=calc();
    if(remain==0)
    {
        printf("NO\n");
        return 0;
    }
    printf("YES\n%d\n",remain);
    cow=0,s=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(gangs[j])
            {
                int tempc=cow,temps=s;
                Go(j),gangs[j]--;
                int tempc1=cow,temps1=s;
                if(calc()==remain)
                {
                    printf("%d\n",j);
                    cow=tempc1,s=temps1;
                    break;
                }
                gangs[j]++,cow=tempc,s=temps;
            }
    return 0;
}
  评论这张
 
阅读(155)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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