Codeforces Round #504 E. Down or Right
2024-08-26 03:34:35
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;
}
最新文章
- 认识Android Service
- ArrayList,Vector,LinkedList
- 判断一个数num是否是2的幂(乐视题)
- Jasmine入门(结合示例讲解)
- Chrome RenderText分析(2)
- MongoDB 语法(转)
- js常识
- Dynamic Programming (DP) 问题总结
- 自己写loader
- ASP.NET- 播放视频代码
- oc拨打电话方法
- PropertyGrid自定义控件
- 反射、Attribute
- Excel中如何截取字符串中指定字符后的部分字符
- spring mvc+mybatis 构建 cms + 实现UC浏览器文章功能
- 某公司的C#面试题
- string logo online customization
- 使用vue.js实现checkbox的全选和多个的删除功能
- 工作流模式 (zhuan)
- ubuntu卸载virtualbox