廊坊建设局网站6,网站推广书,长沙做推广的公司有多少,thinkphp微网站开发正题
题目链接:https://loj.ac/p/3005 题目大意
有一个长度为nnn的括号串SSS#xff0c;其中包括[]和两种括号类型#xff0c;一个合法的括号串要求同类型的括号一一对应。
你每次可以询问SSS中的一个字符并且传递一个[0,222)[0,2^{22})[0,222)的数字到下一次。
…正题
题目链接:https://loj.ac/p/3005 题目大意
有一个长度为nnn的括号串SSS其中包括[]和两种括号类型一个合法的括号串要求同类型的括号一一对应。
你每次可以询问SSS中的一个字符并且传递一个[0,222)[0,2^{22})[0,222)的数字到下一次。
你的程序每次只知道字符串长度nnn和上一次传递过来的数字最开始时是000你需要在150001500015000次内得到这个字符串是否为一个合法括号串。
1≤n≤1001\leq n\leq 1001≤n≤100 解题思路
很有趣的题目。
我们需要知道的信息只有这个括号串是否合法考虑怎么把什么信息编码进[0,222)[0,2^{22})[0,222)内。
考虑这样一个算法流程我们先找到一个 ‘[’ 或者 ‘’然后开始往后找它对应的那个括号。
此时一个合法括号串有两种可能
下一个是和它对应的括号此时这个部分的匹配就结束了。下一个也是 ‘[’ 或者 ‘’ 此时我们需要去匹配这个新的左括号之后知道它右括号的位置在继续从这个位置去匹配前面那个左括号。
也就是考虑当一个匹配结束的时候假设位置为yyy考虑怎么返回到前一个还未匹配的左括号xxx那里。显然[x1,y][x1,y][x1,y]这一段括号序列都合法了也就是括号类型也一一对应了那么我们直接往前跑遇到一个左括号就−1-1−1一个右括号就111那第一个和为−1-1−1的位置就是我们需要的位置同时我们还需要带一个位置yyy的信息回去。
那么现在我们需要储存的信息就是当前的位置AAA带回去的位置信息BBB当前的和CCC还有目前的状态DDD。
状态分444种
寻找新的左括号中往回走找之前的左括号中匹配左括号 [ 中匹配左括号 中
这样的状态数就是4×n3≤2224\times n^3\leq 2^{22}4×n3≤222可以通过本题。 code
#includecstdio
#includecstring
#includealgorithm
#include memory.h
using namespace std;//D 0:往后寻找新的 1:往前找 2:前面是[ 3:前面是(
//A:目前所在的位置 B:之前反回来的位置 C:和
int Memory(int N, int M) {int AM%100,BM/100%100,CM/10000%100,DM/1000000;if(AN)return 0;char cGet(A1);if(!D){if(AN-1)return -2;if(c||c])return -2;if(c[)return (A1)2000000;if(c)return (A1)3000000;}else if(D1){if(c||c[)C--;else C;if(C-1){if(BN-1)return -2;return (B1)20000001000000*(c);}if(A0BN-1)return -1;if(A0)return B1;return (A-1)B*100C*100001000000; }else if(D2){if(c])return AA*1001000000;else if(c)return -2;if(AN-1)return -2;return (A1)20000001000000*(c);}else{if(c)return AA*1001000000;else if(c])return -2;if(AN-1)return -2;return (A1)20000001000000*(c);}return M;
}
