第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）E.Evil Coordinate (分类讨论+模拟)

https://ac.nowcoder.com/acm/contest/21739/E

  • 这题有更简单的做法(枚举UDLR全排列),我用这个分类讨论的方法折腾了2个半小时才终于AC….

思路:

  • 1.首先我们可以想到,给定了一个走法的序列,不管这个序列的排列是怎样,它的终点一定确定了.所以炸弹(mx,my)如果在起点(0,0)或终点(x,y)那结果肯定是$Impossible$.

  • 2.还有一种$Impossible$的情况就是当X轴方向没有步数($Cnt_R=0&&
    Cnt_L=0$)且炸弹在Y轴方向的必经之路上;当Y轴方向没有步数($Cnt_U=0&&
    Cnt_D=0$)且炸弹在X轴方向的必经之路上.

  • 3.除去上面两种,剩余情况都是总能找到一个序列使机器人不经过炸弹的. 我们可以分情况讨论:

    • a.终点不在坐标轴上

      我们将路径简化为两种,先横着走再后竖着走和先竖着走再横着走.

      image-20211013230143511

    这种情况比较简单,只需要判断炸弹是否在任意一条路径上,那么不走这条路径即可.例如:若炸弹在1上,那就走2;若炸弹在2上或者炸弹在其他地方,那就走1.

    • b.终点在坐标轴上

      这种情况看似简单,实则比较复杂.例如:终点在Y轴上,那说明L和R的步数相等.但先L或先R可能会对答案造成影响,所以我们要进行一些判断.例如:炸弹若在X轴下方,那么我们先U后D肯定不会有问题;炸弹若在Y轴左方,那先R和L肯定不会有问题.(会有问题的我们已经在第二种impossible中筛掉了).这里语言描述起来会比较麻烦,直接看代码应该会比较好理解.

  • 4.最后要注意一下正负号的问题,然后把每种情况交代清楚,应该就能AC了.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIII pair<int,PII>
#define PLLL pair<ll,PLL>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

ll mx, my;

bool tong(ll x, ll y) {//判断两个数是否同号
    if (x == 0 || y == 0)return true;
    if (x >= 0 && y >= 0)return true;
    if (x <= 0 && y <= 0)return true;
    return false;

}

void solve() {
    map<char, ll> mp;
    cin >> mx >> my;
    string path;
    cin >> path;
    int len = path.length();
    for (int i = 0; i < len; i++) {
        if (path[i] == 'L')mp['L']++;
        else if (path[i] == 'R')mp['R']++;
        else if (path[i] == 'U')mp['U']++;
        else if (path[i] == 'D')mp['D']++;
    }
    ll x = mp['R'] - mp['L'];//计算终点（一定会到达）
    ll y = mp['U'] - mp['D'];
    //炸弹的位置在终点或起点
    if ((mx == x && my == y) || (mx == 0 && my == 0)) {
        cout << "Impossible\n";
    }
        //只能在Y轴移动，炸弹在必经之路上
    else if ((!mp['L'] && !mp['R']) && (tong(my, y) && abs(my) <= abs(y) && mx == 0)) {
        cout << "Impossible\n";
    }
        //只能在X轴移动，炸弹在必经之路上
    else if ((!mp['U'] && !mp['D']) && (tong(mx, x) && abs(mx) <= abs(x) && my == 0)) {
        cout << "Impossible\n";
    }
    else {
        //L和R最终抵消了
        if (x == 0) {
            string ans;
            if (mx > 0) {//炸弹在Y轴右侧，那么就先走左面
                for (int i = 0; i < mp['L']; i++) ans += 'L';
                if (my < 0) {
                    //炸弹在X轴下侧，那么就先走上面
                    for (int i = 0; i < mp['U']; i++) ans += 'U';
                    for (int i = 0; i < mp['D']; i++) ans += 'D';
                }
                else {
                    for (int i = 0; i < mp['D']; i++) ans += 'D';
                    for (int i = 0; i < mp['U']; i++) ans += 'U';
                }
                for (int i = 0; i < mp['R']; i++) ans += 'R';
            }
            else {
                for (int i = 0; i < mp['R']; i++) ans += 'R';
                if (my < 0) {
                    for (int i = 0; i < mp['U']; i++) ans += 'U';
                    for (int i = 0; i < mp['D']; i++) ans += 'D';
                }
                else {
                    for (int i = 0; i < mp['D']; i++) ans += 'D';
                    for (int i = 0; i < mp['U']; i++) ans += 'U';
                }
                for (int i = 0; i < mp['L']; i++) ans += 'L';
            }
            cout << ans << '\n';
            return;
        }
        //U和D最终抵消了
        if (y == 0) {
            string ans;
            if (my > 0) {
                //炸弹在X轴上侧，那么就先走下面
                for (int i = 0; i < mp['D']; i++) ans += 'D';
                if (mx < 0) {//炸弹在Y轴左侧，那么就先走右面
                    for (int i = 0; i < mp['R']; i++) ans += 'R';
                    for (int i = 0; i < mp['L']; i++) ans += 'L';
                }
                else {
                    for (int i = 0; i < mp['L']; i++) ans += 'L';
                    for (int i = 0; i < mp['R']; i++) ans += 'R';
                }
                for (int i = 0; i < mp['U']; i++) ans += 'U';
            }
            else {
                for (int i = 0; i < mp['U']; i++) ans += 'U';
                if (mx < 0) {
                    for (int i = 0; i < mp['R']; i++) ans += 'R';
                    for (int i = 0; i < mp['L']; i++) ans += 'L';
                }
                else {
                    for (int i = 0; i < mp['L']; i++) ans += 'L';
                    for (int i = 0; i < mp['R']; i++) ans += 'R';
                }
                for (int i = 0; i < mp['D']; i++) ans += 'D';
            }
            cout << ans << '\n';
            return;
        }
        //终点不在坐标轴上，可以通过先横后竖或者先竖后横的方法走
        if ((my == 0 || mx == x)) {//如果炸弹不在先横后竖的走法上，那就走先竖后横
            string ans;
            for (int i = 0; i < mp['U']; i++) ans += 'U';
            for (int i = 0; i < mp['D']; i++) ans += 'D';
            for (int i = 0; i < mp['L']; i++) ans += 'L';
            for (int i = 0; i < mp['R']; i++) ans += 'R';
            cout << ans << '\n';
        }
        else {
            string ans;
            for (int i = 0; i < mp['L']; i++) ans += 'L';
            for (int i = 0; i < mp['R']; i++) ans += 'R';
            for (int i = 0; i < mp['U']; i++) ans += 'U';
            for (int i = 0; i < mp['D']; i++) ans += 'D';
            cout << ans << '\n';
        }
    }

}

int main() {
    ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}