打卡信奥刷题（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的类型。

但他的记忆并不总是准确的。

对于每个操作222，sss可能没有在之前的操作111中出现过。

我们定义两个字符串s1s_1s1​和s2s_2s2​的相似度为∑i=1min⁡{∣s1∣,∣s2∣}[s1,i=s2,i]\sum_{i=1}^{\min\{|s_1|,|s_2|\}} [s_{1,i}=s_{2,i}]∑i=1min{∣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

输入 #1

4 1 aaa 1 2 aa 1 ab 2 2 bb

输出 #1

1 2

说明/提示

（由 ChatGPT 4o 翻译）

C++实现

#include<bits/stdc++.h>usingnamespacestd;intq,x,ans,p;map<string,int>mp;map<string,int>op;structnode{intp,v;node(intp_=-1,intv_=1e9):p(p_),v(v_){}};voiddfs1(string s,intcur){//枚举状态并存入if(cur==5){intcnt=0;for(charc:s)if(c!='%')cnt++;//匹配度if(!mp.count(s)||cnt>mp[s]||(cnt==mp[s]&&x<op[s])){mp[s]=cnt;op[s]=x;}return;}dfs1(s,cur+1);//改变或者不改变chartmp=s[cur];s[cur]='%';dfs1(s,cur+1);s[cur]=tmp;return;}nodedfs2(string s,intcur){if(cur==5){if(mp.count(s))returnnode(mp[s],op[s]);returnnode();}node res=dfs2(s,cur+1);chartmp=s[cur];s[cur]='%';node res2=dfs2(s,cur+1);if(res2.p>res.p||(res2.p==res.p&&res2.v<res.v))res=res2;returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>q;while(q--){into;string s;cin>>o>>s;while(s.size()<5)s+='%';//补全长度if(o==1){cin>>x;dfs1(s,0);}else{node res=dfs2(s,0);cout<<res.v<<'\n';}}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容