题解 P1333 【瑞瑞的木棍】

刚开始以为本题很水，只需要判断每一种颜色出现次数即可，然而 ``` #include<bits/stdc++.h> using namespace std; const int N=5e5+5; string s[N],s1,s2; int cnt; map<string,int>mp; int main() { for(;cin>>s1>>s2;) { if(mp[s1]==0) s[++cnt]=s1;++mp[s1]; if(mp[s2]==0) s[++cnt]=s2;++mp[s2]; } int flag=0; for(int i=1;i<=cnt;++i) if(mp[s[i]]%2!=0) ++flag; if(flag>=3) printf("Impossible\n"); else printf("Possible\n"); } ``` 只拿了80分 事实上，本题是一个欧拉回路问题，我们只需要根据性质判断一下即可 即：奇入度点是否小于3并且联通块个数是否小于2 对于本题字符串问题，我们建立两个map，一个储存字符串出现个数，另一个则是映射用的（对每个字符串重新标号） 其实另外一个map用数组就好了，~~只是那时候忘记了~~ ACcode ``` // luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int N=5e5+5; string s[N],s1,s2; int cnt,fa[N]; map<string,int>mp; map<string,int>id; inline int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { int block=0,pt=0; for(;cin>>s1>>s2;) { if(mp[s1]==0) s[++cnt]=s1,fa[cnt]=cnt,++block,id[s1]=cnt; ++mp[s1]; (mp[s1]&1)?++pt:--pt; if(mp[s2]==0) s[++cnt]=s2,fa[cnt]=cnt,++block,id[s2]=cnt; ++mp[s2]; (mp[s2]&1)?++pt:--pt; if(find(id[s1])!=find(id[s2])) fa[fa[id[s1]]]=fa[id[s2]], --block; } (block<2&&pt<3)?printf("Possible\n"):printf("Impossible\n"); } ```