题目列表：
| 2146 Problem A | 【手速】阔绰的Dim |
| 2147 Problem B | 【手速】颓废的Dim |
| 2148 Problem C | 【手速】我的滑板鞋 |
| 2149 Problem D | 【手速】潦倒的Dim |
| 2150 Problem E | 【手速】被NTR的Dim |
2146 Problem A：
简单的最长回文串统计算法，这里没有过高要求，n^2算法可以AC。其中包括dp动规以及中心法（以上两种都是O(n^2)算法，可以参考白书）。推广，可以尝试扩展KMP(O(nlogn))或者Manacher算法（O(n)）。可以查阅相关资料自行选择学习。这里给出中心法。
/****************************************/
/***** Desgard_Duan *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric> using namespace std; char s[]; int len; inline void get_val(int &a) {
int value = , s = ;
char c;
while ((c = getchar()) == ' ' || c == '\n');
if (c == '-') s = -s; else value = c - ;
while ((c = getchar()) >= '' && c <= '')
value = value * + c - ;
a = s * value;
} int tofind(int h, int t) {
int re = t - h + ;
while (h < t) {
if (s[h++] != s[t--]) return ;
}
return re;
} int main() {
//freopen("huiwen.in", "r", stdin);
//freopen("huiwen.out","w",stdout);
int T;
cin >> T;
while (T--) {
scanf("%s", s);
len = strlen(s);
int ans = ;
for (int i = ; i < len - ; i++)
for (int j = i + ; j < len; j++) {
ans = max(ans, tofind(i, j));
}
cout << ans << endl;
}
return ;
}
2147 Problem B:
一道字符串水题，只要按位置遍历一遍即可。C语言基础题。
/****************************************/
/***** Desgard_Duan *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric> using namespace std; inline void get_val(int &a) {
int value = , s = ;
char c;
while ((c = getchar()) == ' ' || c == '\n');
if (c == '-') s = -s;
else value = c - ;
while ((c = getchar()) >= '' && c <= '')
value = value * + c - ;
a = s * value;
} string str1, str2;
int main () {
int T;
//cin >> T;
while (cin >> str1 >> str2) { int ans = ;
for (int i = ; i < str1.size(); ++ i) {
if (str1[i] == str2[i]) {
ans ++;
}
}
cout << ans << endl;
}
return ;
}
2148 Problem C:
一道贪心的白书例题，类型归类为查找不相交区间的最大个数。具体思路：对于相交的任意两个区间分为两种情况（图A、图B）。若出现情况A，直接将大区间删除即可。若出现情况B，我们先将集合按照x进行升序排列，然后优先选取x最小的情况B中的区间，这样可以得到最佳的方案。
/****************************************/
/***** Desgard_Duan *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric> using namespace std; inline void get_val(int &a) {
int value = , s = ;
char c;
while ((c = getchar()) == ' ' || c == '\n');
if (c == '-') s = -s;
else value = c - ;
while ((c = getchar()) >= '' && c <= '')
value = value * + c - ;
a = s * value;
} vector<pair<int, int> > shoes;
bool flag[]; int main () {
int n, x, y;
//freopen("out.txt", "w", stdout);
while (~scanf ("%d", &n)) {
shoes.clear();
for (int i = ; i < n; ++ i) {
cin >> x >> y;
shoes.push_back (make_pair(x, y));
}
sort (shoes.begin(), shoes.end()); memset (flag, , sizeof (flag));
for (int i = ; i < n; ++ i) {
if (flag[i]) {
continue;
}
for (int j = ; j < n; ++ j) {
if (i == j) continue;
else {
if (shoes[i].first <= shoes[j].first && shoes[i].second >= shoes[j].second) {
flag[i] = ;
}
}
}
}
int cur = , ans = ;
for (; cur < shoes.size() && flag[cur]; cur ++);
int last_end = shoes[cur].second, this_begin;
for (int i = cur + ; i < shoes.size(); ++ i) {
if (flag[i]) continue;
this_begin = shoes[i].first;
if (last_end <= this_begin) {
ans ++;
last_end = shoes[i].second;
}
}
cout << ans << endl; }
return ;
}
2149 Problem D:
一道大数题目。在n个大数中寻找最小的数。大数推荐使用Java大数类，相对来说代码比较清晰。也可以直接开一个数组进行模拟。
import java.math.*;
import java.io.*;
import java.util.*; public class Main {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
BigInteger ans = BigInteger.ZERO;
for (int i = 0; i < n; ++i) {
BigInteger a = in.nextBigInteger();
if (i == 0) {
ans = a;
} else {
ans = ans.min(a);
}
}
System.out.println (ans);
}
}
}
2150 Problem E:
一道简单的数学题目。稍微推导一下就会发现这个函数最多只有六项。分别是a, b, b - a, -a, -b, a - b六个数，只要我们去一下重复的数即可。去重方法可以用一个字符串数组来做，这里用了set容器的性质进行了去重操作。
/****************************************/
/***** Desgard_Duan *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric> using namespace std; inline void get_val(int &a) {
int value = , s = ;
char c;
while ((c = getchar()) == ' ' || c == '\n');
if (c == '-') s = -s;
else value = c - ;
while ((c = getchar()) >= '' && c <= '')
value = value * + c - ;
a = s * value;
} int a, b, n;
set<int> S;
int main () {
while (cin >> a >> b >> n) {
S.clear();
if (n >= ) {
S.insert (a);
S.insert (b);
S.insert (b - a);
S.insert (-a);
S.insert (-b);
S.insert (a - b);
cout << S.size() << endl;
continue;
} else {
int last = a, now = b, t;
S.insert (a);
S.insert (b);
for (int i = ; i <= n; ++ i) {
S.insert (now - last);
t = now;
now = now - last;
last = t;
}
cout << S.size() << endl;
}
}
return ;
}
最后，感谢这次的命题者：王浩宇（stdiohero），叶鹏(yeahpeng)，王驰（wid），谢文亮（Dim），朱吴帅（JM）同学为我们出的这套热身题目。祝大家在参赛后有所提高。谢谢大家。
——Desgard_Duan
2014.10.31
