NOIP2015
跳石头
题目：
【问题描述】
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选
择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终
点的岩石） 。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达
终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳
跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能
移走起点和终点的岩石） 。
【输入格式】
输入文件名为 stone.in。
输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终
点之间的岩石数，以及组委会至多移走的岩石数。
接下来 N 行，每行一个整数，第 i 行的整数 Di（ 0 < Di < L ）表示第 i 块岩石与
起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同
一个位置。
【输出格式】
输出文件名为 stone.out。
输出文件只包含一个整数，即最短跳跃距离的最大值。
【输入输出样例 1】
stone.in stone.out
25 5 2
2
11
14
17
21
4
见选手目录下的 stone/stone1.in 和 stone/stone1.ans。
【输入输出样例 1 说明】
将与起点距离为 2 和 14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离
17 的岩石跳到距离 21 的岩石，或者从距离 21 的岩石跳到终点） 。
【输入输出样例 2】
见选手目录下的 stone/stone2.in 和 stone/stone2.ans。
【 数据规模与约定 】
对于 20%的数据，0 ≤ M ≤ N ≤ 10。
对于 50%的数据，0 ≤ M ≤ N ≤ 100。
对于 100%的数据，0 ≤ M ≤ N ≤ 50,000，1 ≤ L ≤ 1,000,000,000。
解题思路： 二分答案
所谓二分答案，就是求出答案的区间，然后判断所求的答案是否满足题目的条件，并以此来调整区间，最后求出解。使用二分答案要满足一些性质：
1. 能快速判断
2. 能够算出答案区间
3. 可行解满足单调性（若x可行，则x+1也可）
//模板
int l = min_ans, r = max_ans;
for (; l < r ;){ int mid = (l + r + 1) / 2; if (ok(mid)) l = mid; else r = mid - 1;
} 此题代码
#include <cstdio>
#include <iostream>
using namespace std;
#define oo 50000 + 10
#define Name "stone"int L, N, M;
int l, r, ans;
int a[oo] = {
0};
int find ( int dis ){int tot = 0, tod = 0;for ( int i = 1; i <= N+1; i++) if ( a[i] - a[tod] >= dis ) tot ++, tod = i;return tot > N - M;
}
int main(){freopen( Name".in", "r", stdin);freopen( Name".out", "w", stdout);scanf( "%d%d%d", &L, &N, &M);for(int i = 1 ; i <= N; i++) scanf( "%d", &a[i]);a[ N+1 ] = L,l = 0, r = L;for ( ;l <= r; ){int mid = ( l + r ) >> 1;if( find(mid) ) ans = mid, l = mid + 1;else r = mid - 1;}printf("%d",ans);return 0;
}子串
题目：
2 ． 子串
(substring.cpp/c/pas)
【问题描述】
有两个仅包含小写英文字母的字符串 A 和 B。 现在要从字符串 A 中取出 k 个 互不重
叠 的非空子串， 然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一
个新的字符串，请问有多少种方案可以使得这个新串与字符串 B 相等？注意：子串取出
的位置不同也认为是不同的方案 。
【输入格式】
输入文件名为 substring.in。
第一行是三个正整数 n，m，k，分别表示字符串 A 的长度，字符串 B 的长度，以及问
题描述中所提到的 k，每两个整数之间用一个空格隔开。
第二行包含一个长度为 n 的字符串，表示字符串 A。
第三行包含一个长度为 m 的字符串，表示字符串 B。
【输出格式】
输出文件名为 substring.out。
输出共一行，包含一个整数，表示所求方案数。 由于答案可能很大，所以这里要求输
出答案对 1,000,000,007 取模 的结果。
【输入输出样例 1】
substring.in substring.out
6 3 1
aabaab
aab
2
见选手目录下 substring/substring1.in 与 substring/substring1.ans。
【输入输出样例 2】
substring.in substring.out
6 3 2
aabaab
aab
7
见选手目录下 substring/substring2.in 与 substring/substring2.ans。
【输入输出样例 3】
substring.in substring.out
6 3 3
aabaab
aab
7
见选手目录下 substring/substring3.in 与 substring/substring3.ans。
全国信息学奥林匹克联赛（NOIP2015）复赛 提高组 day2
第 4 页共 6 页
【输入输出样例说明】
所有合法方案如下： （加下划线的部分表示取出的子串）
样例 1：aab aab / aab aab
样例 2：a ab aab / a aba ab / a a ba ab / aab a ab
aa b aab / aa baa b / aab aa b
样例 3：a a b aab / a a baa b / a ab a a b / a aba a b
a a b a a b / a a ba a b / aab a a b
【输入输出样例 4】
见选手目录下 substring/substring4.in 与 substring/substring4.ans。
【数据规模与约定】
对于第 1 组数据：1≤n≤500，1≤m≤50，k=1；
对于第 2 组至第 3 组数据：1≤n≤500，1≤m≤50，k=2；
对于第 4 组至第 5 组数据：1≤n≤500，1≤m≤50，k=m；
对于第 1 组至第 7 组数据：1≤n≤500，1≤m≤50，1≤k≤m；
对于第 1 组至第 9 组数据：1≤n≤1000，1≤m≤100，1≤k≤m；
对于所有 10 组数据：1≤n≤1000，1≤m≤200，1≤k≤m。
解题思路： DP
此题是字符串匹配的问题，可以想到用DP来解决，我们可以使用dp[i][j][k]来表示a串匹配到j，b串匹配到i，a被分为k快时的方案数，这时，就可以比较i+1位和j+1位是否相等，若相等则可以把第j为和第i位看成一个整体，就有方程：
dp[i][j][k] = dp[i-1][j-1][k-1] + dp[i-1][j-1][k]
#include <cstdio>
#include <iostream>
#include <algorithm>
#define Mod 100000007
#define LL long long
using namespace std;char a[1010], b[205];
LL f[2][205][205], dp[2][205][205];
int n, m, K, now, last;int main(){scanf( "%d%d%d", &n, &m, &K);scanf( "%s%s", a+1, b+1);now = 1, last = 0;dp[0][0][0] = 1;for ( int i = 1; i <= n; i++){dp[now][0][0] = 1;for ( int j = 1; j <= m; j++)for ( int k = 1; k <= K; k++){if ( a[i] == b[j] ) f[now][j][k] = ( f[last][j-1][k] + dp[last][j-1][k-1] ) % Mod;else f[now][j][k] = 0;dp[now][j][k] = ( dp[last][j][k] + f[now][j][k] ) % Mod; }swap( now, last);}printf( "%lld", dp[last][m][K]);
}其中，用到了滚动数组来优化