[BZOJ4776] [Usaco2017 Open]Modern Art（差分 + 思维？）

传送门

可以预处理出每种颜色的上下左右的位置，这样就框出来了一个个矩形，代表每种颜色分别涂了哪里。

然后用二维的差分。

就可以求出来每个位置至少涂了几次，如果 > 1 的话，就肯定不是先涂的，

如果是1的话，并且不是只有一种颜色，那么也有可能是先涂的，

如果只有一种颜色，并且 n ！= 1，那么一定不是先涂的，如果 n == 1，也就只有一种颜色了，那么它就是先涂的

#include <cstdio>#include <cstring>#include <iostream>#define N 1011using namespace std;int n, cnt, ans;int a[N][N], b[N][N], u[N * N], d[N * N], l[N * N], r[N * N];bool vis[N * N];inline int read()int main()}for(i = 1; i <= n * n; i++)if(u[i] <= 1e9)for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)for(i = 1; i <= n * n; i++)if(!vis[i])ans++;if(cnt == 1 && n != 1) ans;printf("%d\n", ans);return 0;}

上一篇：[BZOJ4994] [Usaco2017 Feb]Why Did the Cow Cross the Road III（树状数组）

下一篇：[BZOJ1419] Red is good（期望DP）