题目列表：
51Nod 1081 子段求和
题目链接：点击这里
题意：给出一个长度为
例如，1 3 7 9 -1，查询第 2 个元素开始长度为 3 的子段和，3 + 7 + 9 = 19，输出19。
思路：一维前缀和。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 50010;
ll a[N];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
a[i] = a[i - 1] + x;
}
int q;
scanf("%d", &q);
while(q--)
{
int l, len;
scanf("%d%d", &l, &len);
int r = l + len - 1;
printf("%lld\n", a[r] - a[l - 1]);
}
return 0;
}
51Nod 1083 矩阵取数问题
题目链接：点击这里
题意：一个
例如：3 * 3 的方格。
1 3 3
2 1 3
2 2 1
能够获得的最大价值为：11。
思路：记忆化搜索。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 510;
int a[N][N];
int f[N][N];
int dx[] = {1, 0};
int dy[] = {0, 1};
int n;
int dfs(int x, int y)
{
int &v = f[x][y];
if(v) return f[x][y];
v = a[x][y];
for(int i = 0; i < 2; ++i)
{
int tx = x + dx[i], ty = y + dy[i];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= n)
{
v = max(v, dfs(tx, ty) + a[x][y]);
}
}
return v;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
}
}
int ans = -1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
ans = max(ans, dfs(i, j));
}
}
printf("%d", ans);
return 0;
}
51Nod 1087 1 10 100 1000
题目链接：点击这里
题意：1,10,100,1000...组成序列1101001000...，求这个序列的第N位是0还是1。
思路：预处理，把所有
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<unordered_set>
using namespace std;
typedef long long ll;
const int N = 510;
unordered_set<int> s;
int main()
{
int d = 1;
int t = 1;
while(t <= 1e9)
{
s.insert(t);
t += d;
d++;
}
int T;
scanf("%d", &T);
while(T--)
{
int x;
scanf("%d", &x);
if(s.count(x)) puts("1");
else puts("0");
}
return 0;
}
51Nod 1088 最长回文子串
题目链接：点击这里
题意：输入一个字符串 Str，输出 Str 里最长回文子串的长度。
回文串：指 aba、abba、cccbccc、aaaa 这种左右对称的字符串。
串的子串：一个串的子串指此（字符）串中连续的一部分字符构成的子（字符）串
例如 abc 这个串的子串：空串、a、b、c、ab、bc、abc
思路：动态规划。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1010;
char a[N];
int dp[N][N];
int main()
{
scanf("%s", a);
int len = strlen(a);
if(len == 0)
{
puts("0");
return 0;
}
int ans = 1;
for(int i = 0; i < len; i++)
{
dp[i][i] = 1;
if(i + 1 < len)
{
if(a[i] == a[i + 1])
{
ans = 2;
dp[i][i + 1] = 1;
}
}
}
for(int L = 2; L <= len; L++)
{
for(int i = 0; i + L - 1 < len; i++)
{
int j = i + L - 1;
if(a[i] == a[j] && dp[i + 1][j - 1] == 1)
{
dp[i][j] = 1;
ans = L;
}
}
}
printf("%d\n", ans);
return 0;
}
51Nod 1090 3个数和为0
题目链接：点击这里
题意：给出一个长度为N的无序数组，数组中的元素为整数，有正有负包括0，并互不相等。从中找出所有和 = 0的3个数的组合。如果没有这样的组合，输出No Solution。如果有多个，按照3个数中最小的数从小到大排序，如果最小的数相等则按照第二小的数排序。
思路：双指针。
注意：本题数据保证了数组元素互不相等，降低了难度。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
int a[N];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
bool have_ans = false;
for(int i = 0; i < n; i++)
{
int l = i + 1, r = n - 1;
while(l < r)
{
int t = a[l] + a[r];
if(t == -a[i])
{
have_ans = true;
printf("%d %d %d\n", a[i], a[l], a[r]);
l++;
r--;
}
else if(t < -a[i]) l++;
else r--;
}
}
if(!have_ans) puts("No Solution");
return 0;
}
51Nod 1082 与7无关的数
题目链接：点击这里
题意：一个正整数，如果它能被 7 整除，或者它的十进制表示法中某个位数上的数字为 7，则称其为与 7 相关的数。求所有小于等于 N 的且与 7 无关的正整数的平方和。
例如：N = 8，<= 8 与 7 无关的数包括：1 2 3 4 5 6 8，平方和为：155。
思路：如题。
注意：由于涉及到多次查询，所以，先把小于等于 N 的且与 7 无关的正整数找出来，然后再预处理出这些正整数平方和的前缀和。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<unordered_set>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
bool st[N];
ll s[N];
bool judge(int x)
{
if(x % 7 == 0) return true;
while(x)
{
if(x % 10 == 7) return true;
x /= 10;
}
return false;
}
int main()
{
for(int i = 1; i <= N; i++)
if(judge(i))
st[i] = true;
ll t = 0;
for(int i = 1; i <= N; i++)
{
if(st[i] == false)
t += (ll)i * i;
s[i] = t;
}
int T;
scanf("%d", &T);
while(T--)
{
int x;
scanf("%d", &x);
printf("%lld\n", s[x]);
}
return 0;
}
51Nod 1267 4个数和为0
题目链接：点击这里
题意：给出 N 个整数，你来判断一下是否能够选出 4 个数，他们的和为 0，可以则输出"Yes"，否则输出"No"。
思路：双指针。
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int a[N];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
bool have_ans = false;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
int l = j + 1, r = n - 1;
while(l < r)
{
int t = a[l] + a[r];
if(t < -a[i]-a[j]) l++;
else if(t > -a[i]-a[j]) r--;
else
{
have_ans = true;
break;
}
}
if(have_ans) break;
}
if(have_ans) break;
}
if(have_ans) puts("Yes");
else puts("No");
return 0;
}
