PAT乙级1061-1073

于由astupidcoder发布

1061 判断题

#include<iostream>
#include<vector>

using namespace std;

int main(){

  ios::sync_with_stdio(false);
  int studentnum,question_num;
  cin >> studentnum>> question_num;
  vector<int> score(question_num);
  for(int i = 0 ; i != question_num ; ++i){
    cin >> score[i];
  }
  vector<int> answer(question_num);
  for(int i = 0 ; i != question_num ; ++i){
    cin >> answer[i];
  }
  vector<int> student(studentnum,0);
  for(int i = 0 ; i != studentnum; ++i){
    for(int j = 0 ; j != question_num ; ++j){
      int tmp;
      cin >> tmp;
      if (tmp == answer[j]){
        student[i] += score[j];
      }
    }
  }
  for(auto it = student.begin() ; it != student.end() ; ++it){
    cout << *it << endl;
  }
  return 0;

}

1062 最简分数

//一道求最大公因数的题

#include <cstdio>
#include<vector>

using namespace std;

int gcd(int a, int b) {
  return a == 0 ? b : gcd(b % a, a);
}

int main() {

  int num1,den1,num2,den2,den3;
  scanf("%d/%d %d/%d %d",&num1,&den1,&num2,&den2,&den3);
  if(num1/1.0/den1 > num2/1.0/den2){    //并没有说第一个分数小于第二个分数……
    num1 ^= num2 ^= num1 ^= num2;
    den1 ^= den2 ^= den1 ^= den2;
  }
  int den_tmp = (den1 * den2) / gcd(den1,den2);
  int den_all = (den3 * den_tmp) / gcd(den3,den_tmp);
  int begin = num1 * den_all / den1;
  int end = num2 * den_all / den2;
  vector<int> nums;
  for(int i = begin + 1 ; i < end ; ++i){
    int tmp =  gcd(i,den_all);
    int den4 = den_all / tmp;
    if (den4 == den3)
      nums.push_back(i/tmp);
  }

  for(int i = 0 ; i != nums.size()-1;++i){
    printf("%d/%d ",nums[i],den3);
  }
  printf("%d/%d\n",nums.back(),den3);
  return 0;
}

1063 计算谱半径

#include<cstdio>
#include<math.h>

int main(){

  int N;
  scanf("%d",&N);
  float max = 0;
  for(int i = 0 ; i != N ; ++i){
    int a,b;
    scanf("%d %d",&a,&b);
    float tmp = sqrt(a*a + b*b);
    if (tmp > max){
      max = tmp;
    }
  }
  printf("%.2f\n",max);
  return 0;
}

1064 朋友数

#include <cstdio>
#include <set>

using namespace std;

int main() {

  int n;
  scanf("%d", &n);
  set<int> res;
  for (int i = 0; i != n; ++i) {
    char s[4];
    scanf("%s", s);
    int j = 0;
    int sum = 0;
    while (s[j] != '\0') {
      sum += s[j++] - '0';
    }
    res.insert(sum);
  }
  auto it = res.begin();
  printf("%d\n",res.size());
  for (int i = 0; i != res.size(); ++i) {
    printf("%d%c", *it++, (i == res.size() - 1 ? '\n' : ' '));
  }
  return 0;
}

1065 单身狗

//比较容易想到的就是map大法，但是不知道效率如何。

#include <algorithm>
#include <cstdio>
#include <map>
#include <set>

using namespace std;

int main() {

  int n;
  scanf("%d", &n);
  map<int, int> couples;
  for (int i = 0; i != n; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    couples[a] = b;
    couples[b] = a;
  }
  scanf("%d", &n);
  set<int> cus;
  for (int i = 0; i != n; ++i) {
    int tmp;
    scanf("%d", &tmp);
    if (cus.find(couples[tmp]) != cus.end()) { //就是说对象已经来了
      cus.erase(couples[tmp]);
    } else
      cus.insert(tmp);
  }
  printf("%ld\n", cus.size());
  if (cus.empty())
    return 0;
  auto it = cus.begin();
  for (int i = 0; i != cus.size(); ++i) {
    printf("%05d%c", *it++, i == cus.size() - 1 ? '\n' : ' ');
  }
  return 0;
}

1066 图像过滤

#include <stdio.h>

int main() {
  int M, N, A, B, C;
  scanf("%d %d %d %d %d", &M, &N, &A, &B, &C);
  int tmp;
  for (int i = 0; i != M; ++i) {
    for (int j = 0; j != N; ++j) {
      scanf("%d", &tmp);
      if (tmp >= A && tmp <= B) {
        printf("%03d%c", C, (j == N - 1 ? '\n' : ' '));
      } else
        printf("%03d%c", tmp, (j == N - 1 ? '\n' : ' '));
    }
  }
  return 0;
}

1067 试密码

#include <iostream>
#include <string>

using namespace std;

int main() {

  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string correct, tmp;
  int times;
  cin >> correct >> times;
  cin.get();
  int triedtime = 0;
  while (triedtime++ < times) {
    getline(cin,tmp);   //正确密码不能有空格，但用户输入就不一定了= =
    if (tmp == "#")
      return 0;
    else if (tmp == correct) {
      cout << "Welcome in" << endl;
      return 0;
    } else {
      cout << "Wrong password: " + tmp << endl;
    }
  }
  cout << "Account locked" << endl;
  return 0; 
}

1068 万绿丛中一点红

#include <cstdio>
#include <map>
#include <set>
#include <utility>
#include <vector>

using namespace std;

inline int my_minus(int a, int b) { return a > b ? a - b : b - a; }

int main() {

#ifndef ONLINE_JUDGE
  freopen("input", "r", stdin);
#endif
  int M, N, TOL;
  scanf("%d %d %d", &M, &N, &TOL);
  vector<vector<int>> graph(N + 2, vector<int>(M + 2, -1));
  set<int> appeared;
  map<int, pair<int, int>> unique;
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j) {
      scanf("%d", &graph[i][j]);
      if (appeared.find(graph[i][j]) != appeared.end()) {
        unique.erase(graph[i][j]);
      } else {
        unique[graph[i][j]] = {i, j};
        appeared.insert(graph[i][j]);
      }
    }
  }
  map<int, pair<int, int>> res;
  for (auto it = unique.begin(); it != unique.end(); ++it) {
    int x = it->second.first, y = it->second.second;
    int uni = true;
    for (int i = x - 1; i <= x + 1; ++i) {
      for (int j = y - 1; j <= y + 1; ++j) {
        if (i == x && j == y)
          continue;
        else if (my_minus(graph[i][j], it->first) <= TOL) {
          uni = false;
          break;
        }
      }
    }
    if (uni) {
      res[it->first] = it->second;
    }
  }
  if (res.empty()) {
    printf("Not Exist\n");
  } else if (res.size() != 1) {
    printf("Not Unique\n");
  } else {
    printf("(%d, %d): %d\n", res.begin()->second.second,
           res.begin()->second.first, res.begin()->first);
  }
  return 0;
}

1069 微博转发抽奖

//在排序时不检查重名，但是如果有人中奖了，那就不能重复中奖，需要顺延。
#include <fstream>
#include <iostream>
#include <set>
#include <string>

using namespace std;

int main() {

#ifndef ONLINE_JUDGE
  ifstream cin("input");
#endif
  ios::sync_with_stdio(false);
  int M, N, S;
  cin >> M >> N >> S;
  cin.get();
  string tmp;
  set<string> winner; //不允许重复主要是
  bool outputed = false;
  int start = 0;
  for (int i = 1; i <= M; ++i) {
    getline(cin, tmp);
    ++start;
    if (start - S >= 0 and (start - S) % N == 0) {
      outputed = true;                        //已经有一个中奖者了
      if (winner.find(tmp) != winner.end()) { //这个人出现过了。
        --start;                              //并不需要复杂的处理
        continue;
      } else {
        winner.insert(tmp);
        cout << tmp << endl;
      }
    }
  }
  if (!outputed){
    cout << "Keep going..." << endl;
  }

  return 0;
}

1070 结绳

//这道题也有点意思，其实是，最长的绳子最后打结就行了。
//因为每次打结都会损失1/2的长度，当然是越长的绳子损失越小越好啊。
#include <cstdio>
#include <fstream>
#include <set>

using namespace std;

int main() {

#ifndef ONLINE_JUDGE
  //ifstream cin("input");
  freopen("input","r",stdin);
#endif
  multiset<float> ropes;
  int rope_nums;
  scanf("%d", &rope_nums);
  for (int i = 0; i != rope_nums; ++i) {
    float tmp;
    scanf("%f", &tmp);
    ropes.insert(tmp);
  }

  while (ropes.size() != 1) { //等于1就可以输出了
    auto it = ropes.begin();
    float a = *it;
    ropes.erase(it);
    it = ropes.begin();
    float b = *it;
    ropes.erase(it);
    ropes.insert((a + b) / 2);
  }
  auto it = ropes.begin();
  printf("%d\n",static_cast<int>(*it));
  return 0;
}

1071 小赌怡情

//小赌也不怡情，坚决远离赌博。
#include <cstdio>

int main() {

#ifndef ONLINE_JUDGE
  // ifstream cin("input");
  freopen("input", "r", stdin);
#endif
  long T, K;
  scanf("%ld %ld", &T, &K);
  int n1, n2, b, t;

  for (int i = 0; i != K; ++i) {
    scanf("%d %d %d %d", &n1, &b, &t, &n2);
    if (t > T) {
      printf("Not enough tokens.  Total = %ld.\n", T);
    } else if ((b == 0 and n1 > n2) || (b == 1 and n1 < n2)) { // win
      T += t;
      printf("Win %d!  Total = %ld.\n", t, T);
    } else {
      T -= t;
      printf("Lose %d.  Total = %ld.\n", t, T);
    }
    if (T == 0){
      printf("Game Over.\n");
      break;
    }
  }
  return 0;
}

1072 开学寄语

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<string>

using namespace std;

int main(){
#ifndef ONLINE_JUDGE
  ifstream cin("input");
  // freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int M,N;
    cin >> M >> N;
    set<string> forbidden;
    for(int i = 0 ; i != N ; ++i){
        string tmp;
        cin >> tmp;
        forbidden.insert(tmp);
    }

    map<string,vector<string>> fuck;
    vector<string> name;
    for (int i = 0 ; i != M ; ++i){
        string nn;
        int things;
        cin >> nn >> things;
        bool flag = true;
        for(int j = 0 ; j != things ; ++j){
            string tt;
            cin >> tt;
            if (forbidden.find(tt) != forbidden.end()){
                if (flag){
                    name.push_back(nn);
                    flag = false;
                }
                fuck[nn].push_back(tt);
            }
        }
    }

    int all = 0;

    for(const string& a:name){
        cout << a << ": ";
        for (int i = 0 ; i != fuck[a].size(); ++i)
            cout << fuck[a][i] << ((i == fuck[a].size() - 1) ? "\n" : " "); 

        all += fuck[a].size();
    }

    cout << name.size() << " " << all << "\n";

}

1073 多选题常见计分法

//这道题有点绕，先来分析一下吧。首先是要看每个学生的得分，这个倒很简单。
//之后要看每道题的错题情况，这个就有点恶心了。要输出错误次数、题目编号
//以及错的选项号。问题是，一道题的题目序号和编号是共同作为key来确定一个错误项的。
//索性用map好了。一句话总结：一道繁琐、恶心又简单的题目。

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define RIGHT 0
#define WRONG 1
#define HALF_RIGHT 2

struct Timu {
  int score;    //分值
  int xx_num;   //选项数量
  int r_xx_num; //正确选项数量
  char xxs[5];
};

void parasline(const string &line, const int timunum,
               vector<vector<char>> &res) {

  istringstream is(line);
  char kuohao;
  for (int i = 0; i != timunum; ++i) {
    int num = 0;
    is >> kuohao;
    is >> num;
    for (int j = 0; j != num; ++j) {
      char c;
      is >> c;
      res[i].push_back(c);
    }
    is >> kuohao;
  }
}

float pigai(const vector<vector<char>> &choose, const vector<Timu> &timus,
            const int timunum, map<pair<int, char>, int> &wrongs,
            int &mostwrong) {
  float res = 0.0;
  for (int i = 0; i != timunum; ++i) {
    int status = RIGHT;
    for (int j = 0; j != timus[i].r_xx_num; ++j) {
      //对该题的每一道正确选项，在该学生的选项里找，目的是看有没有漏选
      if (find(choose[i].begin(), choose[i].end(), timus[i].xxs[j]) ==
          choose[i].end()) {
        //漏选了
        status = HALF_RIGHT;
        ++wrongs[{i, timus[i].xxs[j]}];
        if (wrongs[{i, timus[i].xxs[j]}] > mostwrong)
          mostwrong = wrongs[{i, timus[i].xxs[j]}];
      }
    }
    for (int j = 0; j != choose[i].size(); ++j) {
      //对该学生的每一个选项，在正确选项里找，目的是看有没有选错
      if (find(timus[i].xxs, timus[i].xxs + timus[i].r_xx_num,
               choose[i][j]) == timus[i].xxs + timus[i].r_xx_num) { //错选了
        status = WRONG;
        ++wrongs[{i, choose[i][j]}];
        if (wrongs[{i, choose[i][j]}] > mostwrong)
          mostwrong = wrongs[{i, choose[i][j]}];
      }
    }
    //又有漏选又有错选的话，就是错。
    if (status == RIGHT) {
      res += timus[i].score;
    } else if (status == HALF_RIGHT) {
      res += timus[i].score / 2.0;
    }
  }
  return res;
}

int main() {

  int student_num, timunum;
  cin >> student_num >> timunum;
  vector<Timu> timus(timunum);
  for (int i = 0; i != timunum; ++i) {
    cin >> timus[i].score >> timus[i].xx_num >> timus[i].r_xx_num;
    for (int j = 0; j != timus[i].r_xx_num; ++j) {
      cin >> timus[i].xxs[j];
    }
  }
  map<pair<int, char>, int> wrongs; // key是题目序号和错误选项，int是错误次数
  cin.get();
  int mostwrong = 0;
  vector<float> students(student_num, 0.0);
  for (int i = 0; i != student_num; ++i) {
    string line;
    getline(cin, line);
    vector<vector<char>> choose(timunum);
    parasline(line, timunum, choose);
    students[i] += pigai(choose, timus, timunum, wrongs, mostwrong);
  }
  cout.flags(ios::fixed);
  cout.precision(1);
  for (auto it = students.begin(); it != students.end(); ++it) {
    cout << *it << endl;
  }
  if (wrongs.empty()){
    cout << "Too simple" << endl;
    return 0;
  }
  for(auto it = wrongs.begin() ; it != wrongs.end() ; ++it){
    if (it->second == mostwrong){
      cout << mostwrong << " " << it->first.first + 1 << '-' << it->first.second << endl;
    }
  }

  return 0;
}
分类： 刷题不休

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。

相关文章

刷题不休

PAT甲级1051-1060

1055是0通过率，错题； 1056的题目先就看不明白，看明白后我陷入 阅读更多…

刷题不休

PAT甲级1041-1050

其中1047题通过率为0，目测应该是题目有问题。 1041 Be Un 阅读更多…

刷题不休

PAT乙级1041-1060

1041 考试座位号 #include <iostream&gt 阅读更多…