２０１９山东ＡＣＭ省赛Ｃ题
地址
题意很简单 ， 就是让你通过移动位置， 找到一个距离原点最远的一个位置。
但是， 要注意：
这道题第一个显眼的坑就是 ， 数据特别大 ， 不能直接暴力做 ，
第二个点要注意的是，位置最大的点只能出现在第一次循环 或最后一次循环中出现，因为中间的点可能出现的话 ， 那么就会递推到最后一次循环 ， 所以只要考虑最后一次循环位置最大点和第一次循环位置最大的点取最大就行。
第三点，我自己傻子一样的错误， 题上 明明说的是绝对值 相加，我硬是写成了相加后再绝对值
附上蒟蒻AC代码：
#include <iostream>
#include <algorithm>
#include <cmath>
//#include <bits/stdc++.h>
#include <vector>
#include<cstdio>
#include <iomanip>
using namespace std;
int main( )
{
int t ;
cin >>t;
while(t--){
long long a , b;
cin >>a >>b;
string s;
cin >>s;
long long mx=0 , num=0;
long long x=0 , y=0;
for(int i=0;i<a;i++){
if(s[i]=='U'){
y++;
}
else if(s[i]=='D'){
y--;
}
else if(s[i]=='L'){
x--;
}
else if(s[i]=='R'){
x++;
}
if(mx<abs(x)+abs(y) )
mx = abs(x)+abs(y);
}
x =(b-1)*x;
y= (b-1)*y;
long long m=0;
for(int i=0;i<a;i++){
if(s[i]=='U'){
y++;
}
else if(s[i]=='D'){
y--;
}
else if(s[i]=='L'){
x--;
}
else if(s[i]=='R'){
x++;
}
if(m<abs(x)+abs(y) )
m = abs(x)+abs(y);
}
mx = max(m , mx);
cout<<mx<<endl;
}
return 0;
}
附上错误思路的代码：
#include <iostream>
#include <algorithm>
#include <cmath>
//#include <bits/stdc++.h>
#include <vector>
#include<cstdio>
#include <iomanip>
using namespace std;
int main( )
{
int t ;
cin >>t;
while(t--){
long long a , b;
cin >>a >>b;
string s;
cin >>s;
long long mx=0 , num=0;
long long x=0 , y=0;
for(int i=0;i<a;i++){
if(s[i]=='U'){
y++;
num++;
if(mx<abs(x+y) )
mx = abs(x+y);
}
else if(s[i]=='D'){
y--;
num--;
if(mx<abs(x+y) )
mx = abs(x+y);
}
else if(s[i]=='L'){
x--;
num--;
if(mx<abs(x+y) )
mx = abs(x+y);
}
else if(s[i]=='R'){
x++;
num++;
if(mx<abs(x+y) )
mx = abs(x+y);
}
}
//cout<<mx <<endl;
mx = mx + (b-1)*abs(num);
cout<<mx<<endl;
}
return 0;
}
//u (x, y+1)
//d (x , y-1)
//l (x-1 , y)
//r (x+1 , y)
