Uva oj （算法入门经典）排序与检索系列水题系列

淡淡的烟草味﹌ 2022-01-12 14:30 331阅读 0赞

### Uva[10420 - List of Conquests][] 题意就是首先给出一个n，表示字符的行数，下面n行字母，开头一个单词国家名字，后面一串人名，要你统计出每个国家人出现的次数，并按字母序输出。 用map容器写的，map容器本身的特性，很好用，代码： ###

#include <iostream>
    #include <cstdio>
    #include <map>
    #include <string>
    using namespace std;
    
    int main()
    {
        map<string,int> v;
        int T;
        cin>>T;
        while(T--)
        {
            string s,p,t;
            cin>>s;
            getchar();          //吸收留在缓冲区的空格
            getline(cin,p);
            //cout<<s<<" "<<p<<endl;
            if(v[s])
                v[s]++;
            else
                v[s]=1;
        }
        map<string,int>::iterator i;
        for(i=v.begin();i!=v.end();i++)
                cout<<(*i).first<<" "<<(*i).second<<endl;
        return 0;
    }

[Uvo340 - Master-Mind Hints][] 题目很长，大概意思就是第一行给出一个长度n的数字串a，后面给出p个串s直到这个串全部为0结束，找出这p个串与第一个串，如果a \[ i \] == s\[ j \] && i == j. 则A++; 如果 i ！= j && a \[ i \] == s \[ j \] B++;注意的是如果行或者列已经满足A的条件，就不能再B中计算，即A的优先级大于B，代码：

#include <stdio.h>
    int main()
    {
        int i,j,f,n,A,B,a[1010],b[1010],c[1010],sum=0,num;
        while (scanf("%d",&n),n)
        {
            ++sum;
            printf("Game %d:\n",sum);
            for (i=1;i<=n;i++)
            scanf("%d",&a[i]);
            f=1;
            while (f)
            {
                num=0;
                for (i=1;i<=n;i++)
                {scanf("%d",&b[i]); c[i]=a[i]; if (b[i]==0) ++num; }
                if (num==n) break;
                A=0;B=0;
                for (i=1;i<=n;i++)
                if (c[i]==b[i]) {++A;c[i]=-1;b[i]=-1;}
                for (i=1;i<=n;i++)
                {
                    if (c[i]!=-1)
                    {
                        for (j=1;j<=n;j++)
                        if ((c[i]==b[j])) 
                        {
                            ++B;c[i]=-1;b[j]=-1;break;
                        }
                    }
                }
                printf("    (%d,%d)\n",A,B);  
            }
        }
        return 0;
    }

### [Uva10474 - Where is the Marble?][Uva10474 - Where is the Marble] 注意：位置不是简单的计算，理解错了。。wa了一次。看代码吧。。。真实水题不水啊。 ###

#include <cstdio>
    #include <cstring>
    int a[10005],b[10005];
    int main()
    {
        int m,n,tmp,x,count;
        int cas=1;
        while(~scanf("%d%d",&m,&n))
        {
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            if(m==0&&n==0) break;
            for(int i=0;i<m;i++)
                {scanf("%d",&x);a[x]++;}
            for (int i=1;i<=10000;i++) b[i]=b[i-1]+a[i];
            printf("CASE# %d:\n",cas++);
            for(int cas=1;cas<=n;cas++)
            {
                  scanf("%d",&x);
                  if (a[x]==0) printf("%d not found\n",x);
                  else printf("%d found at %d\n",x,b[x-1]+1);
            }
        }
        return 0;
    }

### [Uva10161 - Ant on a Chessboard ][Uva10161 - Ant on a Chessboard]这题很考验判断能力，粗心让我在这个题上花了1个小时，题意就是给你一个如图的一个矩阵规律的排布，求一个数字在矩阵中的位置，可以先把题目中给出的先变换一下。然后直接判断控制。代码： ###

#include <stdio.h>
    #include <math.h>
    int main()
    {
        long a;
        int sa;
        while(~scanf("%ld",&a))
        {
            if(a==0) break;
            int A,B,i,j;
            A=B=0;
            sa=sqrt(a);
            if(a==sa*sa)
                sa--;
            //printf("%d\n",sa);
            if(sa%2){
                bool ok=true;
                for(int i=sa*sa+1;i<=sa*sa+sa+1;i++){
                    A++;
                    if(i==a){
                        B=sa+1;ok=false;break;
                    }
                }
                if(ok){
                    B=sa+1;
                    for(int j=sa*sa+sa+1;j<=(sa+1)*(sa+1);j++){
                        if(j==a){A=sa+1;break;}--B;
                    }
                }
            }
            else{
                bool ok=true;
                for(int i=sa*sa+1;i<=sa*sa+sa+1;i++){
                    B++;
                    if(a==i){
                        A=sa+1;ok=false;break;
                    }
                }
                if(ok){
                    A=sa+1;
                    for(int j=sa*sa+sa+1;j<=(sa+1)*(sa+1);j++){
                        if(a==j)
                            {B=sa+1;break;}
                        --A;
                    }
                }
            }
            printf("%d %d\n",A,B);
        }
        return 0;
    }

###  ###

### [Uva575 - Skew Binary][] 很水。题意为计算斜二进制。与二进制不同的是每次每位乘的是（2^n-1）；直接按计算二进制的方法模拟计算。10分钟搞定。代码： ###

#include <iostream>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    int main()
    {
        string s;
        int a[100];
        while(cin>>s)
        {
            long num=0;
            int i,j,la;
            la=s.size();
            if(s=="0") break;
            for(int i=1,j=la-1;j>=0;j--,i++)
                a[i]=s[j]-'0';
            for(int i=1;i<=la;i++)
                num+=(a[i]*(pow(2,i)-1));
            cout<<num<<endl;
        }
        return 0;
    }

### [Uva10250 - The Other Two Trees][] 题意即求两个点的连线长度与其垂直平分线长度相等的。确定直线垂直平分线的两个点。带公式， ###

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    int main()
    {
        double x1,x2,x3,x4;
        double y1,y2,y3,y4;
        while(scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2)!=EOF)
        {
            x3=(x1+x2)/2-(y2-y1)*0.5;
            y3=(y1+y2)/2+(x2-x1)*0.5;
            x4=(x1+x2)/2+(y2-y1)*0.5;
            y4=(y1+y2)/2-(x2-x1)*0.5;
            printf("%.10lf %.10lf %.10lf %.10lf\n",x3,y3,x4,y4);
        }
        return 0;
    }

[10420 - List of Conquests]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1361
[Uvo340 - Master-Mind Hints]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=276
[Uva10474 - Where is the Marble]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1415&mosmsg=Submission+received+with+ID+12019631
[Uva10161 - Ant on a Chessboard]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1102
[Uva575 - Skew Binary]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=516
[Uva10250 - The Other Two Trees]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1191