1010.txt

acm.pku.edu.cn/JudgeOnline上的题目1001到1010的十道题的代码

#include<iostream>  
//#include<search>  
#include<memory.h>  
using namespace std;
const int MAX_STAMP_TYPES =100; 
const int MAX_TOT_VALUE = 100; 
const int MAX_CUSTOMER=100; 
int s[MAX_STAMP_TYPES],s_size,cus[MAX_CUSTOMER],c_size,maxc,count[100]; 
bool custom[MAX_TOT_VALUE];     
class Combine{  
public: 
    int tot; 
    int ts;//types of stamps 
    int f;//flag 1 can 2 tie,0 can't 
    int s[4];//each stamps used here 
    int sc;//used stamps number 
    int max;//single maxed stamp value; 
public: 
    bool isHave(int type){  
        for(int i=0;i<sc;i++)  
            if(s[i]==type)return true; 
        return false; 
    }  
    void findMax(){  
        max=0; 
        for(int i=0;i<sc;i++)  
            if(::s[s[i]]>max)max=::s[s[i]]; 
    }  
    void addStamp(int type){  
        if(!isHave(type))ts++; 
        s[sc++]=type; 
        tot+=::s[type]; 
        if(::s[type]>max)max=::s[type]; 
    }  
    void removeLastStamp(int type){  
        sc--; 
        if(!isHave(type))ts--; 
        tot-=::s[type]; 
        findMax(); 
    }         
}currCus[MAX_TOT_VALUE],c; 
int com(const void * a,const void *b)  
{  
    return *((int *)a)-*((int*)b); 
}  
void init()  
{  
    maxc=c_size=s_size=0; 
    memset(custom,0,MAX_TOT_VALUE*sizeof(bool)); 
    memset(count,0,100*sizeof(int)); 
}  
bool read()  
{  
    init(); 
    int t; 
    cin>>t; 
    if(!cin)return false; 
    while(t!=0){  
        if(count[t]++<5)s[s_size++]=t; //modify by duoshute here 
        cin>>t; 
    }  
    qsort(s,s_size,sizeof(int),com); 
    cin>>t; 
    while(t!=0){  
        cus[c_size++]=t; 
        custom[t]=true; 
        if(t>maxc)maxc=t; 
        cin>>t; 
    }  
    return true; 
}  
int a[4],b[4]; 
bool same(int *t1,int *t2,int n)  
{  
  
    memcpy(a,t1,n*sizeof(int)); 
    memcpy(b,t2,n*sizeof(int)); 
/*    qsort(a,n,sizeof(int),com);           //omited by duoshute 
    qsort(b,n,sizeof(int),com); */ 
    return memcmp(a,b,n*sizeof(int))==0; 
}  
void solve(int ss,int last) //int last is added by duoshute 
{  
    if(custom[c.tot])  
    {  
        if(!currCus[c.tot].f  
                ||c.ts>currCus[c.tot].ts  
                ||c.ts==currCus[c.tot].ts&&c.sc<currCus[c.tot].sc  
                ||c.ts==currCus[c.tot].ts&&c.sc==currCus[c.tot].sc&&c.max>currCus[c.tot].max)  
        {  
            currCus[c.tot]=c; 
            currCus[c.tot].f=1; 
        }  
        else if(c.ts==currCus[c.tot].ts&&c.sc==currCus[c.tot].sc&&c.max==currCus[c.tot].max)  
        {  
            if(!same(c.s,currCus[c.tot].s,c.sc))  
                currCus[c.tot].f=2; 
        }  
             
    }  
    if(c.sc>=4||c.tot>maxc)return; 
    for(int i=last;i<s_size;i++)  
    {  
        c.addStamp(i); 
        solve(ss+1,i); 
        c.removeLastStamp(i); 
    }  
}  
int main()  
{  
    while(read())  
    {  
        memset(&c,0,sizeof(Combine)); 
        memset(currCus,0,MAX_TOT_VALUE*sizeof(Combine)); 
        solve(0,0); 
        for(int i=0;i<c_size;i++)  
            if(currCus[cus[i]].f==0)  
                cout<<cus[i]<<" ---- none"<<endl; 
            else if(currCus[cus[i]].f==2)  
                cout<<cus[i]<<" ("<<currCus[cus[i]].ts<<"): "<<"tie"<<endl; 
            else  
            {  
                cout<<cus[i]<<" ("<<currCus[cus[i]].ts<<"):"; 
                qsort(currCus[cus[i]].s,currCus[cus[i]].sc,sizeof(int),com); 
                for(int j=0;j<currCus[cus[i]].sc;j++)  
                    cout<<' '<<s[currCus[cus[i]].s[j]]; 
                cout<<endl; 
            }  
    }  return 0;
}