转载请注明出处：http://www.cnblogs.com/xianyue
题1：最长连续非降子序列
题目描述
给你一个长度为n个数组，求该数组的最长连续非降子序列的长度。
输入
第一行一个正整数n，表示数组的长度。
第二行n个正整数，表示数组a。
输出
数组a的最长连续非降子序列的长度。
样例输入
6
2 2 1 3 4 1
样例输出
3
题解
if a[i] >= a[i-1]: f[i] = f[i-1] + 1
else : f[i] = 1
然后求最大的f[i]，即为答案。
代码
#include <iostream>
using namespace std;
int n, a[100100], f[100100], res = 0;
int main()
{
cin >>n;
for (int i = 0; i < n; i ++)
cin >> a[i];
f[0] = 1;
for (int i = 1; i < n; i ++)
{
if (a[i] >= a[i-1])
f[i] = f[i-1] + 1;
else
f[i] = 1;
}
for (int i = 0; i < n; i ++)
{
if (f[i] > res)
res = f[i];
}
cout << res << endl;
return 0;
}
题2：AB与BA子串
题目描述
给你一个字符串S，请问能否在里面找到不重叠的两个子串"AB"和"BA"？
输入
一个字符串S
输出
如果能够在S中找到一对不重叠的"AB"和"BA"子串，则输出"YES"，否则输出"NO"。
样例输入
BACFXAB
样例输出
YES
题解
我们可以开两个数组f,g，其中：
- f[i][0]表示S(0...i)中是否包含"AB"
- f[i][1]表示S(0...i)中是否包含"BA"
- g[i][0]表示S(i...n-1)中是否包含"AB"
- g[i][1]表示S(i...n-1)中是否包含"BA"
其中S(i...j)代表S[i]到S[j]组成的一个S的子串。
然后正序循环一遍就能求得f，逆序循环一遍就能求得g。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100010;
char s[maxn];
int f[maxn][2], g[maxn][2], n;
int main()
{
cin >> s;
n = strlen(s);
for (int i = 1; i < n; i ++)
{
int t1 = (s[i-1] == 'A' && s[i] == 'B');
f[i][0] = max(f[i-1][0], t1);
int t2 = (s[i-1] == 'B' && s[i] == 'A');
f[i][1] = max(f[i-1][1], t2);
}
for (int i = n-1; i >= 0; i --)
{
int t1 = (s[i] == 'A' && s[i+1] == 'B');
g[i][0] = max(g[i+1][0], t1);
int t2 = (s[i] == 'B' && s[i+1] == 'A');
g[i][1] = max(g[i+1][1], t2);
}
bool flag = false;
for (int i = 1; i < n-1; i ++)
if (f[i][0] && g[i+1][1] || f[i][1] && g[i+1][0])
{
flag = true;
break;
}
puts(flag ? "YES" : "NO");
return 0;
}
题3：遛狗
题目描述
丁丁今天领养了一只狗狗——灰灰。但是他发现为了保持狗狗健康，他必须在连续的两天至少出门遛狗k千米。假设k=5，那么假设我今天遛狗遛了2千米，则我明天必须至少遛狗3千米才能保持狗狗健康。丁丁看了一下字节接下来n天的计划表，发现自己第i天需要出门a[i]千米（买零食，超市购物……）。但是他发现自己的计划表并不能满足遛狗计划，但是他又不想多跑，所以请你帮他设计一张新的计划表，b[i]>=a[i]，并且能够满足遛狗计划。我们需要增加的千米数最少的一种方案。
输入
第一行两个正整数n,k。
第二行n个正整数表示数组a。
输出
第一行一个正整数用于表示至少需要增加的千米数。
第二行n个数字表示数组b。
样例输入1
3 5
2 0 1
样例输出1
4
2 3 2
样例输入2
4 6
2 4 3 5
样例输出2
0
2 4 3 5
题解
状态转移方程为：
b[i] = max(a[i], k-b[i-1])
代码
#include <iostream>
using namespace std;
const int maxn = 550;
int n, a[maxn], b[maxn], k, sum = 0;
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i ++)
cin >> a[i];
b[0] = a[0];
for (int i = 1; i < n; i ++)
{
b[i] = max(a[i], k-b[i-1]);
sum += b[i] - a[i];
}
cout << sum << endl;
for (int i = 0; i < n; i ++)
cout << b[i] << " ";
return 0;
}
题4：不同的后缀
题目描述
给你一个长度为n的数组a（坐标从1开始），然后接下来有m次询问，每一次询问都给出一个数i，你需要回答出a[i]到a[n]中间有多少个不同的数。
输入
第一行两个正整数n，m。
第二行n个数表示数组a。
然后m行，每一行一个正整数i（1<=i<=n）。
输出
针对每一个询问i给出a[i]到a[n]之间有多少个不同的数。
样例输入
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10
样例输出
6
6
6
6
6
5
4
3
2
1
题解
开一个数组f，f[i]表示a[i]到a[n]之间有多少个不同的数。
状态转移方程为：
f[i] = f[i+1] + (a[i]有没有出现过?1:0)
不过在实现的时候我是开了一个变量cnt记录的。
代码
#include <iostream>
#include <map>
using namespace std;
const int maxn = 100010;
map<int, int> mp;
int n, m, a[maxn], f[maxn], l, cnt;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> a[i];
cnt = 0;
for (int i = n; i >= 1; i --)
{
if (!mp[ a[i] ])
{
mp[ a[i] ] = 1;
cnt ++;
}
f[i] = cnt;
}
while (m--)
{
cin >> l;
cout << f[l] << endl;
}
return 0;
}
题5： 三分数组
题目描述
给你一个长度为n的数组a，在其中找i，j（1<=i<=j<n），满足：
求方案数。
输入
第一行一个正整数n。
第二行n个数表示数组a。
输出
输出有多少种方案
样例输入
5
1 2 3 0 3
样例输出
2
题解
这里假设两个分隔的数。
首先计算一下数组a的总和sum。
s[i]表示a[1]到a[i]的总和
然后开一个数组f1，f1[i]表示a[1]到a[i]一共有多少个数值为sum/3的。
f2[i]表示以a[i]为第二个分割的数的方案数。
则：
f1[i] = f1[i-1] + (s[i] == sum/3)
f2[i] = f2[i-1] + f1[i-1] * (s[i] == sum*2/3)
代码
#include <iostream>
using namespace std;
const int maxn = 500050;
int n, a[maxn];
long long sum = 0, s[maxn], f1[maxn], f2[maxn];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n; i ++)
sum += a[i];
s[0] = a[0];
for (int i = 1; i < n; i ++)
s[i] = s[i-1] + a[i];
if (sum % 3 != 0)
cout << "0" << endl;
else
{
f1[0] = (a[0] == sum/3);
for (int i = 1; i < n - 1; i ++)
{
f1[i] = f1[i-1] + (s[i] == sum/3);
f2[i] = f2[i-1] + f1[i-1] * (s[i] == sum*2/3);
}
cout << f2[n-2] << endl;
}
return 0;
}