本次作业在 Sorting and Searching 部分选择一道二分题目（$21$），此外 Introductory Problems 部分顺序练习（$1\sim 7$），在看到做有挑战性的题目的要求后，又继续倒序练习（$14\sim 19$）。
Sorting and Searching
CSES-1620 Factory Machines
题意
已知 $n$ 台机器的效率，求制造 $t$ 件产品所需的最短时间。
思路
直接计算方案并不能很高效地得到答案。一个很直观的想法是，可以通过一分钟一分钟地增加时间来计算当前生产的产品数量，但是因为 $t$ 和 $k_i$ 的量级都在 $10^9$，不能满足时间限制。但是，求出时间 $T$ 内可以制造多少产品是可以在 $\mathrm O(n)$ 复杂度下做到的，同时观察可以制造出的产品数量同 $T$ 成正比，增长趋势是单调的，因此我们便可以通过二分的方法通过 $\mathrm O(\log T)$ 次检查来快速求出答案。最终复杂度为 $\mathrm O(n\log T)$。
特别要注意的是，使用 C++ 编码的时候计算较长时间可以生产的产品数量时会遇到溢出问题，可以通过达到要求的产品数量直接退出来规避。
代码
C++：Source code - Virtal Judge
#include <cstdio>
using namespace std;
const int maxn = 2e5 + 7;
long long n, t, k[maxn];
int main()
{
scanf("%lld%lld", &n, &t);
for (int i = 1; i <= n; ++i) scanf("%lld", &k[i]);
long long l = 1, r = 1e18, ans = 1;
while (l <= r)
{
long long mid = (l + r) >> 1, sum = 0;
for (int i = 1; i <= n && sum < t; ++i) sum += mid / k[i];
if (sum >= t) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%lld\n", ans);
return 0;
}
Python3：Source code - Virtal Judge
from functools import reduce
n, t = map(int, input().split())
k = list(map(int, input().split()))
l, r, ans = 1, 10**18, 0
while l <= r:
mid = (l + r) >> 1
tmp = 0
tmp = reduce(lambda acc, i: acc + mid // k[i], range(n), tmp)
if tmp >= t:
ans, r = mid, mid - 1
else:
l = mid + 1
print(ans)
Introductory Problems
CSES-1068 Weird Algorithm
思路
按照分支条件简单模拟即可。
代码
n = int(input())
while n != 1:
print(n, end = ' ')
n = ((n << 1) + n + 1) if n & 1 == 1 else n >> 1
print(n)
CSES-1083 Missing Number
思路
因为只缺一个数，因此用所有数字的和减去输入的所有数字之和便是所缺的数。
代码
n = int(input())
print((n * n + n >> 1) - sum(map(int, input().split())))
CSES-1069 Repetitions
题意
最长相同字母子串的长度
思路
存住上一个字符，若相同则当前相同字母子串长度增加，否则重新开始计长度。长度更新同时更新答案即可。
代码
s, lst, now, ans = input(), 'w', 0, 1
for ch in s:
if ch == lst:
now, ans = now + 1, max(ans, now + 1)
else:
now, lst = 1, ch
print(ans)
CSES-1094 Increasing Array
题意
每次操作为使数组中任一元素加 $1$，求使数组单调不降最少的操作次数。
思路
贪心地来说，如果要让数组中的元素单调不降，就需要让数组中的每个数至少与前面所有数的最大值相等，也就是至少跟前一个数相等。因此直接 $\mathrm O(n)$ 扫描一遍数组，将比前面一个数小的数通过操作变成与前数相等即可。
代码
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(1, n):
if a[i - 1] > a[i]:
ans += a[i - 1] - a[i]
a[i] = a[i - 1]
print(ans)
CSES-1070 Permutations
题意
寻找一个排列使得相邻两数之差均不为 $1$。
思路
经过简单分析发现，空一个放一个，等放满再从头开始插空放便可以满足要求，经过简单找规律，第 $i$ 个位置上放置的数为 $\begin{cases} \frac{i + 1}{2} + \lfloor\frac n 2 \rfloor & i 为奇数，\\frac i 2 & i为偶数.\end{cases}$，根据此公式直接编码即可。特别地，当 $1 < n < 4$ 时无解。
代码
n = int(input())
if 1 < n < 4:
print("NO SOLUTION")
else:
for i in range(1, n + 1):
print(i >> 1 if i & 1 == 0 else ((n >> 1) + (i + 1 >> 1)), end=' ')
CSES-1071 Number Spiral
题意
计算数字方阵中指定位置上的数字。
思路
经过观察发现，方阵的生成规律是每次加一层数，第 $i$ 层数字区间为 $\left((i - 1) ^ 2, i ^ 2\right]$，且根据 $i$ 的奇偶不同排列顺序相反。对此，我们不妨假设所有层的排列顺序都是从右上至左下，如果遇到 $i$ 是奇数的情况就交换 $x, y$ 坐标。
此外，第 $i$ 层的坐标特点便是总有一个坐标是 $i$，即 $i = \max(x, y)$，这样我们便可以通过坐标确定 $i$。
最后便需要确定在 $(x, y)$ 位置的数具体是多少。当 $x = i$ 时，即数字在第 $i$ 圈下面一行时，我们首先加上右边一列的数字个数，然后加上数字在该行的位置，即 $ans = (i - 1) ^ 2 + (i - 1) + (i - y)$；当 $y = i$ 时，也就是数字在第 $i$ 圈右边一列时，$ans = (i - 1) ^ 2 + x$。直接套公式计算即可。
代码
for _ in range(int(input())):
x, y = map(int, input().split())
base = max(x, y) - 1
if base & 1 == 0: x, y = y, x
ans = base ** 2 + (((base << 1) + 2 - y) if x == base + 1 else x)
print(ans)
CSES-1072 Two Knights
题意
向 $k \times k$ 的棋盘上放两匹马互相不会攻击到的方案数。
思路
如果直接计算符合条件的放置方案会非常复杂，我们不妨反过来解决，先计算出棋盘上放两匹马的所有方案数，再减去棋盘上两匹马能互相攻击到的方案数。
总方案数则可以看成在 $k \times k$ 个物品中选 $2$ 个，即 $C_{k ^ 2} ^2$；而两匹马能互相攻击到的方案数，可以等效为在 $k\times k$ 的棋盘上找 $2 \times 3$ 和 $3 \times 2$ 的长方体，个数均为 $(k - 1) * (k - 2)$，同时将两匹马放到 $2 \times 3$ 的长方体格子中并且互相能够攻击到有两种放置方法，因此需要再 $\times 2$，最终答案为 $C_{k^2}^2 - (k - 1) \times (k - 2) \times 2 \times 2$。使用 Python3 一行即可。
代码
for k in range(1, int(input()) + 1): print((k * k * (k * k - 1) >> 1) - ((k - 1) * (k - 2) << 2))
CSES-2165 Tower of Hanoi
题意
计算汉诺塔的最小步数以及每一步的移动方式。
思路
让我们先考虑只剩下最后一个盘子的情况，显然只需要从 $1$ 柱到 $3$ 柱移动一次即可。当剩下两个盘子时，我们可以先将最上面的盘子从 $1$ 柱移动到 $2$ 柱，然后将最下面的盘子从 $1$ 柱移动到 $3$ 柱，最后将最上面的盘子从 $2$ 柱移动到 $3$ 柱，这样我们便完成了两个盘子的移动。扩展到 $n$ 个盘子，我们可以先将 $n - 1$ 个盘子从 $1$ 柱移动到 $2$ 柱，然后将最后一个盘子从 $1$ 柱移动到 $3$ 柱，最后将 $n - 1$ 个盘子从 $2$ 柱移动到 $3$ 柱，其中，这 $n - 1$ 个盘子的移动又可以复用这个过程，只是由 $1$ 柱移动到 $3$ 柱变为了 $1$ 柱移向 $2$ 柱和 $2$ 柱移向 $3$ 柱，我们可以用同一个函数处理这个操作：由其中一个参数对应的柱子移动到另一个参数对应的柱子，第三个参数为辅助柱（题目中是由 a 移到 c，辅助柱为 b），这样我们便完成了 $n$ 个盘子的移动。
代码
#include<cstdio>
using namespace std;
int n;
void hanoi(int n, int a, int b, int c)
{
if(n == 1)
{
printf("%d %d\n", a, c);
return;
}
hanoi(n - 1, a, c, b);
printf("%d %d\n", a, c);
hanoi(n - 1, b, a, c);
}
int main()
{
scanf("%d", &n);
printf("%d\n", (1 << n) - 1);
hanoi(n, 1, 2, 3);
}
CSES-1622 Creating Strings
题意
生成给定字符串的字符可以创建的全部不同的字符串。
思路
题意可以转化为对字母做全排列，因此直接使用 C++ 中的 next_permutation 算法生成 $n$ 个字符的全排列即可。对于总数量，为了节省内存，可以提前用数学方法计算出 $n$ 个字符的全排列的数量，即 $A_n^n \over A_{s_1}^{s_1} \times \cdots \times A_{s_x}^{s_x}$，其中 $s_i$ 表示 $n$ 个字符中第 $i$ 种字符的出现次数，这部分将 $s$ 排序后直接遍历计算即可。
代码
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
char s[10];
int len, cnt;
int fact(int n) { return n == 1 ? 1 : n * fact(n - 1); }
int main()
{
scanf("%s", s);
len = strlen(s);
sort(s, s + len);
cnt = fact(len);
for (int i = 0, now = 1; i < len; i++) s[i] == s[i + 1] ? ++now : (cnt /= fact(now), now = 1);
printf("%d\n", cnt);
do { puts(s); } while (next_permutation(s, s + len));
}
CSES-1623 Apple Division
题意
将 $n$ 个数分成两组，求两组之差的最小值。
思路
直接对分组的所有可能进行二进制枚举，然后更新答案即可。
对于二进制枚举，是指将 $n$ 个数看成 $n$ 位二进制数，每一位上的 $1$ 表示该数在第一组中，$0$ 表示该数在第二组中，因此一共有 $2 ^ n$ 种可能，而每次枚举需要遍历数组计算两组的数字和，因此时间复杂度为 $\mathrm O(n \times 2 ^ n)$。
代码
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int maxn = 25;
long long n, p[maxn], cnt, ans;
int main()
{
for (int i = scanf("%lld", &n); i <= n; ++i) scanf("%lld", &p[i]), cnt += p[i], ans += p[i];
for (long long i = 1, end = 1 << n, tmp = 0; i < end; ++i, tmp = 0)
{
for (int j = 0; j < n; ++j) tmp += i & (1 << j) ? p[j + 1] : 0;
ans = min(ans, abs(tmp - (cnt - tmp)));
}
printf("%lld", ans);
return 0;
}
CSES-1624 Chessboard and Queens
题意
带放置限制的八皇后问题。
思路
经典的八皇后问题，直接搜索即可。需要注意的是，$(x, y)$ 格子能够放置皇后的条件除所在行列和两条对角线外，还需要满足对应格子允许放置皇后。
代码
#include <cstdio>
using namespace std;
const int maxn = 8;
int n = maxn, ans, r[maxn], c[maxn], d1[maxn << 1], d2[maxn << 1];
char M[maxn][maxn];
void search(int x, int y, int cnt)
{
if (y == n) x++, y = 0;
if (cnt == n) ++ans;
if (x == n || cnt == n) return;
if (M[x][y] == '.' && !r[x] && !c[y] && !d1[x + y] && !d2[x - y + n])
{
r[x] = c[y] = d1[x + y] = d2[x - y + n] = 1;
search(x, y + 1, cnt + 1);
r[x] = c[y] = d1[x + y] = d2[x - y + n] = 0;
}
search(x, y + 1, cnt);
}
int main()
{
for (int i = 0; i < n; ++i) scanf("%s", M[i]);
search(0, 0, 0);
printf("%d\n", ans);
}
CSES-2431 Digit Queries
题意
求由自然数看作字符串拼成的字符串序列第 $n$ 位上的数字。
思路
首先我们可以发现，可以将自然数根据长度分组，第 $i$ 组的数字个数为 $9 \times 10 ^ {(i - 1)}$，因此可以计算出每组数字的总长度，即 $i \times 9 \times 10 ^ {(i - 1)}$，然后我们便可以根据 $n$ 的大小确定 $n$ 在哪一组中。为了加快计算速度，我们可以预处理出每组数字的总长度，然后使用二分查找确定 $n$ 在哪一组中。
确定了 $n$ 在哪一组中之后，我们发现只要用 $n$ 减去前面所有组的总长度，便可以通过除以该组的单个数字长度确定 $n$ 位于当前组中的第几个数中，通过余数可以确定 $n$ 位于这个数的第几位中。
代码
#include <algorithm>
#include <cstdio>
using namespace std;
long long t, n, x, ans, num[] = {0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889, 8888888889, 98888888889, 1088888888889, 11888888888889, 128888888888889, 1388888888888889, 14888888888888889, 158888888888888889, 1688888888888888889}, pow10[] = {0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000};
int main()
{
for (scanf("%lld", &t); t--;)
{
scanf("%lld", &n);
x = lower_bound(num, num + 18, n) - num;
n -= num[x - 1] + (x > 1);
ans = n / x + pow10[x - 1];
for (int t = x - n % x - 1; t--;) ans /= 10;
printf("%lld\n", ans % 10);
}
}
CSES-1625 Grid Paths
题意
求解 $7\times 7$ 的地图中满足输入限制的路径方案数。
思路
如果直接暴力搜索，最差复杂度会到达 $\mathrm O(4 ^ {n^2})$，成功超时，因此我们需要对搜索进行剪枝。
一个可能的剪枝方法是，如果一个点以及相对方向上相邻点均已经遍历过，而另外两个相对方向上的相邻点均未被遍历过，那么最终后两个点一定不可能都被遍历，因此可以直接剪枝。
代码
#include <cstdio>
using namespace std;
const int maxm = 50, maxn = 10;
int ans, step;
char s[maxm], vis[maxn][maxn];
bool check(int x, int y) { return x >= 1 && x <= 7 && y >= 1 && y <= 7 && !vis[x][y]; };
void search(int x, int y)
{
if (!check(x, y)) return;
if (step == 48)
if (x == 7 && y == 1) ans++;
else return;
if (x == 7 && y == 1) return;
if (check(x - 1, y) && check(x + 1, y) && !check(x, y - 1) && !check(x, y + 1)) return;
if (!check(x - 1, y) && !check(x + 1, y) && check(x, y - 1) && check(x, y + 1)) return;
vis[x][y] = 1, ++step;
if (s[step] == '?' || s[step] == 'U') search(x - 1, y);
if (s[step] == '?' || s[step] == 'D') search(x + 1, y);
if (s[step] == '?' || s[step] == 'L') search(x, y - 1);
if (s[step] == '?' || s[step] == 'R') search(x, y + 1);
vis[x][y] = 0, --step;
}
int main()
{
scanf("%s", s + 1);
search(1, 1);
printf("%d", ans);
return 0;
}
