1. 回文串构造

题目描述
给定任意一个字符串，它至少需要替换多少个字符才能将它变为回文字符串。一次替换操作中，牛牛可以选择任何一个位置的字符，将其变为另外一个字符。

• 第一行一个整数 N，表示回文串的长度
• 接下来一行 N 个小写字母表示字符串

• 输出一个整数表示答案

// 输入
5
acacb

// 输出
1 

将 b 替换成 a 即可，故答案为 1

2. 方格染色

题目描述
给定 N\*M 的方格图，现在要求你对其中每个 1\*1 的小方格进行染色，要求如下：

• 每种颜色的各自数都是相同的
• 相邻格子染的颜色不同
• 所有格子必须染色

输入
- 第一行一个整数 T，表示测试数据的组数(1<=T<=100)
- 接下来 T 行每行两个空格分隔的正整数 N, M，代表方格图的行数和列数

输出

• 输出 T 行，每行一个整数表示答案

// 输入
1
2 2

// 输出
2

题目描述
牛牛进入了方格世界，方格世界由 n*m 个方格构成的高为 n 宽为 m 的矩形，牛牛所在的方格为 (1,1)，而方格世界的出口在(n,m)。在方格世界中，牛牛只能**向上走或者向左或向右走**，而且牛牛走过的方格不能再次进入。牛牛想知道他有多少种走出方格世界的路径，答案可能很大请对 1000000007  取模。


输入

• 第一行一个整数 t，表示有 t 组测试数据的组数(1<=t<=100000)
• 接下来 t 行每行两个正整数 n, m

输出

• 输出 t 行，每行一个整数表示答案

例子

// 输入
2
2 2
3 3

// 输出
2
9

4. 牛牛们上班

题目描述
在工厂中，有 N 个牛牛工作在一个流水线上，流水线可以看作一个坐标轴，第 i 个牛牛的位置为 Xi（i 为下标），延长其手臂的长度为 Li，手臂可以朝向正向和反向，即第 i 个牛牛在流水线的工作范围为[Xi - Li,Xi + Li]，你需要计算最多可以让多少个牛牛同时在流水线上工作且工作范围互不相交（相交一个点也算相交）。

输入

• 第一行一个整数 n
• 接下来 n 行，每行两个整数，Xi 和 Li
• 接下来 T 行每行两个空格分隔的正整数 N, M，代表方格图的行数和列数

输出

• 一个整数表示答案

例子

// 输入
5
2 3
7 1
5 1
8 3
0 2

// 输出
2