HRBUST - 2322 Team

冷不防 2022-05-28 12:14 146阅读 0赞

<table style="border-spacing:0px;border:1px solid rgb(206,225,238);margin:20px auto 0px;background:rgb(240,245,248);font-family:Arial, Helvetica, sans-serif;width:790px;color:rgb(0,0,0);text-align:center;"> 
 <tbody> 
 <tr style="padding:0px;"> 
 <td style="padding:30px 10px;color:rgb(26,92,200);font-family:'Times New Roman';font-size:32px;font-weight:bold;text-align:center;">Team</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:3px 10px;"> 
 <table style="border-spacing:0px;border:0px;margin:0px auto;color:#008000;font-family:Arial, Helvetica, sans-serif;font-size:10pt;"> 
 <tbody> 
 <tr style="padding:0px;"> 
 <td style="padding:3px 10px;">Time Limit: 1000 MS</td> 
 <td style="padding:3px 10px;">Memory Limit: 130172 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table style="border-spacing:0px;border:0px;margin:0px auto;color:#008000;font-family:Arial, Helvetica, sans-serif;font-size:10pt;"> 
 <tbody> 
 <tr style="padding:0px;"> 
 <td style="padding:3px 10px;">Total Submit: 367(70 users)</td> 
 <td style="padding:3px 10px;">Total Accepted: 74(54 users)</td> 
 <td style="padding:3px 10px;">Rating:&nbsp;<img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" style="border:0px;margin-bottom:0px;padding:0px;" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" style="border:0px;margin-bottom:0px;padding:0px;" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" style="border:0px;margin-bottom:0px;padding:0px;" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-half2.png" style="border:0px;margin-bottom:0px;padding:0px;" alt=""></td> 
 <td style="padding:3px 10px;">Special Judge:&nbsp;No</td> 
 </tr> 
 </tbody> 
 </table></td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;color:rgb(124,169,237);font-family:Arial;font-size:18px;font-weight:bold;width:770px;">Description</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;font-family:'courier new', courier, monospace;font-size:13px;table-layout:fixed;width:770px;">Kim&nbsp;正在玩一款手游，在这款游戏中，Kim可以选择若干个角色编成一队作战。为了挑战不同的关卡，Kim需要不断的调整编队阵容。然而随着游戏不断更新，队伍成员变得越来越多，Kim已经记不清哪些角色在队伍中，哪些角色不在队伍中了。请你写一个程序来帮助他。具体来说，Kim有三种可以执行的操作。1&nbsp;x&nbsp;&nbsp;：把&nbsp;x&nbsp;号角色加入队伍。如果x号角色已经在队伍中，什么都不会发生。2&nbsp;x&nbsp;&nbsp;：把&nbsp;x&nbsp;号角色从队伍中移除。如果x号角色不在队伍中，什么都不会发生。3&nbsp;x&nbsp;&nbsp;：撤销第x次操作。如果第x次操作已经被撤销，什么都不会发生。每次操作有一个编号，从1开始。对于3&nbsp;x操作，第x次操作会被撤销。被撤销的操作相当于没有进行这次操作。Kim可能撤销一次插入，撤销一次删除，或撤销另一次撤销操作。现在请你告诉Kim所有操作都结束后，队伍中有几个角色，都是谁。</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;color:rgb(124,169,237);font-family:Arial;font-size:18px;font-weight:bold;width:770px;">Input</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;font-family:'courier new', courier, monospace;font-size:13px;table-layout:fixed;width:770px;">第一行一个整数T，表示有T组数据。每组数据第一行两个整数n,m表示一共有n个角色（编号1-n）,m个操作。初始队伍中没有角色。接下来m行，每行一个操作，格式为1&nbsp;x&nbsp;或&nbsp;2&nbsp;x&nbsp;或&nbsp;3&nbsp;x,含义见题目描述。操作的编号等价于给出操作的顺序。第一个给出的操作是1号，第二个给出的操作是2号，以此类推。对于3&nbsp;x&nbsp;操作，保证&nbsp;x&nbsp;小于&nbsp;这条操作的编号。</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;color:rgb(124,169,237);font-family:Arial;font-size:18px;font-weight:bold;width:770px;">Output</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;font-family:'courier new', courier, monospace;font-size:13px;table-layout:fixed;width:770px;">对于每组数据，输出两行。第一行一个整数n,表示最后队伍中有n个人。接下来一行n个整数，表示队伍中角色的编号，角色编号按照从小到大的顺序输出。（每个编号后面有一个空格，包括最后一个编号。如果第一行n为0，则第二行为一个空行，即没有编号，只有一个换行符）</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;color:rgb(124,169,237);font-family:Arial;font-size:18px;font-weight:bold;width:770px;">Sample Input</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;font-family:'courier new', courier, monospace;font-size:13px;table-layout:fixed;width:770px;"><pre>1 5 8 1 1 1 2 3 2 1 4 3 3 3 5 1 5 2 5 </pre></td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;color:rgb(124,169,237);font-family:Arial;font-size:18px;font-weight:bold;width:770px;">Sample Output</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;font-family:'courier new', courier, monospace;font-size:13px;table-layout:fixed;width:770px;"><pre>2 1 4 </pre></td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;color:rgb(124,169,237);font-family:Arial;font-size:18px;font-weight:bold;width:770px;">Hint</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;font-family:'courier new', courier, monospace;font-size:13px;table-layout:fixed;width:770px;">T&lt;=10n&lt;=50000m&lt;=50000</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;color:rgb(124,169,237);font-family:Arial;font-size:18px;font-weight:bold;width:770px;">Source</td> 
 </tr> 
 <tr style="padding:0px;"> 
 <td style="padding:10px;font-family:'courier new', courier, monospace;font-size:13px;table-layout:fixed;width:770px;">"科林明伦杯"哈尔滨理工大学第六届程序设计团队赛</td> 
 </tr> 
 </tbody> 
</table>

思路：模拟，如果按照顺序来，会产生一系列的连锁反应，所以我认为从后面开始，如果为3标记一下，下次的循环中直接跳过，如果为2，则也也标记下，在下次添加时跳过，若为1，则在前面的删除中跳过

代码：

#include<queue>
 #include<math.h>
 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<algorithm>
 using namespace std;
 struct ss
 {
 int q,k;
 } a[60000];
 int main()
 {
 int test;
 scanf("%d",&test);
 while(test--)
 {
 int m,n,i,j,ans=0,book[60000],ans1=0,b[60000],mark[60000];
 memset(book,0,sizeof(book));
 memset(b,0,sizeof(b));
 memset(mark,0,sizeof(mark));
 scanf("%d%d",&n,&m);
 for(i=1; i<=m; i++)
 scanf("%d%d",&a[i].q,&a[i].k);
 for(i=m; i>=1; i--)
 {
 if(book[i])
 continue;
 int w=a[i].k;
 if(a[i].q==3)
 {
 book[w]=1;
 }
 else if(a[i].q==2)
 {
 if(!mark[w])
 {
 b[w]=0;
 mark[w]=1;
 }
 }
 else
 {
 if(!mark[w])
 {
 b[w]=1;
 mark[w]=1;
 }
 }
 }
 for(i=1;i<=n;i++)
 if(b[i])
 ans1++;
 printf("%d\n",ans1);
 for(i=1;i<=n;i++)
 if(b[i])
 printf("%d ",i);
 printf("\n");
 }
 return 0;
 }