深圳住房和建设局官网站,天猫商城官网下载,湖北网络推广,交换友情链接的途径有哪些第一题#xff1a;中间数 在一个整数序列 a1,a2,…,an 中#xff0c;如果存在某个数#xff0c;大于它的整数数量等于小于它的整数数量#xff0c;则称其为中间数。 在一个序列中#xff0c;可能存在多个下标不相同的中间数#xff0c;这些中间数的值是相同的。 给定一个…第一题中间数 在一个整数序列 a1,a2,…,an 中如果存在某个数大于它的整数数量等于小于它的整数数量则称其为中间数。 在一个序列中可能存在多个下标不相同的中间数这些中间数的值是相同的。 给定一个整数序列请找出这个整数序列的中间数的值。 输入格式 输入的第一行包含了一个整数 n表示整数序列中数的个数。 第二行包含 n 个正整数依次表示 a1,a2,…,an。 输出格式 如果约定序列的中间数存在则输出中间数的值否则输出 −1−1 表示不存在中间数。 数据范围 对于所有评测用例1≤n≤10001≤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
#includeiostream
#includecstring
#includealgorithmusing 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 元则他应交的个人所得税按如下公式计算 个人所得税起征点为 3500 元若 S 不超过 3500则不交税3500 元以上的部分才计算个人所得税令 AS−3500 元A 中不超过 1500 元的部分税率 3%A 中超过 1500 元未超过 4500 元的部分税率 10%A 中超过 4500 元未超过 9000 元的部分税率 20%A 中超过 9000 元未超过 35000 元的部分税率 25%A 中超过 35000 元未超过 55000 元的部分税率 30%A 中超过 55000 元未超过 80000 元的部分税率 35%A 中超过 80000 元的部分税率 45% 例如如果小明的税前工资为 10000 元则 A10000−35006500 元其中不超过 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
#includeiostreamusing 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≤1001≤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 setusing 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_mapstring, setP 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 串不是另一个单词编码的前缀这种编码称为前缀码。 使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。 一段文字经过前缀编码后的长度为 La1的编码长度 ×t1a2× 的编码长度 ×t2…an 的编码长度 ×tn。 定义一个前缀编码为字典序编码指对于 1≤inai 的编码对应的 01 串的字典序在 ai1 编码之前即 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×13×32×42×22×5343×13×32×42×22×534。 在这个例子中如果使用哈夫曼(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% 的评测用例1n≤101≤ti≤20 对于 60% 的评测用例1n≤1001≤ti≤100 对于 100% 的评测用例1n≤10001≤ti≤10000。 输入样例 5
1 3 4 2 5输出样例 34样例解释 这个样例就是问题描述中的例子。如果你得到了 35说明你算得有问题请自行检查自己的算法而不要怀疑是样例输出写错了。 解题思路一开始我以为使用的是哈夫曼编码先试着写了一下直接答案错误我看了题解之后发现题目中有两句话非常的重要
1、需要按照字典序进行证明不能使用哈夫曼树进行解决。
2、只能合并相邻的两个点而且要最小代价因此是区间DP
用f[i][j]表示i~j这一些堆合并起来的最小代价 最终答案就是f[1][n]
用i~k表示左边石堆 k1~j表示右边石堆 则i~j的最小代价是f[i][j] min(f[i][k] f[k1][j] sum[i][j])
c
#includeiostream
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 algorithmusing 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;
}
