打卡信奥刷题（3471）用C++实现信奥题 P10564 [ICPC 2024 Xi‘an I] Rubbish Sorting

P10564 [ICPC 2024 Xi’an I] Rubbish Sorting题目描述Bob 有很多垃圾。有一天他想要对它们进行分类。对于每一件垃圾其类型用一个正整数表示。他有qqq个操作。对于每个操作可能是以下两种操作之一。1 s x他告诉你名为sss的垃圾类型为xxx。2 s他想询问你垃圾sss的类型。但他的记忆并不总是准确的。对于每个操作222sss可能没有在之前的操作111中出现过。我们定义两个字符串s1s_1s1​和s2s_2s2​的相似度为∑i1min⁡{∣s1∣,∣s2∣}[s1,is2,i]\sum_{i1}^{\min\{|s_1|,|s_2|\}} [s_{1,i}s_{2,i}]∑i1min{∣s1​∣,∣s2​∣}​[s1,i​s2,i​]。这里所有字符串的索引从111开始。对于一个字符串sss其类型是与sss相似度最大的字符串的类型在所有之前操作111中出现过的字符串中。如果有多个字符串与sss的相似度都最大那么sss的类型是这些字符串类型中的最小值。现在他希望你解决这个问题。输入格式第一行包含一个整数q(1≤q≤3×105)q(1\le q\le 3\times 10^5)q(1≤q≤3×105)表示操作的数量。接下来的qqq行包含操作每行一个。它们对应于题目中给出的描述。保证对于每个操作222在它之前至少有一个操作111。但有些垃圾会有多种类型你可以将其视为你读到的最小类型。垃圾的名称仅由小写拉丁字母组成。1≤∣s∣≤5,1≤x≤1091 \le |s| \le 5, 1 \le x \le 10^91≤∣s∣≤5,1≤x≤109。输出格式对于每个操作222你应该在单独的一行中输出一个整数即垃圾sss的类型。输入输出样例 #1输入 #14 1 aaa 1 2 aa 1 ab 2 2 bb输出 #11 2说明/提示由 ChatGPT 4o 翻译C实现#includebits/stdc.husingnamespacestd;intq,x,ans,p;mapstring,intmp;mapstring,intop;structnode{intp,v;node(intp_-1,intv_1e9):p(p_),v(v_){}};voiddfs1(string s,intcur){//枚举状态并存入if(cur5){intcnt0;for(charc:s)if(c!%)cnt;//匹配度if(!mp.count(s)||cntmp[s]||(cntmp[s]xop[s])){mp[s]cnt;op[s]x;}return;}dfs1(s,cur1);//改变或者不改变chartmps[cur];s[cur]%;dfs1(s,cur1);s[cur]tmp;return;}nodedfs2(string s,intcur){if(cur5){if(mp.count(s))returnnode(mp[s],op[s]);returnnode();}node resdfs2(s,cur1);chartmps[cur];s[cur]%;node res2dfs2(s,cur1);if(res2.pres.p||(res2.pres.pres2.vres.v))resres2;returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinq;while(q--){into;string s;cinos;while(s.size()5)s%;//补全长度if(o1){cinx;dfs1(s,0);}else{node resdfs2(s,0);coutres.v\n;}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容