[思维][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<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据