//大一老登过来水篇题解

题目大意：给定一个 $n*m$ 的矩阵和一个字符串s，s中包含D,R,?，分别表示下，右，下和右中的任意方向，开始从（1，1）出发，按照s的要求走，要求最后走到(n,m)，求最多能够走到的格子数 数据范围 对于所有数据，保证： t<=5,n+m<4*10^4

考点：预处理前缀/后缀，思维

P1: 首先我们很容易可以想到，如果把？全部看成R，这条路径一定是最靠上的，如果把？全部看成D，那它一定是最向下的，于是我们就可以预处理出每个时间节点所能走出的最大和最小的向下值，分别记为mins,maxs;

for(int i=1;i<=len;i++){
		char c=s[i - 1];
        if (c=='D'){
            mins[i] = mins[i-1]+1;
            maxs[i] = maxs[i-1]+1;
        } else if (c == 'R') {
            mins[i] = mins[i-1];
            maxs[i] = maxs[i - 1];
        } else { 
            mins[i] = mins[i-1]; 
            maxs[i] = maxs[i-1]+1; 
        }
	}

但同时题目中还有一个要求，最后要走到(n,m)点，也就是说，对于每一个s中从后往前数对应的时间,剩余需要走的向下步数，也是固定的，所以我们可以通过预处理后缀的方式求出每一个时间点还需要向下走几格，记为revmins，revmaxs;

for(int i=len;i>=1;i--){
		char c=s[i-1];
        if (c=='D'){
            revmins[i] = revmins[i+1]+1;
            revmaxs[i] = revmaxs[i+1]+1;
        } else if (c=='R'){
            revmins[i]=revmins[i+1];
            revmaxs[i]=revmaxs[i+1];
        } else { 
            revmins[i]=revmins[i+1]; 
            revmaxs[i]=revmaxs[i+1]+1; 
        }
	}

P2: 预处理完成，现在我们需要判断能够走到的格子数 S1: 一种比较朴素的想法是，遍历每一个格子，每个格子的i-1对应已经向下走了几格，n-i对应还需要向下走几格，该格子合法意味着i-1和n-i分别位于对应的max和min之间 代码如下

ll res=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if((i==1&&j==1)||(i==n&&j==m)){
				res++;
				continue;
			}
			if(i-1>=mins[i+j-2]&&i-1<=maxs[i+j-2]&&n-i>=revmins[i+j-1]&&n-i<=revmaxs[i+j-1]){
				res++;
			}
		}
	}
	cout<<res<<"\n";

相信大部分没有通过的同学也是这么想的,但这么交上去的代码会显示时间超限，原因在于$(n+m)\le4*10^4$,而上述代码的时间复杂度在O(nm),极限情况下会来到 $4\times10^8$,同时t=5,相乘足足有 $2*10^9$ 的复杂度，必定会导致超时 也就是说，在这题的数据范围内,遍历每一个格子是不允许的 那么如何不用遍历每一个格子求解呢？ S2: 我们可以遍历时间，从1~(n+m-2),把每一个时间点所能到达的i的最大值和最小值相减再加1，就是该时间节点能到达的点的个数 那么，如何判断i是否合法呢 我们现在假设目前步数为k 条件1：经过k步后，1+mins[k]<=i<=1+maxs[k]; 条件2：还需要走的步数 n-i>=revmins[k+1] n-i<=revmaxs[k+1] ==> n-revmaxs[k+1]<=i<=n-revmins[k+1] 条件3：对于每个i，对应的J=k-i+2; 1<=j<=m; 所以 k+2-m<=i<=k+1;

联立以上三个式子 同大取小，同小取大，每一步判断如果小比大大，不合法，continue; 开始时将res设置成1((1,1)点默认染色) 代码如下

ll res = 1;   
    for (int k = 1; k <= len; ++k) {
        int mindown=mins[k];
        int maxdown=maxs[k];
        int minre=revmins[k + 1];
        int maxre=revmaxs[k + 1];
        int mini=1+mindown;
        int maxi=1+maxdown;
        int minj=1+(k-maxdown);
        int maxj=1+(k-mindown);
        int lowi=max(mini,n-maxre);
        int highi=min(maxi,n-minre);       
        if (lowi>highi) continue;
        int lowij=max(lowi,k+2-m);
        int highij=min(highi,k+1);       
        if (lowij>highij) continue;
        res+=(highij-lowij+1);
}

于是就这样ac啦 全篇代码如下（建议c++选手开时间优化哦）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
	int n,m;
	string s;
	cin>>n>>m;
	cin>>s;
	int len=s.size();
	vector<int>mins(len+1,0),maxs(len+1,0),revmins(len+2,0),revmaxs(len+2,0);
	for(int i=1;i<=len;i++){
		char c=s[i - 1];
        if (c=='D'){
            mins[i] = mins[i-1]+1;
            maxs[i] = maxs[i-1]+1;
        } else if (c == 'R') {
            mins[i] = mins[i-1];
            maxs[i] = maxs[i - 1];
        } else { 
            mins[i] = mins[i-1]; 
            maxs[i] = maxs[i-1]+1; 
        }
	}
	for(int i=len;i>=1;i--){
		char c=s[i-1];
        if (c=='D'){
            revmins[i] = revmins[i+1]+1;
            revmaxs[i] = revmaxs[i+1]+1;
        } else if (c=='R'){
            revmins[i]=revmins[i+1];
            revmaxs[i]=revmaxs[i+1];
        } else { 
            revmins[i]=revmins[i+1]; 
            revmaxs[i]=revmaxs[i+1]+1; 
        }
	}
    
    ll res = 1;   
    for (int k = 1; k <= len; ++k) {
        int mindown=mins[k];
        int maxdown=maxs[k];
        int minre=revmins[k + 1];
        int maxre=revmaxs[k + 1];
        int mini=1+mindown;
        int maxi=1+maxdown;
        int minj=1+(k-maxdown);
        int maxj=1+(k-mindown);
        int lowi=max(mini,n-maxre);
        int highi=min(maxi,n-minre);       
        if (lowi>highi) continue;
        int lowij=max(lowi,k+2-m);
        int highij=min(highi,k+1);       
        if (lowij>highij) continue;
        res+=(highij-lowij+1);
    }
    cout<<res<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}


//Os:大概区域赛2~3题的难度？
//yehyehyeh看出来大学生有多闲了吧hahhhh甚至无聊到回高中写了篇题解