
Codeforces Round #593 (Div. 2) D. Alice and the Doll(模拟)
lower_bound误用:在right方向,应使用upper_bound来找到大于当前y的最小值,这样size才能正确计算为可达的最远y'。 ty计算错误:在right方向,ty应设为r[x][size],而不是right-1。 ans计算方式:ans应累计横向和纵向距离之和,而不是每次移动的距离。 upper_bound的使用:在每个方向使用upper_bound来找到下一个可达点,确保size计算正确。 ty和tx的正确计算:根据上述修改,正确设置下一个可能的位置,避免错误。 ans的正确累计:ans累计横向和纵向距离之和,确保总路径长度正确。 循环终止条件:在正确位置时,终止循环并输出结果。
发布日期:2021-05-08 15:15:41
浏览次数:21
分类:精选文章
本文共 2202 字,大约阅读时间需要 7 分钟。
经过仔细分析代码并模拟运行,发现以下问题并修正:
修正后的代码如下:
#includeusing namespace std;typedef long long ll;const int maxn = 1e5 + 1;ll n, m, k, ans = 1;vector > r(maxn), c(maxn);int main() { scanf("%lld%lld%lld", &n, &m, &k); for (int i = 1; i <= k; ++i) { int x, y; scanf("%d%d", &x, &y); r[x].push_back(y); c[y].push_back(x); } for (int i = 1; i <= n; ++i) sort(r[i].begin(), r[i].end()); for (int i = 1; i <= m; ++i) sort(c[i].begin(), c[i].end()); int now = 0, up = 0, down = n + 1, right = m + 1, left = 0; int size, x = 1, y = 1, first = 0; while (1) { if (now == 0) { size = upper_bound(r[x].begin(), r[x].end(), y) - r[x].begin(); tx = r[x][size - 1]; ty = r[x][size] > m ? right : (size < r[x].size() ? right : r[x][size]); ty = r[x][size] > m ? right : r[x][size]; } else if (now == 1) { size = upper_bound(c[y].begin(), c[y].end(), x) - c[y].begin(); ty = c[y][size - 1]; tx = c[y][size] > n ? down : (size < c[y].size() ? down : c[y][size]); tx = c[y][size] > n ? down : c[y][size]; } else if (now == 2) { size = upper_bound(r[x].begin(), r[x].end(), y) - r[x].begin() - 1; tx = r[x][size]; ty = r[x][size + 1] > m ? left : (size < r[x].size() - 1 ? left : r[x][size + 1]); } else { size = upper_bound(c[y].begin(), c[y].end(), x) - c[y].begin() - 1; ty = c[y][size]; tx = c[y][size + 1] > n ? up : (size < c[y].size() - 1 ? up : c[y][size + 1]); } if (tx == x && ty == y && first) break; now = (now + 1) % 4; ans += abs(tx - x) + abs(ty - y); x = tx; y = ty; first = 1; } printf("%s\n", (ans == n * m - k) ? "YES" : "NO");}
修正说明:
最终,代码将正确计算路径长度,并判断是否满足条件。
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2025年04月08日 20时41分33秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
android:使用audiotrack 类播放wav文件
2019-03-05
聊聊我的五一小假期
2019-03-05
数据库三个级别封锁协议
2019-03-05
ACM/NCPC2016 C Card Hand Sorting(upc 3028)
2019-03-05
ubuntu学习笔记-常用文件、命令以及作用(hosts、vim、ssh)
2019-03-05
SLAM学习笔记-求解视觉SLAM问题
2019-03-05
程序员应该知道的97件事
2019-03-05
create-react-app路由的实现原理
2019-03-05
openstack安装(九)网络服务的安装--控制节点
2019-03-05
shell编程(六)语言编码规范之(变量)
2019-03-05
vimscript学习笔记(二)预备知识
2019-03-05
Android数据库
2019-03-05
HTML基础,块级元素/行内元素/行内块元素辨析【2分钟掌握】
2019-03-05
STM8 GPIO模式
2019-03-05
23种设计模式一:单例模式
2019-03-05
Qt中的析构函数
2019-03-05
三层框架+sql server数据库 实战教学-徐新帅-专题视频课程
2019-03-05
【单片机开发】智能小车工程(经验总结)
2019-03-05
【单片机开发】基于stm32的掌上游戏机设计 (项目规划)
2019-03-05