第三届河北省大学生程序设计竞赛燕山大学选拔赛（上）

水深无声 2022-01-13 12:37 289阅读 0赞

### 第三届河北省大学生程序设计竞赛燕山大学选拔赛（上） ###

*  A+B+C+D问题
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  数据范围及约定：
     *  题解
     *  源代码
 *  考试排名
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  数据范围及约定：
     *  题解
     *  源代码
 *  数学计算题
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  题解
     *  源代码
     *   *  题解一：
         *  题解二：
 *  IP地址的秘密
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  题解
     *  源代码
 *  人口异或
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  数据范围及约定：
     *  题解
     *  源代码

# A+B+C+D问题 #

## 问题描述 ##

温暖的签到题~ 对于输入的四个整数，输出它们的和。

## 输入格式 ##

只有一行，输入空格隔开的四个整数A、B、C、D

## 输出格式 ##

只有一行，输出A、B、C、D四个整数的和

## 输入样例 ##

1 2 3 4

## 输出样例 ##

## 数据范围及约定： ##

对于所有数据，保证0≤A,B,C,D≤2^62

## 题解 ##

这一题的关键是题目给的数据范围，A+B+C+D≤2^64, 而c++给出的数据范围是
    有限，long long 类型的最大范围是2^63-1， unsigned long 的最大范围是2^64-1
    而取得2^64 的条件是A=B=C=D=2^62 ,所以先判断，以字符串输出2^64

## 源代码 ##

#include<stdio.h>
    typedef unsigned long long ll;
    
    int main(){ 
        ll a,b,c,d;
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        ll z=(ll(1))<<62;
        if(a==b&&a==c&&a==d&&a==z)printf("18446744073709551616");
        else printf("%lld",a+b+c+d);
        return 0;
    }

# 考试排名 #

## 问题描述 ##

现在给出燕山大学软件学院每一位同学的期末考试成绩，请按照输入顺序输出每一位同学的排名。

## 输入格式 ##

第一行，输入一个整数n，表示燕山大学软件学院学生的总数 第二行，输入n个
    用空格隔开的整数ai，表示每一位同学的期末考试成绩

## 输出格式 ##

只有一行，输出n个用空格隔开的整数，表示每一位同学的排名

## 输入样例 ##

5
    150 150 142 148 137

## 输出样例 ##

1 1 4 3 5

## 数据范围及约定： ##

对于所有数据，保证1≤n≤10^3，0≤ai≤10^6

## 题解 ##

根据学生的分数进行排名，利用一个结构体存储学生的分数与排名，利用c++STL内置的排序算法，
    根据分数进行排序，排序后，进行排名，注意的是当分数相同的时候名次相同
    由于题目是要根据输入顺序输出排名，所以在结构体里加入一个变量记录顺序，
    在根据这个再进行一次排序，输出结果。

## 源代码 ##

#include<bits/stdc++.h>
    using namespace std;
    int n;
    struct s{ 
        int a,b,c;
    };
    bool cmp1(s A,s B){ 
       return A.a>B.a;
    }
    bool cmp2(s A,s B)
    { 
       return A.c<B.c;
    }
    int main()
    { 
    	cin>>n;
    	s a[1000];
    	for(int i=0;i<n;i++)
    	{ 
    		cin>>a[i].a;
            a[i].b=1;
    		a[i].c=i+1;
    	}
    	sort(a,a+n,cmp1);//先按照分数排序
        for(int i=1;i<n;i++){ 
            if(a[i].a==a[i-1].a)a[i].b=a[i-1].b;
            else a[i].b=i+1;
        }
        sort(a,a+n,cmp2);//按照输入顺序排序
        for(int i=0;i<n;i++)cout<<a[i].b<<" ";
    	return 0;
    }

# 数学计算题 #

## 问题描述 ##

请你写一个小程序，用来计算表达式的值。在表达式中，允许出现加法（+）、
    减法（-）、乘法（）、除法（/）和皮法（@）五种运算符以及小括号和小数
    点，结果要求四舍五入保留小数点后三位。
    其中皮法运算的运算法则是这样的：a@b=ab-a-b
    我们规定算符优先级：（））=（/）=（@）＞（+）=（-）

## 输入格式 ##

只有一行，输入一个字符串s，表示需要计算的表达式

## 输出格式 ##

只有一行，输出一个浮点数，表示表达式的答案

## 输入样例 ##

10@8-(2*3+6)

## 输出样例 ##

50.000

## 题解 ##

方法一：根据中缀表达式写出后缀表达式，再根据后缀表达式的顺序直接求得结果
    方法二：直接利用栈求解中缀表达式

## 源代码 ##

### 题解一： ###

#include<iostream>
    #include<stack>
    #include<queue>
    #include<string>
    #include<map>
    #include<fstream>
    using namespace std;
    struct node{                 //定义结构体，该结构体用于存储每次处理的字符 
        char op;                //如果是操作符，存入到op中，并且要将flag置为false 
        double data;            //如果是操作数，存入到data中，并且要将flag置为true 
        bool flag;
    };
    stack<node> s;         //操作符栈，存放操作符的临时工作栈。 
    queue<node> q;         //后缀表达式队列 
    map<char,int> op;      //操作符优先级 
    void change(string str){ 
        op['+']=op['-']=1;                  //输入操作符优先级 
        op['*']=op['/']=op['@']=2;  
        int len=str.length();
        for(int i=0;i<len;){ 
            node temp;         
            if(str[i]>='0'&&str[i]<='9'){      //如果是操作数的话 
                temp.flag =true;              //标记置为true 
                temp.data=str[i++]-'0';       //存储到临时结构体temp中 
                int flag=1;
                double x=0.1;
                while(i<len){          //因为数字可能不止一位，因此循环至不是数字为止 
                    if(str[i]=='.')flag=0;
                    else if(str[i]>='0' && str[i]<='9'){ 
                        if(flag)temp.data=temp.data*10+(str[i]-'0');
                        else temp.data+=(str[i]-'0')*x,x*=0.1;
                    }
                    else break;
                    i++;
                }
                q.push(temp);                //将该操作数扔进后缀序列的队列中 
            }
            else if(str[i]=='('){           //之前一直以为我这一块处理括号的写错了。。。。。后来发现代码没错。。。是因为自己输入的是中文括号。。。
                temp.flag =false;
                temp.op =str[i];             //是左括号直接压入队列 
                s.push(temp); 
                i++;
            }
            else if(str[i]==')'){             //终于等到了右括号 
                while(s.top().op!='('){       //将栈里面的操作符弹出到后缀表达式中，知道碰到了左括号 
                    q.push(s.top());
                    s.pop();                 
                }
                s.pop() ;                     //扔掉左括号 
                i++;
            } 
            else{ 
                temp.flag =false;              //如果是操作符，那么标记置为false 
                while(!s.empty()&&op[str[i]]<=op[s.top().op]){       //只有当该操作符的优先级高于栈顶元素的优先级，才压入栈内 
                    q.push(s.top());                                //否则将栈顶元素弹出，压入到队列中 
                    s.pop() ; 
                }
                temp.op=str[i];                  
                s.push(temp);
                i++; 
            }
    
        }
        while(!s.empty()){                  //最后如果操作符栈还不空的话。依次弹出压入到队列中 
                q.push(s.top());
                s.pop() ; 
            }
    }
    double cal(){                   //计算后缀表达式 
        node cur,temp;
        double temp1,temp2;        //第一操作数，第二操作数 
        while(!q.empty()){ 
            cur=q.front();         //取得队首元素 
            q.pop() ;             
            if(cur.flag==true){    //如果是操作数，压入栈中 
                s.push(cur); 
            }
            else{                     //如果是操作符 
                temp2=s.top().data ;  //取出第二操作数 
                s.pop() ;
                temp1=s.top().data ;  //取出第一操作数 
                s.pop() ;
                temp.flag =true;      //临时存放结果的temp，当然是新的操作数 
                if(cur.op =='+'){ 
                    temp.data =temp1+temp2;
                }
                else if(cur.op =='-'){ 
                    temp.data =temp1-temp2;
                }
                else if(cur.op =='*'){ 
                    temp.data =temp1*temp2;
                }
                else if(cur.op =='/'){ 
                    temp.data =temp1/temp2;
                }
                else if(cur.op =='@'){ 
                    temp.data =temp1*temp2-temp1-temp2;
                }
                s.push(temp); 
            }
        }
        return s.top().data;         //最后栈顶剩的唯一一个元素就是最终的结果了 
    }
    
    int main()
    { 
        string str;
        cin>>str;
        change(str);      //改成后缀表达式 
        printf("%.3lf",cal());    //计算结果。 
    }

### 题解二： ###

#include<bits/stdc++.h> 
    using namespace std;
    int cnt;
    char s[105];
    double transla(int &p)
    { 
        double integer=0.0;    // 整数部分
        double remainder=0.0;  // 余数部分
        while(s[p]>='0'&&s[p]<='9')
        { 
            integer*=10;
            integer+=(s[p]-'0');
            p++;
        }
        if(s[p]=='.')
        { 
            p++;
            int c=1;
            while(s[p]>='0'&&s[p]<='9')
            { 
                double t =s[p]-'0';
                t*=pow(0.1, c);
                c++;
                remainder+=t;
                p++;
            }
        }
        return integer+remainder;
    }
    int get_level(char ch)
    { 
        switch(ch)
        { 
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
            case '@': 
                return 2;
            case '(':
                return 0;
            case '#':
                return -1;
        };
        return 0;
    }
    double opera(double a1,char op,double a2)
    { 
        switch(op)
        { 
            case '+':
                return a1+a2;
            case '-':
                return a1-a2;
            case '*':
                return a1*a2;
            case '/':
                return a1/a2;
            case '@':
                return a1*a2-a1-a2;
        };
        return 0.0;
    }
    
    double calc()
    { 
        stack<char> opsym;
        stack<double> opnum;
        opsym.push('#');
        int len=strlen(s);
        bool is_minus=1;
        for(cnt=0;cnt<len;)
        { 
            if(s[cnt]=='-'&&is_minus)
            { 
                opnum.push(0);
                opsym.push('-');
                cnt++;
            }
            else if(s[cnt]==')')
            { 
                is_minus=0;
                cnt++;
                while(opsym.top()!='(')
                { 
                    double a2=opnum.top();
                    opnum.pop();
                    double a1=opnum.top();
                    opnum.pop();
                    char op=opsym.top();
                    opsym.pop();
                    double res=opera(a1,op,a2);
                    opnum.push(res);
                }
                opsym.pop();
            }
            else if(s[cnt]>='0'&&s[cnt]<='9')
            { 
                is_minus=0;
                opnum.push(transla(cnt));
            }
            else if(s[cnt]=='(')
            { 
                is_minus=1;
                opsym.push(s[cnt]);
                cnt++;
            }
            else
            { 
                while(get_level(s[cnt])<=get_level(opsym.top()))
                { 
                    double a2=opnum.top();
                    opnum.pop();
                    double a1=opnum.top();
                    opnum.pop();
                    char op=opsym.top();
                    opsym.pop();
                    double res=opera(a1,op,a2);
                    opnum.push(res);
                }
                opsym.push(s[cnt]);
                cnt++;
            }
        }
        while(opsym.top()!='#')
        { 
            double a2=opnum.top();
            opnum.pop();
            double a1=opnum.top();
            opnum.pop();
            char op=opsym.top();
            opsym.pop();
            double res=opera(a1,op,a2);
            opnum.push(res);
        }
        return opnum.top();
    }
    int main()
    { 
        cin>>s;
        printf("%.3lf",calc());
        return 0;
    }

# IP地址的秘密 #

## 问题描述 ##

给定若干个32位无符号整数n，将其转换为点分十进制表示法的IP地址
    我们以3232235521这个整数为例 首先将其转换成二进制表示： 
    11000000101010000000000000000001 在二进制表示中，左侧表示高位，右侧
    表示低位
    将二进制表示平均分为四段： 11000000.10101000.00000000.00000001 再
    把每一小段的二进制数转换成十进制数： 192.168.0.1 就是大家熟悉的形式了
    现在请你编程完成这个任务

## 输入格式 ##

输入包含若干行，每行一个整数

## 输出格式 ##

输出包含若干行，每行一个字符串，表示转换之后的IP地址

## 输入样例 ##

3232235521
    3402559508

## 输出样例 ##

192.168.0.1
    202.206.240.20

## 题解 ##

这题直接把int类型化成32位的二进制，根据每8位进行求和，求得最后的IP地址。

## 源代码 ##

#include<stdio.h>
    typedef unsigned long long ll;
    
    int main(){ 
        unsigned int a;
        while(scanf("%d",&a)!=EOF){ 
       	    int flag=1;//标记是不是第一个输出
            for(int i=31;i>=0;){ 
                int sum=0;
                for(int j=0;j<8;j++,i--)sum=sum*2+(a>>i&1);
                if(flag)printf("%d",sum),flag=0;
                else printf(".%d",sum);
            }
            printf("\n");
        }
        return 0;
    }

# 人口异或 #

## 问题描述 ##

据说，燕山大学的人都是成双成对出现的呢
    现在有一个长度为n的正整数序列，其中只有两种数值出现了奇数次，其他数值
    均出现偶数次，请你找出那两个出现奇数次的数值
    本题内存限制严格，请选手注意

## 输入格式 ##

第一行：一个整数n，表示序列的长度
    第二行：n个正整数ai，两个数中间以空格隔开

## 输出格式 ##

请在这里描述输出格式。例如：对每一组输入，在一行中输出A+B的值。

## 输入样例 ##

6
    2 1 5 2 3 1

## 输出样例 ##

3 5

## 数据范围及约定： ##

2<=n<=2*10^6；1<=ai<=10^9。

## 题解 ##

由于题目给出空间较小，无法利用数组保存所有的数，可以利用异或的性质进行求解
    首先可以参考怎样利用异或，有一个长度为n的正整数序列，其中只有一种数值出现了奇数次，
    其他数值均出现偶数次，找出那一个出现奇数次的数值
    对于这题，所有的数的异或结果就是这两个出现奇数次的数a,b异或的结果并且不等于0，
    异或结果的二进制，对于某一位是1的话，是由于a，b在相同位上一个是0，一个是1的结果
    利用这个性质可以对于每一个输入的数某位是1时进行异或。
    对于怎样得到a,b值可以借鉴怎样利用异或交换两个数。

## 源代码 ##

#include <bits/stdc++.h>
    using namespace std;
    int main()
    { 
        int n,a[32]={ 0},b,c=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++){ 
            scanf("%d",&b);
            c^=b;
            for(int i=0;i<32;i++)if(b>>i&1)a[i]^=b;
        }
        for(int i=0;i<32;i++){ 
            if(c>>i&1){ 
                int x=a[i]^c,y=x^c;
                if(x>y)swap(x,y);
                printf("%d %d",x,y);
                return 0;
            }
        }
    }