[思维][meet in the middle] codeforces 1023 E

其实也不是正常意义上的meet in the middle了，只是这个处理的思想有点像。（似乎每次做交互题都会卡？

自己做的时候是理解错题目意思了，以为图上只要联通的点都能返回YES，但是其实是按照他的限制下走的时候能走到才能返回YES。这样的话需要考虑的问题就比较好处理了。。。。一开始理解的那种的话根本没法在4*n次询问的限制下做出来。

因为右下半矩阵的路线只能通过询问（1，1）到该点的可行性来获得，左上半矩阵的路线只能通过询问（n,n）到该点的可行性获得，要想获得完整的可行路线只能在交界重合的地方处理，也就是反对角线上的方块。为了使得两个方向的推法能够走到同样的对角线点上，可以采取极端策略，左边的就尽量往下走，右边的尽量往左走，这样两种操作到最后的结果都是相同的，会走到对角线上的极端点（最左下的可行点），这时候就保证了两条路能够接上。

#include

using namespace std;

typedef long long LL;
const int maxn=2e5+10;
const int mod=1e9+7;
string str;
bool query(int r1,int c1,int r2,int c2)
{
    cout<<"? "<>str;
    if(str=="YES")
        return 1;
    else
        return 0;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vectorans;
    int row=1,col=1;
    while(row+col rans;
    row=n,col=n;
    while(row+col>n+1)
    {
        if(query(1,1,row,col-1))
        {
            rans.push_back('R');
            col--;
        }
        else
        {
            rans.push_back('D');
            row--;
        }
    }
    cout<<"! ";
    for (int i=0;i=0;i--)
        cout<