首页 > 其他 > 详细

Codeforces Round #504 E. Down or Right

时间:2018-08-18 23:24:04      阅读:199      评论:0      收藏:0      [点我收藏+]

Codeforces Round #504 E. Down or Right

题目描述:交互题。 有一个\(n \times n\)的方阵,有一些格子是障碍,从\((1, 1)\)出发,只能向右向下走,能走到\((n, n)\),你有\(4n\)次询问,每次询问\((r_1, c_1)\)能否走到\((r_2, c_2)\),但这两个点的曼哈顿距离要大于\(n-1\),最后输出一条从\((1, 1)\)\((n, n)\)的路径。

solution
\((1, 1)\)出发,优先向下走,向下走能到\((n, n)\)就向下走,走到对角线。然后从\((n, n)\)出发,优先向左走,\((1, 1)\)能到左边的点就向左走,走到对角线,这样构造能保证最终在对角线的点一定重合。
因为优先向下走能保证\(D_1-R_1\)最大,那后面一半的\(R_2-D_2=(n-1-R_1)-(n-1-D_1)=D_1-R_1\)最大,而优先向左走正是保证\(R_2-D_2\)最大,因此对角线的点一定重合。

时间复杂度:\(O(2n)\)

#include <bits/stdc++.h>
using namespace std;

int n;
vector<char> ans;
char st[10];

bool ask(int r1, int c1, int r2, int c2)
{
    printf("? %d %d %d %d\n", r1, c1, r2, c2);
    fflush(stdout);
    scanf("%s", st);
    return st[0]==‘Y‘;
}
void solve()
{
    scanf("%d", &n);
    int x=1, y=1;
    for (int i=1; i<=n-1; ++i)
        if (ask(x+1, y, n, n)) x++, ans.push_back(‘D‘);
        else y++, ans.push_back(‘R‘);
    
    x=n, y=n;
    for (int i=1; i<=n-1; ++i)
        if (ask(1, 1, x, y-1)) y--, ans.push_back(‘R‘);
        else x--, ans.push_back(‘D‘);

    printf("! ");
    for (int i=0; i<n-1; ++i) putchar(ans[i]);
    for (int i=n*2-2-1; i>=n-1; --i) putchar(ans[i]);
    puts("");
    fflush(stdout);
}
int main()
{
    solve();
    return 0;
}

Codeforces Round #504 E. Down or Right

原文:https://www.cnblogs.com/GerynOhenz/p/9498978.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!