P1580 yyy loves Easter_Egg I【洛谷算法习题】

P1580 yyy loves Easter_Egg I网页链接P1580 yyy loves Easter_Egg I题目背景Soha 的出题效率着实让人大吃一惊。OI数学化学的题目都出好了物理的题还没有一道。于是Huntfireabsi2011redbag 对 soha 进行轮番炸准备炸到 soha 出来不料人群中冲出了个 kkksc03……题目描述yyy loves OIHuntfireyyy loves Mathsredbagyyy loves Chemistryabsi2011对 yyy loves Physicssoha进行轮番炸轰炸按照顺序进行顺序为 Huntfireredbagabsi2011。现在这一题中我们不考虑太复杂的队形形式。我们认为只要这一句内含有且恰好含有一次的人和上一句话一样就算为队形。比如以下也视为队形yyy loves OI : yyy loves Microelectronicyyy loves Maths : yyy loves Microelectronic 我佩服soha的出题效率yyy loves OI : yyy loves Microelectronic 1yyy loves Chemistry : 1 yyy loves Microelectronic若 的人与第一个人不同就算队形被打破。若这个人在队形被打破之前出来发言了或者就是他打破队形了就算油炸成功了。若油炸成功输出Successful 某某某 attempt若队形被破坏先输出Unsuccessful 某某某 attempt再输出队形第一次被破坏的行数与第一次破坏队形的人的id \text{id}id。如果队形一直没被打破就先输出Unsuccessful 某某某 attempt再输出队形的长度最后输出Good Queue Shape。p.s.yyy loves Microelectronic 是 kkksc03输入格式N NN行为轰炸开始后的一段消息记录每行一条消息。消息格式「消息发送者:消息内容」每行消息长度不超过1000 10001000。中文用拼音代替输出格式若油炸成功输出Successful 某某某 attempt若队形被破坏第一行输出Unsuccessful 某某某 attempt接下来一行输出队形第一次被破坏的行数第三行输出第一次破坏队形的人的id \text{id}id。如果队形一直没被打破就先输出Unsuccessful 某某某 attempt再输出队形的长度最后输出Good Queue Shape。输入输出样例 #1输入 #1yyy loves OI : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Maths : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Chemistry : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Microelectronic : ni men wu liao me yyy loves OI : yyy loves Physics wo pei fu ni de chu ti xiao lv输出 #1Unsuccessful yyy loves Physics attempt 4 yyy loves Microelectronic输入输出样例 #2输入 #2yyy loves OI : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Maths : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Chemistry : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves OI : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Maths : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Chemistry : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves OI : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Maths : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Chemistry : yyy loves Physics wo pei fu ni de chu ti xiao lv yyy loves Physics : ni men gou le输出 #2Successful yyy loves Physics attempt说明/提示yyy loves Physics 我佩服你的出题效率此题仅吐槽 soha纪念出题者的队形此队形长达91 9191行。对于100 % 100\%100%的数据,每行消息长度≤ \le≤10 3 10^3103。保证行数不超过5 × 10 4 5\times 10^45×104保证输入文件大小不超过4 MB 4\text{MB}4MB保证第一个说话的一定在 某人保证大家的名字都是yyy loves *** \text{yyy loves ***}yyy loves ***的格式保证每个人说的话中没有:保证第一个说话的一定艾特了一个人且只 了一个人保证第一个说话的一定不会艾特自己保证文件结束一定有一行空行方便你判定文件结束并不保证后面说话的艾特了几个人 然而艾特人数不为一个人视为破坏队形并不保证后面说话是否会反复艾特同一个人并不保证被炸的人一定破坏队形并不保证这一题是或不是压轴题并不保证这一套比赛存在压轴题并不保证下一套比赛和这一套比赛一样水并不保证群里除了这4 44个人和 kkksc03 以外没有别人了并不保证你没 AC 这题的情况下吐槽 soha 不会出事儿AC 了可以吐槽 soha 一句soha 不会介意。解题思路本题是一个字符串匹配与协议检查的模拟问题要求根据给定的消息记录判断“轰炸队形”是否被遵守以及是否成功炸出目标人物。核心在于逐行解析每条消息的发送者、数量与对象并与第一行的“目标人物”进行比对按照规则输出对应结果。1. 规则抽象队形发起第一条消息必定包含恰好一个 的人即为“目标人物”设为target之后的每一条消息需保持队形。队形保持条件消息中恰好出现一次该的人与target完全一致。终止条件炸成功在队形被破坏之前target本人发言无论发言内容是否含只要发送者是target队形破坏某条消息的发送者不是target但消息不符合队形保持条件无、多个或的人不是target自然结束输入读完遇到空行仍未出现以上两种情况。输出要求炸成功输出Successful target attempt队形破坏输出Unsuccessful target attempt破坏行号破坏者 ID自然结束输出Unsuccessful target attempt队形持续行数Good Queue Shape。2. 算法实现读取并解析首条消息找到的位置提取其后的连续非空格字符串作为target。逐行处理后续消息行号从 2 开始累计获取发送者sender冒号前的字符串去掉冒号前可能存在的空格。若sender target直接输出成功信息并结束。查找的位置若无则队形破坏输出破坏信息当前行号与sender并结束。若有提取后的人名mention并临时屏蔽该后再检查是否还有。若存在多个或mention ! target队形破坏输出破坏信息并结束。读完仍未终止输出自然结束信息队形行数为总行数追加Good Queue Shape。3. 复杂度分析时间复杂度每行消息长度≤ 1000 \le 1000≤1000最多5 × 10 4 5\times 10^45×104行每条消息的扫描和子串操作均为O ( l e n ) O(len)O(len)总体O ( 总字符数 ) ≈ 5 × 10 7 O(\text{总字符数}) \approx 5\times 10^7O(总字符数)≈5×107在限制内可轻松完成。空间复杂度仅需存储当前行字符串和少量变量O ( 1 ) O(1)O(1)额外空间。总结逐行模拟严格按规则检查发送者、次数与对象。边界情况目标本人发言、无、多、错人均在逐行分析中覆盖最终根据不同条件输出对应格式的结果。代码简要说明getnm(p)函数从字符串位置p之后提取的人名以空格为界。init()函数读取第一行定位并提取target存入全局变量nm。主循环读取一行若为空或长度≤ 1 \le 1≤1则退出循环解析发送者cur和的位置若发送者为target成功退出若无破坏退出否则提取对象判断是否唯一且匹配target不满足则破坏退出。正常退出输出Unsuccessful、总行数、Good Queue Shape。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;string s,t,nm;ll l;voidgetnm(ll p){boolf0;ll cnt0;for(ll ip11;il;i){if(s[i] ){cnti-p-1;break;}}ts.substr(p1,cnt);}voidinit(){getline(cin,s);s[s.size()-1] ;ll ps.find();ls.size();getnm(p);nmt;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);init();ll ql1;while(getline(cin,s)s.size()1){ql;s[s.size()-1] ;ls.size();ll ps.find();ll p2s.find(:);string curs.substr(0,p2-1);if(nmcur){coutSuccessful nm attemptendl;return0;}if(p-1){if(nmcur){coutSuccessful nm attemptendl;return0;}else{coutUnsuccessful nm attemptendl;coutqlendl;coutcurendl;return0;}}else{getnm(p);s[p].;if(s.find()!-1||t!nm){ll p2s.find(:);string curs.substr(0,p2-1);coutUnsuccessful nm attemptendl;coutqlendl;coutcurendl;return0;}}}coutUnsuccessful nm attemptendl;coutqlendl;coutGood Queue Shapeendl;return0;}