CodeChef August Lunchtime 2014 题解

给一个由ａ和ｂ两种类型的字符组成的字符串，每次可以从中选取任意长度的回文子序列（不一定连续）并删除。问最少需要几次能将整个字符串为空。

思路：如果本身是个回文串，那么只需要一次，否则需要两次（第一次选全部的ａ，第二次全部选ｂ）。

Accepted Code:

 1 def is_palidrome(s):
 2       n = len(s);
 3       for i in xrange(n / 2):
 4           if s[i] != s[n - i - 1]:
 5             return False;
 6     return True;
 7 
 8 if __name__ == '__main__':
 9     T = int(input())
10     while T:
11         T -= 1;
12         H = raw_input();
13         print 1 if is_palidrome(H) else 2;

B题

知识点：给出公式：ind = (A * ind + B) % M，求其循环节长度。从公式可以看出，循环节不超过Ｍ。

另外，这题精度也是个坑，可以手动输出：".5"和".0"。

Accepted Code:

 1 /*************************************************************************
 2     > File Name: WALL.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年08月31日 星期日 19时16分49秒
 6     > Propose: 
 7  ************************************************************************/
 8 
 9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <vector>
13 #include <iomanip>
14 #include <fstream>
15 #include <cstring>
16 #include <iostream>
17 #include <algorithm>
18 using namespace std;
19 /*Let's fight!!!*/
20 
21 const int MAX_M = 524300;
22 typedef long long LL;
23 LL IND[MAX_M], D[MAX_M], vis[MAX_M];
24 LL t, h, n, m, a, b, ind;
25 #define rep(i, n) for (int i = (0); i < (n); i++)
26 void seed(LL &ind) {
27     ind = (a * ind + b) % m;
28 }
29 
30 int main(void) {
31     ios::sync_with_stdio(false);
32     cin >> t;
33     while (t--) {
34         cin >> h >> n >> m >> a >> b >> ind;
35         rep (i, m) cin >> D[i];
36 
37         int loop = 1;
38         memset(vis, -1, sizeof(vis));
39         vis[ind] = 0;
40         IND[0] = ind;
41         LL ans = 0;
42         while (loop < n) {
43               ans += D[ind];
44             seed(ind);
45             if (vis[ind] != -1) break;
46             vis[ind] = loop;
47             IND[loop] = ind;
48             ++loop;
49         }
50 
51         if (loop <= n - 1) {
52             LL sum = 0;
53             for (int i = vis[ind]; i < loop; i++) sum += D[IND[i]];
54             LL times = (n - 1 - loop) / (loop - vis[ind]);
55             ans += times * sum;
56             loop += times * (loop - vis[ind]);
57             loop++;
58         }
59         while (loop <= n - 1) {
60             ans += D[ind];
61             seed(ind);
62             loop++;
63         }
64 
65         cout << ans * h / 2;
66         if (ans * h % 2) cout << ".5";
67         else cout << ".0";
68         cout << endl;
69     }
70 
71     return 0;
72 }

C题

待续。。。

D题

待续。。。