首页 > 代码库 > CodeChef August Lunchtime 2014 题解
CodeChef August Lunchtime 2014 题解
A题
给一个由ａ和ｂ两种类型的字符组成的字符串，每次可以从中选取任意长度的回文子序列（不一定连续）并删除。问最少需要几次能将整个字符串为空。
思路：如果本身是个回文串，那么只需要一次，否则需要两次（第一次选全部的ａ，第二次全部选ｂ）。
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题
待续。。。
CodeChef August Lunchtime 2014 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。