8月27日总结 - 洛谷保存站

## P2689 东南西北

1. **时间复杂度**：

$ O(T) $

2. **错误原因**：

开了x1和y1的全局变量导致报错

2. **正确思路**：

看看每次按照输入的方位移动是否会接近目标位置

3. **正确代码**：

```cpp
#include <bits/stdc++.h>
using namespace std;

int ax1, ay1, ax2, ay2, ans, T;
char c;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> ax1 >> ay1 >> ax2 >> ay2 >> T;
	while (T--) {
		if (ax1 == ax2 && ay1 == ay2) {
			cout << ans;
			return 0;
		} 
		cin >> c;
		if (c == 'E') {
			if (abs(ay2 - (ay1 + 1)) < abs(ay1 - ay2)) {
				ans++;
				ay1 += 1;
			}
		} else if (c == 'S') {
			if (ax2 - abs((ax1 - 1)) < abs(ax1 - ax2)) {
				ans++;
				ax1 -= 1;
			}
		} else if (c == 'W') {
			if (abs(ay2 - (ay1 - 1)) < abs(ay1 - ay2)) {
				ans++;
				ay1 -= 1;
			}
		} else if (c == 'N') {
			if (ax2 - abs((ax1 + 1)) < abs(ax1 - ax2)) {
				ans++;
				ax1 += 1;
			}
		}
	}
	cout << -1;
	return 0;
} 
```

## P9012 Moo Operations B

1. **时间复杂度**：

$ O(T) $

1. **错误原因**：

情况没有处理完整，而且写了会直接导致挂掉的代码 `s.size() - 1`

2. **正确思路**：

判断每一种题目中存在的可行的解，并用一个 ` ans ` 记录最小需要的修改的值即可

3. **正确代码**：
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
	int t, ans;
	string s;
	cin >> t;
	while (t--) {
		ans = INT_MAX;
		cin >> s;
		int len = s.size(), c;
		for (int i = 1; i < len - 1; i++) {
			if (s[i] != 'O') {
				continue;
			}
			if (s[i - 1] == 'M' && s[i + 1] == 'O') {
				c = len - 3;
			}
			if (s[i - 1] == 'M' && s[i + 1] == 'M') {
				c = len - 2;
			}
			if (s[i - 1] == 'O' && s[i + 1] == 'O') {
				c = len - 2;
			}
			if (s[i - 1] == 'O' && s[i + 1] == 'M') {
				c = len - 1;
			}
			ans = min(ans, c);
		}
		if (ans == INT_MAX) {
			cout << -1 << endl;
		} else {
			cout << ans << endl;
		}
	}
	return 0;
}
```

## T659293 可可口乐

1. **时间复杂度**：

$ O(n) $

2. **正确思路**：

通过交换任意两个不同位置的字符生成新的状态，然后存储各状态及对应的交换次数，并且记录已访问状态避免重复处理，接着按顺序遍历所有可能状态，因此第一个到达目标字符串 "cocacola" 时的交换次数即为最少次数。

3. **正确代码**：
```cpp
#include <bits/stdc++.h>
using namespace std;

const string str = "cocacola";

int main() {
    string start;
    cin >> start;
    
    if (start == str) {
        cout << 0 << endl;
        return 0;
    }
    
    queue<pair<string, int>> q;
    set<string> vis;
    
    q.push( {start, 0)} );
    vis.insert(start);
    
    while (!q.empty()) {
        pair<string, int> cur = q.front();
        q.pop();
        
        string cnt = cur.first;
        int steps = cur.second;
        
        for (int i = 0; i < 8; i++) {
            for (int j = i + 1; j < 8; j++) {
                string next = cnt;
                swap(next[i], next[j]);
                
                if (next == str) {
                    cout << steps + 1 << endl;
                    return 0;
                }
                
                if (vis.find(next) == vis.end()) {
                    vis.insert(next);
                    q.push(make_pair(next, steps + 1));
                }
            }
        }
    }
    
    return 0;
}
```

## T659951 磁铁迷宫

1. **时间复杂度**：

$ O(nm) $

2. **正确思路**：

先预处理 ` a ` 数组，用来后续查找非磁性格子，然后从每一个非磁性格子开始` dfs `来查找，每次判断是否本回合跑过了(使用 `  vis `数组统计)，或相邻的格子是磁铁，或者以前来过了，否则就继续走，并且 ` cnt++ ` 表示多走了一个格子，` ans `每次搜索完毕后更新答案

3. **正确代码**：
```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e3 + 10;

int n, m, cnt, color, ans = 1, a[N][N];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int vis[N][N];

void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || xx > n || yy < 1 || yy > m) {
			continue;
		} 
        if (vis[xx][yy] == color) {
			continue;
		} 
        if (a[xx][yy] == 1) {
		} 
        if (a[xx][yy] == 2) {
            cnt++; 
            vis[xx][yy] = color;
            continue;
        }
        if (vis[xx][yy] != 0) {
			continue;
		} 
        vis[xx][yy] = color;
        cnt++;
        dfs(xx, yy);
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
            char c; cin >> c;
            if (c == '#') {
				a[i][j] = 1;
			} 
            else a[i][j] = 0;
        }
	} 
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
            if (a[i][j] == 1) {
				continue;
			} 
            if (a[i - 1][j] == 1 || a[i + 1][j] == 1 || a[i][j - 1] == 1 || a[i][j + 1] == 1) {
            	a[i][j] = 2;
			} 
        }
	}
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
    		if (vis[i][j] == 0 && a[i][j] == 0) { 
                color++;
                cnt = 1;
                vis[i][j] = color;
                dfs(i, j);
                ans = max(ans, cnt);
            }
		} 
	} 
    cout << ans;
    return 0;
}
```

## T659324 图像处理

1. 时间复杂度：

$ O(输入的字符的数量) $

2. 正确思路：

先用一个二维字符串去输入，因为输入是没有空格且可能会有字符。在输入的同时算出将其中的十六进制转为十进制，次数加一。然后用 sort 排序，并用十六进制输出前十六个。如果不是前十六个，则绝对值相减找出最近的。

3. 正确代码：
```cpp
#include <bits/stdc++.h>
using namespace std;

int n, sp[100][100];
string a[20], x;
char tt[] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };

struct sz {
	int t, z;
	string s;
	char xx;
}p[10000];

void z(string x, int j, int i) {
	int sum = 0;
	if (x[1] <= '9' && x[1] >= '0') {
		sum += (x[1] - '0') * 1;
	} else {
		sum += (x[1] - 'A' + 10) * 1;
	}
	if (x[0] <= '9' && x[0] >= '0') {
		sum += (x[0] - '0') * 16;
	} else {
		sum += (x[0] - 'A' + 10) * 16;
	}
	p[sum].t++;
	p[sum].s = x;
	sp[i][j] = sum;
}

bool cmp(sz a, sz b) {
	if (a.t != b.t) {
		return a.t > b.t;
	}
	else return a.z < b.z;
}

int main() {
	cin >> n;
	for (int i = 0; i <= 256; i++) {
		p[i].z = i, p[i].t = 0;
	}
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		for (int j = 0; j < a[i].size(); j += 2) {
			x += a[i][j], x += a[i][j + 1];
			z(x, j / 2, i);
			x = "";
		}
	}
	sort(p, p + 256, cmp);
	for (int i = 0; i < 16; i++) {
		cout << p[i].s;
		p[i].xx = tt[i];
	}
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < a[i].size() / 2; j++) {
			int mm = 300, wz;
			for (int q = 0; q < 16; q++) {
				if (abs(sp[i][j] - p[q].z) < mm) {
					wz = q, mm = abs(sp[i][j] - p[q].z);
				}
			}
			cout << p[wz].xx;
		}
		cout << endl;
	}
	return 0;
}
```

正在渲染内容...