Codeforces Round #593 (Div. 2) D. Alice and the Doll(模拟)
发布日期:2021-05-08 15:15:41 浏览次数:21 分类:精选文章

本文共 2202 字,大约阅读时间需要 7 分钟。

经过仔细分析代码并模拟运行,发现以下问题并修正:

  • lower_bound误用:在right方向,应使用upper_bound来找到大于当前y的最小值,这样size才能正确计算为可达的最远y'。
  • ty计算错误:在right方向,ty应设为r[x][size],而不是right-1。
  • ans计算方式:ans应累计横向和纵向距离之和,而不是每次移动的距离。
  • 修正后的代码如下:

    #include 
    using 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");
    }

    修正说明:

  • upper_bound的使用:在每个方向使用upper_bound来找到下一个可达点,确保size计算正确。
  • ty和tx的正确计算:根据上述修改,正确设置下一个可能的位置,避免错误。
  • ans的正确累计:ans累计横向和纵向距离之和,确保总路径长度正确。
  • 循环终止条件:在正确位置时,终止循环并输出结果。
  • 最终,代码将正确计算路径长度,并判断是否满足条件。

    上一篇:Codeforces Round #590 (Div. 3) E. Special Permutations(数学)
    下一篇:Codeforces Round #553 (Div. 2) B. Dima and a Bad XOR(异或+思维)

    发表评论

    最新留言

    留言是一种美德,欢迎回访!
    [***.207.175.100]2025年04月08日 20时41分33秒