題目列表：
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 矩陣取數(shù)問題
題目鏈接：點擊這里
題意：一個
例如：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。
思路：預(yù)處理乡洼，把所有
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 這種左右對稱的字符串。
串的子串：一個串的子串指此（字符）串中連續(xù)的一部分字符構(gòu)成的子（字符）串
例如 abc 這個串的子串：空串轻绞、a采记、b、c政勃、ab唧龄、bc、abc
思路：動態(tài)規(guī)劃奸远。
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個數(shù)和為0
題目鏈接：點擊這里
題意：給出一個長度為N的無序數(shù)組选侨，數(shù)組中的元素為整數(shù)，有正有負包括0然走，并互不相等。從中找出所有和 = 0的3個數(shù)的組合戏挡。如果沒有這樣的組合芍瑞，輸出No Solution。如果有多個褐墅，按照3個數(shù)中最小的數(shù)從小到大排序拆檬，如果最小的數(shù)相等則按照第二小的數(shù)排序。
思路：雙指針妥凳。
注意：本題數(shù)據(jù)保證了數(shù)組元素互不相等竟贯，降低了難度。
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無關(guān)的數(shù)
題目鏈接：點擊這里
題意：一個正整數(shù)逝钥，如果它能被 7 整除屑那，或者它的十進制表示法中某個位數(shù)上的數(shù)字為 7，則稱其為與 7 相關(guān)的數(shù)艘款。求所有小于等于 N 的且與 7 無關(guān)的正整數(shù)的平方和持际。
例如：N = 8，<= 8 與 7 無關(guān)的數(shù)包括：1 2 3 4 5 6 8哗咆，平方和為：155蜘欲。
思路：如題。
注意：由于涉及到多次查詢晌柬，所以姥份，先把小于等于 N 的且與 7 無關(guān)的正整數(shù)找出來郭脂，然后再預(yù)處理出這些正整數(shù)平方和的前綴和。
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個數(shù)和為0
題目鏈接：點擊這里
題意：給出 N 個整數(shù)澈歉，你來判斷一下是否能夠選出 4 個數(shù)展鸡，他們的和為 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;
}
