[HDU][4269][模拟] Defend Jian Ge

前言


此题坑爹啊,描述上有误啊,不玩war3做不出来啊!

比赛时同学说这是道纯模拟,纯模拟我擅长啊,但是这一写就是300行啊,还没写完啊!就算写完也肯定不对啊,因为是按描述理解的啊!

但是这么坑爹的题,也有队伍过啊!一过还他么几十个队啊!OMG啊!坑爹啊!

题目大意


模拟魔兽争霸的装备购买行为。在游戏中,可以购买三种装备:

  • 普通装备:每个普通装备占一个装备栏,可以直接购买。
  • 合成装备:每个合成装备占一个装备栏,购买时需要有足够的材料和合成金。
  • 消耗装备:多个同类型的合成装备占一个装备栏。

另外,还有一些规则上需要注意的地方:

  • 当你的背包满时,你不能购买任何东西。
  • 当你购买合成装备时,相应材料将会从装备栏中消失。
  • 当一个操作非法时,现有装备和金钱不会出现任何变化。
  • 刚开始时,你的金钱为0,没有任何装备。
  • 金钱不能为负数。

思路


纯模拟题。题意稍微有些歧义,不玩war3的同学很难作对这道题。下面说些需要注意的地方:

首先,装备栏满时不可以购买普通装备,这个很正常。对于消耗型装备,装备栏满时,就算已拥有同类型装备,也不能继续购买。但是,合成装备却与以上两种装备不同,在装备栏满时,只要合成金和材料充足,就可以购买!这里就与题目描述相违了。但合成装备有一种特殊情况,就是会出现不需要任何材料的合成装备,这时在规则上可以将其视为普通装备。

因为本人基本没什么war3经验,特地请教了在这个领域里比较拔尖的同学,问其合成装备的材料能否是消耗型装备,得到回答是否,但这个回答让我wa了很久。杭电的测试数据中有用消耗型装备充当材料的情况,并且考虑到了“装备栏满时,消耗型装备数量大于合成需求量导致无法空出装备栏,结果没地方给合成装备”这样的情形。

关于物品价值方面,由于合成装备的材料可以是其他合成装备,因此求取物品价值是一个递归的过程。

代码


#include
#include
#include
#include
using namespace std;
#define NAMESIZE 15
#define EQUIPSIZE 20

int total_room;
//目前拥有的空间 
int total_gold;
//目前拥有的金币数量 
char list_equipment[6][NAMESIZE+1];
//目前拥有的装备的列表 

int total_normal;
//普通装备数量 
struct p1
{
    string name;
    //装备名称 
    int value;
    //装备价值 
}normal[EQUIPSIZE];

int total_mixture;
//混合装备数量 
struct p2
{
    string name;
    //装备名称 
    int value;
    //合成价格 
    int num;
    //合成需要的装备种类的数量 
    string need_name[6];
    //合成需要的装备的种类 
    int need_num[6];
     //对应合成所需的各种装备的数量 
}mixture[EQUIPSIZE];

int total_consume;
//消耗型装备数量 
struct p3
{
    string name;
    //装备名称 
    int value;
    //装备价值 
    int num;
    //拥有该装备的数量,此参数在init()中被初始化。 
}consume[EQUIPSIZE];

void init()
//初始化 
{
    total_room=0;
    total_gold=0;
}

int check_num(const char temp[])
//检查字符串name[]是否表示一个整数。若是整数,返回其大小,否则返回-1。 
{
    int len=strlen(temp),sum=0;
    for(int i=len-1,j=1;i>=0;i--,j*=10)
        if(temp[i]>='0'&&temp[i]<='9')
            sum+=(temp[i]-'0')*j;
        else
            return -1;
    return sum;
}

pair check_exist(const char name[])
//检查装备列表中是否存在装备name,返回值为pair<装备数量,装备列表中的位置。> 
//若是消耗型装备,total==1时表示装备栏中有此装备,但并不表示其数量为1。
//消耗型装备的数量记录在对应类型的结构体中。 
{
    int total=0,pos;
    //total表示该装备在装备列表中的数量。
    //pos表示该装备在装备列表中的位置。  
    for(int i=0;i(total,pos);
}

pair get_type(const char name[])
//获取装备name的类别信息,返回值为pair<类别,在类别中的位置>
//类别:分别用1、2、3表示普通、混合、消耗型装备。 
{
    for(int i=0;i(1,i);
    for(int i=0;i(2,i);
    for(int i=0;i(3,i);
    return pair(-1,-1);
    //若找不到,返回pair<-1,-1>。 
}

int get_value(const char name[])
//获取装备name的价值。 
{
    pair equip_type_info=get_type(name);
    //equip_type_info装备name的类别信息。 
    if(equip_type_info.first==1)
        return normal[equip_type_info.second].value;
    else if(equip_type_info.first==2)
    //如果是混合装备,需要计算材料成本。 
    {
        p2* equip_info=&mixture[equip_type_info.second];
        //equip_info指向该混合装备的结构体 
        int sum=equip_info->value;
        //sum表示混合装备的价值
        for(int i=0;inum;i++)
        //遍历所有材料的种类 
            sum+=get_value(equip_info->need_name[i].c_str())*(equip_info->need_num[i]);
        return sum;
    }
    else
    {
        p3* equip_info=&consume[equip_type_info.second];
        return equip_info->value*equip_info->num;
    }
}

void delete_equip(const char name[],bool sell=true,int num=-1)
//删除装备列表中的name装备
//参数sell用于判断当前操作是删去装备(合成时删去材料)还是卖掉装备。
//num==-1时,表示要删除一个装备栏中的内容。支持所有类型装备。 
//num>=0时,表示要删除num个消耗型装备。只支持消耗型装备。
//当num>=0时,sell属性无意义,只支持删除装备,不支持卖装备。 
{
    if(num==-1)
    {
        pair equip_list_info=check_exist(name);
        if(equip_list_info.first)
        //若拥有该装备(数量不为0) 
        {
            for(int i=equip_list_info.second+1;iequip_type_info=get_type(name);
            if(equip_type_info.first==3)
            //若该装别是消耗型装备,则将其装备数量标记为0。 
                consume[equip_type_info.second].num=0;
        }
    }
    else
    {
        pairequip_type_info=get_type(name);
        consume[equip_type_info.second].num-=num;
        if(consume[equip_type_info.second].num==0)
        //当消耗型装备的数量为0时,需要将其从装备列表中删除,采用递归调用方式。 
            delete_equip(consume[equip_type_info.second].name.c_str(),false);
    }
}

void add_equip(const char name[])
//向装备列表中添加装备name 
{
    int add_gold=check_num(name);
    if(add_gold!=-1)
    //若name表示金钱 
    {
        total_gold+=add_gold;
        return;
    }
    pair equip_type_info=get_type(name);
    //获取装备name的信息。 
    if(equip_type_info.first==1)
    //若是普通装备
    {
        if(total_room==6)
        //若装备栏已满 
            return;
        int equip_value=normal[equip_type_info.second].value;
        if(total_gold>=equip_value)
        {
            total_gold-=equip_value;
            strcpy(list_equipment[total_room++],name);
        }
    }
    else if(equip_type_info.first==2)
    //若是混合装备 
    {
        p2* equip_info=&mixture[equip_type_info.second];
        if(total_gold>=equip_info->value)
        //若当前金币总数不满足合成价格。 
        {
            int sum=0;
            //sum表示,因增加mixture装备所新增空余装备栏的数量。 
            for(int i=0;inum;i++) 
            //利用循环判断是否有足够的材料。
            {
                const char* temp_name=equip_info->need_name[i].c_str();
                //temp_name表示mixture装备所需的材料名称。 
                if(get_type(temp_name).first!=3)
                //若材料不是消耗型 
                    if(check_exist(temp_name).firstneed_num[i])
                        return;
                    else
                        sum+=equip_info->need_num[i];
                else
                //若材料是消耗型。 
                {
                    int temp_num=consume[get_type(temp_name).second].num;
                    //temp_num表示消耗型材料的数量。 
                    if(temp_numneed_num[i])
                        return;
                    else if(temp_num==equip_info->need_num[i])
                    //若消耗型材料的数量与所需数量相等,则可以空出一个装备栏。 
                        sum++;
                }
            } 
            if(total_room-sum+1>6)
            //若装备栏的容量符合要求 
                return;
            total_gold-=equip_info->value;
            //更新total_gold 
            for(int i=0;inum;i++)
            //利用循环删除材料。 
            {
                const char* temp_name=equip_info->need_name[i].c_str(); 
                if(get_type(temp_name).first!=3)
                    for(int j=0;jneed_num[i];j++)
                        delete_equip(temp_name,false);
                else
                    delete_equip(temp_name,false,equip_info->need_num[i]);
            } 
            strcpy(list_equipment[total_room++],name);
        }
    }
    else if(equip_type_info.first==3) 
    {
        if(total_room==6)
        //若装备栏已满 
            return;
        p3* equip_info=&consume[equip_type_info.second];
        if(total_gold>=equip_info->value)
        {
            total_gold-=equip_info->value;
            equip_info->num++;
            if(!check_exist(name).first)
            //若装备列表中没有同类的消耗装备 
                strcpy(list_equipment[total_room++],name);
        }
    }
    else if(equip_type_info.first==-1)
    //无该装备 
        return;
}

void input_normal_info()
//输入普通装备信息 
{
    char equip_name[NAMESIZE];
    //装备的名称 
    int equip_value;
    //装备的价值 
    for(int i=0;i equip_type_info=get_type(list_equipment[i]);
        if(equip_type_info.first==3)
        //如果是消耗型装备,则输出其数量。 
            printf("%s: %d\n",&list_equipment[i],consume[equip_type_info.second].num);
        else
            printf("%s: 1\n",&list_equipment[i]);
    }
    printf("\n");
}

int main()
{
    while(~scanf("%d",&total_normal))
    {
        init();
        input_normal_info();
        input_mixture_info();
        input_consume_info();
        operation();
        output();
    }
}

测试数据


2
ring 1
sword 2
1
knife 3: 
1
medicine 1
8
+100
+ring
+ring
+ring
+ring
+ring
+sword
+knife

2
ring 1
sword 2
1
knife 3: ring 2, sword 2
1
medicine 1
6
+100
+ring
+ring
+sword
+sword
+knife

2
ring 1
sword 2
1
knife 3: ring 2, sword 2
1
medicine 1
5
+100
+ring
+ring
+sword
+knife

2
ring 1
sword 2
2
knife 3: ring 1, sword 1
kkk 3: ring 1, sword 1
1
medicine 1
9
+100
+ring
+ring
+ring
+ring
+sword
+sword
+knife
+kkk

2
ring 1
sword 2
2
knife 3: ring 1, sword 1
kkk 2: knife 2, sword 1
1
medicine 1
9
+100
+ring
+ring
+sword
+sword
+knife
+knife
+sword
+kkk

2
ring 1
sword 2
2
knife 3: ring 1, sword 1
kkk 2: knife 2, sword 1
1
medicine 1
10
+100
+ring
+ring
+sword
+sword
+knife
+knife
+sword
+kkk
-kkk

2
ring 1
sword 2
2
knife 3: ring 1, sword 1
kkk 2: knife 2, medicine 2
1
medicine 1
11
+100
+ring
+ring
+sword
+sword
+knife
+knife
+medicine
+medicine
+medicine
+kkk

2
ring 1
sword 2
2
knife 3: ring 1, sword 1
kkk 2: knife 2, medicine 2
1
medicine 1
12
+100
+ring
+ring
+sword
+sword
+knife
+knife
+medicine
+medicine
+medicine
+kkk
-kkk

2
ring 1
sword 2
2
knife 3: ring 1, sword 1
kkk 2: knife 2, medicine 2
1
medicine 1
10
+100
+ring
+ring
+sword
+sword
+knife
+knife
+medicine
+medicine
+kkk

2
ring 1
sword 2
2
knife 3: ring 1, sword 1
kkk 2: knife 2, medicine 2
1
medicine 1
20
+100
+ring
+ring
+sword
+sword
+knife
+knife
+medicine
+medicine
+kkk
+100
+ring
+ring
+sword
+sword
+knife
+knife
+medicine
+medicine
+kkk

2
ring 1
sword 2
2
knife 3: ring 1, sword 1
kkk 2: knife 2, medicine 2
1
medicine 1
21
+100
+ring
+ring
+sword
+sword
+knife
+knife
+medicine
+medicine
+medicine
+kkk
+100
+ring
+ring
+sword
+sword
+knife
+knife
+medicine
+medicine
+kkk

2
ring 1
sword 2
1
knife 3: medicine 1
1
medicine 1
8
+100
+ring
+ring
+ring
+ring
+ring
+medicine
+knife

2
ring 1
sword 2
1
knife 3: medicine 1
1
medicine 1
9
+100
+ring
+ring
+ring
+ring
+medicine
+medicine
+ring
+knife

《[HDU][4269][模拟] Defend Jian Ge》上有2条评论

  1. ”杭电的测试数据中有用消耗型装备充当材料的情况,并且考虑到了“装备栏满时,消耗型装备数量大于合成需求量导致无法空出装备栏,结果没地方给合成装备”这样的情形。“
    测过了,HDOJ的数据里没有将消耗型装备作为合成装备的材料的数据

发表回复

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