1153 Decode Registration Card of PAT (25 分)

题目:

1153 Decode Registration Card of PAT (25 分)

大概描述:

依照三种方式对考生信息进行筛选,涉及到排序,以及常用STL库。

特征词:

排序 STL

使用语言:

C++

解题思路:

前两类的查找可以直接,较为方便,主要是第三类,主要是先获取到,一个unordered_map的解集,然后再进行排序,由于使用map存在超时的问题,所以使用unordered_map

得分 提交次数 时间:

25分 2次 120min

具体代码:

#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int a = 10005;
const int b = 105;

struct st{
  string s;
  int sc;
}sts[a];

struct s3{
  string a;
  int b;
};

int num1,num2;

bool cmp(struct st f,struct st t){
   return f.sc != t.sc ? f.sc > t.sc : f.s < t.s;
}

bool cmp1(struct s3 f,struct s3 t){
   return f.b != t.b ? f.b > t.b : f.a < t.a;
}

void w1(string s){
  vector<st> ans;
  for(int i = 0;i < num1;i++){
    if(s[0] == sts[i].s[0])
        ans.push_back(sts[i]);
  }
  sort(ans.begin(),ans.end(),cmp);
  if(ans.size() != 0)
    for(int i = 0;i < ans.size();i++){
      cout << ans[i].s << " " << ans[i].sc << "\n";
    }
  else
    cout << "NA" <<"\n";
}

void w2(string s){
  int g = 0,num = 0;
  for(int i = 0;i < num1;i++){
    if(s == sts[i].s.substr(1,3)){
        g++;
        num += sts[i].sc;
    }

  }
  if(g != 0)
    cout << g << " " << num <<"\n";
   else
    cout << "NA" << "\n";
}

void w3(string s){
   unordered_map<string,int> ans;
   vector<s3> an;
   //cout << "OOOK";
   for(int i = 0;i < num1;i++){
    //cout << sts[i].s.substr(4,9) <<"\n";
    if(s == sts[i].s.substr(4,6)){
        //cout << "OOOK";
        ans[sts[i].s.substr(1,3)]++;
    }
   }
   struct s3 v;
   for (auto it : ans){
       v.a = it.first;
       v.b = it.second;
       an.push_back(v);
   }
   sort(an.begin(),an.end(),cmp1);
   if(an.size() != 0){
     for(int i = 0;i < an.size();i++){
      cout << an[i].a << " " << an[i].b << "\n";
     }
   }
   else
    cout << "NA" << "\n";
    //cout << it.first << " " << it.second << "\n";
}

int main(){
   int t;
   string rs;
   cin >> num1 >> num2;
   for(int i = 0;i < num1;i++){
    cin >> sts[i].s >> sts[i].sc;

   }
   for(int i = 0;i < num2;i++){
    cin >> t >> rs;
    cout << "Case " << i + 1 <<": " << t << " " << rs << "\n";
    if(t == 1)
        w1(rs);
    if(t == 2)
        w2(rs);
    if(t == 3)
        w3(rs);
   }
}

Hadoop是否未来依旧受欢迎

 

     Hadoop的火爆要得益于Google在2003年底和2004年公布的两篇研究论文,其中 份描述了 GFS(Google File System) ,GFS是 个可扩展的大型数据密集型应用的分布式文件系统,该文件系统可在廉价的硬件上运行,并具有可靠的容错能力,该文件系统可为用户提供好高的计算性能,而同时具备小的硬件投资和运营成本。另外 篇则描述了 MapReduce ,MapReduce是 种处理大型及超大型数据集并生成相关执行的编程模型。其主要思想是从函数式编程语言里借来的,同时也包含了从矢量编程语言里借来的特性。基于MapReduce编写的程序是在成千上万的普通PC机上被并行分布式自动执行的。
    8年后,Hadoop已经被广泛使用在网络上,并涉及数据分析和各类数学运算任务。但Google却提出更好的技术。在2009年,网络巨头开始使用新的技术取代GFS和MapReduce。Mike Olson表示“这些技术代表未来的趋势。如果你想知道大规模、高性能的数据处理基础设施的未来趋势如何,我建议你看看Google即将推出的研究论文”。

Google后Hadoop时代的新“三驾马车”——Caffeine、Pregel、Dremel。

当你谈论大数据的时候你还在说Hadoop?

1018 Public Bike Management(30 分)

题目:

1018 Public Bike Management(30 分)

大概描述:

找出到达目的最短的以及操作开销最小的路径

对图进行最合适路径选择,除了考虑最短路径外,还需要考虑点权重的逻辑关系

特征词:

Dijkstra算法,dfs

使用语言:

C++

解题思想:

利用先对图进行最短路径的存储,主要使用Dijkstra算法,然后再将路径结果存储在vector<int>[]数组中,再利用dfs依照条件进行遍历,选出最合适的路径

题目得分:

30

提交次数:

1

时间

70

代码

#include<vector>
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int inf = 99999999;
int e[510][510];//描述站站之间的关系
vector<int> fans[510];//所有最短路径
int weight[510];//站点的权重
int rig[510];//表示点到原点的最短距离
bool res[510];//表示已经确认的最终点
vector<int> temans;
vector<int> ans;
int findai = inf;
int finnn = inf;
void dfs(int a){
 temans.push_back(a);

 if(a == 0){
 int nn = 0;//表示当前所余
 int dai = 0;//表示需要带的车数
 for(int j = temans.size() - 2;j >= 0;j--){
 int i = temans[j];
 if(weight[i] > 0)
 nn += weight[i];
 if(weight[i] < 0){
 if(nn + weight[i] >= 0){
 nn = nn + weight[i];
 }else{
 dai += 0 - (nn + weight[i]);
 nn = 0;
 }
 }
 }
 if(dai < findai){
 ans = temans;
 findai = dai;
 finnn = nn;
 }else{
 if(dai == findai && nn < finnn){
 ans = temans;
 finnn = nn;
 }
 }

 return;

 }

 for(int i = 0;i < fans[a].size();i++){
 dfs(fans[a][i]);
 temans.pop_back();
 }


}

int main(){
 int maxc,num,st,a,b,c,f;
 scanf("%d %d %d %d",&maxc,&num,&st,&a);
 fill(e[0],e[0] + 510 * 510,inf);
 fill(rig,rig + 510,inf);
 weight[0] = 0;
 for(int i = 0;i < num;i++){
 scanf("%d",&b);
 weight[i + 1] = b - maxc / 2;
 }
 //cout << "f1\n";
 for(int i = 0;i < a;i++){
 scanf("%d %d %d",&b,&c,&f);
 e[b] = f;
 e[b] = f;
 }
 //cout <<"f2\n";

 //进行最短路径的遍历

 rig[0] = 0;
 for(int i = 0;i <= num;i++){
 //查看第二类中最短点
 int u = -1;int mini = inf;
 for(int j = 0;j <= num;j++){
 if(res[j] == false && mini > rig[j]){
 u = j;
 mini = rig[j];
 }
 }
 if(u == -1){
 //cout << "f3\n";
 break;
 }
 //更新相关值
 res[u] = true;
 for(int j = 0 ;j <= num;j++){//特别注意等号
 if(res[j] == false){
 if(e[j][u] + rig[u] < rig[j]){
 rig[j] = e[j][u] + rig[u];
 fans[j].clear();;
 fans[j].push_back(u);
 }
 else{
 if(e[j][u] + rig[u] == rig[j]){
 fans[j].push_back(u);
 }
 }
 }
 }

 }
 //cout <<"45678"<< fans[st][1];
 dfs(st);
/*
 cout << st << " " <<fans[st].size() << fans[st][2];
 int j = st;
 while(fans[j].size()){
 cout << " " << fans[j][0];
 j = fans[j][0];
 }
 */
 printf("%d 0", findai);
 for(int i = ans.size() - 2; i >= 0; i--)
 printf("->%d", ans[i]);
 printf(" %d", finnn);
 return 0;


}


 成长

熟练编写了最短路和深度遍历

1130 Infix Expression(25 分)

题目:

1130 Infix Expression(25 分)

大概描述:

语法树进行解析,实质进行二叉树进行前序遍历

特征词:

树的遍历

使用语言:

C++

解题思想:

利用所给的二叉树,进行前序遍历

题目得分:

25

提交次数:

1

时间

50

代码

#include<iostream>
#include<string>
#include<map>
#include<set>
using namespace std;
struct node{
 string v;
 int l;
 int r;
};

map<int,node> ns;
int st;
void post(int a){
 //cout << a;
 if(a == -1) return;
 if(ns[a].l != -1 || (ns[a].l == -1 && ns[a].r != -1))
 if(st != a)
 cout << "(";
 post(ns[a].l);
 cout << ns[a].v;
 post(ns[a].r);
 if(ns[a].r != -1 || (ns[a].r == -1 && ns[a].l != -1))
 if(st != a)
 cout << ")";
 return;
}
int main(){
 int a,b,c;
 string s;
 cin >> a;

 set<int> se;
 for(int i = 0;i < a;i++){
 cin >> s >> b >> c;
 ns[i + 1] = node{s,b,c};
 se.insert(b);
 se.insert(c);
 }
 for(int i = 1;i < a + 1;i++){
 if(se.find(i) == se.end())
 st = i;
 }
 post(st);
 return 0;
}

 成长

熟练的使用map + struct的组合。

1139. First Contact (30)

题目:

1139. First Contact (30)

大概描述:

两人进行交往,注意并不只考虑异性,也考虑同性

特征词:

STL 模拟

使用语言:

C++

解题思想:

用map建立两个关系,一个是同性联系的map,一个是异性联系的map,而没有使用邻接表,化成两个map处理起来比较方便,直观

题目得分:

18

提交次数:

2

时间

60

代码

#include<map>
#include<cstdio>
#include<set>//利用set自动排序
using namespace std;

//建两个map进行存储
int main(){
 int a,b,c,e1,e2;

 map<int,set<int>> same;
 map<int,set<int>> diff;

 scanf("%d %d",&a,&b);

 for(int i = 0;i < b;i++){
 scanf("%d %d",&e1,&e2);
 if(e1 * e2 > 0){
 same[e1].insert(e2);
 same[e2].insert(e1);
 }
 else{//-0000与0000在diff中
 diff[e1].insert(e2);
 diff[e2].insert(e1);
 }
 }

 scanf("%d",&c);
 for(int i = 0;i < c;i++){
 scanf("%d %d",&e1,&e2);
 map<int,set<int>>ans;
 int t = 0;
 if(e1 * e2 <= 0){
 for(set<int>::iterator it = same[e1].begin();it != same[e1].end();it++){
 for(set<int>::iterator itt = diff[*it].begin();itt != diff[*it].end();itt++){
 if(same[e2].find(*itt) != same[e2].end() && *itt != *it){
 ans[abs(*it)].insert(abs(*itt));
 t++;
 }
 }
 }
 }else{
 for(set<int>::iterator it = same[e1].begin();it != same[e1].end();it++){
 for(set<int>::iterator itt = same[*it].begin();itt != same[*it].end();itt++){
 if(same[e2].find(*itt) != same[e2].end() && *itt != *it){
 ans[abs(*it)].insert(abs(*itt));
 t++;
 }
 }
 }


 }


 printf("%d\n",t);
 for(map<int,set<int>>::iterator it = ans.begin();it != ans.end();it++){
 for(set<int>::iterator itt = (it -> second).begin();itt != (it -> second).end();itt++){
 printf("%d %d\n",it->first,*itt);
 }
 }
 }




}

 成长

我下次一定记得用string进行读取