欢迎点此阅读QvQ

250

Solution

把−1分别替换为0,1,2来判断答案是否变化即可。简单粗暴

Code

#include
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
LL gao(vector<int> a) {stack S;int n &＃61; a.size();for (int i &＃61; 0; i <100; &＃43;&＃43;i) S.push(0);for (int i &＃61; 0; i if (!a[i]) {LL x &＃61; S.top();S.pop();LL y &＃61; S.top();S.pop();S.push(x &＃43; y);}else S.push(a[i]);}return S.top();
}
struct Suminator {int findMissing(vector <int> a, int S) {int n &＃61; a.size();int p;for (int i &＃61; 0; i if (a[i] &＃61;&＃61; -1) p &＃61; i;a[p] &＃61; 0;LL t &＃61; gao(a);if (t &＃61;&＃61; S) return 0;a[p] &＃61; 1;LL u &＃61; gao(a);a[p] &＃61; 2;LL v &＃61; gao(a);if (u &＃61;&＃61; v) return -1;if (u <&＃61; S) return S - u &＃43; 1;return -1;}
};

500

Description

求将地图染成2个凸连通块的方案数

Solution

这是道比较有趣的题，首先发现，如果有一段连续的格子被染成同一颜色，在以后的行上，被同色染的格子数一定非递增或非递减，且会确定以后行的状态。于是可以dp&＃xff0c;大概就是dp到第i行连续j个格子被染成同一颜色&＃xff0c;当前状态是非递增还是非递减还是尚未确定。记忆化搜索可能好写一点。

Code

#include //dp
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N &＃61; 55, M &＃61; 1e9 &＃43; 7;
int n, m;
int dp[N][N][3][2][2];
bool bw[N][N], wb[N][N];
int f(int x, int y, int dir, int ok1, int ok2) {if (x &＃61;&＃61; n) {if (y &＃61;&＃61; m && dir &＃61;&＃61; 2) return 0;return ok1 &＃43; ok2;}int &t &＃61; dp[x][y][dir][ok1][ok2];if (~t) return t;t &＃61; 0;for (int num &＃61; 0; num <&＃61; m; &＃43;&＃43;num) {if (dir &＃61;&＃61; 0 && num 1 && num > y) continue;int ndir &＃61; dir;if (dir &＃61;&＃61; 2 && num 1;if (dir &＃61;&＃61; 2 && num > y) ndir &＃61; 0;if (x &＃61;&＃61; 0) ndir &＃61; 2;if (y &＃61;&＃61; m && num &＃61;&＃61; 0) continue;int t1 &＃61; ok1, t2 &＃61; ok2;if (!bw[x][num]) t1 &＃61; 0;if (!wb[x][num]) t2 &＃61; 0;(t &＃43;&＃61; f(x &＃43; 1, num, ndir, t1, t2)) %&＃61; M;}return t;
}
struct TwoConvexShapes {int countWays(vector <string> grid) {n &＃61; grid.size(), m &＃61; grid[0].size();memset(dp, -1, sizeof(dp));for (int i &＃61; 0; i for (int j &＃61; 0; j <&＃61; m; &＃43;&＃43;j) {bw[i][j] &＃61; 1;for (int k &＃61; 0; k if (grid[i][k] &＃61;&＃61; &＃39;W&＃39;) bw[i][j] &＃61; 0;for (int k &＃61; j; k if (grid[i][k] &＃61;&＃61; &＃39;B&＃39;) bw[i][j] &＃61; 0;wb[i][j] &＃61; 1;for (int k &＃61; 0; k if (grid[i][k] &＃61;&＃61; &＃39;B&＃39;) wb[i][j] &＃61; 0;for (int k &＃61; j; k if (grid[i][k] &＃61;&＃61; &＃39;W&＃39;) wb[i][j] &＃61; 0;}int ans &＃61; 0;(ans &＃43;&＃61; f(0, 0, 2, 1, 1)) %&＃61; M;return ans;}
};