A. ASC(签到题)
已知大写字母 A 的 ASCII 码为 65，请问大写字母 L 的 ASCII 码是多少？
时间复杂度: O(1)
// https://www.lanqiao.cn/problems/1446/learning/?page=1&first_category_id=1&sort=students_count&name=ASC
#include <iostream>
using namespace std;
int main() {
int A = 65;
cout << A + ('L' - 'A') << endl;
return 0;
}
B.空间(签到题)
小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？
分析: 我们知道8个bit为一个字节byte, 所以一个32位二进制数需要 4 个字节, 而 256MB 相当于 256 * 1024 * 1024 个 byte, 所以直接利用除法就可以得出答案了:
时间复杂度: O(1)
// https://www.lanqiao.cn/problems/1445/learning/?page=1&first_category_id=1&sort=students_count&name=%E7%A9%BA%E9%97%B4
#include <iostream>
using namespace std;
int main() {
cout << 256 * 1024 * 1024 / 4 << endl;
return 0;
}C.卡片(模拟)
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
小蓝想知道自己能从 1 拼到多少。
例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，
但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？
提示：建议使用计算机编程解决问题。
分析: 我们可以用一个数组存放各卡片的个数， 然后进行模拟统计各卡片的个数, 当有卡片的数量为 0 时当前数字就是最大的了。
时间复杂度: O(n)
// https://www.lanqiao.cn/problems/1443/learning/?page=1&first_category_id=1&sort=students_count&name=%E5%8D%A1%E7%89%87
#include <iostream>
#include <cstring>
using namespace std;
int a[10];
int main() {
for (int i = 0; i <= 9; i++) a[i] = 2021;
for (int num = 1; ; num++) {
int n = num;
while (n) {
if (--a[n % 10] == 0) {
cout << num << endl;
return 0;
}
n /= 10;
}
}
return 0;
}D.相乘 (模拟)
【问题描述】小蓝发现，他将 1 至 1000000007 之间的不同的数与 2021 相乘后再求除以
1000000007 的余数，会得到不同的数。小蓝想知道，能不能在 1 至 1000000007 之间找到一个
数，与 2021 相乘后再除以 1000000007 后的余数为 999999999。如果存在，请在答案中提交这个数；如果不存在，请在答案中提交 0
1000000007 * 2021 可能会溢出, 所以要用到乘法取模的数学性质避免数据溢出:
(a * b) % p = ( (a % p) * (b % p) ) % p
算法复杂度: O(n)
// https://www.lanqiao.cn/problems/1444/learning/?page=1&first_category_id=1&sort=students_count&name=%E7%9B%B8%E4%B9%98
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
ll mod = 1000000007;
for (ll i = 1; i <= 1000000007; i++) {
if (((i % mod) * (2021 % mod)) % mod == 999999999){
// if ((i * 2021) % mod == 999999999) {
cout << i << endl;
return 0;
}
}
cout << 0 << endl;
return 0;
}E.路径(动态规划 || 图论)
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
分析: 求最短路径的算法有很多， 其中最简单的就是 Floyd 暴力法了(也是对我来说最好理解的)， 算法复杂度为 O(n^3) (这是一道填空题不害怕超时...).
我们根据题意进行建树, 这里我用了邻接矩阵的方式， 定义邻接矩阵map, 每个节点的边权就是最短路径, 那么我们的答案就是 map[1][2021]了。
最后提一下Floyd的基本核心, 就是先枚举每一个节点看看是不是"中转站"， 如果是的话则进行松弛操作， 这样我们就保证了最短路径的子路径是最短的, 核心代码如下:
// 枚举中转站
for (int k = 1; k <= n; k++) {
// 枚举起点
for (int i = 1; i <= n; i++) {
// 枚举终点
for (int j = 1; j <= n; j++) {
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
}
}那么完整代码为:
// https://www.lanqiao.cn/problems/1460/learning/?page=1&first_category_id=1&sort=students_count&name=%E8%B7%AF%E5%BE%84
#include <iostream>
#include <algorithm>
using namespace std;
int map[2022][2022];
#define INF 0x3f3f3f3f
#define lcm(a, b) (a * b / __gcd(a, b))
int main() {
int n = 2021;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) map[i][j] = 0;
map[i][j] = INF;
}
}
// Build tree
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= i + 21; j++) {
if (j > n) continue;
map[i][j] = lcm(i, j);
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
}
}
cout << map[1][n] << endl;
return 0;
}当然，单源最短路径建议还是用 Dijkstra:
时间复杂度: O(n^2):
// https://www.lanqiao.cn/problems/1460/learning/?page=1&first_category_id=1&sort=students_count&name=%E8%B7%AF%E5%BE%84
#include <iostream>
#include <algorithm>
using namespace std;
int map[2022][2022];
int vis[2022];
int dis[2022];
#define INF 0x3f3f3f3f
#define lcm(a, b) (a * b / __gcd(a, b))
int main() {
int n = 2021;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) map[i][j] = 0;
map[i][j] = INF;
}
}
// Build tree
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= i + 21; j++) {
if (j > n) continue;
map[i][j] = lcm(i, j);
}
}
for (int i = 1; i <= n; i++) {
dis[i] = map[1][i];
vis[i] = 0;
}
vis[1] = 1;
// 对除去源点以外的 n - 1 个点进行松弛
for (int i = 1; i <= n - 1; i++) {
// find the shortest node from the source.
int min = INF;
int cur = 0;
for (int j = 1; j <= n; j++) {
if (vis[j] == 0 && dis[j] < min) {
min = dis[j];
cur = j;
}
}
vis[cur] = 1;
// 看看通过 cur 可以到达哪些边, 如果可以则进行松弛操作
for (int v = 1; v <= n; v++) {
if (map[cur][v] < INF) {
if (dis[v] > dis[cur] + map[cur][v]) {
dis[v] = dis[cur] + map[cur][v];
}
}
}
}
cout << dis[n] << endl;
return 0;
}下面我们考虑用动态规划, 我们先定义我们的状态:
dp[i] : 从 1 到 i 的最短路径，我们用闫式dp法来分析一下(最近跟y总学的dp小技巧), 首先我们的问题是要在一个包含所有路径的有限集合(集合)中找到一条最短路径(属性), 我们现在来考虑最后一个合法的状态，对于 dp[i] 包含了21个子集(因为题目说两个节点大于 21，则两个结点之间没有边相连), dp[i] 是从 dp[i - 1], dp[i - 2] , ... , dp[i - 21] 转移过来的 (满足不重不漏), 这是变化的部分(因为dp[i]表示的子集最后一个元素一定是 i (也就是本题中路径的终点一定是 i), 而前面部分不是固定的)。假设从 k 转移过来, 那么不变的部分就是 lcm(k, i)了.
当dp[i]为空时代表我们还没有访问过这条路径, 那么此时 dp[i] = lcm(k, i)。
当dp[i]不为空时 dp[i] = min(dp[k], dp[k] + lcm(k, i))
时间复杂度: O(n ^ 2)
// https://www.lanqiao.cn/problems/1460/learning/?page=1&first_category_id=1&sort=students_count&name=%E8%B7%AF%E5%BE%84
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <cstring>
#define lcm(a, b) (a * b / __gcd(a, b))
using namespace std;
typedef long long ll;
ll dp[2022] = {0L};
int main() {
for (int i = 1; i <= 2021; i++) {
for (int j = i + 1; j <= i + 21; j++) {
if (j > 2021) break;
if (dp[j] == 0) {
dp[j] = dp[i] + lcm(i, j);
} else {
dp[j] = fminl(dp[j], dp[i] + lcm(i, j));
}
}
}
cout << dp[2021] << endl;
return 0;
}
