2020ICPC 南京 Evil Coordinate（模拟，构造）

本文主要是介绍2020ICPC 南京 Evil Coordinate（模拟，构造），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最后是队友过的，我写的相对复杂
题意：
给一个移动的序列（L,R,U,D代表左右上下），
重排其使得移动的过程不会经过$(X,Y)$。
设终点为$(ex,ey)$
思路：
首先特判掉特殊点为终点或者为原点的情况，
分为两种情况：

• 特殊点不在坐标轴上，此时如果$ex=X$,那么先用$L,R$使其只剩下一个，然后用光U,D，再使用剩下的L,R。如果$ex!=X$，那么先用$L,R$，再用$U,D$。
• 特殊点在坐标轴上，仅考虑在X轴上的情况，Y轴上的情况类似考虑。
• • 如果只存在$L,R$，那么如果有这个条件则无解：(abs(ex) >= abs(X) && ((ex > 0 && X > 0) || (ex < 0 && X < 0)))。否则如果$L>R$，则按照$LRLRLR..LLL$的方式输出，如果$R>L$则按照$RLRLRLRL...RRR$的方式输出。如果$L=R$，则如果$X<0$，则按照$RLRLRL...$输出，否则按照$LRLRLR$的方式输出。
• • 如果只存在$U,D$，则直接输出$U,D$
• • 如果同时存在$L,R$和$U,D$，那么当$U!=D$的时候全部输出，否则输出到$U,D$剩下一个，再输出$L,R$，最后输出剩下的那个$U,D$。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <assert.h>using namespace std;
const int maxn = 1e6+10;
char s[maxn];
int L,R,U,D;
int ex,ey;
int X,Y;
int all;
int rx,ry;
void Print(char x,int cnt) {for(int i = 1;i <= cnt;i++) {printf("%c",x);}
}void PrintAll() {Print('L',L);Print('R',R);Print('U',U);Print('D',D);
}void PrintSwap(char x,char y,int cnt) {for(int i = 1;i <= cnt;i++) {printf("%c%c",x,y);}
}void solve1() {if(X) {if(all == 1) {if(L || R) {if(abs(ex) >= abs(X) && ((ex > 0 && X > 0) || (ex < 0 && X < 0))) {printf("Impossible");} else if(L < R) {PrintSwap('R','L',L);Print('R',R - L);} else if(L > R) {PrintSwap('L','R',R);Print('L',L - R);} else if(L == R) {if(X < 0) {PrintSwap('R','L',L);} else {PrintSwap('L','R',L);}}} else if(U || D) {PrintAll();}} else {int flag = 0;if(U != D) {Print('U',U);Print('D',D);} else {Print('U',U - 1);Print('D',D);flag = 1;}Print('L',L);Print('R',R);if(flag) {Print('U',1);}}} else if(Y) {if(all == 1) {if(L || R) {PrintAll();} else if(U || D) {if(abs(ey) >= abs(Y) && ((ey > 0 && Y > 0) || (ey < 0 && Y < 0))) {printf("Impossible");} else if(U < D) {PrintSwap('D','U',U);Print('D',D - U);} else if(U > D) {PrintSwap('U','D',D);Print('U',U - D);} else if(U == D) {if(Y < 0) {PrintSwap('U','D',U);} else {PrintSwap('D','U',U);}}}} else {int flag = 0;if(L != R) {Print('L',L);Print('R',R);} else {Print('L',L - 1);Print('R',R);flag = 1;}Print('U',U);Print('D',D);if(flag) {Print('L',1);}}}
}void solve2() {if(ex == X) {if(X > 0) {Print('L',L);Print('R',R - 1);Print('U',U);Print('D',D);Print('R',1);} else if(X < 0) {Print('L',L - 1);Print('R',R);Print('U',U);Print('D',D);Print('L',1);}} else {Print('L',L);Print('R',R);Print('U',U);Print('D',D);}
}int main() {int T;scanf("%d",&T);while(T--) {scanf("%d%d",&X,&Y);rx = 0,ry = 0;scanf("%s",s + 1);int n = strlen(s + 1);L = 0,R = 0,U = 0,D = 0;ex = 0,ey = 0;for(int i = 1;i <= n;i++) {if(s[i] == 'L') {L++;ex--;} else if(s[i] == 'R') {R++;ex++;} else if(s[i] == 'U') {U++;ey++;} else if(s[i] == 'D') {D++;ey--;}}all = (L || R) + (U || D);//        printf("DEBUG: %d\n",all);if(X == 0 && Y == 0) {printf("Impossible");} else if(ex == X && ey == Y) {printf("Impossible");} else if(X == 0 || Y == 0) { //如果特殊点在坐标轴上solve1();} else {solve2();}printf("\n");}
}

这篇关于2020ICPC 南京 Evil Coordinate（模拟，构造）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---