第九次CCF计算机软件认证

第一题：中间数

在一个整数序列 a1,a2,…,an 中，如果存在某个数，大于它的整数数量等于小于它的整数数量，则称其为中间数。

在一个序列中，可能存在多个下标不相同的中间数，这些中间数的值是相同的。

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例1：

6
2 6 5 6 3 5

输出样例1：

5

样例1解释

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

输入样例2：

4
3 4 6 7

输出样例2：

-1

样例2解释

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

输入样例3：

5
3 4 6 6 7

输出样例3：

-1

样例3解释

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

解题思路： 

可以使用二分去做但是没有什么必要，排完序后直接进行模拟就行，针对每一个点都统计一下这些值的大于它的整数数量等于小于它的整数数量。

c++

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1010;
int n;
int a[N];int main()
{cin >> n;for(int i = 0;i < n;i ++)cin >> a[i];sort(a , a + n);int res = -1;for(int i = 0;i < n;i ++){int cnt = 0;for(int j = 0;j < i;j ++)if(a[j] < a[i]) cnt ++;for(int j = n - 1;j > i;j --)if(a[j] > a[i]) cnt --;if(!cnt) res = a[i];}cout << res << endl;return 0;
}

第二题：工资计算

小明的公司每个月给小明发工资，而小明拿到的工资为交完个人所得税之后的工资。

假设他一个月的税前工资（扣除五险一金后、未扣税前的工资）为 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，表示小明的税前工资。

数据范围

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

输入样例：

9255

输出样例：

10000

解题思路：

如果工资小于3500不交税直接返回，大于3500的部分按照题目的方式进行计算。枚举每一个整百的点计算税后的钱数对比输入的结果即可得到结果。

c++

#include<iostream>using namespace std;int s , res;int check(int x)
{if(x <= 3500) return x;int a[] = {0, 1500, 4500, 9000, 35000, 55000, 80000, 1000000};double b[] = {0, 0.03, 0.1, 0.2, 0.25, 0.3, 0.35, 0.45};int tax = x - 3500 , sum = 0;for(int i = 1;i <= 7;i ++)if(tax >= a[i]) sum += (a[i] - a[i - 1]) * b[i];else{sum += (tax - a[i - 1]) * b[i];break;}return x - sum;
}int main()
{cin >> s;for(int i = 0;;i += 100){if(check(i) == s) {cout << i << endl;return 0;}}
}

第三题：权限查询

授权 (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 段，每行一个字符串，描述各个权限。

对于分等级权限，格式为 <category>:<level>，其中 <category> 是权限类名，<level> 是该类权限的最高等级。

对于不分等级权限，字符串只包含权限类名。

接下来一行是一个正整数 r，表示不同的角色数量。

紧接着的 r 行被称为 R 段，每行描述一种角色，格式为

<role> <s> <privilege 1> <privilege 2> ... <privilege s>

其中 <role> 是角色名称，<s> 表示该角色具有多少种权限。

后面 <s> 个字符串描述该角色具有的权限，格式同 P 段。

接下来一行是一个正整数 u，表示用户数量。

紧接着的 u 行被称为 U 段，每行描述一个用户，格式为

<user> <t> <role 1> <role 2> ... <role t>

其中 <user> 是用户名，<t> 表示该用户具有多少种角色。

后面 <t> 个字符串描述该用户具有的角色。

接下来一行是一个正整数 q，表示权限查询的数量。

紧接着的 q 行被称为 Q 段，每行描述一个授权查询，格式为 <user> <privilege>，表示查询用户 <user> 是否具有 <privilege> 权限。

如果查询的权限是分等级权限，则查询中的 <privilege> 可指定等级，表示查询该用户是否具有该等级的权限；也可以不指定等级，表示查询该用户具有该权限的等级。

对于不分等级权限，只能查询该用户是否具有该权限，查询中不能指定等级。

输出格式

输出共 q 行，每行为 false、true，或者一个数字。

false 表示相应的用户不具有相应的权限，true 表示相应的用户具有相应的权限。

对于分等级权限的不带等级查询，如果具有权限，则结果是一个数字，表示该用户具有该权限的（最高）等级。

如果用户不存在，或者查询的权限没有定义，则应该返回 false。

数据范围

评测用例规模：

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

约定：

• 输入保证合法性，包括：
  　　1) 角色对应的权限列表（R 段）中的权限都是之前（P 段）出现过的，权限可以重复出现，如果带等级的权限重复出现，以等级最高的为准
  　　2) 用户对应的角色列表（U 段）中的角色都是之前（R 段）出现过的，如果多个角色都具有某一分等级权限，以等级最高的为准
  　　3) 查询（Q 段）中的用户名和权限类名不保证在之前（U 段和 P 段）出现过
• 前 20% 的评测用例只有一种角色
• 前 50% 的评测用例权限都是不分等级的，查询也都不带等级

额外声明：

• 保证没有两个不同的人或两个不同的角色或两个不同的权限出现重名的情况。
• 查询（Q 段）中的权限类名如果在之前（U 段和 P 段）出现过，则一定严格按照题面描述查询规定，为上述三类查询之一。（如果权限本身是不分等级的，则保证查询时不指定等级）

输入样例：

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 未描述，因此不具有任何权限

解题思路：

使用结构体表示一种权限，在结构体中写一个构造函数进行判断每一个字符串的类型。

使用哈希表存储每一条权限的信息，可以使用O(1)的复杂度进行筛选。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <set>using namespace std;struct P
{string name;mutable int level;  // level == -1, 表示无等级权限P(string str){int k = str.find(":");if (k == -1) name = str, level = -1;else{name = str.substr(0, k);level = stoi(str.substr(k + 1));}}bool operator< (const P& t) const{return name < t.name;}
};
unordered_map<string, set<P>> role, person;int main()
{int n;string str;cin >> n;while (n -- ) cin >> str;cin >> n;while (n -- ){string name;int cnt;cin >> name >> cnt;auto& r = role[name];while (cnt -- ){cin >> str;P t(str);if (t.level == -1) r.insert(t);else{if (!r.count(t)) r.insert(t);else{auto it = r.find(t);it->level = max(it->level, t.level);}}}}cin >> n;while (n -- ){string name;int cnt;cin >> name >> cnt;auto& p = person[name];while (cnt -- ){string str;cin >> str;for (auto& t: role[str]){if (t.level == -1) p.insert(t);else{if (!p.count(t)) p.insert(t);else{auto it = p.find(t);it->level = max(it->level, t.level);}}}}}cin >> n;while (n -- ){string user, pr;cin >> user >> pr;P t(pr);auto& p = person[user];if (!p.count(t)) puts("false");else{auto it = p.find(t);if (t.level != -1){if (it->level >= t.level) puts("true");else puts("false");}else{if (it->level == -1) puts("true");else cout << it->level << endl;}}}return 0;
}

第四题：压缩编码

给定一段文字，已知单词 a1,a2,…,an 出现的频率分别 t1,t2,…,tn。

可以用 0101 串给这些单词编码，即将每个单词与一个 0101 串对应，使得任何一个单词的编码（对应的 0101 串）不是另一个单词编码的前缀，这种编码称为前缀码。

使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。

一段文字经过前缀编码后的长度为：

L=a1的编码长度 ×t1+a2× 的编码长度 ×t2+…+an 的编码长度 ×tn。

定义一个前缀编码为字典序编码，指对于 1≤i<n，ai 的编码（对应的 01 串）的字典序在 ai+1 编码之前，即 a1,a2,…,an 的编码是按字典序升序排列的。

例如，文字 E A E C D E B C C E C B D B E 中， 55 个单词 A、B、C、D、E 出现的频率分别为 1,3,4,2,5，则一种可行的编码方案是 A:000, B:001, C:01, D:10, E:11，对应的编码后的 0101 串为 1100011011011001010111010011000111，对应的长度 L 为 3×1+3×3+2×4+2×2+2×5=343×1+3×3+2×4+2×2+2×5=34。

在这个例子中，如果使用哈夫曼(Huffman)编码，对应的编码方案是 A:000, B:01, C:10, D:001, E:11，虽然最终文字编码后的总长度只有 3333，但是这个编码不满足字典序编码的性质，比如 C 的编码的字典序不在 D 的编码之前。

在这个例子中，有些人可能会想的另一个字典序编码是 A:000, B:001, C:010, D:011, E:1，编码后的文字长度为 35。

请找出一个字典序编码，使得文字经过编码后的长度 L 最小。

在输出时，你只需要输出最小的长度 L，而不需要输出具体的方案。

在上面的例子中，最小的长度 L 为 34。

输入格式

输入的第一行包含一个整数 n，表示单词的数量。

第二行包含 n 个整数，用空格分隔，分别表示 a1,a2,…,an 出现的频率，即 t1,t2,…,tn。

请注意 a1,a2,…,an 具体是什么单词并不影响本题的解，所以没有输入 a1,a2,…,an。

输出格式

输出一个整数，表示文字经过编码后的长度 L 的最小值。

数据范围

对于 30% 的评测用例，1<n≤10，1≤ti≤20；
对于 60% 的评测用例，1<n≤100，1≤ti≤100；
对于 100% 的评测用例，1<n≤1000，1≤ti≤10000。

输入样例：

5
1 3 4 2 5

输出样例：

34

样例解释

这个样例就是问题描述中的例子。如果你得到了 35，说明你算得有问题，请自行检查自己的算法而不要怀疑是样例输出写错了。

 解题思路：一开始我以为使用的是哈夫曼编码，先试着写了一下，直接答案错误，我看了题解之后，发现题目中有两句话非常的重要

1、需要按照字典序进行，证明不能使用哈夫曼树进行解决。

2、只能合并相邻的两个点而且要最小代价，因此是区间DP

用f[i][j]表示i~j这一些堆合并起来的最小代价
最终答案就是f[1][n]

用i~k表示左边石堆 k+1~j表示右边石堆
则i~j的最小代价是f[i][j] = min(f[i][k] + f[k+1][j] + sum[i][j])

c++

#include<iostream>
using namespace std;
const int N = 1005;
int sum[N];
int f[N][N];int main() 
{int n; cin >> n;for(int i = 1;i <= n;i ++) {cin >> sum[i];sum[i] += sum[i - 1];}//先枚举区间长度//因为合并石堆至少需要两堆 所以区间长度从2开始for(int len = 2;len <= n;len ++) {//枚举左端点for(int l = 1;l + len - 1 <= n;l ++){//确定右端点int r = l + len - 1;//初始化最大值f[l][r] = 1e8;//在区间上枚举for(int k = l;k <= r;k ++)f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);}}cout << f[1][n];return 0;
}

第五题：卡牌游戏

应该使用的是概率论的知识，我是做不出来

 

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 15, M = 1 << N;int n, m;
double p[N][N], s1[N], s2[N];
double f[2][M], w[M][N];int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++ )for (int j = i + 1; j < n; j ++ ){scanf("%lf", &p[i][j]);p[j][i] = 1 - p[i][j];}for (int i = 1; i + 1 < 1 << n; i ++ ){memset(s1, 0, sizeof s1);memset(s2, 0, sizeof s2);for (int j = 0; j < n; j ++ )if (i >> j & 1){for (int k = 0; k < n; k ++ )if (!(i >> k & 1))s1[j] += p[j][k];}else{for (int k = 0; k < n; k ++ )if (i >> k & 1)s2[j] += p[j][k];}double sum1 = 0, sum2 = 0;for (int j = 0; j < n; j ++ ){sum1 += s1[j];sum2 += s2[j];}for (int j = 0; j < n; j ++ )if (i >> j & 1){for (int k = 0; k < n; k ++ )if (!(i >> k & 1))w[i][j] += s1[j] / sum1 * s2[k] / sum2 * p[k][j];}else{for (int k = 0; k < n; k ++ )if (i >> k & 1)w[i][j] += s2[j] / sum2 * s1[k] / sum1 * p[k][j];}}for (int k = 1; k <= 1000; k ++ ){memset(f[k & 1], 0, sizeof f[k & 1]);f[k & 1][(1 << n) - 1] = 1;for (int i = 1; i + 1 < 1 << n; i ++ )for (int j = 0; j < n; j ++ )f[k & 1][i] += f[k - 1 & 1][i ^ (1 << j)] * w[i][j];}while (m -- ){int state = 0;for (int i = 0; i < n; i ++ ){int x;scanf("%d", &x);state += x << i;}printf("%.5lf\n", f[0][state]);}return 0;
}