【计算机本科补全计划】CCF计算机职业资格认证 2016-12 试题详解

正文之前

最近练算法,不过最可气的,我写出来的程序一直算法越界!!题目要求到1000个输入都能正常工作,但是我的一般500个就直接越界了!!!咋办!!!咋办!!!???算了,先体会思想,后面再慢慢的琢磨如何防止越界?OK~~? 就这么办!!!


正文


2016-12-01题

试题编号

2016-12-1

试题名称

中间数

时间限制

1.0 s

内存要求

256M

问题描述

在一个整数序列a1, a2, …, an中,如果存在某个数,大于它的整数数量等于小于它的整数数量,则称其为中间数。在一个序列中,可能存在多个下标不相同的中间数,这些中间数的值是相同的。

给定一个整数序列,请找出这个整数序列的中间数的值。

输入格式

输入的第一行包含了一个整数n,表示整数序列中数的个数。

第二行包含n个正整数,依次表示a1, a2, …, an。

输出格式

如果约定序列的中间数存在,则输出中间数的值,否则输出-1表示不存在中间数。

样例输入 1

6

2 6 5 6 3 5

样例输出 1

5

样例说明

比5小的数有2个,比5大的数也有2个。

样例输入 2

4

3 4 6 7

样例输出 2

-1

样例说明

在序列中的4个数都不满足中间数的定义。

样例输入 3

5

3 4 6 6 7

样例输出 3

-1

样例说明

在序列中的5个数都不满足中间数的定义。

评测用例规模与约定

对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ ai ≤ 1000。

  • 问题描述

在一个整数序列a1, a2, …, an中,如果存在某个数,大于它的整数数量等于小于它的整数数量,则称其为中间数。在一个序列中,可能存在多个下标不相同的中间数,这些中间数的值是相同的。 给定一个整数序列,请找出这个整数序列的中间数的值。

  • 输入格式

输入的第一行包含了一个整数n,表示整数序列中数的个数。 第二行包含n个正整数,依次表示a1, a2, …, an。

  • 输出格式

如果约定序列的中间数存在,则输出中间数的值,否则输出-1表示不存在中间数。

  • 样例输入 1

6 2 6 5 6 3 5

  • 样例输出 1

5

  • 样例说明

比5小的数有2个,比5大的数也有2个。

  • 样例输入 2

4 3 4 6 7

  • 样例输出 2

-1

  • 样例说明

在序列中的4个数都不满足中间数的定义。

  • 样例输入 3

5 3 4 6 6 7

  • 样例输出 3

-1

  • 样例说明

在序列中的5个数都不满足中间数的定义。

  • 评测用例规模与约定

对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ ai ≤ 1000。

提交后满分(100分)的C++版本的答案代码:

/* CCF201612-1 中间数 */  

#include <iostream>  
#include <map>  

using namespace std;  

int main()  
{  
    map<int, int> m;  
    int n, v;  

    // 输入数据,构建Map  
    cin >> n;  
    for(int i=0; i<n; i++) {  
        cin >> v;  
        m[v]++;  
    }  

    // 找出中间数  
    int ans, mid=(n+1)/2, count=0, left;  
    for(map<int,int>::iterator it=m.begin(); it!=m.end(); it++)  
        if(count + it->second >= mid) {  
            left = count;  
            count = 0;  
            ans = it->first;  
        } else  
            count += it->second;  

    // 输出结果  
    if(left == count)  
        cout << ans << endl;  
    else  
        cout << -1 << endl;  

    return 0;  
}

我的答案代码

#include <iostream>
using namespace std;


int main()
{
    int n,mid=0;
    cout<<"first: ";
    cin>>n;
    int a[n];
    cout<<"Second: ";
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
    }
    for (int i=0; i<n; ++i)
    {
        for (int j=i+1; j<n; ++j)
        {
            if (a[j]>a[j+1])
            {
                int temp;
                temp=a[j+1];
                a[j]=a[j+1];
                a[j]=temp;
            }
            else
                break;
        }
    }
    for(int i=0; i<n; ++i)
    {
        if (a[i]==a[n-i-1]&&a[i-1]<a[i]&&a[n-i-1]<a[n-i])
        {
            mid=a[i];
            break;
        }
    }
    if (mid==0)
        cout<<"-1"<<endl;
    else
        cout<<mid<<endl;
}

我的算法时间复杂度比较高,毕竟用上了很麻烦的冒泡法对数组进行排序,整体的时间复杂度为O(n^2) 而我看了满分的答案,其时间复杂度为O(n),从性能上来说远远由于我的算法,当然,也许是因为我不知道map这个标准库的用法?但是看起来跟vector很像啊。也有迭代器等操作~ 不过不重要了。测试了几个案例,都还算正常通过 想法是好的!但是还需要很大的优化~继续努力吧!等我积攒了更多的经验,我再回头来修正,反正时间还够,11-26报名截止,12月份的考试,时间还很充足!宿舍里还有一本《算法导论》,我迫不及待的多线程作战了!!!《C++ Primer》 《算法导论》《计算机组成与设计》《Linux Shell 编程实战》~~ and so on


2016-12-02题

试题编号

2016-12-1

试题名称

工资的计算

时间限制

1.0 s

内存要求

256M

问题描述

小明的公司每个月给小明发工资,而小明拿到的工资为交完个人所得税之后的工资。假设他一个月的税前工资(扣除五险一金后、未扣税前的工资)为S元,则他应交的个人所得税按如下公式计算:

1) 个人所得税起征点为3500元,若S不超过3500,则不交税,3500元以上的部分才计算个人所得税,令A=S-3500元;

2) A中不超过1500元的部分,税率3%;

3) A中超过1500元未超过4500元的部分,税率10%;

4) A中超过4500元未超过9000元的部分,税率20%;

5) A中超过9000元未超过35000元的部分,税率25%;

6) A中超过35000元未超过55000元的部分,税率30%;

7) A中超过55000元未超过80000元的部分,税率35%;

8) A中超过80000元的部分,税率45%;

例如,如果小明的税前工资为10000元,则A=10000-3500=6500元,其中不超过1500元部分应缴税1500×3%=45元,超过1500元不超过4500元部分应缴税(4500-1500)×10%=300元,超过4500元部分应缴税(6500-4500)×20%=400元。总共缴税745元,税后所得为9255元。

已知小明这个月税后所得为T元,请问他的税前工资S是多少元。

输入格式

输入的第一行包含一个整数T,表示小明的税后所得。所有评测数据保证小明的税前工资为一个整百的数。

输出格式

输出一个整数S,表示小明的税前工资。

样例输入

9255

样例输出

10000

评测用例规模与约定

对于所有评测用例,1 ≤ T ≤ 100000。

  • 问题描述

小明的公司每个月给小明发工资,而小明拿到的工资为交完个人所得税之后的工资。假设他一个月的税前工资(扣除五险一金后、未扣税前的工资)为S元,则他应交的个人所得税按如下公式计算: 1) 个人所得税起征点为3500元,若S不超过3500,则不交税,3500元以上的部分才计算个人所得税,令A=S-3500元; 2) A中不超过1500元的部分,税率3%; 3) A中超过1500元未超过4500元的部分,税率10%; 4) A中超过4500元未超过9000元的部分,税率20%; 5) A中超过9000元未超过35000元的部分,税率25%; 6) A中超过35000元未超过55000元的部分,税率30%; 7) A中超过55000元未超过80000元的部分,税率35%; 8) A中超过80000元的部分,税率45%; 例如,如果小明的税前工资为10000元,则A=10000-3500=6500元,其中不超过1500元部分应缴税1500×3%=45元,超过1500元不超过4500元部分应缴税(4500-1500)×10%=300元,超过4500元部分应缴税(6500-4500)×20%=400元。总共缴税745元,税后所得为9255元。 已知小明这个月税后所得为T元,请问他的税前工资S是多少元。

  • 输入格式

输入的第一行包含一个整数T,表示小明的税后所得。所有评测数据保证小明的税前工资为一个整百的数。

  • 输出格式

输出一个整数S,表示小明的税前工资。

  • 样例输入

9255

  • 样例输出

10000

  • 评测用例规模与约定

对于所有评测用例,1 ≤ T ≤ 100000。

提交后100分的C++标准代码:

/* CCF201612-2 工资计算 */  

#include <iostream>  

using namespace std;  

//#define DEBUG  

int salaryrange[] = {3500, 3500+1500, 3500+4500, 3500+9000, 3500+35000, 3500+55000, 3500+80000 };  
int taxrate[] = {3, 10, 20, 25, 30, 35, 45};  
const int SIZE = sizeof(salaryrange) / sizeof(int);  

int range[SIZE];  

int main()  
{  
    int t, s;  

    // 计算各种收入范围  
    range[0] = salaryrange[0];  
    for(int i=1; i<SIZE; i++) {  
        range[i] = range[i-1] + (salaryrange[i] - salaryrange[i-1])  
                - (salaryrange[i] - salaryrange[i-1]) * taxrate[i-1] / 100;  
    }  

#ifdef DEBUG  
    for(int i=0; i<SIZE; i++)  
        cout << range[i] << " ";  
    cout << endl;  
#endif  

    // 输入数据:  
    cin >> t;  

    // 计算收入范围  
    int i;  
    for(i=0; i<SIZE; i++)  
        if(t <= range[i])  
            break;  

    // 计算税前工资  
    if(i == 0)  
        s = t;  
    else {  
        s = salaryrange[i-1] + (t - range[i-1]) * 100 / (100 - taxrate[i-1]);  
    }  

    // 输出结果  
    cout << s << endl;  

    return 0;  
}

我的答案代码:

#include <iostream>
using namespace std;
int main()
{
    int a[7]={3500,5000,8000,12500,38500,58500,83500};
    int b[7]={3500,4955,7655,11255,30755,44755,61005};
    double c[8]={0,0.03,0.1,0.2,0.25,0.3,0.35,0.45};
    double T;
    cin>>T;
    int i;
    for(i=0;i<7;++i)
    {
        if (T<a[i])
        {
            break;
        }
    }
    if (i==0)
        cout<<T<<endl;
    else
    {
        T=(T-b[i-1])/(1-c[i])+a[i-1];
        cout<<T<<endl;
    }
    return 0;
}

我用初期的复杂计算,来代替机器工作,从效率来说,我的代码更加简洁而且逆向的精度也很高!!!当然,看了标准的答案,思路是差不多的。只是实现手法会稍微不同点~~~ 这个还是蛮好的咯~~~


2016-12-03题

试题编号

2016-12-3

试题名称

权限查询

时间限制

1.0 s

内存要求

256M

问题描述

授权 (authorization) 是各类业务系统不可缺少的组成部分,系统用户通过授权机制获得系统中各个模块的操作权限。

本题中的授权机制是这样设计的:每位用户具有若干角色,每种角色具有若干权限。例如,用户 david 具有 manager 角色,manager 角色有 crm:2 权限,则用户 david 具有 crm:2 权限,也就是 crm 类权限的第 2 等级的权限。

具体地,用户名和角色名称都是由小写字母组成的字符串,长度不超过 32。权限分为分等级权限和不分等级权限两大类。分等级权限由权限类名和权限等级构成,中间用冒号“:”分隔。其中权限类名也是由小写字母组成的字符串,长度不超过 32。权限等级是一位数字,从 0 到 9,数字越大表示权限等级越高。系统规定如果用户具有某类某一等级的权限,那么他也将自动具有该类更低等级的权限。例如在上面的例子中,除 crm:2 外,用户 david 也具有 crm:1 和 crm:0 权限。不分等级权限在描述权限时只有权限类名,没有权限等级(也没有用于分隔的冒号)。

给出系统中用户、角色和权限的描述信息,你的程序需要回答多个关于用户和权限的查询。查询可分为以下几类:

不分等级权限的查询:如果权限本身是不分等级的,则查询时不指定等级,返回是否具有该权限;

分等级权限的带等级查询:如果权限本身分等级,查询也带等级,则返回是否具有该类的该等级权限;

分等级权限的不带等级查询:如果权限本身分等级,查询不带等级,则返回具有该类权限的等级;如果不具有该类的任何等级权限,则返回“否”。

输入格式

输入第一行是一个正整数 p,表示不同的权限类别的数量。紧接着的 p 行被称为 P 段,每行一个字符串,描述各个权限。对于分等级权限,格式为 :,其中 是权限类名,是该类权限的最高等级。对于不分等级权限,字符串只包含权限类名。

接下来一行是一个正整数 r,表示不同的角色数量。紧接着的 r 行被称为 R 段,每行描述一种角色,格式为

...

其中 是角色名称, 表示该角色具有多少种权限。后面 个字符串描述该角色具有的权限,格式同 P 段。

接下来一行是一个正整数 u,表示用户数量。紧接着的 u 行被称为 U 段,每行描述一个用户,格式为

...

其中 是用户名, 表示该用户具有多少种角色。后面 个字符串描述该用户具有的角色。

接下来一行是一个正整数 q,表示权限查询的数量。紧接着的 q 行被称为 Q 段,每行描述一个授权查询,格式为 ,表示查询用户 是否具有 权限。如果查询的权限是分等级权限,则查询中的 可指定等级,表示查询该用户是否具有该等级的权限;也可以不指定等级,表示查询该用户具有该权限的等级。对于不分等级权限,只能查询该用户是否具有该权限,查询中不能指定等级。

输出格式

输出共 q 行,每行为 false、true,或者一个数字。false 表示相应的用户不具有相应的权限,true 表示相应的用户具有相应的权限。对于分等级权限的不带等级查询,如果具有权限,则结果是一个数字,表示该用户具有该权限的(最高)等级。如果用户不存在,或者查询的权限没有定义,则应该返回 false。

样例输入

3

crm:2

git:3

game

4

hr 1 crm:2

it 3 crm:1 git:1 game

dev 2 git:3 game

qa 1 git:2

3

alice 1 hr

bob 2 it qa

charlie 1 dev

9

alice game

alice crm:2

alice git:0

bob git

bob poweroff

charlie game

charlie crm

charlie git:3

malice game

样例输出

false

true

false

2

false

true

false

true

false

样例说明

样例输入描述的场景中,各个用户实际的权限如下:

* 用户 alice 具有 crm:2 权限

* 用户 bob 具有 crm:1、git:2 和 game 权限

* 用户 charlie 具有 git:3 和 game 权限

* 用户 malice 未描述,因此不具有任何权限

评测用例规模与约定

评测用例规模:

1 ≤ p, r, u ≤ 100

1 ≤ q ≤ 10 000

每个用户具有的角色数不超过 10,每种角色具有的权限种类不超过 10

约定:

输入保证合法性,包括:

1) 角色对应的权限列表(R 段)中的权限都是之前(P 段)出现过的,权限可以重复出现,如果带等级的权限重复出现,以等级最高的为准

2) 用户对应的角色列表(U 段)中的角色都是之前(R 段)出现过的,如果多个角色都具有某一分等级权限,以等级最高的为准

3) 查询(Q 段)中的用户名和权限类名不保证在之前(U 段和 P 段)出现过

前 20% 的评测用例只有一种角色

前 50% 的评测用例权限都是不分等级的,查询也都不带等级

提交后100分的满分示例代码:

  • 问题描述

授权 (authorization) 是各类业务系统不可缺少的组成部分,系统用户通过授权机制获得系统中各个模块的操作权限。 本题中的授权机制是这样设计的:每位用户具有若干角色,每种角色具有若干权限。例如,用户 david 具有 manager 角色,manager 角色有 crm:2 权限,则用户 david 具有 crm:2 权限,也就是 crm 类权限的第 2 等级的权限。 具体地,用户名和角色名称都是由小写字母组成的字符串,长度不超过 32。权限分为分等级权限和不分等级权限两大类。分等级权限由权限类名和权限等级构成,中间用冒号“:”分隔。其中权限类名也是由小写字母组成的字符串,长度不超过 32。权限等级是一位数字,从 0 到 9,数字越大表示权限等级越高。系统规定如果用户具有某类某一等级的权限,那么他也将自动具有该类更低等级的权限。例如在上面的例子中,除 crm:2 外,用户 david 也具有 crm:1 和 crm:0 权限。不分等级权限在描述权限时只有权限类名,没有权限等级(也没有用于分隔的冒号)。 给出系统中用户、角色和权限的描述信息,你的程序需要回答多个关于用户和权限的查询。查询可分为以下几类:

  • 不分等级权限的查询:如果权限本身是不分等级的,则查询时不指定等级,返回是否具有该权限;
  • 分等级权限的带等级查询:如果权限本身分等级,查询也带等级,则返回是否具有该类的该等级权限;
  • 分等级权限的不带等级查询:如果权限本身分等级,查询不带等级,则返回具有该类权限的等级;如果不具有该类的任何等级权限,则返回“否”。
  • 输入格式

输入第一行是一个正整数 p,表示不同的权限类别的数量。紧接着的 p 行被称为 P 段,每行一个字符串,描述各个权限。对于分等级权限,格式为 :,其中 是权限类名,是该类权限的最高等级。对于不分等级权限,字符串只包含权限类名。 接下来一行是一个正整数 r,表示不同的角色数量。紧接着的 r 行被称为 R 段,每行描述一种角色,格式为 ... 其中 是角色名称, 表示该角色具有多少种权限。后面 个字符串描述该角色具有的权限,格式同 P 段。 接下来一行是一个正整数 u,表示用户数量。紧接着的 u 行被称为 U 段,每行描述一个用户,格式为 ... 其中 是用户名, 表示该用户具有多少种角色。后面 个字符串描述该用户具有的角色。 接下来一行是一个正整数 q,表示权限查询的数量。紧接着的 q 行被称为 Q 段,每行描述一个授权查询,格式为 ,表示查询用户 是否具有 权限。如果查询的权限是分等级权限,则查询中的 可指定等级,表示查询该用户是否具有该等级的权限;也可以不指定等级,表示查询该用户具有该权限的等级。对于不分等级权限,只能查询该用户是否具有该权限,查询中不能指定等级。 输出格式 输出共 q 行,每行为 false、true,或者一个数字。false 表示相应的用户不具有相应的权限,true 表示相应的用户具有相应的权限。对于分等级权限的不带等级查询,如果具有权限,则结果是一个数字,表示该用户具有该权限的(最高)等级。如果用户不存在,或者查询的权限没有定义,则应该返回 false。

  • 样例输入

3 crm:2 git:3 game 4 hr 1 crm:2 it 3 crm:1 git:1 game dev 2 git:3 game qa 1 git:2 3 alice 1 hr bob 2 it qa charlie 1 dev 9 alice game alice crm:2 alice git:0 bob git bob poweroff charlie game charlie crm charlie git:3 malice game 样例输出 false true false 2 false true false true false

  • 样例说明

样例输入描述的场景中,各个用户实际的权限如下: * 用户 alice 具有 crm:2 权限 * 用户 bob 具有 crm:1、git:2 和 game 权限 * 用户 charlie 具有 git:3 和 game 权限 * 用户 malice 未描述,因此不具有任何权限

  • 评测用例规模与约定

评测用例规模:

  • 1 ≤ p, r, u ≤ 100
  • 1 ≤ q ≤ 10 000
  • 每个用户具有的角色数不超过 10,每种角色具有的权限种类不超过 10
  • 约定:

输入保证合法性,包括: 1) 角色对应的权限列表(R 段)中的权限都是之前(P 段)出现过的,权限可以重复出现,如果带等级的权限重复出现,以等级最高的为准 2) 用户对应的角色列表(U 段)中的角色都是之前(R 段)出现过的,如果多个角色都具有某一分等级权限,以等级最高的为准 3) 查询(Q 段)中的用户名和权限类名不保证在之前(U 段和 P 段)出现过

  • 前 20% 的评测用例只有一种角色
  • 前 50% 的评测用例权限都是不分等级的,查询也都不带等级

提交后100分的满分示例代码:

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

map<string,int> Input_Privilege(map<string,int> &privilege)
{
    string line,priname;
    int prilevel;
    cin>>line;
    if(line.find(':')!=-1)
    {
        priname=line.substr(0,line.find(':'));
        prilevel=stoi(line.substr(line.find(':')+1));
    }
    else
    {
        priname=line;
        prilevel=-2; //use -2 to prevent that the privilege don't have a level so that it will smaller than -1, we can compare it with the level after Depart() directly
    }
    privilege.insert(make_pair(priname,prilevel));
    return privilege;

}

void Depart(string &Ask_Privilege, string &priname,int &prilevel)
{
    if(Ask_Privilege.find(':')!=-1)
    {
        priname=Ask_Privilege.substr(0,Ask_Privilege.find(':'));
        prilevel=stoi(Ask_Privilege.substr(Ask_Privilege.find(':')+1));
    }
    else
    {
        priname=Ask_Privilege;
        prilevel=-1;
    }
}


int main()
{
    int p,r,u,q;
    // First input parameter
    cin>>p;
    map<string,int> privilege;
    for(int i=0;i<p;i++)
        privilege=Input_Privilege(privilege);


    // Second input parameter
    multimap<string,string> Job_Privilege;
    cin>>r;
    for(int i=0;i<r;i++)
    {
        int Job_Num;
        string Job_Name,line;
        cin>>Job_Name>>Job_Num;
        while(Job_Num--)
        {
            cin>>line;
            Job_Privilege.insert(make_pair(Job_Name,line));
        }
    }

    // Third input parameter
    multimap<string,string> Worker_Job;
    cin>>u;
    for(int i=0;i<u;i++)
    {
        int Worker_Job_Num;
        string Worker_Name,line;
        cin>>Worker_Name>>Worker_Job_Num;
        while(Worker_Job_Num--)
        {
            cin>>line;
            Worker_Job.insert(make_pair(Worker_Name,line));
        }
    }
    // user input and we don't need to save it
    cin>>q;
    string Name,Ask_Privilege;
    while(q--)
    {
        cin>>Name>>Ask_Privilege;
        int Ask_prilevel;
        string Ask_priname;
        Depart(Ask_Privilege,Ask_priname,Ask_prilevel);
        if(privilege.find(Ask_priname)==privilege.end())
        {
            cout<<"flase,no this privilege"<<endl;
            continue;
        }

        if (Worker_Job.count(Name)!=0)
        {
            auto pos=Worker_Job.equal_range(Name).first;
            auto endpos=Worker_Job.equal_range(Name).second;
            while(pos!=endpos)
            {
                string Job_of_Worker=pos->second;
                if(Job_Privilege.find(Job_of_Worker)!=Job_Privilege.end())
                {
                    auto Privilege_of_Job=Job_Privilege.equal_range(Job_of_Worker);
                    auto Job_pos=Privilege_of_Job.first;
                    while(Job_pos!=Privilege_of_Job.second)
                    {
                        string priname_1;
                        int prilevel_1;
                        string privilege_1=Job_pos->second;
                        Depart(privilege_1,priname_1,prilevel_1);
                        if(priname_1==Ask_priname)
                        {
                            if(Ask_prilevel<=prilevel_1&&(prilevel_1!=-1))
                                cout<<prilevel_1<<endl;
                            else
                                cout<<Ask_priname<<endl;
                        }
                        Job_pos++;
                    }
                }
                pos++;
            }
        }
        else
            cout<<"false! no this guy"<<endl;
    }

    return 0;
}

我自己的代码,貌似还有点瑕疵~ 不过也差不多了??? maybe~~

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

map<string,int> Input_Privilege(map<string,int> &privilege)
{
    string line,priname;
    int prilevel;
    cin>>line;
    if(line.find(':')!=-1)
    {
        priname=line.substr(0,line.find(':'));
        prilevel=stoi(line.substr(line.find(':')+1));
    }
    else
    {
        priname=line;
        prilevel=-2; //use -2 to prevent that the privilege don't have a level so that it will smaller than -1, we can compare it with the level after Depart() directly
    }
    privilege.insert(make_pair(priname,prilevel));
    return privilege;
}

void Depart(string &Ask_Privilege, string &priname,int &prilevel)
{
    if(Ask_Privilege.find(':')!=-1)
    {
        priname=Ask_Privilege.substr(0,Ask_Privilege.find(':'));
        prilevel=stoi(Ask_Privilege.substr(Ask_Privilege.find(':')+1));
    }
    else
    {
        priname=Ask_Privilege;
        prilevel=-1;
    }
}

int main()
{
    int p,r,u,q;
    // First input parameter
    cin>>p;
    map<string,int> privilege;
    for(int i=0;i<p;i++)
        privilege=Input_Privilege(privilege);


    // Second input parameter
    multimap<string,string> Job_Privilege;
    cin>>r;
    for(int i=0;i<r;i++)
    {
        int Job_Num;
        string Job_Name,line;
        cin>>Job_Name>>Job_Num;
        while(Job_Num--)
        {
            cin>>line;
            Job_Privilege.insert(make_pair(Job_Name,line));
        }
    }

    // Third input parameter
    multimap<string,string> Worker_Job;
    cin>>u;
    for(int i=0;i<u;i++)
    {
        int Worker_Job_Num;
        string Worker_Name,line;
        cin>>Worker_Name>>Worker_Job_Num;
        while(Worker_Job_Num--)
        {
            cin>>line;
            Worker_Job.insert(make_pair(Worker_Name,line));
        }
    }
    // user input and we don't need to save it
    cin>>q;
    string Name,Ask_Privilege;
    while(q--)
    {
        cin>>Name>>Ask_Privilege;
        int Ask_prilevel;
        string Ask_priname;
        Depart(Ask_Privilege,Ask_priname,Ask_prilevel);
        if(privilege.find(Ask_priname)==privilege.end())
        {
            cout<<"flase,no this privilege'name"<<endl;
            continue;
        }

        if (Worker_Job.count(Name)!=0)
        {
            auto pos=Worker_Job.equal_range(Name).first;
            auto endpos=Worker_Job.equal_range(Name).second;
            while(pos!=endpos)
            {
                string Job_of_Worker=pos->second;
                if(Job_Privilege.count(Job_of_Worker)!=0)
                {
                    auto Privilege_of_Job=Job_Privilege.equal_range(Job_of_Worker);
                    auto Job_pos=Privilege_of_Job.first;
                    auto Job_endpos=Privilege_of_Job.second;
                    while(Job_pos!=Job_endpos)
                    {
                        string priname_1;
                        int prilevel_1;
                        string privilege_1=Job_pos->second;
                        Depart(privilege_1,priname_1,prilevel_1);
                        if(priname_1==Ask_priname)
                        {
                            if(Ask_prilevel<=prilevel_1&&(prilevel_1!=-1))
                                cout<<Name<<" "<<priname_1<<" : "<<prilevel_1<<endl;
                            else
                                cout<<Name<<" "<<priname_1<<endl;
                        }
                        Job_pos++;
                    }
                }
                else
                    cout<<"this guy don't have the power!";
                pos++;
            }
        }
        else
            cout<<"false! no this guy'name"<<endl;
    }
    return 0;
}

整体来说我的代码。。嗯,还需要改进,就好比这个

会出现一个人对应同一个权限的不同层次,具体参照bob的两个git权限等级。我画个图大家就明白了!

没错,当一个人身兼数职,然后这数个职务之间有着交叉的权限的时候,应该是取最高级别的,但是我这个代码中没有实现,只是中规中矩的找一个人,找他的职务,找他的职务对应的权限,是否符合请求,符合则输出,不符合就报错。结果,两个职务都符合!所以就两个都out了。我在想的是,要不要加一个信号量,就是确定这个人已经确认过了、但是后来想想如果高级权限在后面遍历,那岂不是就错过了?后来仔细想想,其实应该在最外围的时候就定义输出的对象,然后再在所有的计算完成后依次输出,这样的话就可以进行一定程度的遍历,我11点半的时候完成了上面的工作,后面想了两三种改进机制,但是毫无疑问都失败了!!现在一点半了!再不吃饭真的就没得吃了!所以,走也!~ 不过虽然我的代码比较起满分代码没有性能和空间上的优势,但是我代码行数少 啊,只有标准答案的40%。好吧,这没什么好骄傲 的!!慢慢改进吧!

正文之后

为毛2016 12 的试题比1703多了那么多????还是说我找的1703的试题是不完整的???好吧,应该是的,虽然我花了很多时间,但是以我的菜鸡水平,应该来说不至于三个小时左右就做完了。毕竟头一遭做,怎么可能还算顺利的处理完毕???不过也意识到了自己的弱鸡程度。毕竟要考280分,前面几题应该是吊打小学生的程度解决掉的!!继续加油。每天多刷刷~~身体健康心情好!

这篇文章八天前就开始写了!只是因为碰到了第三题,实在啃不动,所以闲置了好几天,直到昨晚学了关联容器!!!嘿嘿嘿~~ map map map 神奇的map~ 我来了~set set set你怕不怕?!!

原文发布于微信公众号 - 工科狗和生物喵(gh_3507b116a1f8)

原文发表时间:2017-11-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java 成神之路

高亮标红

3028
来自专栏数据结构与算法

01:谁考了第k名 个人博客:doubleq.win

个人博客:doubleq.win 01:谁考了第k名 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 在一次考试中,每个学...

3595
来自专栏数据结构与算法

洛谷P1731 [NOI1999]生日蛋糕(爆搜)

设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时,要求 R_i>R_{i+1}Ri​>Ri+1​ 且 H_i>H_{i+1}...

1051
来自专栏海天一树

NOIP 2011初赛普及组C/C++答案详解

3 C 8G = 8 * 1024 M 8 * 1024 / 2 = 4096张 注意,题目说的是“大约”,不要求精确。

1402
来自专栏Laoqi's Linux运维专列

python3–装饰器

4196
来自专栏CreateAMind

CS231n课程笔记翻译:Python Numpy教程

译者注:本文智能单元首发,翻译自斯坦福CS231n课程笔记Python Numpy Tutorial,由课程教师Andrej Karpathy授权进行翻译。本篇...

1193
来自专栏数说工作室

统计师的Python日记【第七天:数据清洗(1)】

本文是【统计师的Python日记】第7天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函数、...

55410
来自专栏编程札记

世界名画陈列馆问题(回溯法)

7923
来自专栏Crossin的编程教室

【每周一坑】谁是哪国人?

一道比较老套的题目: 在一个宾馆里住着六个不同国籍的人,他们分别来自美国、德国、英国、法国、俄罗斯和意大利。他们的名字叫 A、B、C、D、E、F。名字的顺序与...

2694
来自专栏owent

POJ PKU Let's Go to the Movies 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3513

852

扫码关注云+社区

领取腾讯云代金券