# 程序员进阶之算法练习（八）附两道搜狐笔试题

### 正文

• 为了不剧透，把对题目的总结放到最后面。

### A

``` 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";
}```

### B

``` 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;```

### C

``` 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;
}```

### D

``` 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);
}
}
}
}```

### E

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;

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];

int x1, y1, x2, y2;
Ask(int x1, int y1, int x2, int y2):x1(x1), y1(y1), x2(x2), y2(y2){};
};

char ch[10];

inline int lowbit(int x) {
return x & -x;
}

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;
while (len--) {
int x, y, 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') {
}
else {
int x1, y1, x2, y2;
}
}

for (int i = 0; i < k; ++i) {
for (int j = 0; j < g[i].size(); ++j) {
}
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) {
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 {
}
}

return 0;
}```

### 总结

• A题是简单题；
• B题是简单题；
• C题是构造题；
• D题是DFS；
• E题是数据结构+离线处理；

### 附加题

#### 题目二：《袋鼠》

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)。

```input
8
AFBCFFDE
1 2 3 4 5 6 7 8
output
11```

```input
5
1 2 3 4 5
output
9```

172 篇文章88 人订阅

0 条评论

## 相关文章

42580

10830

14230

586100

### 42:出书最多

42:出书最多 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 假定图书馆新进了m（10 ≤ m ≤ 999）本图书，它们...

29250

### 1647: [Usaco2007 Open]Fliptile 翻格子游戏

1647: [Usaco2007 Open]Fliptile 翻格子游戏 Time Limit: 5 Sec  Memory Limit: 64 MB Subm...

29560

44260

### Python Algorithms - C5 Traversal

Traversal就是遍历，主要是对图的遍历，也就是遍历图中的每个节点。对一个节点的遍历有两个阶段，首先是发现(discover)，然后是访问(visit)。遍...

10410

36970

7320