CSP历年真题题解思考过程 —— 2P7072 [CSP-J 2020] 直播获奖100pts解法P5658 [CSP-S 2019] 括号树20pts解法55pts解法70pts解法100ptsP7073 [CSP-J 2020] 表达式50pts解法100pts解法P7072 [CSP-J 2020] 直播获奖题干链接100pts解法注意到数据规模中每个选手成绩不超过600分容易想到桶存储。for(int32_ti1;in;i){slmax(1,int32_t(floor(i*w*1.0f/100)));cinai;b[ai];for(int32_ti600;i0;i--){sl-b[i];if(sl0){couti ;break;}}}P5658 [CSP-S 2019] 括号树题干链接20pts解法观察数据范围发现前4个点中f i i − 1 f_i i-1fii−1这说明树呈一条链并且因为数据不大我们可以尝试对于每个节点i ii枚举1 11~i ii中所有字串来统计所需的k i k_iki。boolable(int32_tf,int32_tt){stackboolss;for(int32_tif;it;i){if(s[i]()ss.push(true);else{if(ss.empty())returnfalse;elsess.pop();}}returnss.empty();}int32_tmain(){// 省略部分代码...int32_tans{};for(int32_ti1;in;i){int32_ttans{};for(int32_tl1;li;l){for(int32_trl;ri;r){if(able(l,r)){tans;}}}ans^(tans*i);}coutans;// 省略部分代码...}55pts解法很容易发现我们重复处理了部分子串那我们就要考虑使用其他线性的办法重新实现。我们规定d p i dp_idpi为以第i ii个字符结尾的字串中的括号串那么就有k i Σ d p i k_i \Sigma dp_ikiΣdpi。对于每一个新的括号对我们令p o s t postpost为括号对开始的下标。新括号对自己是合法括号对再加上之前的那么就有d p i d p p o s t − 1 1 dp_i dp_{post-1}1dpidppost−11最后就能求出对应i ii的k i k_iki了。stackint64_tst;for(int64_ti1;in;i){if(s[i](){st.push(i);}else{if(!st.empty()){int64_tpostst.top();st.pop();dp[i]dp[post-1]1;}}}for(int64_ti1;in;i){sumdp[i];ans^(sum*i);}coutans;记得使用int64_t。70pts解法其他测试点没有特殊性质说明我们必须按序遍历整棵树所以选择dfs。测试点8~10中有n ≤ 2000 n\leq2000n≤2000完全足够我们枚举所有子串来计算。boolable(int32_tf,int32_tt){stackboolss;for(int32_tif;it;i){if(str[i]()ss.push(true);else{if(ss.empty())returnfalse;elsess.pop();}}returnss.empty();}voiddfs(int32_tn){str.push_back(s[n]);sum0;for(int32_tl1;lint32_t(str.size());l){for(int32_trl;rint32_t(str.size());r){if(able(l-1,r-1)){sum;}}}ans^(sum*n);for(constautoi:son[n]){dfs(i);}str.pop_back();}100pts到这里我们已经快结束了。只需要把上面实现的dp套用在dfs上只要在退出节点时恢复栈即可。voiddfs(int64_tn,int64_tacc){str.push_back(s[n]);sum0;int64_tpost;if(s[n](){st.push(n);}else{if(!st.empty()){postst.top();st.pop();dp[n]dp[f[post]]1;}else{post-1;}}ans^((accdp[n])*n);for(constautoi:son[n]){dfs(i,accdp[n]);}str.pop_back();if(s[n](){st.pop();}else{if(post!-1){st.push(post);}}}P7073 [CSP-J 2020] 表达式题干链接50pts解法30%的数据中n , q ≤ 1000 n, q\leq1000n,q≤1000完全支撑我们进行在线的计算。另外20%的数据中表达式仅含与或者或运算只要对初值进行简单的标记处理即可得到。100pts解法不难发现在线计算可能导致重复计算了多个相同节点结合该题目中计算结果仅为1或者0考虑分析变量值对结果的影响性。显然我们有∀ x .0 ∧ x 0 , 1 ∨ x 1 \forall x. 0 \wedge x 0, 1 \vee x 1∀x.0∧x0,1∨x1那么先尝试以初值计算表达式结果然后分析每个与和或节点。对于与节点若某方计算得0那么将“无影响”下放到另一方下所有变量节点或节点同理。那么询问时若有要取反的变量“无影响”那么直接输出之前计算的结果。否则就是对结果有影响取反输出即可。structnode{int32_tkind;// 0: id, 1: neg. 2: conj, 3: disjint32_tid;shared_ptrnodeleft,right;booluseless{false};boolval{false};node(int32_tkind,int32_tid,shared_ptrnodeleftnullptr,shared_ptrnoderightnullptr):kind(kind),id(id),left(left),right(right){}};stacknodees;string src;stringstream ss;string tok;int32_tn;arraybool,100005init,ul;int32_tq;int32_tqi;voidprint(shared_ptrnodep){switch(p-kind){case0:{coutxp-id;break;}case1:{cout!(;print(p-left);cout);break;}case2:{cout(;print(p-left);cout)(;print(p-right);cout);break;}case3:{cout(;print(p-left);cout)|(;print(p-right);cout);break;}}}voideval(shared_ptrnodep){switch(p-kind){case0:{p-valinit[p-id];break;}case1:{eval(p-left);p-val!p-left-val;break;}case2:{eval(p-left);eval(p-right);p-valp-left-valp-right-val;break;}case3:{eval(p-left);eval(p-right);p-valp-left-val||p-right-val;break;}}}voiduseless(shared_ptrnodep){if(p-useless)return;switch(p-kind){case0:{ul[p-id]true;break;}case1:{p-uselesstrue;useless(p-left);break;}case2:{p-uselesstrue;useless(p-left);useless(p-right);break;}case3:{p-uselesstrue;useless(p-left);useless(p-right);break;}}}voidopt(shared_ptrnodep){switch(p-kind){case0:{break;}case1:{opt(p-left);break;}case2:{opt(p-left);opt(p-right);if(!p-left-val)useless(p-right);if(!p-right-val)useless(p-left);break;}case3:{opt(p-left);opt(p-right);if(p-left-val)useless(p-right);if(p-right-val)useless(p-left);break;}}}int32_tmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);getline(cin,src);sssrc;while(sstok){if(tok[0]x){es.emplace(0,stoi(tok.substr(1,tok.size()-1)));}if(tok[0]!){autoleftstd::make_sharednode(es.top());es.pop();es.emplace(1,-1,left);}if(tok[0]){autoleftstd::make_sharednode(es.top());es.pop();autorightstd::make_sharednode(es.top());es.pop();es.emplace(2,-1,left,right);}if(tok[0]|){autoleftstd::make_sharednode(es.top());es.pop();autorightstd::make_sharednode(es.top());es.pop();es.emplace(3,-1,left,right);}}cinn;for(int32_ti1;in;i){cininit[i];}autoastmake_sharednode(es.top());eval(ast);opt(ast);cinq;for(int32_ti1;iq;i){cinqi;if(ul[qi]){coutast-val;}else{cout!ast-val;}cout\n;}return0;}
)
