AtCoder Beginner Contest 175

发表于2020-08-17更新于2023-09-15字数统计1.8k阅读时长17分

比赛链接

D Moving Piece

Description

有 nn 个格子排成一列。给定 1,2,...,n1, 2, ..., n 的排列 P1,P2,...,PnP_1, P_2, ..., P_n，以及数组C1,C2,...,CnC_1, C_2, ..., C_n，表示格子 ii 能达到 PiP_i，获得的分数为 CPiC_{P_i}。从任意一点出发走 KK 步，求能获得的最大分数。

Solution

O(N2)O(N^2)：
以每个点作为起点 stst，求出路径，记录环的起点 cyBegcyBeg 和终点 cyEndcyEnd (终点指再走一步能回到环的起点的节点)。
求起点 stst 到 cyEndcyEnd 的 CC 前缀和，以及前缀和中的最大值。并求出环上的 CC 总和，以及从 cyBegcyBeg 开始的前缀和及其最大值。
判断能否走完整个环，若环为正环，则可以一直走到若干圈直到不能再走完整个环，或者少走一圈再加上前缀和最大值 (虽然环是正环，但可能环上存在一个极小值，少走一圈反而能使答案更大)。
O(nlogn)O(nlogn)：
通过 PP 求出每个点的入度，从入度为 0 的点开始 dfsdfs 建图 (若没有点入度为 0，则所有点在环上，任意找一个点为起点即可)，并记录每个点是否在环上。分起点在环上和不在环上，起点在环上需分段讨论，然后可用支持区间修改查询的数据结构维护区间最大值。也有multiset做法 link。

Code

Moving Piece O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr int MAXN = 5e3 + 5;

int n, k, ans(-1e18), cyBeg, cyEnd;
array<int, MAXN> to, c, vis, pre, preMax;
vector<int> node;

inline void dfs(int cur) {
    vis[cur] = true;
    node.push_back(cur);
    if (vis[to[cur]]) {
        cyEnd = node.size() - 1; //环终点
        for (int i = 0; i < node.size(); i++)
            if (node[i] == to[cur]) {
                cyBeg = i; //环起点
                break;
            }
    }
    else dfs(to[cur]);
}

inline void search(int st) {
    node.clear();
    fill(vis.begin(), vis.end(), 0);
    fill(pre.begin(), pre.end(), 0);
    fill(preMax.begin(), preMax.end(), -1e18);
    cyBeg = cyEnd = -1;
    dfs(st);
    for (int i = 1; i < node.size(); i++)
        pre[i] = pre[i - 1] + c[node[i]], preMax[i] = max(preMax[i - 1], pre[i]);
    ans = max(ans, preMax[min(k, (int)node.size() - 1)]);
    if (k <= cyEnd || cyBeg == - 1 || cyEnd == -1) return;
    if (cyBeg == 0) { //一开始就有环
        int valC = pre[cyEnd] + c[node[cyBeg]];
        if (valC < 0) return;
        int tim = k / node.size(), res = k % node.size();
        ans = max(ans, tim * valC + max(0LL, preMax[res]));
        ans = max(ans, (tim - 1) * valC + max(0LL, preMax[cyEnd]));
        return;
    }
    int tmp = pre[cyBeg - 1];
    fill(pre.begin(), pre.end(), 0);
    fill(preMax.begin(), preMax.end(), -1e18);
    int valC = 0, cSize = cyEnd - cyBeg + 1, tim, res;
    for (int i = cyBeg; i <= cyEnd; i++) { //环上前缀和
        valC += c[node[i]];
        pre[i] = pre[i - 1] + c[node[i]];
        preMax[i] = max(preMax[i - 1], pre[i]);
    }
    if (valC < 0) return;
    k -= cyBeg - 1, tim = k / cSize, res = k % cSize;
    ans = max(ans, tmp + valC * tim + max(0LL, preMax[cyBeg + res - 1]));
    ans = max(ans, tmp + valC * (tim - 1) + max(0LL, preMax[cyEnd]));
}

signed main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> to[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) search(i);
    cout << ans << endl;
    return 0;
}

E Picking Goods

Description

题目链接

Solution

设 dp[i][j][k]dp[i][j][k] 表示当前为第 ii 行，第jj 列，第 ii 行选了 kk 个数的最大值。状态转移明显。

Code

Picking Goods
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MAXN = 3e3 + 3;

LL R, C, K;
LL dp[MAXN][MAXN][5], mp[MAXN][MAXN];

int main () {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> R >> C >> K;
    for (int i = 1; i <= K; i++) {
        int r, c, v;
        cin >> r >> c >> v;
        mp[r][c] = v;
    }
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++) {
            for (int cnti = 0; cnti < 4; cnti++) {
                    //不选
                    dp[i][j][cnti] = max(dp[i][j][cnti], dp[i][j - 1][cnti]);
                    for (int cntj = 0; cntj < 4; cntj++)
                        dp[i][j][cnti] = max(dp[i][j][cnti], dp[i - 1][j][cntj]);
                    //选
                    dp[i][j][cnti + 1] = max(dp[i][j][cnti + 1], dp[i][j - 1][cnti] + mp[i][j]);
                    for (int cntj = 0; cntj < 4; cntj++)
                        dp[i][j][cnti + 1] = max(dp[i][j][cnti + 1], dp[i - 1][j][cntj] + mp[i][j]);
            }
        }
    LL ans = 0;
    for (int i = 0; i < 4; i++) ans = max(ans, dp[R][C][i]);
    cout << ans << endl;
    return 0;
}

F Making Palindrome

Description

求将一些字符串 S1,S2,...,SnS_1, S_2, ..., S_n 拼接为回文串的最小代价 ( SiS_i 可多次被选，每选一次代价为 CiC_i )。不能拼成回文串则输出 -1。

Solution

将目标回文串分为左右两部分，设左边的字符串为 l=sl1,sl2,...,sljl = s_{l_1}, s_{l_2}, ..., s_{l_j}，右边的字符串为 r=srk,...,sr2,sr1r = s_{r_k}, ..., s_{r_2}, s_{r_1}。要使 l,rl, r 构成回文串，则需要 sl1s_{l_1} 的前缀与 sr1s_{r_1} 回文，或者 sl1s_{l_1} 与 sr1s_{r_1} 的后缀回文，并且将回文部分消去后的 l,rl, r 也满足上述条件 (此时 slis_{l_i} 和 sris_{r_i} 可能只是 SS 的一部分)。
于是可以考虑设当前状态为 state={stringl,stringr}state = \{ string_l, string_r \}，向字符串长度小的一边加入新字符串进行拼接，并消去回文部分，直到 l,rl, r 都为空，或者一个是回文串，一个是空串为止，然后跑 dijkstradijkstra 即可。

Code

Making Palindrome
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MAXN = 55;

struct Node {
    Node() = default;
    Node(LL _c, string& _l, string& _r) : c(_c), l(_l), r(_r) {}
    LL c;
    string l, r;
    friend inline bool operator<(const Node& lhs, const Node& rhs) {
        return lhs.c > rhs.c;
    }
};
LL n, cost[MAXN];
string s[MAXN], emps("");

inline bool isPalindrome(const string& tmp) {
    for (int i = 0; i < tmp.size() /2 + 1; i++)
        if (tmp[i] != tmp[tmp.size() - 1 - i]) return false;
    return true;
}
/*删除l, r公共部分 @return l, r第一个不同的位置*/
inline int check(string& l, string& r) {
    int i = 0;
    for (; i < min(l.size(), r.size()); i++)
        if (l[i] != r[r.size() - 1 - i]) break;
    l = l.substr(i), r = r.substr(0, r.size() - i);
    return i;
}

priority_queue<Node, vector<Node>> q;
map<string, map<string, bool>> vis;
inline void dijkstra() {
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        if (vis[cur.l][cur.r]) continue; //l, r 访问过
        if (isPalindrome(cur.l) && cur.r.empty()) { //左边是回文
            cout << cur.c << endl;
            return;
        } else if (isPalindrome(cur.r) && cur.l.empty()) { //右边是回文
            cout << cur.c << endl;
            return;
        } else if (cur.l.empty() && cur.r.empty()) { //都是空字符串
            cout << cur.c << endl;
            return;
        } else {
            for (int i = 1; i <= n; i++) {
                Node tmp(cur.c, cur.l, cur.r);
                if (tmp.l.size() >= tmp.r.size()) { //左边比右边长，加到右边
                    tmp.r = s[i] + tmp.r, tmp.c += cost[i];
                    int id = check(tmp.l, tmp.r);
                    if (id && (tmp.l.empty() || tmp.r.empty())) q.push(tmp);
                } else { //左边比右边短，加到左边
                    tmp.l = tmp.l + s[i], tmp.c += cost[i];
                    int id = check(tmp.l, tmp.r);
                    if (id && (tmp.l.empty() || tmp.r.empty())) q.push(tmp);
                }
            }
        }
        vis[cur.l][cur.r] = true;
    }
    cout << -1 << endl;
}

int main () {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> cost[i];
        q.push(Node(cost[i], s[i], emps));
        q.push(Node(cost[i], emps, s[i]));
    }
    dijkstra();
    return 0;
}