SRM587 div2

250：题意给你两个字符串,问你B串是否可以由A串任意插入z得到

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <cmath>
 8 using namespace std;
 9 
10 class InsertZ
11 {
12     public:
13            string canTransform(string , string );
14 };
15 
16 string InsertZ::canTransform(string init, string goal)
17 {
18     string ret="";
19     int n = init.size();
20     int m = goal.size();
21     if(n>m) // 如果goal串比init串还短，肯定不可以 
22     {
23         ret+="No";
24         return ret;
25     }
26     int i=0,j=0,flag=1;
27     for( ; i<m ;)//for循环找goal中是否有init串 
28     {
29         if(init[j] != goal[i])
30         {
31             if(goal[i]!='z')
32             {
33                 flag = 0;
34                 break;
35             }
36             else i++;
37         }
38         else
39         {
40             i++;
41             j++;
42         }
43         if(j==n ) break; //找到了就跳出 
44     }
45     if(j!=n)  // 如果没找到,说明得不到 
46     {
47         ret+="No";
48         return ret;
49     }
50     for(int k=i; k<m; k++) // 找到之后 goal 从goal[i]开始的元素如果含有z以外的，也不行 
51     if(goal[k]!='z')
52      {
53          flag = 0;
54          break;
55      }
56     if(flag) ret+="Yes";
57     else ret+="No";
58     return ret;
59 }

View Code

500：题意给你一个N，还有一个badStep,你可以走N次，第 i 次最多可以走 i，问你可以到达的最高高度

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <cmath>
 8 using namespace std;
 9 
10 class JumpFurther
11 {
12     public:
13            int furthest(int , int );
14 };
15 
16 int JumpFurther::furthest(int N, int badStep)
17 {
18     int ret = 0;
19     for(int i=1; i<=N; i++)
20     {
21         if(ret+i==badStep) //如果刚好等于badStep，就少走一步 
22         {
23             ret += (i-1);
24         }
25         else  ret+=i;
26     }
27     return ret;
28 }

View Code

1000：题意给你一个n*m的字符矩阵，里面只含N,Z,N代表的对角线，Z代表 / 对角线，然后再给你三种颜色，给所有结点染色

相邻的结点的颜色不能相等，问你可以不可以做到

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <vector>
 6 #include <cmath>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 class ThreeColorabilityEasy
11 {
12     public:
13            string isColorable(vector <string>);
14 };
15 
16 string ThreeColorabilityEasy::isColorable(vector <string> cells)
17 {
18     string a="Yes",b="No";
19     int n = cells.size();
20     int m = cells[0].size();
21     if(n==1 || m== 1) return a;
22     for(int i=0; i<n-1; i++)
23     {
24         for(int j=0; j<m-1; j++)
25         {
26             int sum1 = 0 , sum2 = 0;
27             if(cells[i][j]=='Z') sum1++; 
28             else sum2++;
29             if(cells[i+1][j]=='Z') sum1++;
30             else sum2++;
31             if(cells[i+1][j+1]=='Z') sum1++;
32             else sum2++;
33             if(cells[i][j+1]=='Z') sum1++;
34             else sum2++;
35             if(sum1==1 || sum2==1) return b; 
36             //如果一个2*2的正方形里,有三条一样的对角线,
37             //有条对角线上的颜色会一样，所以不可以 
38         }
39     }
40     return a;
41 }

View Code