当前位置：首页 > news >正文

打卡信奥刷题（3149）用C++实现信奥题 P7677 [COCI 2013/2014 #5] LADICE

news 2026/7/12 3:42:30

P7677 [COCI 2013/2014 #5] LADICE

题目描述

有N NN个物品，L LL个抽屉，每个抽屉只能放1 11个物品，每个物品都能被放进抽屉A i A_iAi或B i B_iBi中。

放物品的规则如下（按照顺序执行，即满足条件1 11时就立刻执行，不会执行条件2 22；不满足条件1 11时就判断条件2 22）：

1. 1.1.如果抽屉A i A_iAi是空的，就把这个物品放进抽屉A i A_iAi中；
2 22如果抽屉B i B_iBi是空的，就把这个物品放进抽屉B i B_iBi中；
3. 3.3.把抽屉A i A_iAi中的物品移到它的另一个抽屉里；如果这个抽屉也满了，就把这个抽屉里的物品放到它的另一个抽屉里，直到你成功或回到之前遇到过的抽屉为止。如果成功了，就把这个物品放进这个抽屉中；
4. 4.4.把抽屉B i B_iBi中的物品移到它的另一个抽屉里；如果这个抽屉也满了，就把这个抽屉里的物品放到它的另一个抽屉里，直到你成功或回到之前遇到过的抽屉为止。如果成功了，就把这个物品放进这个抽屉中；
5. 5.5.扔掉此物品。

对于给定的每件物品，请你求出哪些物品将被保存，哪些将被扔掉。

输入格式

第一行，两个整数N NN和L LL，分别表示物品个数和抽屉个数；

接下来的N NN行，每行两个整数A i A_iAi和B i B_iBi，表示物品i ii能被储存的两个抽屉。

输出格式

输出共N NN行，每行一个字符串：

如果该物品成功被保存，输出LADICA；

如果该物品被扔掉，输出SMECE。

输入输出样例 #1

输入 #1

5 3 1 2 1 3 1 2 1 3 1 2

输出 #1

LADICA LADICA LADICA SMECE SMECE

输入输出样例 #2

输入 #2

9 10 1 2 3 4 5 6 7 8 9 10 2 3 1 5 8 2 7 9

输出 #2

LADICA LADICA LADICA LADICA LADICA LADICA LADICA LADICA LADICA

说明/提示

【样例解释 #1】

物品1 11放入抽屉1 11，物品2 22放入抽屉3 33，物品3 33放入抽屉2 22，物品4 44和物品5 55没有地方放。

【样例解释 #2】

物品1 11放入抽屉1 11，物品2 22放入抽屉3 33，物品3 33放入抽屉5 55，物品4 44放入抽屉7 77，物品5 55放入抽屉9 99，物品6 66放入抽屉2 22，物品8 88放入抽屉8 88。

物品7 77的两个抽屉都满了，将抽屉1 11里的物品1 11移到抽屉2 22里，将抽屉2 22里的物品6 66移到抽屉3 33里，将抽屉3 33里的物品2 22移到抽屉4 44里，抽屉4 44是空的，成功放入。

物品9 99的两个抽屉都满了，将抽屉7 77里的物品4 44移到抽屉8 88里，将抽屉8 88里的物品8 88移到抽屉2 22里，将抽屉2 22里的物品1 11移到抽屉1 11里，将抽屉1 11里的物品7 77移到抽屉5 55里，将抽屉5 55里的物品3 33移到抽屉6 66里，抽屉6 66是空的，成功放入。

【数据范围】

对于50 % 50\%50%的数据，1 ≤ N , L ≤ 2000 1\le N,L\le 20001≤N,L≤2000；

对于100 % 100\%100%的数据，1 ≤ N , L ≤ 3 × 10 5 1\le N,L\le 3\times 10^51≤N,L≤3×105，1 ≤ A i , B i ≤ L 1\le A_i,B_i\le L1≤Ai,Bi≤L。

【说明】

本题分值按 COCI 原题设置，满分160 160160。

题目译自COCI2013_2014 CONTEST #5T6 LADICE

C++实现

#include<iostream>usingnamespacestd;intn,l;constintN=3e5+5;intvis[N],fa[N];intfind(intx){if(fa[x]==x)returnx;returnfa[x]=find(fa[x]);}voidun(intx,inty){x=find(x),y=find(y);if(x!=y)fa[y]=x;}//并查集基本操作intmain(){cin>>n>>l;for(inti=1;i<=l;i++)fa[i]=i;//初始化for(inti=1;i<=n;i++){intx,y;cin>>x>>y;if(vis[find(x)]==0||vis[find(y)]==0){//放得下cout<<"LADICA\n";if(vis[find(x)]==0){//可以执行条件1/3vis[find(x)]=1;//标记un(y,x);}else{//可以执行条件2/4vis[find(y)]=1;//标记un(x,y);}}elsecout<<"SMECE\n";//放不下}return0;}