正文之前
最近练算法，不过最可气的，我写出来的程序一直算法越界！！题目要求到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。
提交后满分（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。
提交后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 段，每行一个字符串，描述各个权限。对于分等级权限，格式为 <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。样例输入
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你怕不怕？！！
