A - Reign
题解
最大子段和+\(DP\)。
预处理两个数组：
- \(p[i]\)表示 \(i\) 之前的最大子段和。
- \(l[i]\)表示 \(i\) 之后的最大子段和。
最后直接输出即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#define int long long
#define gI gi
#define itn int
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
int t, n, m, k, ans, a[100003], p[100003], l[100003];
signed main()
{
//File("REIGN");
t = gi();
while (t--)
{
n = gi(), k = gi();
for (itn i = 1; i <= n; i+=1) a[i] = gi();
memset(p, 0, sizeof(p)); memset(l, 0, sizeof(l));
ans = -0x7fffffff;
for (itn i = 1; i <= n; i+=1)
{
if (p[i - 1] < 0) p[i] = a[i];
else p[i] = p[i - 1] + a[i];
}
p[0] = -0x7fffffff;
for (itn i = 1; i <= n; i+=1) p[i] = max(p[i], p[i - 1]);
for (int i = n; i >= 1; i-=1)
{
if (l[i + 1] < 0) l[i] = a[i];
else l[i] = l[i + 1] + a[i];
}
l[n + 1] = -0x7fffffff;
for (itn i = n; i >= 1; i-=1) l[i] = max(l[i], l[i + 1]);
for (int i = 1; i < n - k; i+=1) ans = max(ans, p[i] + l[i + k + 1]);
printf("%lld\n", ans);
}
return 0;
}
C - Strongly Connected City
题意简述
给定\(n\)条水平的单向街道和\(m\)条竖直单向的街道，其交点共有\(n \times m\)个，问这些节点是否都能互相到达。
\(2 \leq n,m \leq 20\)
题解
只需要判断最外圈是不是一个环即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <string>
#define gI gi
#define itn int
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
bool fl = false;
int n, m, a[25][25][2], tot, vis[25][25];
char s[2][25];
int main()
{
n = gi(), m = gi();
string s[3];
cin >> s[1];
if (s[1][0] == s[1][n - 1]) {puts("NO"); return 0;}
cin >> s[2];
if (s[1][0] == '<' && s[2][0] == '^') {puts("NO"); return 0;}
if (s[1][0] == '>' && s[2][m - 1] == '^') {puts("NO"); return 0;}
if (s[1][n - 1] == '<' && s[2][0] == 'v') {puts("NO"); return 0;}
if (s[1][n - 1] == '>' && s[2][m - 1] == 'v') {puts("NO"); return 0;}
puts("YES");
return 0;
}
F - Chef and Digit Jumps
题解
\(BFS\)裸题。
有一个优化：让每一个点在队列中只会出现一次，优化时间复杂度。
注意一些细节。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <queue>
#define gI gi
#define itn int
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
char s[100003];
int n, m, len, p, ans, sum, b[1000003], vis[100003];
vector <int> a[15];
queue <int> q;
int main()
{
//File("DIGJUMP");
scanf("%s", s + 1);
len = strlen(s + 1);
for (int i = 1; i <= len; i+=1)
{
a[s[i] - '0'].push_back(i);
}
q.push(1); b[1] = 0;
while (!q.empty())
{
int x = q.front(); q.pop();
if (x == len) break;
int y = s[x] - '0';
if (!vis[y])
{
vis[s[x] - '0'] = 1;
for (int i = 0; i < a[y].size(); i+=1)
{
int z = a[y][i];
if (z != x && b[z] == 0)
{
b[z] = b[x] + 1;
q.push(z);
}
}
}
if (x - 1 >= 1 && b[x - 1] == 0) {b[x - 1] = b[x] + 1; q.push(x - 1);}
if (x + 1 <= len && b[x + 1] == 0) {b[x + 1] = b[x] + 1; q.push(x + 1);}
}
printf("%d\n", b[len]);
return 0;
}
总结
这次做题做得很不理想。
\(T3\)时间复杂度算错浪费了很多时间。
\(T1\)想了很久才想到正解。
要多多练习，才能有提高啊！