hdu4269 Defend Jan Ge changchun online 恶心模拟

各种恶心。。 直接贴代码了。。。

比较混乱。。 直接用STL或者字符串hash等 会更简洁 更容易....

Problem DescriptionDefend Jian Ge, an interesting RPG map in WAR3, has a very complete equipment system as a mini RPG game.
In the game, each player has a backpack which has 6 grids and some gold reserves. There are three kinds of equipments in the game.
1. Normal equipment: Each equipment occupies one grid in the backpack and the player can buy it directly. The value of the normal equipment is equal to its price.
2. Mixture equipment: Each equipment occupies one grid in the backpack and the player can only get it through the synthesis of the corresponding recipe. If you have enough equipment of recipes in your backpack and gold to pay synthesis cost, you can get it. The value of the mixture equipment is equal to the sum of all equipments’ value in the recipe plus the synthesis cost. A mixture equipment can be made from several normal equipments and mixture equipments.
3. Consume equipment: A kind of equipment must occupy one grid and the player can buy it directly. That is to say, if you have a number of consume equipments, they must be in one grid. The value of each consume equipment is equal to its price, and when you want to sell this kind of equipment, you must sell the whole grid's equipments at the same time.



You should pay attention:
1. When the backpack is full, you cannot buy anything.
2. When a mixture equipment is get, the mixture equipment of recipe in you backpack will disappear.
3. If one operation is illegal, there is nothing happened in your backpack and gold.
4. Initially, there is nothing in your backpack and you have 0 gold.
5. The gold you have cannot be a negative number.

As a DS programmer, you want to simulate the dynamic states in your backpack by program. Now you have initial state and several operations, you wonder the final state.

InputThere are multiple test cases.
The first line contains an integer N1 (0 <= N1 <= 20) indicating the kind of normal equipment.
The next N1 lines each line contains a string and an integer indicating the name of this normal equipment and its price respectively.
**Format: str num
The following line contains an integer N2 (0 <= N2 <= 20) indicating the kind of mixture equipment.
Each of the next N2 lines begins with a string and an integer indicating the name of this mixture equipment and its synthesis cost. Following, the synthesis recipe of this kind of equipment: some pairs of string and integer indicating which kind of equipment and the number you need to synthesis.
**Format: str num: str1 num1, str2 num2, ... , strn numn (num1 + num2 + … +numn<=6 and numi >= 0 (1 <= i <= n))
The next line contains an integer N3 (0 <= N3 <= 20) indicating the kind of consume equipment.
Each of the next N3 lines contains a string and an integer indicating the name of this consume equipment and it's price.
**Format: str num
The next line contains an integer M (0 <= M <= 100) indicating the number of operation.
Each of the next M lines contains an operation.
There are three kinds of operation:
1. +num indicating you get num gold (0 <= num <= 1000).
2. +str indicating you want to get an equipment whose name is str.
3. -str indicating you want to sell the equipment whose name is str. If you sell the equipment, you can get gold that is the same to its value.

There is a blank line after each case.
All strings of name only contain lowercase character and its length is no more than 15. The price of the equipment is a non-negative integer which is no more than 1000.

OutputFor each case you should output several lines.
The first line output "Case " + case number + ":".
The next line output an integer indicating the number of gold at last.
The next line output an integer k indicating how many grids occupied.
Each of the next k lines contain a string and an integer indicating the name and the number of the equipment. You should output according to the lexicographic.
**Format: str: num

You can get more details from the sample below.
NOTE: Output a blank line after each test case.

Sample Input

[pre]2ring 1sword 21knife 3: ring 1, sword 11medicine 14+100+ring+sword+knife1shoe 01wing 1: 1medicine 13+10+shoe+wing1shoe 01wing 1: 1medicine 14+10+shoe+wing-wing1shoe 11wing 1: shoe 11medicine 18+100+shoe+shoe+shoe+shoe+shoe+medicine+medicine[/pre]

Sample Output

[pre]Case 1:941knife: 1Case 2:92shoe: 1wing: 1Case 3:101shoe: 1Case 4:946medicine: 1shoe: 1shoe: 1shoe: 1shoe: 1shoe: 1[/pre]

Source2012 ACM/ICPC Asia Regional Changchun Online

#include<cstdio>#include<algorithm>#include<string>#include<cstring>#include<cmath>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>#define MAX 26#define BUG puts("GF")using namespace std;const bool GF1 = true;int Gold,leftG;char stmp[10000];int N_nme, N_mxe, N_cse;char name_nme[22][30], name_mxe[22][30], name_cse[22][30];int  price_nme[22], price_mxe[22], price_cse[22];char mx_part_name[22][60][30];int mx_tt_part[22], mx_part_need[22][60];struct OT{    string os;    int ctr;    bool operator < (const OT &a) const{        return os<a.os;    }};set<OT> Set;map<string,int> type;map<string,int> priceCSE;map<string,int> priceNME;map<string,int> priceMXE;map<string,int> MXEID;typedef struct TrieNode {    int nCount;    struct TrieNode *next[MAX];}TrieNode;TrieNode Memory[100000];int allocp =0;TrieNode *CreateTrieNode() {    int i;    TrieNode *p;    p = &Memory[allocp++];    p->nCount = 0;    for(i =0 ; i < MAX ; i++) {        p->next[i] = NULL;    }    return p;}void InsertTrie(TrieNode * &pRoot , char*s) {    int i, k;    TrieNode *p;    if(!(p = pRoot)) {        p = pRoot = CreateTrieNode();    }    i = 0;    while(s[i]) {        k = s[i++] - 'a';        if( ! p->next[k]) p->next[k] = CreateTrieNode();        p = p->next[k];    }    p->nCount += 1;}void DeletTrie(TrieNode * &pRoot, char *s, int dn){    TrieNode *p;    int i , k;    if(!(p = pRoot)) {        return ;    }    i = 0;    while(s[i]) {        k = s[i++] -'a';        if(p->next[k] == NULL) return ;        p = p->next[k];    }    p->nCount -= dn;    return ;}int SearchTrie(TrieNode * &pRoot , char*s) {    TrieNode *p;    int i , k;    if(!(p = pRoot)) {        return 0;    }    i = 0;    while(s[i]) {        k = s[i++] -'a';        if(p->next[k] == NULL) return 0;        p = p->next[k];    }    return p->nCount;}TrieNode * box = NULL;void init(){    box = NULL;    allocp = 0;    Gold = 0;    leftG = 6;    //N_nme = N_mxe = N_cse = 0;        type.clear();    priceNME.clear();    priceCSE.clear();    priceMXE.clear();    MXEID.clear();    Set.clear();    memset(mx_tt_part,0,sizeof(mx_tt_part));    memset(name_nme,0,sizeof(name_nme));    memset(name_mxe,0,sizeof(name_mxe));    memset(name_cse,0,sizeof(name_cse));    memset(price_nme,0,sizeof(price_nme));    memset(price_mxe,0,sizeof(price_mxe));    memset(price_cse,0,sizeof(price_cse));    memset(mx_part_name,0,sizeof(mx_part_name));    memset(mx_part_need,0,sizeof(mx_part_need));}void input(){    getchar();    for(int i=0; i<N_nme; ++i)    {            scanf("%s %d",name_nme[i],&price_nme[i]);        string nnnn1;        nnnn1 = (name_nme[i]);        type[nnnn1] = 1;        priceNME[nnnn1] = price_nme[i];    }        scanf("%d",&N_mxe);    getchar();    for(int i=0; i<N_mxe; ++i)    {                gets(stmp);        int len = strlen(stmp);        int cur = 0;        sscanf(stmp,"%s%d",name_mxe[i],price_mxe+i);        string sk(name_mxe[i]);        priceMXE[sk] = price_mxe[i];        MXEID[sk] = i;        type[sk] = 2;        while( (*(stmp+cur)) != ':') ++cur;        for(++cur;cur<len;++cur)        {            sscanf(stmp+cur,"%s%d",mx_part_name[i][ mx_tt_part[i] ],&mx_part_need[i][ mx_tt_part[i] ]);            mx_tt_part[i] ++;            while(cur < len && (*(stmp+cur)) != ',') ++cur;            ++cur;        }        }        scanf("%d",&N_cse);    getchar();    for(int i=0; i<N_cse;++i)    {        scanf("%s%d",name_cse+i, price_cse+i);        string nnnn3(name_cse[i]);        type[nnnn3] = 3;        priceCSE[nnnn3] = price_cse[i];    }    }void obtain(char * name){    string mm(name);    int swich2 = type[mm];    if(swich2 == 1 && Gold >= priceNME[mm] && leftG >0)    {        Gold -= priceNME[mm];        leftG -= 1;        InsertTrie(box,name);        return ;    }    if(swich2 == 3 && Gold >= priceCSE[mm] && leftG >0)    {        int ex = SearchTrie(box,name);        if( ex == 0 )        {            if(leftG >=1)            {                leftG -= 1;                Gold -= priceCSE[mm];                InsertTrie(box,name);            }            else return ;        }        else if (ex != 0)        {            Gold -= priceCSE[mm];            InsertTrie(box,name);        }    }    if(swich2 == 2 && Gold >= price_mxe[MXEID[mm]])    {        int ffg = 1;        for(int i=0; i<mx_tt_part[ MXEID[mm] ];++i)        {            if( SearchTrie(box,mx_part_name[MXEID[mm]][i]) < mx_part_need[MXEID[mm]][i])            {                ffg = 0;     break;            }        }        if(ffg)        {            InsertTrie(box,name);                        Gold -= price_mxe[MXEID[mm]];            leftG -= 1;            for(int i=0; i<mx_tt_part[ MXEID[mm] ];++i)                {                    if(mx_part_need[MXEID[mm]][i] == 0) continue ;                    string jj(mx_part_name[ MXEID[mm] ][i]);                    int swch = type[jj];                    DeletTrie(box,mx_part_name[MXEID[mm]][i],mx_part_need[MXEID[mm]][i]);                    if( swch == 1 || swch == 2)                    {                        leftG += mx_part_need[MXEID[mm]][i];                    }                    if( swch == 3)                    {                        if(SearchTrie(box,mx_part_name[MXEID[mm]][i]) == mx_part_need[MXEID[mm]][i])                        {                            leftG += 1;                        }                    }                }        }        return ;    }}void sold(char * name){    int num9 = SearchTrie(box, name);    if( num9 == 0) return ;        leftG += 1;        string etmp(name);    int swich = type[etmp];    if(swich == 3)    {         Gold += num9 * priceCSE[etmp];         DeletTrie(box,name,num9);         return ;    }    if(swich == 1)    {        Gold += priceNME[etmp];        DeletTrie(box,name,1);        return ;    }    if(swich == 2)    {        DeletTrie(box,name,1);        stack<string> Stak;        Stak.push(etmp);        string fobl;        while(! Stak.empty())        {            etmp = Stak.top();            Stak.pop();            Gold += priceMXE[etmp];            for(int i=0; i<mx_tt_part[ MXEID[etmp] ]; ++i)            {                fobl = mx_part_name[MXEID[etmp]][i];                if(type[ fobl ] == 2) Stak.push(fobl);                else if(type[fobl] == 1) Gold+= priceNME[fobl]*mx_part_need[MXEID[etmp]][i];                else if(type[fobl] == 3) Gold+= priceCSE[fobl]*mx_part_need[MXEID[etmp]][i];            }        }        return;    }}void operate(){    char flag = 0;    getchar();    char op = getchar();    char reds[30];    int getgold = -999;     scanf("%s",reds);     if(reds[0]>='0' && reds[0]<='9')     {         sscanf(reds,"%d",&getgold);    }    if(op == '+' && getgold >=0)    {        Gold += getgold; return;            }    if(op == '+' && getgold < 0)    {        obtain(reds); return ;    }    if(op == '-' && getgold <0)    {        sold(reds); return ;    }    return;}int main(){    int CSN = 1;    while(scanf("%d",&N_nme) != EOF)    {        int M;        init();        input();        scanf("%d",&M);        for(int i = 1; i <= M; ++i)        {            operate();        }        getchar();        cout<<"Case "<<CSN++<<':'<<endl;        cout<<Gold<<endl;        cout<<6-leftG<<endl;                for(int i=0;i<N_nme;++i)        {            int sp;            if(sp = SearchTrie(box,name_nme[i]))            {                OT foobar;                foobar.os = name_nme[i];                foobar.ctr = sp;                Set.insert(foobar);            }        }        for(int i=0;i<N_mxe;++i)        {            int sp1;            if(sp1 = SearchTrie(box,name_mxe[i]))            {                OT foobar;                foobar.os = name_mxe[i];                foobar.ctr = sp1;                Set.insert(foobar);            }        }        for(int i=0;i<N_cse;++i)        {            int sp;            if(sp = SearchTrie(box,name_cse[i]))            {                OT foobar;                foobar.os = name_cse[i];                foobar.ctr = sp;                Set.insert(foobar);            }        }        set<OT>::iterator it = Set.begin();        for(;it != Set.end();++it)        {            if(type[(*it).os] == 3)            cout<< (*it).os<<": "<<(*it).ctr<<endl;            else            {                for(int i=0;i<(*it).ctr;++i)                cout<< (*it).os<<": "<<1<<endl;            }        }        cout<<endl;            }    return 0;}

1楼onepiece_zoroshanks昨天 10:16

这题确实比较恶心，比赛基本都耗在它身上了，最后也没过。楼主代码确实看不懂，能否将此题的trick贴出来，感激不尽。

Re: MetalSeed昨天 10:43

回复onepiece_zoroshanksn嗯嗯 这题我用字典树当物品栏太麻烦了ntrick: 1.物品栏满的时候 可以合成物品 但是不能买消耗品。n 2.有些合成物品不需要配件，就是直接能合成，跟第一类物品同样处理。n 3.卖的时候第三类物品要全卖完，第二类物品要加上他所有的配件价值，如果配件中有合成物品，则继续把他的配件价值全加上来n 4. 有可能会出现上面物品中，没给出的物品，直接跳过了就/.. n 其他的暂时想不起来了...