程序员进阶之算法练习（八）附两道搜狐笔试题
前言
前面讲了那么多算法的重要性。口说无凭，这次带上两道搜狐今年的笔试题。
这里先附上两道搜狐题目的大意：
题目一：
《宝石》
有一串宝石首尾相连，用一个大写字母表示一个宝石；
现在需要从这一串宝石中截取一段宝石，要求这一段宝石包含ABCDE这5种字母；求剩下最多有多少个宝石？
题目二：
《袋鼠》
有n个弹簧排成一列，袋鼠起始位置在第一个弹簧；
输入n个数字，代表n个弹簧的力量；
弹簧的力量为5表示可以往后跳最多5个弹簧；
问袋鼠到达第n个弹簧的最小弹跳次数？
答案看最后的附加题部分。
正文
这次正文有5道题，是CF707-DIV2的题目。
- 为了不剧透，把对题目的总结放到最后面。
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
文集：
程序员进阶之算法练习（一）
程序员进阶之算法练习（二）
程序员进阶之算法练习（三）
程序员进阶之算法练习（四）
程序员进阶之算法练习（五）
程序员进阶之算法练习（六）
程序员进阶之算法练习（七）
代码地址
A.Brain's Photos
题目链接
题目大意：输入n * m个字符，字符中存在C M Y为混色，否则为黑白，输出对应的描述。
'C' (cyan)
'M' (magenta)
'Y' (yellow)
'W' (white)
'G' (grey)
'B' (black)
n and m (1 ≤ n, m ≤ 100)
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. Bakery
题目链接
题目大意：n个城市，其中k个城市提供面粉，城市之间存在m条路。
现在需要在n个城市中，选择一个城市开面包店；
要求：
1、不能选择有面粉供应的城市；
2、能到达提供面粉的城市；
3、到达提供面粉城市的路径最短；
输入
第一行 n, m and k (1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ n)
接下来m行 每行u, v and l，分别表示城市u和v之间有一条长为l的路 (1 ≤ u, v ≤ n, 1 ≤ l ≤ 109, u ≠ v)
最后一行有k个数字a[i], a[i]表示提供面粉的城市；
输出：
选择的城市；（没有输出-1）
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与关键点中任意点连接，并且边长最小。
难度都在读题，容易知道，关键点只要存在一条边与非关键点相连，那就有解。
存下边，把点标记为关键点(f[i]=1)和非关键点(f[i]=0)
遍历查找边由f[i]=1到f[i]=0的最小边即可，无解输出-1。
C.Pythagorean Triples
题目链接
题目大意：给出一个数字n，求一组勾股数中的另外两个，使得三个构成勾股数。
输入：
n (1 ≤ n ≤ 10^9)
输出：
勾股数的另外两个m，k (1 ≤ m, k ≤ 1e18)
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）
假设在a^2 + b^2 = 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.Persistent Bookcase
题目链接
题目大意：小明有一个书柜，书柜有n层，每层有m个位置可以放书。（书柜一开始是空的）
小明会对书柜进行整理，整理的操作有四种类型：
- 1 i j，往第i层第j个位置放一本书；（如果上面已经有书则不放）
- 2 i j，把第i层第j个位置清空；（如果上面没有书则不动）
- 3 i， 把第i层空位置放上书，把上面有书的位置清空；
- 4 k，把书柜的状态回到第k次操作后的状态；（如果k=0，表示回到初始状态）
每次操作后输出当前书柜上书的数量。
输入
第一行 n, m and q (1 ≤ n, m ≤ 10^3, 1 ≤ q ≤ 10^5)
接下来q行 每行先输入操作类型，再输入参数。
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是组操作，设置flag[i]表示第i行在最终结算时是否翻转，那么有
操作1为a[i][j] = !flag[i].
操作2为a[i][j] = flag[i].
操作3为flag[i] = !flag[i].
操作4较为复杂，回到操作k，k为之前的操作。
考虑到题目对k没有限制，那么k可以为之前的某个回退操作，从而产生递归回退的效果；
同时回退到操作i之后，下一步可以再回退到操作j，这样线性的操作不可取。
但是单个操作只会是一个线性的分支，整个操作序列可以形成多个线性的分支，汇总在一起就是一颗树的表现。
对于第i个操作，操作完毕后的状态为j，连一条边从i到j，表示从第i个操作完之后会进入操作j的状态。
那么对操作1、2、3，i会连上一条边到i+1；操作4，i会连上一条边到k。
对于某一个操作，先执行，然后dfs，最后撤销执行即可。
E. Garlands
题目链接
题目大意：输入k条链，链上的节点在n * m的矩阵上，如图：
每条链有len[i]个点，每个点的输入包括x、y、w表示在n * m矩阵上的坐标和权值。
有q次操作：
- 操作1，把链上的点翻转（权值由w变成0，或者从0变成w）；
- 操作2，询问子矩阵内点的权值;（ 操作2最多2000次）
n,m,k = 2000, q=10^6.
输入：
第一行 n, m and k (1 ≤ n, m, k ≤ 2000)
接下来输入k条链的信息，每条链的输入格式：
1、 第一行 len，表示长度 (1 ≤ len ≤ 2000)
2、 接下来len行，每行 i, j and w 表示坐标i,j 和 权值w (1 ≤ i ≤ n, 1 ≤ j ≤ m, 1 ≤ w ≤ 1e9)
接着是操作信息，首先是 q 表示操作次数 (1 ≤ q ≤ 1e6)
接下来q行，每行表示操作，操作有两种类型：
1、SWITCH i 表示把第i条链进行翻转；
2、ASK x1 y1 x2 y2 (x1, y1)表示左下角，(x2, y2表示右上角；输出对应矩阵的权值和；
Examples
input
4 4 3
5
1 1 2
1 2 3
2 2 1
2 1 4
3 1 7
4
1 3 1
2 3 3
2 4 3
1 4 1
7
4 1 1
4 2 9
3 2 8
3 3 3
4 3 4
4 4 1
3 4 1
2
ASK 2 2 3 3
ASK 1 1 4 4
output
15
52
样例对应的图
代码实现：
#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，整条链恢复），那么可以预处理出这个值d[i][j]，表示第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数组，Right[i]表示第i种宝石最右边的位置；
假设我们找到了这个最短子串，设最左边的节点为i，最右边的节点为j，有[i, j]，那么有 i = min_element(Right, Right + 5)。
然后遍历 N*2的字符串，不断更新Right数组和ans即可。
题目二：《袋鼠》
有n个弹簧排成一列，袋鼠起始位置在第一个弹簧；
输入n个数字，代表n个弹簧的力量；
弹簧的力量为5表示可以往后跳最多5个弹簧；
问袋鼠到达第n个弹簧的最小弹跳次数？
dp[i] 表示到达第i个的最小步数； dp[1]=1；
对于第i个数字是a[i]，那么有枚举j， 1<= j <= a[i]
d[i+j]=min(d[i+j], d[i]+1);
表示到达i+j的最优解；
复杂度最多可以到O(N*N)。
优先队列优化：
对dp[i], 打包成pair(i, a[i]) 放入优先队列；
这样每次取出来的都是最小步数，然后判断i+a[j]是否大于等于当前位置，是则更新，不是则丢弃这个解，重新在队列里面取；
扩展
《宝石二》
有一串宝石首尾相连，用一个大写字母表示一个宝石，每个宝石有相应价值；
现在需要从这一串宝石中截取一段宝石，要求这一段宝石包含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。
