UVa第五章STL应用习题（（解题报告））具体！

例题5——9 数据库 Database UVa 1592

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<cmath>

#include<string>

#include<queue>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

using namespace std;

int n, m;

int cnt[10034][12];

void before(){

  int x = 0;

  char ch;

  getchar();

  string str;

  map<string, int>dict;

  int t;

  for(int i = 0; i< n; i++){

    t = 0;

    for(;;){

        ch = cin.get();

        if(ch != ',' && ch != '\n'){

            str += ch;

        }

        else{

            if(dict.count(str)){

                cnt[i][t++] = dict[str];

            }

            else{

                dict[str] = ++x;

                cnt[i][t++] = dict[str];

            }

            str.clear();

        }

        if(ch == '\n'){

            break;

        }

    }

  }

}

int main()

{

    while(cin>>n>>m){

        before();

        string str;

        int flag = 0;

        for(int i = 0; i< m - 1 && !flag; i++){

            for(int j = i + 1; j < m && !flag; j++){

                map<pair<int, int>, int >buf;

                for(int k = 0; k < n && !flag; k++){

                    pair<int, int>pq(cnt[k][i], cnt[k][j]);

                    if(buf.count(pq)){

                        flag = 1;

                        cout<<"NO"<<endl

                        <<buf[pq] + 1<<" "<<k + 1<<endl

                        <<i + 1<<" "<<j + 1<<endl;

                    }

                    else{

                        buf[pq] = k;

                    }

                }

            }

        }

        if(!flag){

            cout<<"YES"<<endl;

        }

    }

    return 0;

}

习题5-1 代码对齐 UVa 1593 Alignment of Code

#include<iostream>

#include<string>

#include<stdio.h>

#include<vector>

#include<sstream>

using namespace std;

int main()

{

    vector<string>cnt[1003];

    string str;

    int row=0;

    int M[20]= {0};

    while(getline(cin,str))

    {

        stringstream ss(str); //stringstream 以空格和换行作为分隔符

        string buf;

        int col=0;//控制列数

        while(ss>>buf)

        {

            cnt[row].push_back(buf);  //然后利用ss 能够把一行元素扯开。push到每一行中去。

M[col]=max((int)buf.size(),M[col]);//每循环一次列数加一。那么n行输入之后每一个M元素

            col++;                  // 值即为此列最长字符值。

        }

        row++;      //行数加一

        ss.clear();     // 假设多次使用ss对象，尽量clear一下。

    }

    int j ,i;

    for( i=0; i<row; i++)

    {

        for( j=0; j<cnt[i].size()-1; j++)

        {

            cout<<cnt[i][j];

            for(int k=0; k<=M[j]-cnt[i][j].size(); k++)

                cout<<" ";

        }

        cout<<cnt[i][j]<<endl;

    }

    return 0;

}

习题5-2 Ducci Sequence UVa1594

说实话这个题目挺气人！。主要还是智商问题啊。一開始非常单纯的想，对于每一个多元组的生成，推断是否出现过和是否是0元组。那么想着利用stringstrem 把输入输出到数组。运算完之后。在运用stringstream 生成一个string对象放入map ，所以说不超时才怪！可是还是想把这个过程模拟一遍。至今有一处特别奇异，对于多次运用stringstream。clear（）函数怎么无效！

！！

只是还是在不断调试中学到了好多东西

接下来是一个严重超时的版本号：

#include<iostream>

#include<string>

#include<vector>

#include<cmath>

#include<map>

#include<sstream>

using namespace std;

int main()

{

    int t,n;

    (cin>>t).get();

    while(t--)

    {

        map<string,int>cnt;

        (cin>>n).get();

        string str;

        getline(cin,str);

        cnt[str]=1;

        stringstream ss;

        ss.str(str);

        for(;;)

        {

            int dict[16],t=0;

            while(ss>>dict[t])

            {

                t++;

            }

            string stream,sumstr;

            ss.clear();

            int k=dict[0],flag=1;

            for(int i=0; i<n-1; i++)

            {

                stringstream ss;

                dict[i]=abs(dict[i]-dict[i+1]);

                if(dict[i]!=0)

                    flag=0;

                ss<<dict[i];

                ss>>stream;

                sumstr+=(stream+" ");

                ss.clear();

            }

            dict[t-1]=abs(dict[t-1]-k);

            if(dict[t-1]!=0)

                flag=0;

            if(flag)

            {

                cout<<"ZERO"<<endl;

                break;

            }

            stringstream sss;

            sss<<dict[t-1];

            sss>>stream;

            sumstr+=stream;

            if(cnt.count(sumstr))

            {

                cout<<"LOOP"<<endl;

                break;

            }

            cnt[sumstr]=1;

            ss.clear();

            ss.str(sumstr);

        }

        cnt.clear();

    }

    return 0;

}

/*

4

4

8 11 2 7

**/

然后baidu一下网上代码。仅仅看了一句话就恍然大悟！

！说是在生成1000次之内必定出现结果！那么仅仅需在循环1000次中推断是否出现0元组。假设出现break，一千次之内没出现，那么必定存在loop了，这样就不用保存每次的生成结果了！

！

#include<iostream>

#include<string.h>

#include<cmath>

using namespace std;

int main()

{

    int t,cnt[23];

    cin>>t;

    while(t--)

    {

        int n;

        cin>>n;

        int i;

        for(i=0; i<n; i++)

        {

            cin>>cnt[i];

        }

        int k,ok=0;

        for(int j=0; j<1001; j++)

        {

            int T=cnt[0],flag=1;

            for(k=0; k<i-1; k++)

            {

                cnt[k]=abs(cnt[k]-cnt[k+1]);

                if(cnt[k]!=0)

                    flag=0;

            }

            cnt[k]=abs(cnt[k]-T);

            if(cnt[k]!=0)

                flag=0;

            if(flag)

            {

                ok=1;

                cout<<"ZERO"<<endl;

                break;

            }

        }

        if(!ok)

            cout<<"LOOP"<<endl;

    }

    return 0;

}

之開始真是日了狗了。还算注意到了输入为1的时候。这个时候什么都不输出。可是一開始就是“Discarded cards： ”非多了一个空行。导致输入为1的时候也输出多一个空行，PE N次！

#include<iostream>

#include<queue>

using namespace std;

int main()

{

    int n;

    while(cin>>n,n)

    {

        queue<int>cnt;

        for(int i=1;i<=n;i++)

        {

            cnt.push(i);

        }

        int flag=1;

        cout<<"Discarded cards:";

        while(cnt.size()!=1)

        {

            if(flag)

                {

                    flag=0;

                    cout<<" "<<cnt.front();

                }

                else

            cout<<", "<<cnt.front();

            cnt.pop();

            cnt.push(cnt.front());

            cnt.pop();

        }

        cout<<endl<<"Remaining card: "<<cnt.front()<<endl;

    }

    return 0;

}

习题 5-4 Foreign Exchange UVa 10763

自己还真不会做。哭死…看来水题刷的少~。有两种方法。第一种特别逗比~，另外一种不失为好方法，值得学习。

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int main()

{

    int n;

    while(cin>>n,n)

    {

        vector<int>cnt[2];

        int a,b;

        for(int i=0;i<n;i++)

        {

            cin>>a>>b;

            cnt[0].push_back(a);

            cnt[1].push_back(b);

        }

        sort(cnt[0].begin(),cnt[0].end());

        sort(cnt[1].begin(),cnt[1].end());

        if(cnt[0]==cnt[1])

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return 0;

}

</span></strong></span></span></strong>

TWO：

#include<iostream>

#include<string.h>

using namespace std;

int graph[2000][2000];

int main()

{

    int n;

    while(cin>>n,n)

    {

        int a,b;

        memset(graph,0,sizeof(graph));

        for(int i=0;i<n;i++)

        {

            cin>>a>>b;

            graph[a][b]++;

            graph[b][a]--;

        }

        int ok=0;

        for(int i=0;i<2000;i++)

        {

            for(int j=0;j<2000;j++)

            {

                if(graph[i][j]!=0)

                    {

                        ok=1;

                        goto loop;

                    }

            }

        }

      loop:

          if(ok)

          cout<<"NO"<<endl;

      if(!ok)

        cout<<"YES"<<endl;

    }

}

</span></strong></span></span></strong>

Compound Words UVA 10391 习题 5-5

#include<iostream>

#include<set>

#include<string>

using namespace std;

int main()

{

    string str;

    set<string>cnt;

    while(cin>>str)

        cnt.insert(str);

   set<string>::iterator it;

   for(it=cnt.begin();it!=cnt.end();it++)

   {

       for(int i=0;i<(*it).size()-1;i++)

       {

           string str1=(*it).substr(0,i+1);

           string str2=(*it).substr(i+1,(*it).size()-i-1);

           if(cnt.count(str1)&&cnt.count(str2))

           {

               cout<<*it<<endl;

               break;

           }

       }

   }

   return 0;

}

习题5-6 Symmetry Seoul UVa 1595

事实上很多其它的是学习了stl的使用方法。注意代码运用了类复制构造函数，用产生的暂时对象作为函数參数。

#include<set>

#include<iostream>

using  namespace std;

int main()

{

    int t,n;

    cin>>t;

    while(t--)

    {

        set< pair<double ,double> >cnt;

        typedef pair<double,double>Point;

        cin>>n;

        double sum=0;

        for(int i=0; i<n; i++)

        {

            double x,y;

            cin>>x>>y;

            sum+=x;

            cnt.insert(Point(x,y));

        }

        double aver=sum/n;//cout<<"aver="<<aver<<endl;

        bool ok=true;

        for(set< pair<double,double> >::iterator it=cnt.begin(); it!=cnt.end(); it++)

        {

            if(!cnt.count(Point(2*aver-(*it).first,(*it).second)))

            {

                //cout<<2*aver-(*it).first<<" "<<(*it).second<<endl;

                ok=false;

                break;

            }

        }

        if(ok)

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return 0;

}

习题5-7 Printer Queue UVa 12100

题目有一处想当麻烦。直接导致了优先队列不是那么可取。那就是最后一组測试例子。那么要模拟队列运作了。看了下网上思路。

队列中每一个元素都有两个属性，一个是紧急性，一个是是否是要打印。每一个元素都能够设成类对象。同一时候用一个优先队列保存紧急性属性，对于每一个优先队列队首元素，都是接下来要应该打印的元素，那么对于每次对象P的弹出，推断是不是应该打印的元素。假设是接下来还要推断是不是之前m值所要求打印的元素，假设是那么就该出现结果了。即优先队列弹出的元素总数，不是的话移到末尾，同一时候都要pop（）。

#include<iostream>

#include<queue>

using namespace std;

struct P

{

    int prio,IF;

    P(int x,int y)

    {

        prio=x;

        IF=y;

    }

};

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        priority_queue<int>dict;

        queue<P>cnt;

        int n,m;

        cin>>n>>m;

        for(int i=0; i<n; i++)

        {

            int a;

            cin>>a;

            if(i!=m)

                cnt.push(P(a,1));

            else

                cnt.push(P(a,0));

            dict.push(a);

        }

        int count=0,ok=0;

        for(;;)

        {

            int t=dict.top();

            dict.pop();

            while(1)

            {

                P x=cnt.front();

                cnt.pop();

                if(t==x.prio)

                {

                    count++;

                    if(x.IF!=0)

                    {

                        break;

                    }

                    else

                    {

                        ok=1;

                        cout<<count<<endl;

                        break;

                    }

                }

                else

                {

                    cnt.push(x);

                }

            }

            if(ok)

                break;

        }

    }

    return 0;

}

后半部分兴许！

！

！

！

巴特西

UVa第五章STL应用习题（（解题报告））具体！

最新文章

热门文章

巴特西

UVa第五章STL应用 习题（（解题报告））具体！

最新文章

热门文章

UVa第五章STL应用习题（（解题报告））具体！