Atcoder Beginner Contest 369
C-Count Arithmetic Subarrays
题意
给出一个长度为 \(n\) 的序列 \(A\)，求有多少个 \(A\) 的连续子序列为等差数列。
思路
对于递增的右端点，左端点不减。
使用双指针，枚举右端点，扫描左端点。
时间复杂度：\(O(n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
int a[N], n;
ll ans;
void solve() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1, j = 1; i <= n; i ++) {
j = max(j, i);
while (i < n && j < n && a[j + 1] - a[j] == a[i + 1] - a[i]) j ++;
ans += j - i + 1;
}
cout << ans << "\n";
}
int main() {
int T = 1;
// cin >> T;
while (T --)
solve();
return 0;
}
D-Bonus EXP
题意
给出一个长度为 \(n\) 的序列 \(A\)，每次有两种选择。
- 将得分增加 \(A_i\)，若这是第偶数次执行这个操作，将得分额外增加 \(A_i\)。
- 什么也不做。
求最大得分。
思路
定义 \(dp_{i,0/1}\) 表示前 \(i\) 个数，做了偶数或奇数次操作 \(1\) 的最大得分。
初始状态 \(dp_{0,0}=0\)。
\(dp_{i,0}\) 转移方程：
\[dp_{i,0}=\max(dp_{i-1,0},dp_{i-1,1}+2\times a_i) \]\(dp_{i,1}\) 转移方程：
\[dp_{i,1}=\max(dp_{i-1,1},dp_{i-1,0}+a_i) \]时间复杂度：\(O(n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
int n, a[N];
ll dp[N][2];
void solve() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
memset(dp, -0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; i ++) {
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + a[i]);
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + 2 * a[i]);
}
cout << max(dp[n][0], dp[n][1]) << "\n";
}
int main() {
int T = 1;
// cin >> T;
while (T --)
solve();
return 0;
}
E-Sightseeing Tour
题意
给定一张 \(n\) 个点 \(m\) 条边的图，有 \(q\) 次查询。
每次查询给出 \(k\) 条边，求一条 \(1\) 到 \(n\) 并且经过这 \(k\) 条边的最短路径。
思路
先用 Floyd 求出全源最短路，再枚举给出的边的排列，即经过顺序。
搜索从每条边的哪个点进入，在两条边的端点之间走最短路，并加上该边权。
时间复杂度：\(O(n^3+q k!2^k)\)。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 405, M = 2e5 + 5;
int n, m, q, K, id[N];
ll f[N][N], ans;
int u[M], v[M], w[M];
void dfs(int p, int x, ll cost) {
if (cost > ans) return ;
if (x == u[id[p]]) x = v[id[p]];
else x = u[id[p]];
cost += w[id[p]];
if (p == K) {
cost += f[x][n];
ans = min(ans, cost);
return ;
}
dfs(p + 1, u[id[p + 1]], cost + f[x][u[id[p + 1]]]);
dfs(p + 1, v[id[p + 1]], cost + f[x][v[id[p + 1]]]);
}
void solve() {
cin >> n >> m;
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= m; i ++) {
cin >> u[i] >> v[i] >> w[i];
f[u[i]][v[i]] = min(f[u[i]][v[i]], 1ll * w[i]);
f[v[i]][u[i]] = min(f[v[i]][u[i]], 1ll * w[i]);
}
for (int i = 1; i <= n; i ++) f[i][i] = 0;
for (int k = 1; k <= n; k ++) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
cin >> q;
for (int i = 1; i <= q; i ++) {
cin >> K;
for (int j = 1; j <= K; j ++) cin >> id[j];
sort(id + 1, id + K + 1);
ans = 1e18;
do {
dfs(1, u[id[1]], f[1][u[id[1]]]);
dfs(1, v[id[1]], f[1][v[id[1]]]);
} while(next_permutation(id + 1, id + K + 1));
cout << ans << "\n";
}
}
int main() {
int T = 1;
// cin >> T;
while (T --)
solve();
return 0;
}
F-Gather Coins
题意
给定一个 \(H\times W\) 的网格图，上面有 \(n\) 个格子有金币。
只能向右和向下走，求从 \((1,1)\) 走到 \((H,W)\) 最多能捡到多少金币，并给出一种路径。
思路
考虑对金币动态规划，每个金币 \((x,y)\) 只能从金币 \((p,q)(p\le x)(q \le y)\) 转移过来，转移方程：
\[dp_i = \max dp_j+1 \]暴力转移时间复杂度 \(O(n^2)\)，不能通过，而且存在后效性。
发现转移限制为二维偏序，可先把 \(x\) 从小到大排序，再用线段树维护所有 \(y\)。统计最小值及最小值的位置。
路径可记录一个 \(pre_i\) 表示 \(i\) 从哪里转移过来，倒着输出路径即可。
坑点：排序时不能只排 \(x\)，当 \(x\) 相同时要按 \(y\) 从小到大排序。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define ll long long
const int N = 2e5 + 5;
int h, w, n;
struct P {int x, y;};
struct segt {
struct node {
int l, r, mx, MX;
} t[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
friend node operator + (node a, node b) {
node res; res.l = a.l, res.r = b.r;
if (a.mx > b.mx) res.mx = a.mx, res.MX = a.MX;
else res.mx = b.mx, res.MX = b.MX;
return res;
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
}
void modify(int p, int id, int v, int val) {
if (t[p].l == t[p].r) {
t[p].mx = max(t[p].mx, v);
if (t[p].mx == v) t[p].MX = val;
return ;
}
if (id <= t[ls].r) modify(ls, id, v, val);
else modify(rs, id, v, val);
t[p] = t[ls] + t[rs];
}
node query(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) return t[p];
node res; res.l = -1;
if (t[ls].r >= l) res = query(ls, l, r);
if (t[rs].l <= r) {
if (res.l == -1) res = query(rs, l, r);
else res = res + query(rs, l, r);
}
return res;
}
} T;
P a[N];
bool cmp(P A, P B) {
if (A.x == B.x) return A.y < B.y;
return A.x < B.x;
}
int dp[N], pre[N], ans, lst;
vector <int> path;
string ANS[N];
void solve() {
cin >> h >> w >> n;
for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
a[0].x = 1, a[0].y = 1;
a[n + 1].x = h, a[n + 1].y = w;
sort(a + 1, a + n + 1, cmp);
T.build(1, 1, max(h, w));
T.modify(1, a[1].y, 1, 1);
pre[1] = 0, dp[1] = 1, ans = 1, lst = 1;
for (int i = 2; i <= n; i ++) {
segt::node res = T.query(1, 1, a[i].y);
dp[i] = dp[res.MX] + 1;
pre[i] = res.MX;
if (dp[i] > ans) {
ans = dp[i];
lst = i;
}
T.modify(1, a[i].y, dp[i], i);
}
pre[n + 1] = lst;
int now = n + 1, tot = 0;
while (now) {
lst = pre[now], tot ++;
for (int i = 1; i <= a[now].x - a[lst].x; i ++) ANS[tot] += 'D';
for (int i = 1; i <= a[now].y - a[lst].y; i ++) ANS[tot] += 'R';
now = pre[now];
}
cout << ans << "\n";
for (int i = tot; i >= 1; i --)
cout << ANS[i];
cout << "\n";
}
signed main() {
int T = 1;
// cin >> T;
while (T --)
solve();
return 0;
}