C++笔试强训day41

目录

1.棋子翻转

2.宵暗的妖怪

3.过桥

---

1.棋子翻转

链接https://www.nowcoder.com/practice/a8c89dc768c84ec29cbf9ca065e3f6b4?tpId=128&tqId=33769&ru=/exam/oj

（简单题）对题意进行简单模拟即可：

class Solution {
public:int dx[4] = { 0, 0, 1, -1 };int dy[4] = { 1, -1, 0, 0 };vector<vector<int> > flipChess(vector<vector<int>>& A,vector<vector<int> >& f) {for (auto e : f) {int x = e[0] - 1, y = e[1] - 1;for (int i = 0; i < 4; ++i) {int a = x + dx[i];int b = y + dy[i];if (a >= 0 && a < 4 && b >= 0 && b < 4 && A[a][b] == 0)A[a][b] = 1;else if (a >= 0 && a < 4 && b >= 0 && b < 4 && A[a][b] == 1)A[a][b] = 0;}}return A;}
};

2.宵暗的妖怪

链接https://ac.nowcoder.com/acm/problem/213484

线性dp问题，难点是分析它的状态转移方程：

分析后发现：

dp[i] 与前面很多状态有关，如果强行这样求解，则需要两层for循环，又由于题目的数据范围很大，因此一定会超时。

因此，需要去思考将后面的多个状态变换成一个状态（类似于完全背包中需要解决的问题，不过这个更简单），观察后易发现，后面的状态不就等价于dp[i - 1]吗，然后一层一层递推

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;int n;
LL arr[N];
LL dp[N];int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> arr[i];for (int i = 3; i <= n; i++){dp[i] = max(dp[i - 1], dp[i - 3] + arr[i - 1]);}cout << dp[n] << endl;return 0;
}

即，也可看作是打家劫舍变种问题

3.过桥

链接https://ac.nowcoder.com/acm/problem/229296

贪心、求最短路径（因为每条边的权值都为1）

#include <iostream>
using namespace std;const int N = 2010;
int n;
int arr[N];int bfs()
{int left = 1, right = 1;int ret = 0;while (left <= right){ret++;int r = right;for (int i = left; i <= right; i++){r = max(r, arr[i] + i);if (r >= n){return ret;}}left = right + 1;right = r;}return -1;
}int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> arr[i];cout << bfs() << endl;return 0;
}