dede制作的网站挂马,特殊教育学校网站建设方案,万网免费建企业网站,wordpress文章全部导出坐标平面上有一个机器人。最初#xff0c;机器人位于该点#xff08;0,0#xff09; .它的路径被描述为字符串s长度n由字符“L”、“R”、“U”、“D”组成。这些字符中的每一个都对应着一些动作#xff1a; ‘L’#xff08;左#xff09;#xff1a;表示机器人从该点移…坐标平面上有一个机器人。最初机器人位于该点0,0 .它的路径被描述为字符串s长度n由字符“L”、“R”、“U”、“D”组成。这些字符中的每一个都对应着一些动作 ‘L’左表示机器人从该点移动(xy) 切中要害(x−1y); ‘R’右表示机器人从该点移动(xy) 切中要害(x1y); ‘U’向上表示机器人从该点移动(xy) 切中要害(xy1); ‘D’向下表示机器人从该点移动(xy) 切中要害(xy−1) 创建此机器人的公司要求您以某种方式优化机器人的路径。为此您可以删除路径的任何非空子字符串。但这家公司不希望他们的客户注意到机器人行为的变化。这意味着如果在优化之前机器人在该点结束了其路径(xe,ye)然后在优化后即从中删除一些单个子字符串s 机器人也在该点结束其路径(xe,ye)此优化是一个低预算项目因此您需要删除尽可能短的非空子字符串来优化机器人的路径使其路径的端点不会改变。您可能无法优化路径。此外优化后目标路径可能是一个空字符即删除的子字符串是整个字符串s).回想一下子字符串s是可以从以下位置获取的字符串s通过从前缀中删除一定数量的字符可能为零和从后缀中删除一定数量的字符可能为零。例如“LURLLR”的子字符串是“LU”、“LR”、“LURLLR”、“URL”但不是“RR”和“UL”。 你必须回答t 独立的测试用例。 输入 输入的第一行包含一个整数t (1≤吨≤1000 — 测试用例的数量。 下一个2t行描述测试用例。每个测试用例在两行上给出。测试用例的第一行包含一个整数n(1≤N≤2⋅105 — 机器人路径的长度。测试用例的第二行包含一个字符串s 包括n字符 ‘L’ ‘R’ ‘U’ ‘D’ — 机器人的路径。 可以保证n在所有测试用例上不超过2⋅105 (∑n≤2⋅105). 输出 对于每个测试用例请在其上打印答案。如果无法删除机器人路径端点不更改的非空子字符串请打印 -1。否则打印两个整数l和r这样1≤l≤r≤n 删除的子字符串的端点。价值r−l1 应该是尽可能少的。如果有多个答案请打印其中任何一个。
思路:用map记录每一个出现的点,如果某一个点之前出现过,那么就说明这个点和之前那个点中间的过程步骤是可以删除的,同时借助p数组记录每一个点出现时候的初始时刻或是位置
#includeiostream
#includealgorithm
#includemap
#includecstring
#includestring
#define x first
#define y second
using namespace std;;
int main()
{int t;cin t;while (t--) {int n;string s;cin n s;//输入int l -1, r n;//定义边界mappairint, int, int p;//定义每一个点以及他出现的位置pairint, int flag { 0, 0 };//从(0,0)开始走//记录当前机器人走到哪了p[flag] 0;初始化for (int i 0; i n; i){if (s[i] L) --flag.x;if (s[i] R) flag.x;if (s[i] U) flag.y;if (s[i] D) --flag.y;if (p.count(flag))//如果机器人当前位置,如果这个位置之前出现过说明这一段可以删除{if (i - p[flag] 1 r - l 1) {//当前位置和第一次出现的之前差值小于r-l1l p[flag];//左边界r i;//当前i定义为右边界}}p[flag] i 1;}if (l -1)cout -1 endl;elsecout l 1 r 1 endl;//别忘了加1}return 0;
}
