PAT甲级1021-1040

1021 Deepest Root

思路过程

这道题的内存限制是64M，意味着用vector<vector<int>>存图的话，10000个节点就是1亿个int，一亿个int什么概念，一个int 4byte，一亿个就是4亿byte，大概是400M，妥妥内存超限，所以不能用那玩意来存图。这道题其实是一个稀疏图，可以考虑用邻接链表来存，但是处理起来麻烦，最后考虑用vector<vector<bool>>来存，根据STL的说明，vector<bool>是专门优化过的，一个bite表示一个数，那么一亿个bite是多大呢？12.5M，好，我们解决了内存问题。

接下来考虑算法问题。这道题最容易想到的就是首先判断是不是树，这里给的例题有误导作用，可能会让人觉得不全图连通才不是树，实际上不对，只要有回路就不是树了，不全连通也不是。所以最简单的想法是先判断是不是树，如果不是，那就直接输出最大连通集的数量。如果是，那就直接遍历所有节点，对每个节点进行一次遍历，找到最深的那些节点，把他们收集起来打印，但是我们可以大概计算一下，每次遍历（无论是深度优先还是广度优先）的时间复杂度，对于邻接矩阵来说，是n^2，算一次都够受了，何况每个节点都来一次，那就是一万亿次的计算。我估计得10s……即使用邻接表，一次DFS的复杂度也是n+e，也就是两万，那么每个节点都来一次，也是两亿次的计算量。虽然这道题的超时时间给到了史无前例丧心病狂的1500ms，但保守估计仍然需要优化。

这里琢磨一下，假设已经确定是棵树了，我们可以随意挑选一个节点，以这个节点为根，对他的每个子树进行层序遍历，之后我们挑出子树里面最高的两棵，那么这两棵树最底层的叶节点就是我们要寻找的最深根——Deepest Root，就像一根绳子（因为保证了没有循环节点），我们任选一点拉起来，之后左边最长的和右边最长的点，就是我们要找的绳子的两端。灵魂画图如下：

显然，a,b,c,d为所求的最深根。

因此，在判断给出的节点为树时，这道题首先随意选择一个根节点进行一次层序遍历，得到任意一条最深的顶点，比如a,b，在a,b中再任选一个进行层序遍历，就将得到c,d，最后将a,b,c,d合并起来输出就可以了。

耗时较长的解法

#include <cstdlib>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;

void level_travel(const vector<vector<bool>> &graph, const int dim, int start,
                  set<int> &out) {

  queue<int> level;
  vector<int> deepest;
  int this_level = 1;
  level.push(start);
  vector<bool> visited(dim);

  while (true) {
    int next_level = 0;
    deepest = vector<int>(); //又有新的一层了，因此这一层不要了
    for (int i = 0; i != this_level; ++i) {
      int tmp = level.front();
      level.pop();
      visited[tmp] = true;
      deepest.push_back(tmp);
      for (int i = 0; i != dim; ++i) {
        if (graph[tmp][i] and
            !visited[i]) { // visited是为了避免将父节点再纳入队列
          level.push(i);
          ++next_level;
        }
      }
    }
    this_level = next_level;
    if (this_level == 0)
      break;
  }
  for (auto i : deepest) {
    out.insert(i);
  }
}

void caculate(const vector<vector<bool>> &graph, const int dim, set<int> &out) {

  level_travel(graph, dim, 0, out);
  level_travel(graph, dim, *out.begin(), out);
}

int main() {

  int k;
  scanf("%d", &k);
  vector<vector<bool>> graph(k, vector<bool>(k, false));
  vector<bool> linked(k, false);
  int components = 1;

  for (int i = 0; i != k - 1; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (linked[a] && linked[b])     //这里的取巧之所以正确，在后面解说
      ++components;
    linked[a] = true;
    linked[b] = true;
    graph[a - 1][b - 1] = graph[b - 1][a - 1] = true;
  }

  if (components > 1) {
    printf("Error: %d components", components);
    return 0;
  }
  set<int> out;

  caculate(graph, k, out); 

  for (auto i : out) {
    printf("%d\n", i + 1);
  }

  return 0;
}

之所以求最大连通集数量的那段代码：

if (linked[a] && linked[b])
      ++components;

是正确的，是因为根据题目数据，K个顶点，只有K-1条边，这刚好是一个K个节点的树所需要的边的数量，也就是说只要任意一条边连接了已经被连接过的两个点（也就是说这个图有回路），那么这个图就必定不连通了，因为有一条边连接了两个已经被连接过的顶点，而且这样的边每多一条，图的最大连通集数量就多一个。

正统的求最大连通集的方法是：

int caculate_components(const vector<vector<bool>> &maps, const int N) {

  vector<bool> visited(N, false);
  std::queue<int> qnode;
  int ret = 0;

  for (int i = 0; i != N; ++i) {
    if (!visited[i]) {
      ++ret;
      qnode.push(i);
      visited[i] = true;
    } else
      continue;
    while (!qnode.empty()) {
      int tmp = qnode.front();
      qnode.pop();
      for (int j = 0; j != N; ++j) {
        if (maps[j][tmp] && !visited[j]) {
          qnode.push(j);
          visited[j] = true;
        } // end if
      }   // end for
    }     // end while
  }       // end outside for

  return ret;
}

然而我的解法时间复杂度依然感人肺腑，如下图：

节点3明晃晃的556ms，而网上见到的解法最短只要16ms，差距也太大了。考虑到可能是邻接矩阵的锅（而且据说vector\的效率本身就不高，是用时间换空间，不值当啊，考虑换成邻接表的方式组织。

耗时较短的方法

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

//和上面完全一样，只是将图换成了邻接表表示法

using namespace std;

void level_travel(map<int, vector<int>> &graph, const int dim, int start,
                  set<int> &out) {

  queue<int> level;
  int this_level = 1;
  int depth = 0;
  level.push(start);
  vector<int> visited(dim, 0);
  vector<int> all_depth(dim, 0);

  while (true) {
    int next_level = 0;
    ++depth;
    for (int i = 0; i != this_level; ++i) {
      int tmp = level.front();
      level.pop();
      visited[tmp] = 1;
      for (auto it = graph[tmp].begin(); it != graph[tmp].end(); ++it) {
        if (!visited[*it]) {
          ++next_level;
          level.push(*it);
          all_depth[*it] = depth;
        }
      }
    }
    this_level = next_level;
    if (this_level == 0)
      break;
  }

  for (int i = 0; i != dim; ++i) {
    if (all_depth[i] == depth - 1)
      out.insert(i);
  }
}

void caculate(map<int, vector<int>> &graph, const int dim, set<int> &out) {

  level_travel(graph, dim, 0, out);
  level_travel(graph, dim, *out.begin(), out);
}

int main() {

  int k;
  scanf("%d", &k);
  // vector<vector<bool>> graph(k, vector<bool>(k, false));
  map<int, vector<int>> graph;
  vector<int> linked(k, 0);
  int components = 1;
  if (k == 1) {
    printf("1\n");
    return 0;
  }

  for (int i = 0; i != k - 1; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (linked[a - 1] && linked[b - 1])
      ++components;
    linked[a - 1] = 1;
    linked[b - 1] = 1;
    graph[a - 1].push_back(b - 1);
    graph[b - 1].push_back(a - 1);
  }

  if (components > 1) {
    printf("Error: %d components\n", components);
    return 0;
  }
  set<int> out;

  caculate(graph, k, out);

  for (auto i : out) {
    printf("%d\n", i + 1);
  }

  return 0;
}

运行时间嘛……

可见vector<vector<bool>>有问题，邻接矩阵表示稀疏图在遍历时也不行。

求图是否有回路的正统解法

这道题中判断图是否有回路的做法比较清奇，但这纯粹是因为这道题的数据“太特殊”了。如果给定一个图，要判断这个图是否存在回路的话，我琢磨有这么几种做法：

• 从任一节点出发，遍历整张图，同时收集所有已经遍历过的节点，如果任何一个节点的子节点，所能连通的节点中，出现了已经访问过的节点，而且这个访问过节点并不是他的父节点，那就说明这张图里存在回路。我们假设用邻接表表示一张图。

  bool cyclic(map<int, vector<int>> &graph, int dim) {
  
  vector<int> visited(dim, 0);
  vector<int> father(dim, -1); //记录每个节点的父节点
  queue<int> nodes;
  
  for (int i = 0; i != dim; ++i) {    //每个连通集过一遍
    if (visited[i])
      continue;
    else
      nodes.push(i);
    while (!nodes.empty()) {
      int tmp = nodes.front();
      nodes.pop();
      visited[tmp] = 1;
      for (auto it = graph[tmp].begin(); it != graph[tmp].end(); ++it) {
        if (visited[*it] and *it != father[tmp])
          return true;
        if (!visited[*it]) {
          nodes.push(*it);
          father[*it] = tmp;
        }
      }
    }
  }
  
  return false;
  }
  

• 对每一个连通集来说，如果有顶点为K，边大于K-1，则必然形成回路。

  bool cyclic(map<int, vector<int>> &graph, int dim) {
  
  vector<int> visited(dim, 0);
  queue<int> nodes;
  
  for (int i = 0; i != dim; ++i) {
    if (visited[i])
      continue;
    else
      nodes.push(i);
    int nodes_num = 0;
    int edge_num = 0;
    while (!nodes.empty()) {
      int tmp = nodes.front();
      nodes.pop();
      visited[tmp] = 1;
      ++nodes_num;
      for (auto it = graph[tmp].begin(); it != graph[tmp].end(); ++it) {
        if (!visited[*it]) {
          nodes.push(*it);
          visited[*it] = 1;
        }
        ++edge_num;   //每个边算了两次
      }
    }
    if (nodes_num != 0 && edge_num / 2 >= nodes_num)
      return true;
  }
  
  return false;
  }
  

1022 Digital Library

//所以这道题考核的是如何搞定索引吗？
//直接建立map，简直是送分题……最后一个大节点跑了106ms，相比1000ms的上限也没问题。
//把vector换成set以为能提高效率，结果反而效率变低了，大节点跑了139ms。
//可能是因为插入多而查找少的原因。如果插入少输出多可能set更有效率

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

using namespace std;
const int TITLE = 0;
const int AUTHOR = 1;
const int KEY_WORD = 2;
const int PUBLISHER = 3;
const int YEAR = 4;

int main() {

  ios::sync_with_stdio(false);

  int book_num;
  cin >> book_num;
  string blank;
  getline(cin,blank);   //这一行是为了跳过换行符，也可以用cin.get()完成同样功能
  map<string, vector<string>>
      book_storage[5]; // 0书名，1作者名，2关键字，3出版社，4year
  for (int i = 0; i != book_num; ++i) {
    string ID, title, author, key_words, publisher, year;
    istringstream key_words_stream;
    getline(cin, ID);
    getline(cin, title);
    book_storage[TITLE][title].push_back(ID);
    getline(cin, author);
    book_storage[AUTHOR][author].push_back(ID);
    getline(cin, key_words);
    key_words_stream.str(key_words);
    while (key_words_stream) {
      string key;
      key_words_stream >> key;
      book_storage[KEY_WORD][key].push_back(ID);
    }
    getline(cin, publisher);
    book_storage[PUBLISHER][publisher].push_back(ID);
    getline(cin, year);
    book_storage[YEAR][year].push_back(ID);
  }

  int query_num;
  cin >> query_num;
  getline(cin,blank);   //这一行是为了跳过换行符，也可以用cin.get()完成同样功能
  for (int i = 0; i != query_num; ++i) {
    string query_string;
    getline(cin, query_string);
    cout << query_string << endl;
    int zhonglei = query_string[0] - '0' - 1;
    string query = string(query_string.begin() + 3,query_string.end());
    if (book_storage[zhonglei][query].empty()){
      cout << "Not Found" << endl;
      continue;
    }else{
      sort(book_storage[zhonglei][query].begin(),book_storage[zhonglei][query].end());
      for(auto s:book_storage[zhonglei][query]){
        cout << s << endl;
      }
    }
  }

  return 0;

}

1023 Have Fun with Numbers

砍瓜切菜的python解法

origin_str = input()
origin_int = int(origin_str)

double_int = origin_int * 2
double_str = str(double_int)

ordered_origin = sorted(origin_str)
ordered_double = sorted(double_str)

if ordered_double == ordered_origin:
  print("Yes")
else:
  print("No")

print(double_str)

C++解法的核心部分

//主要就是做乘法这一块有点难度
int jinwei = 0;
int num = 0;
for (auto it = input.rbegin(); it != input.rend(); ++it) {
    char c = *it;
    ++appear_times;
    if ((num = 2 * (c - '0') + jinwei) >= 10) {
        jinwei = 1;
        num -= 10;
    } else jinwei = 0;
    output.insert(output.begin(), num);
}
if (jinwei != 0)
    output.insert(output.begin(),jinwei);

1024 Palindromic Number

Python解法

def Palindromic(a):
  reversea = "".join(reversed(a))
  if a == reversea:
    return True;
  else:
    return False;

def main():
  N,K = input().split()
  K = int(K)
  step = 0

  while Palindromic(N) != True:
    N = str(int(N) + int("".join(reversed(N))))
    step += 1
    if step >= K:
      break

  print(N)
  print(step)

if __name__=="__main__":
  main()

C++解法核心部分

//其实考的主要是大数溢出
string add(const string &output) {

    string ret;
    int jinwei = 0;
    int num = 0;
    auto itr = output.rbegin();
    auto it = output.begin();
    for (; itr != output.rend(); ++itr, ++it) {
        if ((num = (*itr - '0' + *it - '0') + jinwei) >= 10) {
            jinwei = 1;
            num -= 10;
        } else jinwei = 0;
        ret.insert(ret.begin(), num + '0');
    }
    if (jinwei != 0)
        ret.insert(ret.begin(), jinwei + '0');

    return ret;

}

1025 PAT Ranking

//考虑用一个结构体保存考生信息，之后重载该结构的运算符

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct testee {
  string id;
  int score;
  int all_rank;
  int region;
  int region_rank;
  testee() = default;
  bool operator>(const testee &a) const {
    if (score > a.score)
      return true;
    else if (score == a.score and id < a.id)
      return true;
    else
      return false;
  }
};

int main() {

  ios::sync_with_stdio(false);
  int region_num, testee_num_per_region, all_testee_num = 0;
  cin >> region_num;
  vector<testee> all_testee;

  for (int i = 0; i != region_num; ++i) {
    cin >> testee_num_per_region;
    if (testee_num_per_region == 0)
      continue;
    all_testee_num += testee_num_per_region;
    vector<testee> testee_per_region(testee_num_per_region);
    for (int j = 0; j != testee_num_per_region; ++j) {
      cin >> testee_per_region[j].id >> testee_per_region[j].score;
      testee_per_region[j].region = i + 1;
    }
    sort(testee_per_region.begin(), testee_per_region.end(), greater<testee>());
    testee_per_region[0].region_rank = 1;
    for (int j = 1; j != testee_num_per_region; ++j) {
      if (testee_per_region[j].score == testee_per_region[j - 1].score) {
        testee_per_region[j].region_rank = testee_per_region[j - 1].region_rank;
      } else {
        testee_per_region[j].region_rank = j + 1;
      }
    }
    all_testee.insert(all_testee.end(), testee_per_region.begin(),
                      testee_per_region.end());
  }

  sort(all_testee.begin(), all_testee.end(), greater<testee>());
  cout << all_testee_num << endl;
  if (all_testee_num == 0) {
    return 0;
  }
  int last_rank = 1;
  int last_score = all_testee[0].score;
  for (int i = 0; i != all_testee_num; ++i) {
    cout << all_testee[i].id << " ";
    if (all_testee[i].score != last_score){
      last_rank = i + 1;
      last_score = all_testee[i].score;
    }
    cout << last_rank << " " << all_testee[i].region << " " << all_testee[i].region_rank << endl;
  }

  return 0;
}

1026 Table Tennis

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

struct Player {
  int hh;
  int mm;
  int ss;
  int arrive_time; //以秒计数的时间
  int require_time;
  int service_time;
  int wait_time;
  Player() = default;
  bool operator>(const Player &a) const {
    if (hh > a.hh)
      return true;
    else if (hh == a.hh and mm > a.mm)
      return true;
    else if (hh == a.hh and mm == a.mm and ss > a.ss)
      return true;
    else
      return false;
  }
};

struct Table {
  int is_vip = 0;
  int served = false;
  int serve_endtime = 0;
  bool occupied = 0;
  Table() = default;
};

template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;

int main() {

  ios::sync_with_stdio(false);
  int player_num;
  cin >> player_num;
  min_heap<Player> normal_players;
  min_heap<Player> vip_players;
  for (int i = 0; i != player_num; ++i) {
    string time;
    int require_time;
    int vip;
    cin >> time >> require_time >> vip;
    if (require_time > 120)
      //题目说了不得超过120分钟，我以为是给的数据不会超，原来是超的要撵走，这个是节点3的坑
      require_time = 120;
    int hh = stoi(string(time.begin(), time.begin() + 2));
    int mm = stoi(string(time.begin() + 3, time.begin() + 5));
    int ss = stoi(string(time.begin() + 6, time.end()));
    int arrive_time = hh * 3600 + mm * 60 + ss;
    if (vip) {
      vip_players.push({hh, mm, ss, arrive_time, require_time});
    } else {
      normal_players.push({hh, mm, ss, arrive_time, require_time});
    }
  }
  int table_num, vip_table_num;
  cin >> table_num >> vip_table_num;
  vector<Table> tables(table_num);
  for (int i = 0; i != vip_table_num; ++i) {
    int tmp_num;
    cin >> tmp_num;
    tables[tmp_num - 1].is_vip = 1;
  }

  int now = 8 * 3600;
  vector<Player> served;
  while (now < 21 * 3600) {
    if (vip_players.empty() and normal_players.empty())
      break;

    for (int i = 0; i != table_num; ++i) {
      if (!tables[i].occupied and tables[i].is_vip and !vip_players.empty() and
          vip_players.top().arrive_time <= now) { //如果此时有VIP桌且有VIP在等
        tables[i].occupied = true;
        Player pler = vip_players.top();
        pler.service_time = now;
        served.push_back(pler);
        vip_players.pop();
        ++tables[i].served;
        tables[i].serve_endtime = now + pler.require_time * 60;
      }
    }

    for (int i = 0; i != table_num; ++i) {
      //有VIP桌且有VIP在等处理完了，现在处理其他情况，即按先来后到
      if (!tables[i].occupied) {
        if (vip_players.empty() and !normal_players.empty() and
            normal_players.top().arrive_time <= now) {
          tables[i].occupied = true;
          Player pler = normal_players.top();
          pler.service_time = now;
          served.push_back(pler);
          normal_players.pop();
          ++tables[i].served;
          tables[i].serve_endtime = now + pler.require_time * 60;
        } else if (!vip_players.empty() and normal_players.empty() and
                   vip_players.top().arrive_time <= now) {
          tables[i].occupied = true;
          Player pler = vip_players.top();
          pler.service_time = now;
          served.push_back(pler);
          vip_players.pop();
          ++tables[i].served;
          tables[i].serve_endtime = now + pler.require_time * 60;
        } else if (!vip_players.empty() and !normal_players.empty() and
                   vip_players.top().arrive_time <
                       normal_players.top().arrive_time and
                   vip_players.top().arrive_time <= now) {
          tables[i].occupied = true;
          Player pler = vip_players.top();
          pler.service_time = now;
          served.push_back(pler);
          vip_players.pop();
          ++tables[i].served;
          tables[i].serve_endtime = now + pler.require_time * 60;
        } else if (!vip_players.empty() and !normal_players.empty() and
                   normal_players.top().arrive_time <
                       vip_players.top().arrive_time and
                   normal_players.top().arrive_time <= now) {
          tables[i].occupied = true;
          Player pler = normal_players.top();
          pler.service_time = now;
          served.push_back(pler);
          normal_players.pop();
          ++tables[i].served;
          tables[i].serve_endtime = now + pler.require_time * 60;
        }
      }
    }
    bool changed = false;
    for (int i = 0; i != table_num; ++i) {
      if (tables[i].occupied) {
        if (tables[i].serve_endtime <= now) {
          tables[i].occupied = false;
          changed = true;
        }
      }
    }
    if (!changed)
      ++now;
  }
  sort(served.begin(), served.end(),[](const Player &a ,const Player &b){return a.service_time < b.service_time;});
  for (auto &p : served) {
    cout << (p.hh >= 10 ? to_string(p.hh) : '0' + to_string(p.hh)) << ":"
         << (p.mm >= 10 ? to_string(p.mm) : '0' + to_string(p.mm)) << ":"
         << (p.ss >= 10 ? to_string(p.ss) : '0' + to_string(p.ss)) << " ";
    int hh = p.service_time / 3600;
    int mm = (p.service_time % 3600) / 60;
    int ss = (p.service_time % 60);
    cout << (hh >= 10 ? to_string(hh) : '0' + to_string(hh)) << ":"
         << (mm >= 10 ? to_string(mm) : '0' + to_string(mm)) << ":"
         << (ss >= 10 ? to_string(ss) : '0' + to_string(ss)) << " ";
    if ((p.service_time - p.arrive_time) % 60 >= 30) {
      p.wait_time = (p.service_time - p.arrive_time) / 60 + 1;
    } else
      p.wait_time = (p.service_time - p.arrive_time) / 60;
    cout << p.wait_time << endl;
  }
  for (int i = 0 ; i != tables.size() - 1 ; ++i){
    cout << tables[i].served << " ";
  }
  cout << tables.back().served << endl;

  return 0;
}

1027 Colors in Mars

#include<iostream>
#include<string>

using namespace std;

string decto13(int num){
    string ret;
    while(num){
        int yu = num % 13;
        ret.insert(ret.begin(), (yu < 10 ? yu +'0' : yu - 10 + 'A'));
        num/=13;
    }
    while (ret.size() < 2)
        ret.insert(ret.begin(),'0');
    return ret;
}
int main(){

    int red,green,blue;
    cin >> red >> green >> blue;
    cout << "#" << decto13(red) << decto13(green) << decto13(blue);
    return 0;

}

1028 List Sorting

//考虑用一个struct来保存数据，重载运算符或者给sort函数提供comp即可
//用string+cout会超时，改回cstring就OK了

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

struct Record {
  int ID;
  char name[10];
  int grade;
  Record() = default;
};

bool compare_by_ID(const Record &a, const Record &b) { return a.ID < b.ID; }

bool compare_by_name(const Record &a, const Record &b) {
  return strcmp(a.name, b.name) < 0 ||
         (strcmp(a.name, b.name) == 0 && a.ID < b.ID);
}

bool compare_by_grade(const Record &a, const Record &b) {
  return a.grade < b.grade || (a.grade == b.grade && a.ID < b.ID);
}

int main() {

  int record_num, sort_column;
  scanf("%d %d", &record_num, &sort_column);
  vector<Record> records(record_num);
  for (int i = 0; i != record_num; ++i) {
    char tmpname[10];
    scanf("%d %s %d", &records[i].ID, records[i].name, &records[i].grade);
  }
  switch (sort_column) {
  case 1:
    sort(records.begin(), records.end(), compare_by_ID);
    break;
  case 2:
    sort(records.begin(), records.end(), compare_by_name);
    break;
  case 3:
    sort(records.begin(), records.end(), compare_by_grade);
    break;
  }

  for (auto r : records) {
    printf("%06d %s %d\n", r.ID, r.name, r.grade);
  }
  return 0;
}

1029 Median

//时间限制先不说，这道题给了一个特别的内存限制，1.5M，假设所有的数字都是long int
//即8字节，2 x 10^5 个8字节，就已经是1.6M了。也就是只存一个数组都会内存超限。
//因此这道题只能智取啊。想来想去想不到智取的办法，因为一个数列都不允许读完的话
//直接就没办法了啊。你不可能略过第一个数组直接去读第二个数组啊。
//后来看了网上的AC代码，说其实只要所有的LONG INT 数值直接处理成INT MAX就行了
//原因是如果都是long int，这道题就没法做了，所以所有的long int都只是干扰项
//不会真的是中位数。这思路真是脑筋急转弯~我考虑的是没法做，他考虑的是因为没法做
//所以题目不会真的让你做……真是无法认同这种题的意义啊。

#include <climits>
#include <cstdio>
#include <queue>

using namespace std;

int main() {
  queue<int> a, b;
  long long tnum;
  int n, m, num, cnt = 0;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lld", &tnum);
    num = min((long long)INT_MAX, tnum);
    a.push(num);
  }
  a.push(INT_MAX);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%lld", &tnum);
    int num = min((long long)INT_MAX, tnum);
    b.push(num);
    if (cnt == (n + m - 1) / 2) {
      printf("%d", min(a.front(), b.front()));
      return 0;
    }
    if (a.front() < b.front())
      a.pop();
    else
      b.pop();
    cnt++;
  }
  b.push(INT_MAX);
  for (; cnt < (n + m - 1) / 2; cnt++) {
    if (a.front() < b.front())
      a.pop();
    else
      b.pop();
  }
  printf("%d", min(a.front(), b.front()));
  return 0;
}

1030 Travel Plan

//暴力dfs解法，什么djstra，不认识。抄袭1018即可

#include <climits>
#include <iostream>
#include <vector>

using namespace std;

void DFS(const vector<vector<int>> &maps, const vector<vector<int>> &cost,
         const int city_num, const int start_city, const int dest_city,
         int &minlen, int &mincost, int thislen, int thiscost,
         vector<int> tmppath, vector<int> &path, vector<int> visited);

int main() {

  ios::sync_with_stdio(false);
  int city_num, road_num, start_city, dest_city;
  cin >> city_num >> road_num >> start_city >> dest_city;

  vector<vector<int>> maps(city_num, vector<int>(city_num, 0));
  vector<vector<int>> cost(city_num, vector<int>(city_num, 0));

  for (int i = 0; i != road_num; ++i) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    maps[a][b] = maps[b][a] = c;
    cost[a][b] = cost[b][a] = d;
  }

  int minlen = INT_MAX, mincost = INT_MAX;
  int thislen = 0, thiscost = 0;
  vector<int> tmppath, path;
  vector<int> visited(city_num, 0);

  DFS(maps, cost, city_num, start_city, dest_city, minlen, mincost, thislen,
      thiscost, tmppath, path, visited);

  for (auto i : path)
    cout << i << " ";
  cout << minlen << " " << mincost << endl;
}

void DFS(const vector<vector<int>> &maps, const vector<vector<int>> &cost,
         const int city_num, const int start_city, const int dest_city,
         int &minlen, int &mincost, int thislen, int thiscost,
         vector<int> tmppath, vector<int> &path, vector<int> visited) {

  tmppath.push_back(start_city);
  if (start_city == dest_city) { //到了一次终点
    if (thislen < minlen) {
      minlen = thislen;
      mincost = thiscost;
      path = tmppath;
    } else if (thislen == minlen && thiscost < mincost) {
      mincost = thiscost;
      path = tmppath;
    }
    return;
  }

  visited[start_city] = 1;
  for (int i = 0; i != city_num; ++i) {
    if (!visited[i] and maps[start_city][i]) {
      DFS(maps, cost, city_num, i, dest_city, minlen, mincost,
          thislen + maps[start_city][i], thiscost + cost[start_city][i],
          tmppath, path, visited);
    }
  }
}

1031 Hello World for U

//这道题的难点在于他不是一行一行输入，而是翻来翻去，正常解法的话实在麻烦
//考虑直接先初始化整个一大块的空间出来，然后再在这个空间里改空格

#include<iostream>
#include<vector>

using namespace std;

int main(){

  string input;
  cin >> input;
  int len = input.size();
  int n1 = (len + 2) / 3;
  int n2 = len - n1 * 2 + 2;
  vector<vector<char>> output(n1,vector<char>(n2,' '));
  for (int i = 0 ; i != n1 ; ++i){
    output[i][0] = input[i];
  }
  for(int i = 1 ; i != n2 - 1 ; ++i){
    output[n1 - 1][i] = input[n1 + i - 1];
  }
  for(int i = n1 - 1 ; i >= 0 ; --i){
    output[i][n2-1] = input[n1 + n2 - 2 + n1 - ( i + 1 )];
  }
  for(auto &v:output){
    for(int i = 0 ; i != n2 - 1 ; ++i){
      cout << v[i] ;
    }
    cout << v.back() << endl;
  }
  return 0;

}

1032 Sharing

//暴力大数组，这道题的时间限制只有100ms，可见如果要从头到尾扫描的话，大节点肯定超时了。
//因此转换思路，从后到前扫描。方法如下：
//另外一种模拟内存的方式是用map

#include <cstdio>
#include <set>
#include <vector>

using namespace std;

struct node {
  set<int> prev_node;
  char data;
  int next_node;
  node() = default;
};

int main() {

  vector<node> list(100000);
  int head1, head2, N;
  scanf("%d %d %d", &head1, &head2, &N);

  for (int i = 0; i != N; ++i) {
    int addr, next;
    char data;
    scanf("%d %c %d", &addr, &data, &next);
    list[addr].data = data;
    list[addr].next_node = next;
  }

  //不知道这道题有没有废节点的情况，还要捋一遍啊。

  int lastaddr = -2;
  set<int> tail;
  for (int i = head1; i != -1;) {
    list[i].prev_node.insert(lastaddr);
    lastaddr = i;
    i = list[i].next_node;
  }
  tail.insert(lastaddr);
  lastaddr = -3;
  for (int i = head2; i != -1;) {
    list[i].prev_node.insert(lastaddr);
    lastaddr = i;
    i = list[i].next_node;
  }
  tail.insert(lastaddr);
  if (tail.size() != 1) { //说明两个链表不在同一个位置结束，那就没有共同后缀了。
    printf("-1\n");
    return 0;
  }
  for (int i = *tail.begin(); i != -2;) {
    if (list[i].prev_node.size() == 2) {
      printf("%05d\n", i);
      //cout << std::setw(5) << std::setfill('0') << answer << endl;
      //cout这么输出
      return 0;
    }
    i = *list[i].prev_node.begin();
  }

}

1033 To Fill or Not to Fill

//如标题所示，这是一道：加油还是不加油的问题。所以问题就是，没到一个站，加油还是不加油？如果加，加多少。
//那么到底加不加呢？问题在于，在这个站加了油之后可及的范围内，有没有更便宜的加油站。
//如果有，加到这个加油站就可以了，如果没有，就要加满油了，但这样加满油有个问题，就是在路上怎么补充
//就是在他加满油能到达的最远距离里，找一个最便宜的，然后进去加油，此时问题回到最初的问题。

#include <algorithm>
#include <cstdio>
#include <limits>
#include <vector>

using namespace std;

#define FLOAT_MAX numeric_limits<float>::max()

struct Station {
  float price;
  float distance;
  Station() = default;
  Station(const float a, const float b) : price(a), distance(b){};
};

int main() {

  float tank, distance, dis_per_unit;
  int num;
  scanf("%f %f %f %d", &tank, &distance, &dis_per_unit, &num);
  vector<Station> stations(num);
  for (int i = 0; i != num; ++i) {
    scanf("%f %f", &stations[i].price, &stations[i].distance);
  }

  sort(stations.begin(), stations.end(),
       [](const Station &a, const Station &b) {
         return a.distance < b.distance;
       });
  if (stations[0].distance > 0) { //杭州没有加油站，Emmm，出不了门了
    printf("The maximum travel distance = 0.00\n");
    return 0;
  }

  float dis_full_tank = tank * dis_per_unit;
  float now_dis = 0;
  int now_sta = 0;
  float now_gas = 0;
  float price = 0;
  bool reached = false;
  for (; now_dis < distance;) {
    int min_sta = -1;
    float min_price = FLOAT_MAX;
    for (int next_sta = now_sta + 1; next_sta < num; ++next_sta) {
      if (stations[next_sta].distance > distance ||
          stations[next_sta].distance > now_dis + dis_full_tank) {
        //下一个站终点都远，或者说下一个站超出了能到达的范围
        break;
      } else if (stations[next_sta].price < stations[now_sta].price){
        //找到了一个比他更便宜的点
        min_sta = next_sta;
        min_price = stations[next_sta].price;
        break;
      }else {
        //否则找可达的加油站中最便宜的，虽然他没有汽车所在的站点便宜
        if (stations[next_sta].price < min_price) {
          min_sta = next_sta;
          min_price = stations[next_sta].price;
        }
      }
    }
    if (min_sta == -1) {
      if (now_dis + dis_full_tank > distance) {
        price += stations[now_sta].price * (distance - now_dis) / dis_per_unit;
        reached = true;
      } else {
        now_dis += dis_full_tank;
        reached = false;
      }
      break;
    } else { //能到这个点，但是分情况
      if (stations[min_sta].price > stations[now_sta].price) {
        //找到的节点中最便宜的比当前加油站要贵,此时继续分情况
        if (now_dis + dis_full_tank > distance) {
          //这个节点加满油直接跑到
          price +=
              stations[now_sta].price * (distance - now_dis) / dis_per_unit;
          reached = true;
          break;
        }
        price += stations[now_sta].price * (tank - now_gas);
        now_gas = tank - (stations[min_sta].distance - now_dis) / dis_per_unit;
        now_dis = stations[min_sta].distance;
        now_sta = min_sta;
      } else { //找到的节点中最便宜的比当前加油站要便宜，加到这个节点就够了
        price += stations[now_sta].price *
                 ((stations[min_sta].distance - stations[now_sta].distance) /
                      dis_per_unit -
                  now_gas);
        now_gas = 0;
        now_dis = stations[min_sta].distance;
        now_sta = min_sta;
      }
    }
  }

  if (reached){
    printf("%.2f\n",price);
  }else{
    printf("The maximum travel distance = %.2f\n",now_dis);
  }

  return 0;

}

1034 Head of a Gang

//这道题有点意思，理解题意是：一个团伙就是相互之间有通信来往，而且电话来往总时间超过一定
//时长的一群人，其中通话时间最长的那孙子就是团伙老大。话说这方法不怎么靠谱。
//不过既然题目这么说了，我们也就别纠结实际合理性了。这其实就是一个最大连通集的问题。
//设顶点为某个gang，边长为通话时间。如此问题简化为：求此图中每一个最大连通集的节点数量
//以及每个最大连通集中连接的边权重最大的那个顶点。连通集节点数量小于等于二将被抛弃。
//所以问题的关键成了图的表示，如果要用传统的int表示的话，实在是来回转换很麻烦，不如直接用
//map来表示图。map<string,map<string,int>>反正key虽然是string但是长度很短
//效率应该还不错，再长一点是不是要做个hash？哈哈~

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

using namespace std;

int main() {

  ios::sync_with_stdio(false);
  map<string, map<string, int>> Graph;
  int call_num;
  double threshold;
  cin >> call_num >> threshold;
  for (int i = 0; i != call_num; ++i) {
    string name1, name2;
    int time;
    cin >> name1 >> name2 >> time;
    Graph[name1][name2] += time;
    Graph[name2][name1] += time;
  }

  map<string, int> results;
  map<string, int> visited;
  map<string, int> weights;
  for (auto it = Graph.begin(); it != Graph.end(); ++it) {
    queue<string> child_graph;
    if (visited[it->first]) {
      //这个节点已经访问过了，是某一个连通集里面的值
      continue;
    } else {
      visited[it->first] = 1;
      child_graph.push(it->first);
    }
    string max_weight_name;
    int max_weight = -1;
    int gangnum = 0;
    int total_weight = 0;
    while (!child_graph.empty()) {
      string tmp = child_graph.front();
      child_graph.pop();
      ++gangnum;
      for (auto it2 = Graph[tmp].begin(); it2 != Graph[tmp].end(); ++it2) {
        weights[it2->first] += it2->second;
        if (weights[it2->first] > max_weight) {
          max_weight = weights[it2->first];
          max_weight_name = it2->first;
        }
        weights[tmp] += it2->second;
        if (weights[tmp] > max_weight) {
          max_weight = weights[tmp];
          max_weight_name = tmp;
        }
        total_weight += it2->second;
        if (!visited[it2->first]) {
          visited[it2->first] = 1;
          child_graph.push(it2->first);
        }
      }
    } // end while

    if (gangnum > 2 && total_weight / 2.0 > threshold){
      results[max_weight_name] = gangnum;
    }
  } // endfor
  cout << results.size() << endl;
  for(auto it = results.begin() ; it != results.end() ; ++it){
    cout << it->first << " " << it->second << endl;
  }

  return 0;

}

1035 Password

//这不顺手就写了嘛，怪不得只给20分

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

using namespace std;

map<char, char> c_replace = {{'1', '@'}, {'0', '%'}, {'l', 'L'}, {'O', 'o'}};

vector<char> obfs = {'1', '0', 'l', 'O'};

int main() {

  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<pair<string, string>> results;
  for (int i = 0; i != N; ++i) {
    string name, passwd;
    cin >> name >> passwd;
    bool changed = false;
    for (auto it = obfs.begin(); it != obfs.end(); ++it) {
      auto pos = string::npos;
      while ((pos = passwd.find(*it)) != string::npos) {
        changed = true;
        passwd[pos] = c_replace[*it];
      }
    }
    if (changed) {
      results.push_back({name, passwd});
    }
  }

  if (results.empty()) {
    cout << "There " << (N > 1 ? "are " : "is ")  << N << (N > 1 ? " accounts " : " account ")
         << "and no account is modified" << endl;
  }else{
    cout << results.size() << endl;
    for(auto it = results.begin() ; it != results.end() ; ++it)
      cout << it->first << " " << it->second << endl;
  }
  return 0;
}

1036 Boys vs Girls

//莫名其妙的题目，这连10分都不值吧，比上面一个题还简单

#include <iostream>
#include <string>

using namespace std;

int main() {

  int max_female_grade = -1, min_male_grade = 101;
  string female_name, female_ID, male_name, male_ID;
  int N;
  cin >> N;
  for (int i = 0; i != N; ++i) {
    string name, gender, ID;
    int grade;
    cin >> name >> gender >> ID >> grade;
    if (gender == "M") {
      if (grade < min_male_grade) {
        min_male_grade = grade;
        male_name = name;
        male_ID = ID;
      }
    } else {
      if (grade > max_female_grade) {
        max_female_grade = grade;
        female_name = name;
        female_ID = ID;
      }
    }
  }

  cout << (max_female_grade == -1 ? "Absent" : female_name + " " + female_ID)
       << endl;
  cout << (min_male_grade == 101 ? "Absent" : male_name + " " + male_ID)
       << endl;
  cout << (max_female_grade == -1 or min_male_grade == 101
               ? "NA"
               : to_string(max_female_grade - min_male_grade))
       << endl;
  return 0;
}

1037 Magic Coupon

#include<iostream>
#include<queue>
#include<functional>

using namespace std;

int main() {

    int NC, NP;
    ios::sync_with_stdio(false);    //不超时且不用cstdio不二法门

    std::priority_queue<int> positivec, positivep;
    std::priority_queue<int, vector<int>, std::greater<int>> negativec, negativep;

    cin >> NC;
    for (int i = 0; i != NC; ++i) {
        int num;
        cin >> num;
        if (num > 0)
            positivec.push(num);
        if (num < 0)
            negativec.push(num);
    }

    cin >> NP;
    for (int i = 0; i != NP; ++i) {
        int num;
        cin >> num;
        if (num > 0)
            positivep.push(num);
        if (num < 0)
            negativep.push(num);
    }

    int out = 0;
    while (true) {
        if (!positivec.empty() && !positivep.empty()) {
            out += positivec.top() * positivep.top();
            positivec.pop();
            positivep.pop();
        } else if (!negativec.empty() && !negativep.empty()) {
            out += negativec.top() * negativep.top();
            negativec.pop();
            negativep.pop();
        } else break;
    }

    cout << out << endl;

}

1038 Recover the Smallest Number

//难点在想怎么排序，而且主要难在怎么考虑那些相同前缀的数字怎么处理
//节点2的坑在于全0。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool cmp(const string &a, const string &b) {

  int sizea = a.size(), sizeb = b.size();
  int size_min = sizea > sizeb ? sizeb : sizea;
  for (int i = 0; i != size_min; ++i) {
    if (a[i] < b[i])
      return true;
    if (a[i] > b[i])
      return false;
  }
  //说明前缀完全一样。前缀一样的情况下，其实看长一点的字符串的下一个字符
  //如果比他最开始的字符还大，那就说明这个字符应该往后排
  if (a.size() == b.size()) {
    return false;
  } else if (a.size() == size_min) {
    return b[size_min] >= b[0];
  } else {
    return a[size_min] <= a[0];
  }
}

int main() {

  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<string> nums(N);
  for (int i = 0; i != N; ++i) {
    cin >> nums[i];
  }
  sort(nums.begin(), nums.end(), cmp);
  string output;
  for (auto it = nums.begin(); it != nums.end(); ++it) {
    output += *it;
  }
  if (output.find_first_not_of('0') == string::npos)    //处理给了一堆0的情况
    output = "0";
  else
    output = output.substr(output.find_first_not_of('0'));

  cout << output << endl;
  return 0;
}

1039 Course List for Student

超时解法

//输出的麻烦就占了这道题的一半麻烦
//最后一个节点竟然超时了！我擦泪！而且感觉已经没法优化了啊。

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

using namespace std;

inline int name_to_int(const string &A) {
  return (A[0] - 'A') * 26 * 26 * 10 + (A[1] - 'A') * 26 * 10 +
         (A[2] - 'A') * 10 + A[3] - '0';
}

int main() {

  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, courses_num;
  cin >> N >> courses_num;
  map<int, set<int>> student;

  for (int i = 0; i != courses_num; ++i) {
    int course_index, M;
    cin >> course_index >> M;
    for (int j = 0; j != M; ++j) {
      string name;
      cin >> name;
      student[name_to_int(name)].insert(course_index);
    }
  }

  for (int i = 0; i != N; ++i) {
    string name;
    cin >> name;
    cout << name << " ";
    int idx = name_to_int(name);
    cout << student[idx].size(); 
    for (auto it2 = student[idx].begin(); it2 != student[idx].end(); ++it2)
      cout << " " << *it2;
    cout << endl;
  }
  return 0;
}

不超时解法

//可能map的时间复杂度还是有点高，直接弄成一个大数组，不知道还有没有更快的解法

#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

int Name2Num(char *A) { //名字转化为数字
  return (A[0] - 'A') * 26 * 26 * 10 + (A[1] - 'A') * 26 * 10 +
         (A[2] - 'A') * 10 + A[3] - '0';
}

struct Student {
  vector<int> Courses;
} buf[180000];
int main() {

  int N, K;
  scanf("%d %d",&N,&K);
  int idx = 0; // init
  for (int i = 0; i < K; i++) {
    int cou_n, m;
    scanf("%d %d",&cou_n,&m);

    for (int j = 0; j < m; j++) {
      char name[5];
      scanf("%s", name);
      buf[Name2Num(name)].Courses.push_back(cou_n); //把课程放入学生的空间中
    }
  }
  for (int i = 0; i < N; i++) {
    char name[5];
    scanf("%s", name);
    int idx = Name2Num(name);
    sort(buf[idx].Courses.begin(), buf[idx].Courses.end()); //排序输出
    printf("%s %d",name, buf[idx].Courses.size());
    for (int j = 0; j < buf[idx].Courses.size(); j++) {
      printf(" %d",buf[idx].Courses[j]);
    }
    printf("\n");
  }
  return 0;
}

1040 Longest Symmetric String

//翻个个儿，然后求最大公共子串吗？最大公共子串怎么求来着？肯定是用动态规划
//但是子状态是啥啊？

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void LCS(const string s1, const string s2, vector<vector<int>> &len,
         int &max_len);

int main() {

  ios::sync_with_stdio(false);
  string s;
  getline(cin, s);

  string sr = string(s.rbegin(), s.rend());

  vector<vector<int>> len(s.size() + 1, vector<int>(s.size() + 1, 0));
  int max_len = 0;
  LCS(s, sr, len, max_len);
  cout << max_len << endl;
}

void LCS(const string s1, const string s2, vector<vector<int>> &len,
         int &max_len) {
  for (int i = 1; i <= s1.size(); ++i) {
    for (int j = 1; j <= s2.size(); ++j) {
      if (s1[i - 1] == s2[j - 1]) {
        len[i][j] = len[i - 1][j - 1] + 1;
        if (len[i][j] > max_len)
          max_len = len[i][j];
      } else {
        len[i][j] = 0;
      }
    }
  }
}

最长公共子串问题

就是这道题无疑了，最开始肯定能想到暴力解法，就是你让我求子串我就求子串啊，然后拿出来对比。三层循环套上，其中最内层循环控制对比的字符串长度。但是这样的时间复杂度接近n^3，也可以说是不可接受吧。

因此进一步考虑，内层循环其实每次对比的时候，都会从头到尾对比一遍子字符串，这样的话就会有很多重复对比，比如说下列子串：

s1 = "abcdefgh"
s2 = "gsasd23adas"

//而我们的暴力循环大概是这样的:
for (int i = 0; i != s1.size(); ++i) {
  for (int j = 0; j != s2.size(); ++j) {
    for (int k = 0; k != min(s1.size() - i, s2.size() - j); ++k) {
      if (substr(s1[i],s1[i] + k) == substr(s2[j],s1[j] + k)){
        LCS = substr(s1[i],s1[i] + k;
      }else{
        break;
      }
    }
  }
}
//显而易见，内层做了很多无用的比较，当k增大时，实际上只需要比较s1[i+k]和s2[j+k]就可以了
//之前的那些都是重复比较，因此考虑只比较最后一个就可以了，用len[i][j]表示从s1[i],s2[j]
//结尾的字符串的最大公共子串长度。如果要输出最长公共子串，用一个i和j保存下标就行