【无标题】CSP历年真题题解思考过程 ——6

CSP历年真题题解思考过程 —— 6P7912 [CSP-J 2021] 小熊的果篮70分模拟解法AC解法P8815 [CSP-J 2022] 逻辑表达式AC解法P7912 [CSP-J 2021] 小熊的果篮题干链接70分模拟解法我们只需要从左往右遍历所有水果模拟就行了。遇到一个水果如果他和上个水果颜色不同那就是队头则取走然后打上标记说明已经取走下次只要取第一个颜色不同且没打标记的水果就行。while(rn){l-1;for(int32_ti1;in;i){if(l!int32_t(a[i])!u[i]){r;u[i]true;la[i];couti ;}}cout\n;}AC解法容易发现我们每次循环都重复经过了大量已经被取走的水果这就是超时的元凶。结合题意考虑使用双端队列来存储“块”每轮遍历所有块依次取出队头输出。然后再次遍历所有块空的扔了好的和上个比较如果同色就直接合并异色才插入。这样就能让常数降下来一点不会退化到O ( n 2 ) \mathcal{O}(n^2)O(n2)。int32_tl-1;arraybool,200005a;dequedequeint32_tv;for(int32_ti1;in;i){cina[i];if(l!int32_t(a[i])){la[i];v.emplace_back();}v.back().push_back(i);}while(!v.empty()){for(autoi:v){int32_thi.front();couth ;i.pop_front();}cout\n;dequedequeint32_tvv;while(!v.empty()){autonowv.front();v.pop_front();if(now.empty())continue;if(!vv.empty()a[now.front()]a[vv.back().front()]){vv.back().insert(vv.back().end(),range(now));}else{vv.push_back(move(now));}}vmove(v)}P8815 [CSP-J 2022] 逻辑表达式题干链接AC解法对于这种题一个通用的解法就是先建树然后在树上分析。怎么建树这里我们介绍一下“递归下降算法”。简单说就是将解析某种运算这里是或与括号和字面量的过程单独拆分成函数然后按照优先级在每种解析函数中调用下一级的解析函数这里是或调用与获得左右子树与调用括号和字面量获得左右子树括号调用或获取括号内内容来构造这一级的树。structexpr{int32_tk;// 0: num 1: and 2: or 3: parenbooln;shared_ptrexprl,r;expr(int32_tk,booln,shared_ptrexprl,shared_ptrexprr):k(k),n(n),l(l),r(r){}};int32_tpos;shared_ptrexprp_or();shared_ptrexprp_val(){if(s[pos]0||s[pos]1){autovalstd::make_sharedexpr(0,s[pos]-0,nullptr,nullptr);pos;returnval;}elseif(s[pos](){pos;autoinnermake_sharedexpr(3,0,p_or(),nullptr);pos;returninner;}}shared_ptrexprp_and(){autolp_val();while(s[pos]){pos;autorp_val();lmake_sharedexpr(1,0,l,r);}returnl;}shared_ptrexprp_or(){autolp_and();while(s[pos]|){pos;autorp_and();lmake_sharedexpr(2,0,l,r);}returnl;}看到p_or中我们用一个while反复的调用下一级的函数然后构造之后放到左边这是因为或是左结合的运算我们可以始终把较左边的运算放在树的左子上而与运算也是同理。括号中我们忽略了优先级调用了最高级的或运算这正是“括号先算”的运算特性。得到了语法树之后我们就可以自上而下地遍历整棵树。对于一个字面量树我们不需要执行任何操作他不需要求值也不会产生短路。对于一个与树我们先求值它的左子树如果为假那就说明有短路了直接将自己也设为假然后返回如果为真那就无事发生求值右子树即可。或运算差不多只不过是看左子树是否为真。对于括号直接求值内部即可。int32_ts_and,s_or;voiddfs(shared_ptrexpre){if(e-k0){return;}if(e-k1){dfs(e-l);if(!e-l-n){e-nfalse;s_and;return;}dfs(e-r);e-ne-r-n;}if(e-k2){dfs(e-l);if(e-l-n){e-ntrue;s_or;return;}dfs(e-r);e-ne-r-n;}if(e-k3){dfs(e-l);e-ne-l-n;}}