A. Chewbaсca and Number

感觉这道题巨坑，如果题中加粗标出来的输出得是正数算小坑的话。有个巨坑就是

the final number shouldn't start with a zero.

答案不能有前导0，我觉得这句话有两种理解：

比如将9999变为9，算不算有前导0呢？把9当做一位数就没有前导0，当做4位数就有前导0

好吧，根据“剧情需要”，看来是被当做有前导0的

所以，这道题的解法就是除了最高位如果是9的话，把其他所有大于等于5的数字t，全部转变为9-t

1 #include 
      
        2  3 using namespace std; 4  5 const int maxn = 25; 6 char s[maxn]; 7  8 int main() 9 {10     scanf("%s", s);11     int l = strlen(s);12     for(int i = 0; i < l; ++i)13     {14         if(i == 0 && s[i] == '9') continue;15         if(s[i] > '4') s[i] = '0' + '9' - s[i];16     }17     printf("%s\n", s);18 19     return 0;20 }
      

 

B. Han Solo and Lazer Gun

题意：

可能是A题弄得心里比较乱，所以这个题在思路清晰的情况下还WA了两次，真是。。

有一把枪和n个敌人，这把枪一次能消灭经过枪的位置的直线上所有敌人。

已知枪和敌人的坐标，求要消灭所有敌人的最少开枪次数。

分析：

以枪为中心，如果某两个敌人和枪连线斜率一样的话，一次就能全部消灭。

因为浮点运算肯定会有误差，所以我们用两个互素的整数<x, y>(x≥0)来表示斜率。

注意敌人与枪处于同一水平线或竖直线的特殊情况。

1 #include 
      
        2  3 using namespace std; 4  5 const int maxn = 1000 + 10; 6  7 int gcd(int a, int b) 8 { return b == 0 ? a : gcd(b, a % b); } 9 10 int main()11 {12     //freopen("in.txt", "r", stdin);13 14     int n, x0, y0, cnt = 0;15     scanf("%d%d%d", &n, &x0, &y0);16     set
       
        
         > Set;17     for(int i = 0; i < n; ++i)18     {19         int x, y;20         scanf("%d%d", &x, &y);21         x -= x0; y -= y0;22         pair
         
           t;23         if(x == 0) t = make_pair(0, 1);//处于同一竖直线24         else if(y == 0) t = make_pair(1, 0);//处于同一水平线25         else26         {27             int g = gcd(x, y);28             x /= g; y /= g;29             if(x < 0) { x = -x; y = -y; }30             t = make_pair(x, y);31         }32         if(!Set.count(t)) { cnt++; Set.insert(t); }33     }34 35     printf("%d\n", cnt);36 37     return 0;38 }
         
        
       
      

 

C. Watto and Mechanism (哈希)

题意：

给出n个字符串，然后有m个询问，每个询问也都是一个字符串。

恰好改变询问中的字符串的一个字符，是否能变为n个字符串中的某个字符。

分析：

题中说所有的字符串只含abc三种字符，所以我们可以把每个字符串看做一个三进制的数字(abc代表012)。

因为可能会溢出，所以要不断取余。一开始是对1e9+7取余，但是没过，后来改成1e12+7

将这n个字符串对应的哈希值插入到set中，然后对于每个询问枚举改变的字符以及位置。

注意这里不要枚举新字符串然后计算哈希值，还是会超时的。应该在计算出询问串的哈希值的基础上再做相应改动。

1 #include 
      
        2 using namespace std; 3 typedef long long LL; 4  5 const LL MOD = 1000000000007LL; 6  7 inline LL Hash(string& s) 8 { 9     LL ans = 0;10     for(int i = 0; i < s.length(); ++i)    ans = (ans*3+(s[i]-'a')) % MOD;11     return ans;12 }13 14 int main()15 {16     //freopen("in.txt", "r", stdin);17 18     int n, m;19     scanf("%d%d", &n, &m);20     set
       
         Set;21     string s;22     for(int i = 0; i < n; ++i)23     {24         cin >> s;25         Set.insert(Hash(s));26     }27 28     for(int i = 0; i < m; ++i)29     {30         cin >> s;31         bool flag = false;32         LL x = Hash(s);//询问串的hash值33         LL b = 1;34         for(int j = s.length()-1; j >= 0; j--)35         {36             LL t = (x-b*(s[j]-'a'+1) % MOD + MOD) % MOD;//先将枚举的位置变为037             for(char c = 'a'; c <= 'c'; c++) if(c != s[j])38             {39                 LL tt = (t + b*(c-'a'+1)) % MOD;//新串对应的Hash值40                 if(Set.count(tt)) { flag = true; break; }41             }42             if(flag) break;43             b = (b*3) % MOD;//b = (3^i)%MOD44         }45 46         printf("%s\n", flag ? "YES" : "NO");47     }48 49     return 0;50 }