竟然是青题，我想了两个小时...

我真的不知道这道题该怎么快速想到思路，因为按照中间的那个点来选还是太神了。如果有能更快想到的方法希望能指出。

我看到这道题，第一反应是感觉思路挺多的。

首先肯定是先手搓看一下有没有规律。

我找了 20+min20^+min 发现规律全是错的，只有 n≤4n\le 4 的时候直接贪心是对的。

二分图/网络流很容易想到，但是复杂度...还是算了。但过程中我们容易发现这道题的一个比较关键的性质：一个点最多有两种可能的组成方法。

然后去想 dp，发现没有办法进行 1∗31*3 的大小的转移，这个思路好像也进行不下去。

于是就在草稿纸上一直画。会画出类似这种的图案（用数字代替字母）：

C++
         1
  123   12
 123   123
123    23
       3
       1  
  1
 123
 23
 3

比如这几个，我们需要找找有没有规律.

我们看最下面那一个，可以发现，我们如果以中间那个为枚举的基准，可能是很有前途的，然后我们可以发现一些性质（有用的 feihua）：

  • 一个中心点可以经过一个横着的和竖着的。

  • 能够相互影响的只有斜着的，按照枚举顺序在当前点之前的只有右上角那一个。能影响到的也只有左下角那一个。

然后就可以推出有用的结论：

  • 一个点能不能横着/竖着有自身，和右上角是横着/竖着决定。

然后就可以想到，我们可以记录下当前点能否横着/竖着，然后该怎么放就让左下角的点决定。

于是就能写出来类似 dp 的贪心代码。

我感觉考后的思路会比考试时候的思路稍微清晰一点。反正这道题做起来真的有点看“灵机一动”。

看看我考场怎么挂的 1313：

C++
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char a[3010][3010],b[3010][3010];
bool ok[3010][3010][2];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
  //freopen 正确
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j],b[i][j]=a[i][j];
	n=m=max(n,m);
	int ans=0;
	if(n<=4&&m<=4){
		for(int i=1;i<=n;i++){
			for(int j=1;j+2<=n;j++)if(a[j][i]=='R'&&a[j+1][i]=='G'&&a[j+2][i]=='W'){
				a[j][i]=a[j+1][i]=a[j+2][i]='/';
				ans++;
			}
			for(int j=1;j+2<=n;j++)if((a[i][j]=='R'&&a[i][j+1]=='G'&&a[i][j+2]=='W')){
				a[i][j]=a[i][j+1]=a[i][j+2]='/';
				ans++;
			}
		}
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=b[i][j];
		cout<<ans<<endl;
//		return 0;
	}
	ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]!='G')continue;
			if(a[i][j-1]=='R'&&a[i][j+1]=='W')ok[i][j][0]=1;
			if(a[i-1][j]=='R'&&a[i+1][j]=='W')ok[i][j][1]=1;
			if(ok[i-1][j+1][1]==1&&ok[i-1][j+1][0]==0){
				ok[i][j][0]=0;
			}
			if(ok[i-1][j+1][0]==1&&ok[i-1][j+1][1]==0){
				ok[i][j][1]=0;
			}
			if(ok[i][j][0]||ok[i][j][1])ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
首先我们可以先把用了一定不会更劣的情况用了 
第一列和第一行可以直接用掉 
然后第二行和第二列，这种顺序感觉没有问题 
nm 不同就取 max 不影响答案 

感觉像 dp，但是我又不会转移，这玩意儿有上下两种 

哦，这样是错的 
暴力一点，把所有的 RGW 弄出来，网络流，这样显然会 TLE 
这个图有一个性质，一个点最多在两个 RGW 上面 
然后我们可以尝试中间点 G？ 
就是每一种直接匹配中间点 G， 

嗯，这道题既然没有让输出方案数，会不会有更直接的结论？ 
重合一个答案少 1 
先写一下。 
cao，这个结论显然是错的 

我觉得这道题可以用神经网络做...只是我不会而已 
因为这道题神经网络可以训练出来比较优秀的数据，然后应该可以过 
但正解肯定不是了 


等等，如果按照刚刚的匹配中心点，那么从上往下贪心匹配一定是可以的吧 
也就是按照第二个的遍历到的顺序为优先级？ 
这样的话可以证明，横着和竖着都只有一个冲突的，也就是我们可以记录他是否可以横着/竖着 


*/