P7912 [CSP-J 2021] 小熊的果篮

题干链接

70分模拟解法

我们只需要从左往右遍历所有水果模拟就行了。遇到一个水果，如果他和上个水果颜色不同，那就是队头，则取走，然后打上标记说明已经取走，下次只要取第一个颜色不同且没打标记的水果就行。

while(r<n){l=-1;for(int32_ti=1;i<=n;i++){if(l!=int32_t(a[i])&&!u[i]){++r;u[i]=true;l=a[i];cout<<i<<" ";}}cout<<"\n";}

AC解法

容易发现，我们每次循环都重复经过了大量已经被取走的水果，这就是超时的元凶。结合题意，考虑使用双端队列来存储“块”，每轮遍历所有块，依次取出队头输出。然后再次遍历所有块，空的扔了，好的和上个比较，如果同色就直接合并，异色才插入。这样就能让常数降下来一点，不会退化到O ( n 2 ) \mathcal{O}(n^2)O(n2)。

int32_tl=-1;array<bool,200005>a;deque<deque<int32_t>>v;for(int32_ti=1;i<=n;i++){cin>>a[i];if(l!=int32_t(a[i])){l=a[i];v.emplace_back();}v.back().push_back(i);}while(!v.empty()){for(auto&i:v){int32_th=i.front();cout<<h<<" ";i.pop_front();}cout<<"\n";deque<deque<int32_t>>vv;while(!v.empty()){autonow=v.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));}}v=move(v)}

P8815 [CSP-J 2022] 逻辑表达式

题干链接

AC解法

对于这种题，一个通用的解法就是先建树，然后在树上分析。

怎么建树？这里，我们介绍一下“递归下降算法”。简单说，就是将解析某种运算（这里是或，与，括号和字面量）的过程单独拆分成函数，然后按照优先级在每种解析函数中调用下一级的解析函数（这里是或调用与获得左右子树，与调用括号和字面量获得左右子树，括号调用或获取括号内内容）来构造这一级的树。

structexpr{int32_tk;// 0: num 1: and 2: or 3: parenbooln;shared_ptr<expr>l,r;expr(int32_tk,booln,shared_ptr<expr>l,shared_ptr<expr>r):k(k),n(n),l(l),r(r){}};int32_tpos;shared_ptr<expr>p_or();shared_ptr<expr>p_val(){if(s[pos]=='0'||s[pos]=='1'){autoval=std::make_shared<expr>(0,s[pos]-'0',nullptr,nullptr);++pos;returnval;}elseif(s[pos]=='('){++pos;autoinner=make_shared<expr>(3,0,p_or(),nullptr);++pos;returninner;}}shared_ptr<expr>p_and(){autol=p_val();while(s[pos]=='&'){++pos;autor=p_val();l=make_shared<expr>(1,0,l,r);}returnl;}shared_ptr<expr>p_or(){autol=p_and();while(s[pos]=='|'){++pos;autor=p_and();l=make_shared<expr>(2,0,l,r);}returnl;}

看到p_or中，我们用一个while反复的调用下一级的函数，然后构造之后放到左边，这是因为或是左结合的运算，我们可以始终把较左边的运算放在树的左子上，而与运算也是同理。括号中，我们忽略了优先级，调用了最高级的或运算，这正是“括号先算”的运算特性。

得到了语法树之后，我们就可以自上而下地遍历整棵树。对于一个字面量树，我们不需要执行任何操作，他不需要求值也不会产生短路。对于一个与树，我们先求值它的左子树，如果为假那就说明有短路了，直接将自己也设为假然后返回，如果为真那就无事发生，求值右子树即可。或运算差不多，只不过是看左子树是否为真。对于括号，直接求值内部即可。

int32_ts_and,s_or;voiddfs(shared_ptr<expr>e){if(e->k==0){return;}if(e->k==1){dfs(e->l);if(!e->l->n){e->n=false;s_and++;return;}dfs(e->r);e->n=e->r->n;}if(e->k==2){dfs(e->l);if(e->l->n){e->n=true;s_or++;return;}dfs(e->r);e->n=e->r->n;}if(e->k==3){dfs(e->l);e->n=e->l->n;}}