企业官网建设流程全解析

P1580 yyy loves Easter_Egg I

网页链接

P1580 yyy loves Easter_Egg I

题目背景

Soha 的出题效率着实让人大吃一惊。OI，数学，化学的题目都出好了，物理的题还没有一道。于是，Huntfire，absi2011，redbag 对 soha 进行轮番炸，准备炸到 soha 出来，不料，人群中冲出了个 kkksc03……

题目描述

yyy loves OI（Huntfire），yyy loves Maths（redbag），yyy loves Chemistry（absi2011）对 yyy loves Physics（soha）进行轮番炸，轰炸按照顺序进行，顺序为 Huntfire，redbag，absi2011。

现在这一题中，我们不考虑太复杂的队形形式。我们认为只要这一句内含有且恰好含有一次@，@的人和上一句话一样就算为队形。

比如以下也视为队形：

• yyy loves OI : @yyy loves Microelectronic
• yyy loves Maths : @yyy loves Microelectronic 我佩服soha的出题效率
• yyy loves OI : @yyy loves Microelectronic +1
• yyy 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

输入 #1

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 Microelectronic : ni men wu liao me yyy loves OI : @yyy loves Physics wo pei fu ni de chu ti xiao lv

输出 #1

Unsuccessful @yyy loves Physics attempt 4 yyy loves Microelectronic

输入输出样例 #2

输入 #2

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 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

输出 #2

Successful @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. 算法实现

1. 读取并解析首条消息：
   • 找到@的位置，提取其后的连续非空格字符串作为target。
2. 逐行处理后续消息（行号从 2 开始累计）：
   • 获取发送者sender：冒号前的字符串（去掉冒号前可能存在的空格）。
   • 若sender == target，直接输出成功信息并结束。
   • 查找@的位置：
     • 若无@，则队形破坏，输出破坏信息（当前行号与sender）并结束。
     • 若有@，提取@后的人名mention，并临时屏蔽该@后再检查是否还有@。若存在多个@或mention != target，队形破坏，输出破坏信息并结束。
3. 读完仍未终止：输出自然结束信息，队形行数为总行数，追加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)额外空间。

总结

逐行模拟，严格按规则检查发送者、@次数与@对象。边界情况（目标本人发言、无@、多@、@错人）均在逐行分析中覆盖，最终根据不同条件输出对应格式的结果。

代码简要说明

1. getnm(p)函数：从字符串位置p之后提取@的人名（以空格为界）。
2. init()函数：读取第一行，定位@并提取target存入全局变量nm。
3. 主循环：
   • 读取一行，若为空或长度≤ 1 \le 1≤1则退出循环；
   • 解析发送者cur和@的位置；
   • 若发送者为target，成功退出；
   • 若无@，破坏退出；
   • 否则提取@对象，判断是否唯一且匹配target，不满足则破坏退出。
4. 正常退出：输出Unsuccessful、总行数、Good Queue Shape。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;string s,t,nm;ll l;voidgetnm(ll p){boolf=0;ll cnt=0;for(ll i=p+11;i<l;i++){if(s[i]==' '){cnt=i-p-1;break;}}t=s.substr(p+1,cnt);}voidinit(){getline(cin,s);s[s.size()-1]=' ';ll p=s.find('@');l=s.size();getnm(p);nm=t;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);init();ll ql=1;while(getline(cin,s)&&s.size()>1){ql++;s[s.size()-1]=' ';l=s.size();ll p=s.find('@');ll p2=s.find(':');string cur=s.substr(0,p2-1);if(nm==cur){cout<<"Successful @"<<nm<<" attempt"<<endl;return0;}if(p==-1){if(nm==cur){cout<<"Successful @"<<nm<<" attempt"<<endl;return0;}else{cout<<"Unsuccessful @"<<nm<<" attempt"<<endl;cout<<ql<<endl;cout<<cur<<endl;return0;}}else{getnm(p);s[p]='.';if(s.find('@')!=-1||t!=nm){ll p2=s.find(':');string cur=s.substr(0,p2-1);cout<<"Unsuccessful @"<<nm<<" attempt"<<endl;cout<<ql<<endl;cout<<cur<<endl;return0;}}}cout<<"Unsuccessful @"<<nm<<" attempt"<<endl;cout<<ql<<endl;cout<<"Good Queue Shape"<<endl;return0;}