代码练习(2017 计算机学科夏令营上机考试)

Posted on Edited on In Views:
STL（堆）、枚举、最短路（Dijkstra）

题目

判决素数个数

  • 代码
  • 注意输入的两个数，第一个数可能比第二个数大

编码字符串(string)

岛屿周长(matrix)

Safecracker

  • 代码
  • 预处理 + 暴力枚举

怪盗基德的滑翔翼

Full Tank?

  • 最短路问题
  • Bellman-Ford 算法
    • \(O(mncc)\)
    • TLE
  • Dijkstra 算法
    • \(O((m+n+c)\log(m+nc))\)
    • OK

实现堆结构

  • 代码
  • STL 优先队列的应用

Subway

  • 代码
  • 最短路
    • 建图比较麻烦

C Looooops

  • TODO
  • 扩展欧几里得算法
  • 探究如下等式的整数解 \(x\)

\[ (A+Cx)\;\%\;{2^k}=B \]

  • 变形

\[ \begin{aligned} (2^k)y+B=A+Cx\\ Cx+(-2^k)y=B-A \end{aligned} \]

Captain Q's Treasure