程序员进阶之算法练习（八）附两道搜狐笔试题
前言
前面讲了那么多算法的重要性。口说无凭，这次带上两道搜狐今年的笔试题。 这里先附上两道搜狐题目的大意： 题目一： 《宝石》 有一串宝石首尾相连，用一个大写字母表示一个宝石； 现在需要从这一串宝石中截取一段宝石，要求这一段宝石包含ABCDE这5种字母；求剩下最多有多少个宝石？ 题目二： 《袋鼠》 有n个弹簧排成一列，袋鼠起始位置在第一个弹簧； 输入n个数字，代表n个弹簧的力量； 弹簧的力量为5表示可以往后跳最多5个弹簧； 问袋鼠到达第n个弹簧的最小弹跳次数？ 答案看最后的附加题部分。
正文
这次正文有5道题，是CF707-DIV2的题目。
- 为了不剧透，把对题目的总结放到最后面。
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目大意：输入n * m个字符，字符中存在C M Y为混色，否则为黑白，输出对应的描述。
Examples
input
2 2
C M
Y Y
output
#Color
input
3 2
W W
W W
B B
output
\ #Black&White
代码实现：
int n, m, ret = 1;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
char str[10];
scanf("%s", str);
if (str[0] == 'C' || str[0] == 'M' || str[0] == 'Y') {
ret = 0;
}
}
}
if (!ret) {
cout << "#Color";
}
else {
cout << "#Black&White";
}题目解析：
难度在读题，黑白不仅仅是W B，还有G。
B
题目大意：n个城市，其中k个城市提供面粉，城市中有m条路。
在n个城市中的选择一个不提供面粉的城市，要求这个城市能到达提供面粉的城市，如果有多个输出边长最小的一个。（没有输出-1）
n, m and k (1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ n)
Examples
input
5 4 2
1 2 5
1 2 3
2 3 4
1 4 10
1 5
output
3
input
3 1 1
1 2 3
3
output
-1
代码实现：
int n, m, k;
cin >> n >> m >> k;
for(int i = 0; i <= n; ++i) g[i].clear();
for (int i = 0; i < m; ++i) {
lld u, v, l;
cin >> u >> v >> l;
g[u].push_back(make_pair(v, l));
g[v].push_back(make_pair(u, l));
}
for (int i = 0; i < k; ++i) {
int tmp;
scanf("%d", &tmp);
f[tmp] = 1;
}
lld ret = -1;
for (int i = 1; i <= n; ++i) {
if (f[i]) {
for (int j = 0; j < g[i].size(); ++j) {
if (f[g[i][j].first] == 0) {
if (ret == -1) {
ret = g[i][j].second;
}
else {
ret = min(ret, g[i][j].second);
}
}
}
}
}
cout << ret;题目解析：
n个点，m条边，k个关键点。在关键点外的集合n-k，中找到一点T，使得T与关键点中任意点连接，并且边长最小。
难度都在读题，容易知道，关键点只要存在一条边与非关键点相连，那就有解。
存下边，把点标记为关键点(fi=1)和非关键点(fi=0)
遍历查找边由fi=1到fi=0的最小边即可，无解输出-1。
C
题目大意：给出一个数字n，求一组勾股数中的另外两个，使得三个构成勾股数。
n (1 ≤ n ≤ 10^9)
Examples
input
3
output
4 5
input
6
output
8 10
input
1
output
-1
代码实现：
lld k, b;
cin >> k;
lld mod = 2 - k % 2;
b = (k * k / mod - mod) / 2;
if (b == 0) {
cout << -1;
}
else {
cout << b << " " << b + mod << endl;
}题目解析：
容易知道，n=1,2无解。（最小的勾股数3、4、5）
假设在a2+b2=c^2 中 令a=n
那么有n * n=c * c-b * b=(c+b) * (c-b)
当n为奇数时，令c-b=1, 有n * n=(b+1+b) => b=(n * n-1)/2
当n为偶数时，令c-b=2, n * n=(b+2+b) * 2 => b=(n * n/2-2)/2
令mod=2-n%2，那么有b= (n * n/mod - mod)/2
D
题目大意：n * m的格子，q个操作 (1 ≤ n, m ≤ 10^3, 1 ≤ q ≤ 10^5) 每次有4种操作：
1 i j, ai = 1
2 i j, ai = 0
3 i, for j in ai, ai = !ai
4 k, 返回操作到第k次的状态，k=0表示起始状态。
每次操作后输出当前格子为1的数量。
Examples
input
4 2 6
3 2
2 2 2
3 3
3 2
2 2 2
3 2
output
2
1
3
3
2
4
代码实现：
struct Node {
int type, x, y, k;
}node[M];
int flag[N]; // 标志第i行是否翻转
int dfn[M]; // 第i个操作是否已经执行
int a[N][N]; // a[i][j]
int num[N], m; //第i行为1的数量
int sum; // 当前数量
int ans[M]; // 第i个操作答案
vector<int> g[M]; // 顶点
void lookNext(int k) {
dfn[k] = 1;
for (int i = 0; i < g[k].size(); ++i) {
int u = g[k][i];
if (dfn[u] == 0) {
if (node[u].type == 1) {
if (a[node[u].x][node[u].y] == flag[node[u].x]) {
++sum;
++num[node[u].x];
ans[u] = sum;
a[node[u].x][node[u].y] = !flag[node[u].x];
lookNext(u);
a[node[u].x][node[u].y] = flag[node[u].x];
--num[node[u].x];
--sum;
}
else {
ans[u] = sum;
lookNext(u);
}
}
else if (node[u].type == 2) {
if (a[node[u].x][node[u].y] != flag[node[u].x]) {
--sum;
--num[node[u].x];
a[node[u].x][node[u].y] = flag[node[u].x];
ans[u] = sum;
lookNext(u);
a[node[u].x][node[u].y] = !flag[node[u].x];
++num[node[u].x];
++sum;
}
else {
ans[u] = sum;
lookNext(u);
}
}
else if (node[u].type == 3) {
sum = sum - num[node[u].x] + (m - num[node[u].x]);
num[node[u].x] = m - num[node[u].x];
flag[node[u].x] = !flag[node[u].x];
ans[u] = sum;
lookNext(u);
flag[node[u].x] = !flag[node[u].x];
num[node[u].x] = m - num[node[u].x];
sum = sum + num[node[u].x] - (m - num[node[u].x]);
}
else if (node[u].type == 4) {
ans[u] = sum;
lookNext(u);
}
}
}
}题目解析：
操作1、2比较简单，操作3是组操作，设置flagi表示第i行在最终结算时是否翻转，那么有
操作1为ai = !flagi.
操作2为ai = flagi.
操作3为flagi = !flagi.
操作4较为复杂，回到操作k，k为之前的操作。
考虑到题目对k没有限制，那么k可以为之前的某个回退操作，从而产生递归回退的效果；
同时回退到操作i之后，下一步可以再回退到操作j，这样线性的操作不可取。
但是单个操作只会是一个线性的分支，整个操作序列可以形成多个线性的分支，汇总在一起就是一颗树的表现。
对于第i个操作，操作完毕后的状态为j，连一条边从i到j，表示从第i个操作完之后会进入操作j的状态。
那么对操作1、2、3，i会连上一条边到i+1；操作4，i会连上一条边到k。
对于某一个操作，先执行，然后dfs，最后撤销执行即可。
E
题目大意：输入k条链，链上的节点在n * m的矩阵上；
每条链有leni个点，每个点的输入包括x、y、w表示在n * m矩阵上的坐标和权值。
q次操作，操作1把链上的点翻转（权值由w变成0，或者从0变成w）；操作2，询问子矩阵内点的权值;
操作2最多2000次；
n,m,k = 2000, q=10^6.
代码实现：
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
const int N = 2010, M = 1000100, inf = 10110110;
struct Node {
int type, x, y, w;
Node(int x, int y, int w):x(x), y(y), w(w){};
Node(){};
};
vector<Node> g[N];
lld d[N][N]; // 前i条链对第j个矩阵的贡献
lld flag[N]; // 标志是否关闭
int n, m, k;
inline void fastRead(int &x){
char t = getchar();
bool sign = true;
while(t < '0' || t > '9') {
if(t == '-') {
sign = false;
}
t = getchar();
}
for(x = 0; t >= '0' && t <= '9'; t = getchar()) {
x = x * 10 + t - '0';
}
if(!sign) {
x = -x;
}
}
lld tree[N][N];
struct Ask {
int x1, y1, x2, y2;
Ask(int x1, int y1, int x2, int y2):x1(x1), y1(y1), x2(x2), y2(y2){};
};
vector<Ask> matrix;
int ask[M];
char ch[10];
inline int lowbit(int x) {
return x & -x;
}
void tree_add(int x,int y,int w){
for(int i = x;i <= n; i += lowbit(i))
for(int j = y; j <= m; j += lowbit(j))
tree[i][j] += w;
}
lld tree_sum(int x,int y){
lld sum = 0;
for(int i = x; i > 0;i -= lowbit(i))
for(int j = y; j > 0; j -= lowbit(j))
sum += tree[i][j];
return sum;
}
int main(int argc, const char * argv[]) {
// insert code here...
cin >> n >> m >> k;
for (int i = 0; i < k; ++i) {
int len;
fastRead(len);
while (len--) {
int x, y, w;
fastRead(x);
fastRead(y);
fastRead(w);
g[i].push_back(Node(x, y, w));
}
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
scanf("%s", ch);
if (ch[0] == 'S') {
fastRead(ask[i]);
}
else {
int x1, y1, x2, y2;
fastRead(x1);
fastRead(y1);
fastRead(x2);
fastRead(y2);
matrix.push_back(Ask(x1, y1, x2, y2));
}
}
for (int i = 0; i < k; ++i) {
for (int j = 0; j < g[i].size(); ++j) {
tree_add(g[i][j].x, g[i][j].y, g[i][j].w);
}
for (int j = 0; j < matrix.size(); ++j) {
d[i][j] = tree_sum(matrix[j].x2, matrix[j].y2) + tree_sum(matrix[j].x1 - 1, matrix[j].y1 - 1) - tree_sum(matrix[j].x1 - 1, matrix[j].y2) - tree_sum(matrix[j].x2, matrix[j].y1 - 1);
}
}
int ans = 0;
for (int i = 0; i < q; ++i) {
if (ask[i] == 0) {
lld ret = 0;
for (int j = 0; j < k; ++j) { // 枚举k条链
if (flag[j] == 0) {
if (j == 0) {
ret += d[j][ans];
}
else {
ret += d[j][ans] - d[j - 1][ans];
}
}
}
cout << ret << endl;
++ans;
}
else {
flag[ask[i] - 1] ^= 1;
}
}
return 0;
}题目解析：
先看最暴力的做法，对于每个switch，把点的值Switch；对于每个ask，遍历所有的链得出结果。
优化部分，添加flag，标志每次switch，询问时再进行计算。
每条链复杂度为O（Len），k条链的修改为O（n) * O(m)，询问的时间为O(n) * O(m)。
总的复杂度为O(n * m * 2000) * 2=16 * 1e9。（ * 2是因为每次询问都要修改一次、求和一次）
接着使用数据结构来优化。
易知，子矩阵求和使用树状数组即可。求和操作可以优化为O(logN) * O(logM)。
同样在询问的时候再来修改权值，那么有修改复杂度为O(logN) * O(logM) * O(N) * O(M)。
求和复杂度可以忽略，总得复杂度为2000 * log2000 * log2000 * 2000 * 2000 = 8 * 10e10。 （虽然理论上q=10e6限制了当矩阵数为2000时，每次询问前的switch操作有限，但是一条链可以很长，对很长的链进行操作即可，所以最后的修改次数我们还是按N * M来计算）
为什么变大了？
因为每次询问前的修改操作变成耗时操作，如果题目每次在询问前都修改所有的值，复杂度会很高。
继续优化。
每次修改的都是同一个值（整条链为0，整条链恢复），那么可以预处理出这个值di，表示第i条链对第j个子矩阵的贡献。
这样就可以避免每次询问前修改值，使用之前预处理的计算值即可。
复杂度为5 * 2000 * 2000 * log2000 * log2000 = 2billion；
全部为加法，并且题目给出的时限为3s，可行。
总结
- A题是简单题；
- B题是简单题；
- C题是构造题；
- D题是DFS；
- E题是数据结构+离线处理；
只要DIV2没有数论题都能AC，做CF算是赶上大学时候的水平。虽然目前的工作用到的机会比较少，但是做做算法训练还是挺好玩的。
只是喜欢玩，就花点时间在上面；因为对未来可能有用，所以希望自己坚持下去。
附加题
题目一：《宝石》
有一串宝石首尾相连，用一个大写字母表示一个宝石；
现在需要从这一串宝石中截取一段宝石，要求这一段宝石包含ABCDE这5种字母；求剩下最多有多少个宝石？
input
AFBCFFDE
output
2
样例解释：
因为宝石是收尾相连的，所以AFBC和DE是相连的，可以截取这一段下来，剩下FF两个宝石，所以答案为2。
容易知道，我们想要截取一段最短的宝石，包含ABCDE5种宝石； 首先解决首尾相连的问题：把字符串复制一遍放在最后，这样就可以表示循环； 问题变成在字符串str中，找到一个最短的，包含ABCDE 5种字符的子串。 因为对ABCDE的顺序没有要求，故而可以用贪心来解决这个问题： 我们对每一种宝石都设置一个Right数组，Righti表示第i种宝石最右边的位置； 假设我们找到了这个最短子串，设最左边的节点为i，最右边的节点为j，有i, j，那么有 i = min_element(Right, Right + 5)。 然后遍历 N*2的字符串，不断更新Right数组和ans即可。
题目二：《袋鼠》
有n个弹簧排成一列，袋鼠起始位置在第一个弹簧；
输入n个数字，代表n个弹簧的力量；
弹簧的力量为5表示可以往后跳最多5个弹簧；
问袋鼠到达第n个弹簧的最小弹跳次数？
dpi 表示到达第i个的最小步数； dp1=1； 对于第i个数字是ai，那么有枚举j， 1<= j <= ai di+j=min(di+j, di+1); 表示到达i+j的最优解； 复杂度最多可以到O(N*N)。 优先队列优化： 对dpi, 打包成pair(i, ai) 放入优先队列； 这样每次取出来的都是最小步数，然后判断i+aj是否大于等于当前位置，是则更新，不是则丢弃这个解，重新在队列里面取；
扩展
《宝石二》
有一串宝石首尾相连，用一个大写字母表示一个宝石，每个宝石有相应价值；
现在需要从这一串宝石中截取一段宝石，要求这一段宝石包含ABCDE这5种字母；求剩下最大价值数？
input
8
AFBCFFDE
1 2 3 4 5 6 7 8
output
11《袋鼠二》
袋鼠喜欢在弹簧上弹跳；
有n个弹簧排成一列，每个弹簧可以弹到下一个弹簧；
输入n个数字，代表袋鼠对n个弹簧的喜欢值；
袋鼠只喜欢跳到喜欢值大于等于起始位置喜欢值的弹簧；
袋鼠可以在任意弹簧位置起跳；
袋鼠的开心值=起始点的喜欢值*经过的弹簧数；
求袋鼠最大的开心值。
input
5
1 2 3 4 5
output
9袋鼠在位置1，2，3，4，5起跳的开心值分别为5，8，9，8， 5。
腾讯云开发者
