AtCoder ABC176
前面几个题都比较简单,但是F题很考验基本功
C - Step
签到题,贪心维护一个当前的最高值
D - Wizard in Maze
最短路的做法,最小堆维护
/*
* @Author: C.D.
* @Date: 2023-12-12 08:14:36
* @LastEditors: C.D.
* @LastEditTime: 2023-12-12 11:00:11
* @FilePath: atcoder.cpp
*
* Copyright (c) 2023 by C.D./tongwoo.cn, All Rights Reserved.
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int h, w;
int ch, cw, dh, dw;
char mat[1002][1002];
int dist[1002][1002];
struct Grid {
int step;
int r, c;
Grid(int _step, int _r, int _c) {
step = _step, r = _r, c = _c;
}
bool operator <(const Grid& other) const {
return this->step < other.step;
}
bool operator >(const Grid& other) const {
return this->step > other.step;
}
};
priority_queue<Grid, vector<Grid>, greater<Grid>> qu;
int dirs[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };
int main() {
//freopen("in.txt", "r", stdin);
scanf("%d%d", &h, &w);
scanf("%d%d%d%d", &ch, &cw, &dh, &dw);
ch--, cw--;
dh--, dw--;
for (int i = 0; i < h; ++i) {
scanf("%s", mat[i]);
}
memset(dist, 0x33, sizeof(dist));
dist[ch][cw] = 0;
Grid grid(0, ch, cw);
qu.push(grid);
//qu.push(Grid(1, 0, 0));
while (!qu.empty()) {
Grid top = qu.top();
qu.pop();
int r = top.r, c = top.c;
int step = top.step;
if (r == dh && c == dw) {
break;
}
for (int i = 0; i < 4; i++) {
int nr = r + dirs[i][0], nc = c + dirs[i][1];
if (nr >= 0 && nr < h && nc >= 0 && nc < w && mat[nr][nc] == '.') {
if (dist[nr][nc] > step) {
dist[nr][nc] = step;
qu.push(Grid(step, nr, nc));
}
}
}
for (int i = -2; i <= 2; ++i) {
for (int j = -2; j <= 2; ++j) {
int nr = r + i, nc = c + j;
if (nr >= 0 && nr < h && nc >= 0 && nc < w && mat[nr][nc] == '.') {
if (dist[nr][nc] > step + 1) {
dist[nr][nc] = step + 1;
qu.push(Grid(step + 1, nr, nc));
}
}
}
}
}
int ans = dist[dh][dw];
if (ans > 1 << 20) {
ans = -1;
}
printf("%d\n", ans);
return 0;
}
E - Bomber
本题和F题有异曲同工之处
用一个map来记录点
因为答案肯定在maxh和maxw的那些行列中,因此遍历一下行h和列w,如果map[h][w] == 1则跳过,不然就可以直接确定有一个点的答案是maxh+maxw。因为点数量<300000,所以最多遍历300000次,可以做。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int H, W, M;
map<pii, bool> mark;
int h[300005];
int w[300005];
int main() {
//freopen("in.txt", "r", stdin);
scanf("%d%d%d", &H, &W, &M);
for (int i = 0; i < M; ++i) {
int a, b;
scanf("%d%d", &a, &b);
mark[{a, b}] = 1;
h[a] ++, w[b] ++;
}
int maxh = -1, maxw = -1;
for (int i = 1; i <= H; ++i)
maxh = max(maxh, h[i]);
for (int i = 1; i <= W; ++i)
maxw = max(maxw, w[i]);
vector<int> hs, ws;
for (int i = 1; i <= H; ++i) {
if (h[i] == maxh)
hs.push_back(i);
}
for (int i = 1; i <= W; ++i) {
if (w[i] == maxw)
ws.push_back(i);
}
for (auto a : hs) {
for (auto b : ws) {
if (mark[{a, b}]) {
continue;
}
else {
int ans = maxh + maxw;
printf("%d\n", ans);
return 0;
}
}
}
printf("%d\n", maxh + maxw - 1);
return 0;
}
F - Brave CHAIN
首先要确定状态
设dp[i][x][y]是第i次结束后留下牌面为xy的最大得分
看起来很大的状态空间(n*n)其实真正发生转移的不会很多
先考虑得分的转移情况
设每次拿到新的牌的排列情况是:
1.aaa
2.aab
3.abb
4.abc
其中2与3本质相同
我们考虑1
显然可以直接拿走加一分
2 aab
上一轮留下两张牌为ax的情况下,
可以拿走aaa,转移为bx
在上一轮留下牌为bb的情况下,可以拿走bbb,转移为aa
3 abc
唯一可以得分的情况是上一轮留下aa bb cc
然后考虑不得分的转移情况
1.不换牌 不用改变
2.换一张牌
设拿到三张牌abc,前面的状态是xy,
新的状态是ax
转移的时候我们可以遍历剩下的一张牌i,那么
d
p
[
x
]
[
a
]
=
max
?
i
∈
[
1
,
n
]
(
d
p
[
x
]
[
i
]
)
dp[x][a] = \max_{i\in [1,n]}(dp[x][i])
dp[x][a]=maxi∈[1,n]?(dp[x][i])
为了在
O
(
n
)
O(n)
O(n)时间内完成,加入一个维护数组
m
x
mx
mx,维护一行/一列的最大值
3.换两张牌
方法是相似的,现在需要转移两张牌
设新的状态是ab
转移的时候我们需要遍历所有的牌dp[i][j]
那么维护一个最大值就可以
需要注意的是滚动空间。
普通的memcpy是过不了的,因此需要记录一下每次发生update的点对
然后在每次循环结束的时候更新下一个空间
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int n;
int dp[2][2002][2002];
int mx[2002];
int lmx[2002];
int mxy, lmxy; // single point (x, y)
int a[6006];
set<pii> turn; // 记录更新点对
void update(int x, int y, int cur) {
turn.insert({ x, y });
mx[x] = max(mx[x], dp[cur][x][y]);
if (x != y) {
mx[y] = max(mx[y], dp[cur][x][y]);
}
mxy = max(mxy, dp[cur][x][y]);
}
void all_update(int cur) {
int lst = 1 ^ cur;
for (auto it : turn) {
int x = it.first, y = it.second;
dp[lst][x][y] = dp[cur][x][y];
dp[lst][y][x] = dp[cur][y][x];
}
turn.clear();
memcpy(lmx, mx, sizeof(mx));
lmxy = mxy;
}
int main() {
//freopen("in.txt", "r", stdin);
scanf("%d", &n);
for (int i = 0; i < n * 3; ++i) {
scanf("%d", &a[i]);
a[i] --;
}
int upd = 0;
int cur = 2;
int x = a[0], y = a[1];
int p = 0, q = 1;
memset(dp, 0xa3, sizeof(dp));
memset(mx, 0xa3, sizeof(mx));
dp[p][x][y] = dp[p][y][x] = 0;
update(x, y, p);
memcpy(lmx, mx, sizeof(lmx));
while (cur + 2 < n * 3) {
p = p ^ 1;
q = 1 - p;
memset(mx, 0xa3, sizeof(mx));
mxy = int(-1e8);
vi temp{ a[cur], a[cur + 1], a[cur + 2] };
sort(temp.begin(), temp.end());
if (temp[0] == temp[1] && temp[1] == temp[2]) { // xxx
upd += 1;
cur += 3;
continue;
}
else if (temp[0] == temp[1]) { // xxy
int x = temp[0], y = temp[2];
for (int i = 0; i < n; ++i) {
dp[p][i][y] = dp[p][y][i] = max(dp[p][y][i], dp[q][x][i] + 1);
update(i, y, p);
}
dp[p][x][x] = max(dp[p][x][x], dp[q][y][y] + 1);
update(x, x, p);
}
else if (temp[1] == temp[2]) { // xyy
int x = temp[0], y = temp[1];
for (int i = 0; i < n; ++i) {
dp[p][i][x] = dp[p][x][i] = max(dp[p][i][x], dp[q][y][i] + 1);
update(i, x, p);
}
dp[p][y][y] = max(dp[p][y][y], dp[q][x][x] + 1);
update(y, y, p);
}
else { // xyz
int x = temp[0], y = temp[1], z = temp[2];
dp[p][y][z] = dp[p][z][y] = max(dp[p][y][z], dp[q][x][x] + 1);
dp[p][x][y] = dp[p][y][x] = max(dp[p][x][y], dp[q][z][z] + 1);
dp[p][x][z] = dp[p][z][x] = max(dp[p][x][z], dp[q][y][y] + 1);
update(x, y, p);
update(y, z, p);
update(z, x, p);
}
int x = temp[0], y = temp[1], z = temp[2];
// ij -> ij do nothing
// ij -> ix .. max(i, k) // mx[i]
for (int i = 0; i < n; ++i) {
dp[p][x][i] = dp[p][i][x] = max(dp[p][i][x], lmx[i]);
update(i, x, p);
dp[p][y][i] = dp[p][i][y] = max(dp[p][i][y], lmx[i]);
update(i, y, p);
dp[p][z][i] = dp[p][i][z] = max(dp[p][i][z], lmx[i]);
update(i, z, p);
}
// ij -> xy .. max(k, l) // mxy
dp[p][x][y] = dp[p][y][x] = max(dp[p][x][y], lmxy);
dp[p][z][y] = dp[p][y][z] = max(dp[p][z][y], lmxy);
dp[p][x][z] = dp[p][z][x] = max(dp[p][x][z], lmxy);
update(x, y, p); update(y, z, p); update(x, z, p);
all_update(p);
cur += 3;
}
x = a[n * 3 - 1];
int ans = upd + max(dp[p][x][x] + 1, lmxy);
printf("%d\n", ans);
return 0;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!