Tyche 2317 Color

题目大意：有三个人alice，bob，yazid，三种颜色red，blue，green，每个人对应一种颜色。

[name] is [color].

Yazid会做以下操作：

1 将三个句子连在一起

2 去掉逗号和空格

3 全部转换为小写

Alice，Bob会在串中加入任意小写字母。

现给定最后的串，求开始的串。

答案可能有多种，输出字典序最小的一种。

思路：一开始以为很复杂，一看就是一个搜索。

先找名字再找is最后找颜色，重复三次即可得到结果。

考试的时候把字典序理解错了，疯狂0分，换了个搜索顺序就ac了，血亏。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 using namespace std;
  5 int T,a[11][11];
  6 char ch[1005],name[3][15]={"alice","bob","yazid"},nm[3][15]={"Alice","Bob","Yazid"},color[3][15]={"blue","green","red"},pd[]={"is"};
  7 bool flag,b1[3],b2[3];
  8 int fnd(int s,char c)
  9 {
 10     int l=strlen(ch+1);
 11     for(int i=s;i<=l;i++)
 12         if(ch[i]==c)
 13             return i;
 14     return -1;
 15 }
 16 void dfs(int x,int k,int s,int e)
 17 {
 18     if(x==4&&!flag)
 19     {
 20         flag=1;
 21         for(int i=1;i<=3;i++)
 22             printf("%s %s %s.",nm[a[i][0]],pd,color[a[i][1]]);
 23         printf("
");
 24     }
 25     if(k==0)//?? 
 26     {
 27         for(int i=0;i<=2;i++)
 28             if(!b1[i])
 29             {
 30                 bool flg=0;
 31                 int p=s;
 32                 for(int j=0;j<strlen(name[i]);j++)
 33                 {
 34                     p=fnd(p,name[i][j]);
 35                     if(p==-1)
 36                     {
 37                         flg=1;
 38                         break;
 39                     }
 40                     p++;
 41                 }
 42                 if(!flg)
 43                 {
 44                     b1[i]=1;
 45                     a[x][0]=i;
 46                     dfs(x,1,p,e);
 47                     b1[i]=0;
 48                 }
 49             }
 50     }
 51     else if(k==1)
 52     {
 53         bool flg=0;
 54         int p=s;
 55         for(int j=0;j<2;j++)
 56         {
 57             p=fnd(p,pd[j]);
 58             if(p==-1)
 59             {
 60                 flg=1;
 61                 break;
 62             }
 63             p++;
 64         }
 65         if(!flg)
 66             dfs(x,2,p,e);
 67     }
 68     else
 69     {
 70         for(int i=0;i<=2;i++)
 71             if(!b2[i])
 72             {
 73                 bool flg=0;
 74                 int p=s;
 75                 for(int j=0;j<strlen(color[i]);j++)
 76                 {
 77                     p=fnd(p,color[i][j]);
 78                     if(p==-1)
 79                     {
 80                         flg=1;
 81                         break;
 82                     }
 83                     p++;
 84                 }
 85                 if(!flg)
 86                 {
 87                     b2[i]=1;
 88                     a[x][1]=i;
 89                     dfs(x+1,0,p,e);
 90                     b2[i]=0;
 91                 }
 92             }
 93     }
 94 }
 95 int main()
 96 {
 97     scanf("%d",&T);
 98     while(T--)
 99     {
100         scanf("%s",ch+1);
101         flag=0;
102         dfs(1,0,1,strlen(ch+1));
103         if(!flag)
104             printf("No solution.
");
105     }
106     return 0;
107 }

View Code