【笔试】备战秋招,每日一题|20230415携程研发岗笔试

前言

最近碰到一个专门制作大厂真题模拟题的网站 codefun2000，最近一直在上面刷题。今天来进行2023.04.15携程研发岗笔试，整理了一下自己的思路和代码。

比赛地址

A. 找到you

题意：

给定一个仅包含小写字母的 $n\times n$ 的矩阵，问这个矩阵中所有 $2\times 2$ 的矩阵中同时包含 y、o 和 u 三个字符的子矩阵数量。

数据范围：$1\le n,m\le 1000$

题解：

暴力枚举每个 $2\times 2$ 子矩阵，对于每个子矩阵，判断其之中是否同时存在 y、o 和 u 三个字符即可，共需要枚举 $(n-1)\times (m-1)$ 个子矩阵。

时间复杂度分析：$O(nm)$

#include <bits/stdc++.h>
using namespace std;const int N = 1010;
char s[N][N];
int n, m;bool check(int i, int j) {int val = 0;for (int x = 0; x < 2; ++x)for (int y = 0; y < 2; ++y) {if (s[i + x][y + j] == 'y') val |= 1 << 0;if (s[i + x][y + j] == 'o') val |= 1 << 1;if (s[i + x][y + j] == 'u') val |= 1 << 2;}return val == 7;
}int main()
{scanf("%d%d", &n, &m);;for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);int ans = 0;for (int i = 1; i + 1 <= n; ++i)for (int j = 1; j + 1 <= m; ++j) {if (check(i, j)) ans += 1;}printf("%d\n", ans);return 0;
}

B. 最小公倍数

题意：

$T$ 组数据，每组数据给定一个 $n$，现在问在 $a+b=n$ 的情况下，使得 $lcm(a,b)$ 最大的 $a$ 和 $b$ 是多少？

数据范围：$1\le T\le 10^5,2\le n\le 10^{13}$

题解：

$T$ 组数据，而 $T$ 最大为 $10^5$ ，则每组数据至多要在 $O(\log n)$ 的时间解决，因为这个题需要求 $lcm$，这个求解的复杂度是 $O(\log n)$ 的，
所以判断的操作得在 $O(1)$ 时间复杂度内。

下面我们都认为 $a\le b$
当两个数 $a$ 和 $b$ ，满足 $a+1=b$ ，那么此时 $a$ 和 $b$ 互质，$lcm(a,b)=a\times b$。

考虑奇数：将其拆分成 $a=\lfloor \frac{n}{2}\rfloor ,b=\lceil \frac{n}{2}\rceil$，有 $a+1=b$，故此时最大的 $lcm(a,b)$ 就是 $a=\lfloor \frac{n}{2}\rfloor ,b=\lceil \frac{n}{2}\rceil$。
考虑偶数：将其拆分成 $a=\frac{n}{2},b=\frac{n}{2}$ 的 $lcm(a,b)=\frac{n}{2}$。

因为 $n$ 是偶数，所以拆分出必然是要么 $a$ 和 $b$ 均为偶数，要么 $a$ 和 $b$ 均为奇数。
这里有一个结论，对于正数 $a,b,n$，如果有 $a+b=n$，且 $a$ 和 $b$ 均为奇数，则 $gcd(a,b)=1$ 。

当 $n=2$，只有一种拆分法：$a=1,b=1$。

当 $n>2$，对于拆分 $a=1,b=n-1，lcm(1,n-1)>lcm(\frac{n}{2},\frac{n}{2})$，所以$a=\frac{n}{2},b=\frac{n}{2}$这个拆分必然不如其他任意一个拆分。

此外，下面的讨论都只针对大于 $2$ 的偶数。

所以对于一个数 $n$，我们至多只需要考虑 $2$ 个位置，因为其他位置都不如这些位置中的任意一个：

当 $\frac{n}{2}$ 为奇数，

• $a=\frac{n}{2}-1,b=\frac{n}{2}+1,lcm(a,b)=\frac{a\times b}{gcd(a,b)}=\frac{(\frac{n}{2}-1)\times (\frac{n}{2}+1)}{2}$，因为 $b-a=2$，且 $a$ 和 $b$ 都是偶数，故 $gcd(a,b)=2$
• $a=\frac{n}{2}-2,b=\frac{n}{2}+2,lcm(a,b)=\frac{a\times b}{gcd(a,b)}=\frac{(\frac{n}{2}-2)\times (\frac{n}{2}+2)}{1}$，因为 $b-a=4$，故公约数只能为$1,2,4$，且 $a$ 和 $b$ 都是奇数，故最大公约数只能为$1$。

当 $\frac{n}{2}$ 为偶数，

• $a=\frac{n}{2}-1,b=\frac{n}{2}+1,lcm(a,b)=\frac{a\times b}{gcd(a,b)}=\frac{(\frac{n}{2}-1)\times (\frac{n}{2}+1)}{1}$，因为 $b-a=2$，故公约数只能为 $1,2$，且 $a$ 和 $b$ 都是奇数，故 $gcd(a,b)=1$
• $a=\frac{n}{2}-2,b=\frac{n}{2}+2,lcm(a,b)=\frac{a\times b}{gcd(a,b)}=\frac{(\frac{n}{2}-2)\times (\frac{n}{2}+2)}{gcd(a,b)\ge 2}$，因为 $b-a=4$，故公约数只能为$1,2,4$，且 $a$ 和 $b$ 都是偶数，故最大公约数至少为 $2$。

上面已经说明了，对于本题中的 $a+b=n$，$a\times b>(a-1)\times (b+1)=a\times b+a-b-1$
因为 $a-b-1<0$，故 $a\times b>(a-1)\times (b+1)$。

当 $\frac{n}{2}$ 为奇数，
$lcm(\frac{n}{2}-1,\frac{n}{2}+1)-lcm(\frac{n}{2}-2,\frac{n}{2}+2)=(\frac{n^2}{8}-\frac{1}{2})-(\frac{n^2}{4}-4)=\frac{28-n^2}{8}$，因为 $\frac{n}{2}$ 为奇数且 $n>2$，故 $n\ge 6$，故 $\frac{28-n^2}{8}<0$，故$lcm(\frac{n}{2}-2,\frac{n}{2}+2)>lcm(\frac{n}{2}-1,\frac{n}{2}+1)$

当 $\frac{n}{2}$ 为偶数，
$lcm(\frac{n}{2}-1,\frac{n}{2}+1)>lcm(\frac{n}{2}-2,\frac{n}{2}+2)$

总结：

当 $n$ 为奇数：$a=\lfloor \frac{n}{2}\rfloor ,b=\lceil \frac{n}{2}\rceil$

当 $n$ 为偶数：

• 当 $n=2$，$a=1,b=1$
• 当 $\frac{n}{2}$ 为奇数，$a=\frac{n}{2}-2,b=\frac{n}{2}+2$
• 当 $\frac{n}{2}$ 为偶数，$a=\frac{n}{2}-1,b=\frac{n}{2}+1$

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;void solve() {ll n; scanf("%lld", &n);if (n & 1) {printf("%lld %lld\n", n / 2, n - n / 2);} else {if (n == 2) puts("1 1\n");if ((n / 2) & 1) {printf("%lld %lld\n", n / 2 - 2, n / 2 + 2);} else {printf("%lld %lld\n", n / 2 - 1, n / 2 + 1);}}}int main()
{int T;scanf("%d", &T);while (T--) {solve();}return 0;
}

C.魔法之树

题意：

给定一个 $n$ 个点的树，问这棵树上任意一条简单路径，有起点和终点，这条路径上的点构成的二进制字符串对应的十进制数在 $[l,r]$ 范围内的简单路径数。这里的简单路径长度至少为 $1$ ，即自己到自己不算在内

数据范围：$1\le n\le 1000,1\le l\le r\le 10^{14}$

题解：
枚举以每个点作为起点，遍历完所有的其他 $n-1$ 个点为终点，当遇到值大于 $r$ ，则后面的点作为终点的简单路径构成的二进制字符串对应的十进制数都必然大于 $r$ 了，不会再可能成为答案了。这里必须要及时判断，一方面可以剪枝，另一方面是为了避免爆 long long。

时间复杂度：$O(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 1010;
vector<int> g[N];
int n;
ll l, r;
char s[N];
int ans;void dfs(int cur, int u, int fa, ll val) {val = val * 2 + (s[u] - '0');if (val > r) return ;if (val >= l && u != cur) ans += 1;for (int v: g[u]) {if (v == fa) continue ;dfs(cur, v, u, val);}
}void solve() {scanf("%d%lld%lld", &n, &l, &r);scanf("%s", s + 1);for (int i = 1; i < n; ++i) {int a, b;scanf("%d%d", &a, &b);g[a].push_back(b);g[b].push_back(a);}ans = 0;for (int i = 1; i <= n; ++i) {dfs(i, i, 0, 0);}printf("%d\n", ans);
}int main()
{int T = 1;
//    scanf("%d", &T);while (T--) {solve();}return 0;
}

D.01串的回文子串

题意：

给定 $n$ 个数 $a_i$，当 $i$ 为奇数，表示生成 $a_i$ 个 1，当 $i$ 为偶数，表示生成 $a_i$ 个 0。即生成一个长度为 $\sum _{i=1}^n{a}_i$ 的序列 $s$，$s[1,a_1]=1,s[a_1+1,a_2]=0,s[a_2+1,a_3]=1,s[a_3+1,a_4]=0,...$ 。问这个序列中有多少个回文子串。答案对 $10^9+7$ 取模

数据范围：
$1\le n\le 1000,1\le a_i\le 10^9$

题解：

可以将看成序列看成分为 $n$ 块，每块内部都是连续的 $0$ 或 $1$。

考虑每块内部可以生成多少回文子串：一块内部有 $x$ 个数，以第 $i$ 个数结尾的回文子串数量为 $i$ ，即 $\sum _{i=1}^{x}i=\frac{x\times (x+1)}{2}$

再考虑包含第 $i$ 块的回文子串数量。那么以第 $i$ 块为回文子串中心，向左右扩展。当且仅当左右两个数都相同，会多生成一个回文子串。这个什么时候截止呢，假设我们当前 $a[i-1]=a[i+1],a[i-2]=a[i+2],...a[i-p]=a[i+p]$，但是 $a[i-p-1]\ne a[i+p+1]$，则生成的回文子串数为：$min(a[i-p-1],a[i+p+1])+\sum _{j=1}^{p}a[j]$

时间复杂度：$O(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;const int N = 1010;
const int mod = 1e9 + 7;long long a[N];
int n;void solve() {long long ans = 0;scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%lld", &a[i]);ans = (ans + a[i] * (a[i] + 1) / 2) % mod;}for (int i = 2; i < n; ++i) {int L = i - 1, R = i + 1;while (L >= 1 && R <= n) {ans = (ans + min(a[L], a[R])) % mod;if (a[L] == a[R]) L -= 1, R += 1;else break;}}printf("%lld\n", ans);
}int main()
{int T = 1;
//    scanf("%d", &T);while (T--) {solve();}return 0;
}