算法竞赛入门经典第五章总结

#include<iostream>
#include<cstdio>
#include<sstream>//stringstream保存在sstream文件中 
#include<string>
#include<algorithm>
using namespace std;

int main(void)
{
    string line;
    //string 使用getline(cin,str)  char[]使用cin.getline(str,100); 
    while(getline(cin,line))
    {
        int sum=,x;
        stringstream ss(line); 
        while(ss>>x) sum+=x;
        cout << sum << endl;
    } 
    return ;
}

#include<iostream>
using namespace std;

struct Point{
    int x,y;
    Point(int x=,int y=):x(x),y(y){ }//这里可以初始化操作<br />　　//Point(int x=0,int y=0){ this->x=x; this->y=y; }
};

Point operator+(const Point&a,const Point&b)//重载运算符
{
    return Point(a.x+b.x,a.y+b.y); 
} 

ostream& operator<<(ostream&out,const Point &b)//重载运算符
{
    out << "(" << b.x << "," << b.y << ")";
    return out;
}
int main(void)
{
    Point a,b(,);
    a.x=;
    cout << a+b << endl;
    return ;    
}

大理石在哪里

//自己写的代码
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int main(void)
{
    int n,m,x,time=;
    while(cin >> n >> m)
    {
        vector<int>v;
        for(int i=;i<n;i++)
        {
            cin >> x;
            v.push_back(x);    
        } 
        sort(v.begin(),v.end());
        cout << "CASE# " << ++time << ":"<<endl; 
        for(int i=;i<m;i++)
        {
            cin >> x;
            int p=-;
            for(int j=;j<v.size();j++) 
            if(v[j]==x)
            {
                p=j;
                break;    
            }
            if(p == -)cout << x << " not found\n" << endl;
            else  cout << x << " found at " << p+ << endl;
        }
    }
    return ;    
}

//思路：先排序，再查找，使用algorithm头文件中的sort和lower_bound
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = ;

int main(void)
{
    int n,q,x,a[maxn],kase;
    while(scanf("%d%d",&n,&q)== && n)
    {
        printf("CASE# %d\n",++kase);
        for(int i=;i<n;i++) scanf("%d",&a[i]);
        sort(a,a+n);
        while(q--)
        {
            scanf("%d",&x);
            //lower_bound（a,a+n,x）函数返回x应该在的位置 ,lower_bound()函数作用是查找：大于或等于x的第一个位置； 
            int p = lower_bound(a,a+n,x)-a;
            if(a[p]==x) printf("%d found at %d\n",x,p+);
            else printf("%d not found\n",x);
        }    
    }
    return ;    
}

集合：

#include<iostream>
#include<cstring>
#include<sstream> 
#include<set>
#include<algorithm>
using namespace std;
int main(void){
    string s,buf;
    set<string>dict;
    while(cin >> s)
    {
        for(int i=;i<s.length();i++)//isalpha(ch)判断是不是英文字母 ,等价于isupper(ch) || islower(ch) 
            if(isalpha(s[i])) s[i]=tolower(s[i]); else s[i]=' ';
        stringstream ss(s);
        while(ss >> buf) dict.insert(buf);
    }
    for(set<string>::iterator it=dict.begin();it!=dict.end();it++) cout << *it << endl; 
    return ;
}

映射：

#include<set>
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

map<string ,int >cnt;//使用映射记录相应的字符串的数量，类似使用一个数组记录一个 
vector<string>words;

string standard(string s)
{
    for(int i=;i<s.length();i++)
        if(isalpha(s[i])) s[i]=tolower(s[i]);
    sort(s.begin(),s.end());
    return s;
}


int main(void)
{
    int n=;
    string s;
    while(cin >> s)
    {
        if(s[]=='#') break;
        words.push_back(s);
        string r=standard(s);
        if(!cnt.count(r)) cnt[r]=;
        cnt[r]++; 
    }
    vector<string>ans;
    for(int i=;i<words.size();i++)
    {
        if(cnt[standard(words[i])]==) ans.push_back(words[i]);
    }
    sort(ans.begin(),ans.end());
    for(int i=;i<ans.size();i++) cout << ans[i] << endl; 
    return ;
}

map 和 set 都支持insert,find,count,remove操作。map也称为关联数组。

集合栈：

#include<set>
#include<string>
#include<iostream>
#include<cstdio>
#include<stack>
#include<map> 
#include<vector>
#include<algorithm>
using namespace std;

typedef set<int> Set;
map<Set,int>IDcache; //将一个集合映射为一个整数 
vector<Set>Setcache; //将集合保存在向量数组中 

int ID(Set x)
{
    //如果在已经存在这个集合，那么就直接返回这个集合的编号，
    //否则就在集合向量数组中添加 这个集合，并在映射中保存编号 
    if(IDcache.count(x)) return IDcache[x];
    Setcache.push_back(x);
    IDcache[x]=Setcache.size()-;
    return IDcache[x]; 
}

stack<int>s;

int main(void)
{
    int n;
    cin >> n;
    for(int i=;i<n;i++)
    {
        string op;
        cin >> op;
        if(op[]=='P') s.push(ID(Set()));    
        else if(op[]=='D') s.push(s.top());
        else 
        {
            Set x1=Setcache[s.top()]; s.pop();
            Set x2=Setcache[s.top()]; s.pop();
            Set x;
            if(op[]=='U') set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
            if(op[]=='I') set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
            if(op[]=='A') {
                x=x2;
                x.insert(ID(x1));
            }
            s.push(ID(x));    
        }
    } 
    cout << Setcache[s.top()].size() << endl; 
    return ;
}

自己重新写了一个，但是没有使用技巧

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<stack> 
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;

map<set<int>,int>IDcache;
vector<set<int> >Setcache;

int ID(set<int> x)
{
    if(IDcache.count(x)) return IDcache[x];
    Setcache.push_back(x);
    IDcache[x]=Setcache.size()-;
    return IDcache[x];
}

stack<int>s;

int main(void)
{
    int n;
    cin >> n;
    for(int i=;i<n;i++)
    {
        string op;
        cin >> op;
        if(op[]=='P') s.push(ID(set<int>()));    
        else if(op[]=='D') s.push(s.top());
        else 
        {
            set<int> x;
            set<int> x1=Setcache[s.top()]; s.pop();
            set<int> x2=Setcache[s.top()]; s.pop();
            if(op[]=='U') set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
            if(op[]=='I') set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
            if(op[]=='A'){
                x=x2; x.insert(ID(x1));
            } 
            s.push(ID(x));
         }
    }
    cout << Setcache[s.top()].size() << endl; 
    return ;    
}

团队队列

#include<cstdio>
#include<iostream>
#include<queue>
#include<map>

using namespace std;

const int maxn = 1000 + 10;

int main(void)
{
    int t,kase=0;
    while(scanf("%d",&t)==1 && t)
    {
        printf("Scenario #%d\n",++kase);
        
        map<int,int>team;
        for(int i=0;i<t;i++)
        {
            int n,x;
            scanf("%d",&n);
            while(n--) {
                scanf("%d",&x);
                team[x]=i;
            }
        }
        queue<int> q,q2[maxn];
        for(;;)
        {
            int x;
            char cmd[10];
            scanf("%s",cmd);
            if(cmd[0]=='S') break;
            else if(cmd[0]=='D'){
                int t=q.front();
                printf("%d\n",q2[t].front()); q2[t].pop();
                if(q2[t].empty()) q.pop();
            }
            else if(cmd[0]=='E')
            {
                scanf("%d",&x);
                int t = team[x];
                if(q2[t].empty()) q.push(t);
                q2[t].push(x); 
            }
        }
        printf("\n");
    }
    return 0;
}

丑数：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;

const int a[3]={2,3,5};

typedef long long LL;

int main(void)
{
    priority_queue<LL,vector<LL>,greater<LL> >pq;
    set<LL> s;
    pq.push(1);
    s.insert(1);
    for(int i=1;;i++)
    {
        LL x=pq.top(); pq.pop();
        if(i==1500){
            cout << x << endl;
            break;
        }
        for(int j=0;j<3;j++)
        {
            LL temp = x*a[j];
            if(!s.count(temp)){
                s.insert(temp);
                pq.push(temp);
            }     
        }    
    } 
    return 0;
}