2021-12-29

A. Robot Cleaner

题目详情

一个机器人清洁器被放置在一个长方形房间的地板上,四周是墙壁。地板由 n n n 行和 m m m 列组成。地板的行从上到下从 1 1 1 n n n 编号,地板的列从左到右从 1 1 1 m m m 编号。第 r r r 行和第 c c c 列交叉处的单元格表示为 ( r , c ) (r,c) (r,c)。机器人的初始位置为 ( r b , c b ) (r_b,c_b) (rb,cb)

在一秒内,机器人移动dr行和dc列,即一秒后,机器人从单元格 ( r , c ) (r,c) (r,c)移动到 ( r + d r , c + d c ) (r+d_r,c+d_c) (r+dr,c+dc)。初始 d r = 1 d_r=1 dr=1 d c = 1 d_c=1 dc=1。如果移动方向有垂直墙(左墙或右墙),则在移动前反射 d c d_c dc,所以dc的新值为 − d c -d_c dc。并且如果有水平墙(上墙或下墙), d r d_r dr 在移动之前被反射,所以 d r d_r dr 的新值是 − d r -d_r dr

每一秒(包括机器人开始移动之前的那一刻),机器人都会清理与其位置位于同一行或同一列的每个单元格。在 ( r d , c d ) (r_d,c_d) (rd,cd) 处只有一个脏单元格。机器人的工作是清洁那个肮脏的牢房。

第一个示例的插图。蓝色弧线是机器人。红星是目标脏单元格。机器人每秒清理一行和一列,用黄色条纹表示。

给定地板尺寸 n 和 m,机器人的初始位置 ( r b , c b ) (r_b,c_b) (rb,cb) 和脏单元的位置 ( r d , c d ) (r_d,c_d) (rd,cd),找到机器人完成工作的时间。

输入
每个测试包含多个测试用例。第一行包含测试用例数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1t104)。测试用例的描述如下。

一个测试用例只有一行,包含六个整数 n , m , r b , c b , r d , 和 c d ( 1 ≤ n , m ≤ 100 , 1 ≤ r b , r d ≤ n , 1 ≤ c b , c d ≤ m ) n, m, rb, cb, rd, 和 cd (1≤n,m≤100, 1≤r_b,r_d≤n, 1≤c_b,c_d≤m) n,m,rb,cb,rd,cd(1n,m100,1rb,rdn,1cb,cdm) —房间的大小、机器人的初始位置和脏物单元的位置。

输出
对于每个测试用例,打印一个整数——机器人清洁脏单元的时间。我们可以证明机器人最终总是会清理脏的单元格。

input
5
10 10 6 1 2 8
10 10 9 9 1 1
9 8 5 6 2 1
6 9 2 2 5 8
2 2 1 1 2 1
output
7
10
9
3
0

题解:

让我们考虑这个问题的一维问题:有 n 个单元格,排成一排。 机器人位于第 x 个单元格,脏单元格位于第 y 个单元格。 每一秒,机器人都会在其位置清洁细胞。 机器人最初每秒向右移动 1 个单元格。 如果移动方向上没有单元格,则将反映其方向。 机器人清洁脏单元的最短时间是多少?

有两种情况需要考虑:

如果 x ≤ y x≤y xy,那么答案是 y − x y-x yx 。 机器人直接进入肮脏的牢房。
否则,如果 x > y x>y x>y,则机器人需要先到正确的端点,然后再回到脏单元。 到达正确的端点需要 n − x n-x nx秒钟,而从那个单元到脏单元需要 n − y n-y ny秒钟。 因此,这种情况的答案是 2 ⋅ n − x − y 2⋅n-x-y 2nxy
回到我们最初的问题,我们可以把它分成两个一维版本来解决。 这是通过将机器人和脏单元的位置投影到 x x x y y y轴上来完成的,如下所示。

通过这样做,我们可以看到我们可以清洁脏单元,当且仅当机器人的一个投影可以到达脏单元。 因此,答案是两个子问题的答案之间的最小值。

【code】:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 5;
void solve()
{
   
    ll n, m, rb, cb, rd, cd, count = 0, dr = 1, dc = 1;
    cin >> n >> m >> rb >> cb >> rd >> cd;

    while (1)
    {
   
        if (rb == rd || cb == cd)
        {
   
            break;
        }
        if (dr == 1 && rb == n)
        {
   
            dr = -1;
        }
        else if (dr == 1 && rb == 1)
        {
   
            dr = 1;
        }
        if (dc == 1 && cb == m)
        {
   
            dc = -1;
        }
        else if (dc == -1 && cb == 1)
        {
   
            dc = 1;
        }
        rb += dr;
        cb += dc;
        count++;
    }
    cout << count << endl;
}

int main()
{
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
int main() {
   
    int ntest;
    cin >> ntest;
    while (ntest--) {
   
        int n, m, rb, cb, rd, cd;
        cin >> n >> m >> rb >> cb >> rd >> cd;
        cout << min(
            rb <= rd ? rd - rb : 2 * n - rb - rd,
            cb <= cd ? cd - cb : 2 * m - cb - cd
        ) << '\n';
    }
    return 0;
}

B. Game on Ranges

题目详情:

爱丽丝和鲍勃玩以下游戏。 Alice 有一组不相交的整数范围的集合 S,最初只包含一个范围 [1,n]。在一轮中,Alice 从集合 S 中选择一个范围 [l,r] 并要求 Bob 在该范围内选择一个数字。 Bob 选择一个数字 d (l≤d≤r)。然后 Alice 从 S 中删除 [l,r] 并将范围 [l,d−1](如果 l≤d−1)和范围 [d+1,r](如果 d+1≤r )。当集合 S 为空时,游戏结束。我们可以证明每场比赛的回合数正好是 n。

玩完游戏后,Alice 记住了她从集合 S 中选择的所有范围 [l,r],但 Bob 不记得他选择的任何数字。但是 Bob 很聪明,他知道他可以从 Alice 的范围中找出他的数字 d,所以他向你寻求编程技巧方面的帮助。

给定 Alice 选择的范围列表 ([l,r]),对于每个范围,帮助 Bob 找到 Bob 选择的数字 d。

我们可以证明 Bob 总是有一种独特的方式来为 Alice 选择的有效范围列表选择他的号码。

输入
每个测试包含多个测试用例。第一行包含测试用例数 t (1≤t≤1000)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 n (1≤n≤1000)。

接下来的 n 行中的每一行都包含两个整数 l 和 r (1≤l≤r≤n),表示 Alice 在某个点选择的范围 [l,r]。

请注意,范围没有按特定顺序给出。

保证所有测试用例的n之和不超过1000,每个测试用例的范围均来自有效游戏。

输出
对于每个测试用例打印 n 行。每行应包含三个整数 l、r 和 d,表示对于 Alice 的范围 [l,r],Bob 选择了数字 d。

您可以按任何顺序打印这些行。我们可以证明答案是唯一的。

不需要在每个测试用例之后打印一个新行。示例输出中的新行仅用于可读性。

input:
4
1
1 1
3
1 3
2 3
2 2
6
1 1
3 5
4 4
3 6
4 5
1 6
5
1 5
1 2
4 5
2 2
4 4


output:
1 1 1

1 3 1
2 2 2
2 3 3

1 1 1
3 5 3
4 4 4
3 6 6
4 5 5
1 6 2

1 5 3
1 2 1
4 5 5
2 2 2
4 4 4

题解:

【code】:


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 5;
void solve()
{
   
    int n;
    cin >> n;
    map<pair<int, int>, bool> mp;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++)
    {
   
        cin >> l[i] >> r[i];
        mp[{
   l[i], r[i]}] = 1;
    }
    for (int i = 0; i < n; i++)
    {
   
        for (int j = l[i]; j <= r[i]; j++)
        {
   
            if ((j == l[i] || mp[{
   l[i], j - 1}]) && (j == r[i] || mp[{
   j + 1, r[i]}]))
            {
   
                cout << l[i] << " " << r[i] << " " << j << endl;
                break;
            }
        }
    }
}

int main()
{
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}