A. Pangram

题意：判断字符串中26种字母是否全都出现过，不区分大小写。

题本身不难，可是忘了用getchar()吞掉输入第一行最末的换行符，导致被某些别有用心的人在比赛快结束的时候Hack了。

1 #include 
      
        2 using namespace std; 3  4 const int maxn = 100 + 10; 5  6 char s[maxn]; 7 bool vis[30]; 8  9 int main()10 {11     //freopen("in.txt", "r", stdin);12 13     int n, cnt = 0;14     scanf("%d", &n);15     getchar();16     for(int i = 0; i < n && cnt < 26; i++)17     {18         char c = getchar();19         int x;20         if(c < 'a') x = c - 'A';21         else x = c - 'a';22         if(!vis[x]) cnt++;23         vis[x] = true;24     }25 26     printf("%s\n", cnt == 26 ? "YES" : "NO");27 28     return 0;29 }
      

 

B. Two Buttons (BFS)

题意：

最开始有个数字n，有两种按钮，一种可以将这个数字减1，一种按钮可以将这个数字乘2.求将这个数字变为m的最短步数。

分析：

一开始以为是DP，后来在纸上演算了一下，发现其实就是一个BFS求最短路。

1 #include 
      
        2 using namespace std; 3  4 const int maxn = 10000 + 10; 5  6 int n, m; 7 int d[maxn]; 8 bool vis[maxn]; 9 10 struct Node11 {12     int u, d;13     Node(int u, int d):u(u), d(d) {}14 };15 16 queue
       
         Q;17 18 int BFS()19 {20     Node head = Node(n, 0);21     vis[n] = true;22     Q.push(head);23     while(!Q.empty())24     {25         Node x = Q.front(); Q.pop();26 27         if(x.u == m) { return x.d; }28 29         int a = x.u - 1;30         int d = x.d + 1;31         if(a > 0 && !vis[a])32         {33             vis[a] = true;34             Q.push(Node(a, d));35         }36 37         a = x.u * 2;38         if(a < maxn && !vis[a])39         {40             vis[a] = true;41             Q.push(Node(a, d));42         }43     }44     return -1;45 }46 47 int main()48 {49     //freopen("in.txt", "r", stdin);50 51     scanf("%d%d", &n, &m);52     printf("%d\n", BFS());53 54     return 0;55 }
       
      

 

C. DNA Alignment (贪心 快速幂)

题意：

题目描述还是比较蛋疼的。观察一下，根据题中的定义可以把p(s,t)改写成这样：

也就是t中的每个DNA都会和s中的每个DNA匹配n次，为了使p(s,t)最大，对于t中的每个DNA只要选择s中出现次数最多的那个即可。

如果有s中有多种DNA出现的次数最多且相等，选哪种都可以，所以最终答案是kⁿ，其中k是s中重复次数最多的DNA总数。

1 #include 
      
        2 using namespace std; 3 typedef long long LL; 4 const int maxn = 100000 + 10; 5 const LL MOD = 1000000007; 6 int n; 7 char s[maxn]; 8  9 LL pow_mod(LL a, LL n)10 {11     if(n == 0) return 1LL;12     LL ans = pow_mod(a, n >> 1);13     ans = ans * ans % MOD;14     if(n%2 == 1) ans = ans * a % MOD;15     return ans;16 }17 18 int ID(char c)19 {20     if(c == 'A') return 0;21     if(c == 'G') return 1;22     if(c == 'C') return 2;23     return 3;24 }25 26 int sum[4];27 28 int main()29 {30     //freopen("in.txt", "r", stdin);31 32     scanf("%d", &n);33     scanf("%s", s);34     for(int i = 0; i < n; i++) sum[ID(s[i])]++;35     sort(sum, sum + 4);36     reverse(sum, sum + 4);37     int i = 1;38     while(i < 4 && sum[i] == sum[i - 1]) i++;39     LL ans = pow_mod(i, n);40     printf("%I64d\n", ans);41 42     return 0;43 }
      

 

D. Cubes (博弈 贪心 模拟)

题意：

这道题题意还挺繁琐的。有n个木块，像搭积木一样搭起来，每个木块有自己的编号0~n-1。两个人现在要把积木一块一块的拿下来，而且拿的过程中不会影响其他积木。这样拿积木的顺序就可以看做一个n进制的数(第一个拿下来的积木的编号在最高位)。第一个人想让这个数最大，第二个人想让这个数最小，求最后拿积木所确定下来的数字。

分析：

首先如何判断一个积木拿下来不会影响到其他积木，就是判断一下它上方三块积木(如果有的话)是否只被这唯一一块积木支撑着。

我们可以用C++里面的set来存储可以拿下来的积木的编号，在拿下来一块积木的同时，也可能会暴露出新的积木，如果符合要求的话也要加入到set里面。

最后再强调一点，并不是加入到set中后就一定可以拿下来，在拿下来的时候还要再判断一次。因为可能发生这样的情况：

在加入set的时候这块积木可以被拿下来，但是要拿下来这一刻，积木的布局发生变化，这块积木就可能变成了支撑上面积木的唯一一块，所以就不能被拿下来了。

1 #include 
      
        2 using namespace std; 3 #define MP make_pair 4  5 const int maxn = 100000 + 10; 6 const int MOD = 1000000009; 7 const int dx[] = {-1, 0, 1}; 8  9 int x[maxn], y[maxn];10 map
       
        
         , int> ID;11 set
         
           Set;12 bool vis[maxn];13 14 bool available(int t)15 {16     for(int i = 0; i < 3; i++)17     {18         int nx = x[t] + dx[i];19         int ny = y[t] + 1;20         int id = ID[MP(nx, ny)];21         if(id && !vis[id])22         {23             int cnt = 0;24             for(int j = 0; j < 3; j++)25             {26                 int nnx = nx + dx[j];27                 int nny = y[t];28                 int nid = ID[MP(nnx, nny)];29                 if(nid && !vis[nid]) cnt++;30             }31             if(cnt == 1) return false;32         }33     }34     return true;35 }36 37 int main()38 {39     //freopen("in.txt", "r", stdin);40 41     int n;42     scanf("%d", &n);43     for(int i = 1; i <= n; i++)44     {45         scanf("%d%d", &x[i], &y[i]);46         ID[MP(x[i], y[i])] = i;47     }48 49     for(int i = 1; i <= n; i++) if(available(i))50         Set.insert(i);51 52     long long ans = 0;53     bool turn = false;54     while(Set.size())55     {56         int t = turn ? *Set.begin() : *Set.rbegin();57         Set.erase(t);58         if(!available(t)) continue;59         turn = !turn;60         vis[t] = true;61         ans = (ans * n + t - 1) % MOD;62         for(int i = 0; i < 3; i++)63         {64             int nx = x[t] + dx[i];65             int ny = y[t] - 1;66             int id = ID[MP(nx, ny)];67             if(id && !vis[id] && available(id))68                 Set.insert(id);69         }70     }71 72     printf("%I64d\n", ans);73 }
         
        
       
      

 

E. Pluses everywhere (数论 组合数学 乘法逆元)

题意：

有一串数字长度为n，要在数字与数字之间加k个加号构成一个表达式，求所有合法表达式的值之和。

分析：

插入k个加号会得到k+1个加数，其中这些加数可能存在前导0.考虑每个表达式太麻烦了，不如换个角度，我们固定一个数字d。

无论加号怎样放，它最终都是贡献d*10^l这么多的。具体这个l是多少，就要看它右边离它最近的一个加号有多远；当然也可能它在最后一个加数里面，右边没有加号。

上面两种情况都要考虑进去，这里只说大概思路好了，官方题解已经说得很详细了。

其中要求组合数，所以要预处理前n个阶乘以及阶乘的逆元。

因为刚刚接触乘法逆元这个概念，所以就多说两句：

如果ax≡1(mod p)，则a和x互为关于模p的乘法逆元

《训练指南》上给出了用扩展欧几里得的算法求乘法逆元的代码，就是解方程：ax + py = 1，找到一组解，x就是a的逆元。

还有一种办法就是利用费马小定理 或者 欧拉定理，这里以费马小定理为例：

假如p是质数，且gcd(a,p)=1，那么 a^(p-1) ≡1(mod p)，那么就有a * a^(p-2) ≡ 1 (mod p)，所以a^(p-2)就是a关于模p的逆元。

如果是欧拉定理，就有     ，于是a^phi(n)-1就是a的逆元，如果n为素数的话，phi(n) = n - 1，所以a^n-2就是a的逆元。

所以我们可以统一用快速幂来求乘法逆元了。

如果是求连续阶乘的逆元，还可以递推来求：

先求出n的阶乘 fac(n)的逆元inv_fac(n)，fac(n) * inv_fac(n) ≡ fac(n-1) * n * inv_fac(n) ≡ 1，所以fac(n-1)的逆元为n * inv_fac(n)，这样递推公式就是：

inv_fac(n-1) = n * inv_fac(n)

1 #include 
      
        2 using namespace std; 3 typedef long long LL; 4  5 const int maxn = 100000 + 10; 6 const int MOD = 1000000007; 7  8 inline LL mul_mod(LL a, LL b, LL n = MOD) 9 { return a * b % n; }10 11 LL pow_mod(LL a, LL p, LL n = MOD)12 {13     if(p == 0) return 1LL;14     LL ans = pow_mod(a, p>>1, n);15     ans = ans * ans % n;16     if(p & 1) ans = ans * a % n;17     return ans;18 }19 20 int n, k;21 int a[maxn], sum[maxn];22 int ten_pow[maxn], fac[maxn], ifac[maxn];23 24 void Init()25 {26     sum[0] = a[0];27     for(int i = 1; i < n; i++) sum[i] = sum[i - 1] + a[i];28 29     fac[0] = 1;30     for(int i = 1; i <= n; i++) fac[i] = mul_mod(fac[i - 1], i);31     ifac[n] = pow_mod(fac[n], MOD - 2);32     for(int i = n-1; i >= 0; i--) ifac[i] = mul_mod(ifac[i+1], i+1);33 34     ten_pow[0] = 1;35     for(int i = 1; i < n; i++) ten_pow[i] = mul_mod(ten_pow[i-1], 10);36 }37 38 inline LL C(int n, int k)39 {40     if(k > n || k < 0) return 0;41     return mul_mod(mul_mod(fac[n], ifac[k]), ifac[n-k]);42 }43 44 int main()45 {46     scanf("%d%d", &n, &k); getchar();47     for(int i = 0; i < n; i++) a[i] = getchar() - '0';48 49     Init();50 51     LL ans = 0;52     for(int l = 0; l <= n-2; l++)53     {54         ans = (ans + mul_mod(mul_mod(ten_pow[l], C(n-l-2, k-1)), sum[n - l - 2])) % MOD;55         ans = (ans + mul_mod(mul_mod(a[l], ten_pow[n-l-1]), C(l, k))) % MOD;56     }57     ans = (ans + mul_mod(a[n-1], C(n-1, k))) % MOD;58     printf("%I64d\n", ans);59 60     return 0;61 }