Weekend PartyTime Limit:2 Seconds Memory Limit:65536 KB
As the onlyOni(a kind of fabulous creature with incredible strength and power) living on the surface ofGensokyo,Ibuki Suikahas an interest in gatheringHumansandYoukaiinGensokyoand holding party every day.
TodaySuikahas asked several friends to participate in a weekend party, which will be held atHakurei Shrineas usual. ThoughGensokyowas isolated from the outside world, everyone here is still a fan of ACG (Anime, Comic and Game). Of course, some people may only like parts of ACG. For example,Reimulikes Anime and Game,Marisaonly likes Comic butKaguyalikes all of them.
In order to make everyone enjoy the party,Suikadecide to arrange them into a circle so that everyone can have at least one common interest with both left and right hand side, which means one has at least a common interest with leftANDhas at least a common interest with right. By the way,Suikaknows all her friends’ interest. Please find out if she can get an arrangement of seats that satisfies the constraint described above.
Input
There are multiple test cases. For each test case:
The first line contains an integerN(1 <=N<= 64) indicates the number of girls inGensokyo. Then followed by N lines, each line contains two stringsAiandBi(each contains only alphanumeric characters).Airepresents the name of thei-th girl and the length of it will not exceed 10.Biis a non-empty subset of "ACG".
Output
For each test case, output "Yes" if there exists at least one arrangement of seats, otherwise output "No".
Sample Input1Reimu AG2Reimu AGMarisa C3Reimu AGMarisa CKaguya GACSample OutputYesNoNo
题意：告诉n个人，每个人都有AGC这三个爱好中的一种或多种，聚会时间，大家坐成一个圈，为了让大家都欢乐，那么就要保证每个人左右两边的人都和他有共同爱好。
思路：只有三个爱好嘛，情况比较少，所以可以直接暴力枚举。先用map缩一下点，方便讨论，然后找一个讨论对象，AGC这种万能的就无需过多考虑，AG AC GC也还好，但是对于单个爱好的人，就会比较棘手，所以我们选择单个爱好的人作为突破口。感觉代码注释已经很详细了，还是不懂滴，可以留言
#include <iostream>#include <stdio.h>#include <string>#include <cstring>#include <cmath>#include <algorithm>#include <map>using namespace std;int n;string s,a;int main(){while(~scanf("%d",&n)){map<string,int>mp;for(int i=0;i<n;i++){cin>>a>>s;mp[s]++;}int A=mp["A"];int C=mp["C"];int G=mp["G"];int AG=mp["AG"]+mp["GA"];int AC=mp["AC"]+mp["CA"];int GC=mp["GC"]+mp["CG"];int AGC=mp["AGC"]+mp["ACG"]+mp["CGA"]+mp["CAG"]+mp["GCA"]+mp["GAC"];//cout<<"A="<<A<<" "<<"C="<<C<<" "<<"G="<<G<<endl;//cout<<"AG="<<AG<<" "<<"AC="<<AC<<" "<<"GC="<<GC<<endl;//cout<<"AGC="<<AGC<<endl;if( (A+AC+AG+AGC==n) || (C+AC+AGC+GC==n) || (G+AG+GC+AGC==n) )//一个{puts("Yes");//cout<<"********1"<<endl;continue;}if( (A==0&&(GC+AGC>=2)) || (C==0 && (AG+AGC)>=2 ) || (G==0 && (AC+AGC)>=2 ))//两个{puts("Yes");//cout<<"********2"<<endl;continue;}if( (AG?1:0)+(GC?1:0)+(AC?1:0)+AGC>=3 )//三个{puts("Yes");//cout<<"********3"<<endl;continue;}if( (AC>=2&&AG>=2) || (AG>=2&&GC>=2) || (GC>=2&&AC>=2) )//三个{puts("Yes");//cout<<"********4"<<endl;continue;}//对于这种没有的情况，其实上面已经包含了，例如：如果只有AC AG GC中的两个（AGC比较特殊，可以无所谓）那么在第一种情况就判断了，可以输出Yes,如果三个都有，，那//么在第三种情况也会考虑到，所以输出Yes.//if( (A==0&&C==0&&G==0) && ( (AG>=1&&AC>=1) || (AC>=1&&GC>=1) || (GC>=1&&AG>=1) || AGC>=2) )//没有//{//puts("Yes");////cout<<"********4"<<endl;//continue;//}puts("No");}return 0;}/*5fd Afdfd Gfsd Cds AGfsf CA*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
你曾经说，最大的愿望，
