AtCoder复盘

发布日期: 2023-12-03

文章字数: 2.8k

阅读时长: 16 分

阅读次数:

信息奥赛复盘｜AtCoder ABC 322（2023.12.3）

比赛信息 📚

VP时间：2023 年 12 月 3 日 19:15 - 20:55

竞赛链接：https://atcoder.jp/contests/abc322

个人情况 ✍️

个人排名：328/784

AC情况：3/7

A 字符串签到题，利用好 s.find(str) == string::npos 即可 ✅

B 字符串签到题，利用好 s.substr(pos, length) 即可 ✅

C 思维题 ✅

D 思维 + 模拟，比较难的D题 ❌

E 赛场看出可以用线性DP，但是不知道怎么表示状态 ❌

F 需要维护区间最大值，已知树状数组不行，线段树可以，但是不会线段树 ❌

G 未看 ❌

题目列表 🧑🏻‍💻

题目名称	难度	赛时VP	补题
A - First ABC 2	🟢	✅	✅
B - Prefix and Suffix	🟢	✅	✅
C - Festival	🟢	✅	✅
D - Polyomino	🟡	❌
E - Product Development	🟡	❌
F - Vacation Query	🟡	❌
G - Two Kinds of Base	🟡	❌

题解 🚀

A - First ABC 2

题目信息 📚

【题目描述】

You are given a string $S$ of length $N$ consisting of A, B, and C.

Find the position where ABC first appears as a (contiguous) substring in $S$. In other words, find the smallest integer $n$ that satisfies all of the following conditions.

$1 \le n \le N−2$.
The string obtained by extracting the $n$-th through $(n+2)$-th characters of $S$ is ABC.

If ABC does not appear in $S$, print -1.

【输入】

The input is given from Standard Input in the following format:

$N$
$S$ $T$

【输出】

Print the position where ABC first appears as a substring in $S$, or -1 if it does not appear in $S$.

【数据范围】

$3 \le N \le 100$
$S$ is a string of length $N$ consisting of A, B, and C.

【输入样例1】

8
ABABCABC

【输出样例1】

【输入样例2】

3
ACB

【输出样例2】

-1

【输入样例3】

20
BBAAABBACAACABCBABAB

【输出样例3】

【题目来源】

https://atcoder.jp/contests/abc322/tasks/abc322_a

题目解析 🍉

【题目分析】

A 字符串签到题，利用好 s.find(str) == string::npos 即可 ✅

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;

int main() {
    string s;
    cin >> n >> s;

    // 在s中查找"ABC"
    // 若存在，返回第一次出现的下标；否则，返回std::string::npos
    if (s.find("ABC") == string::npos)
        cout << -1 << endl;
    else
        cout << s.find("ABC") + 1;

    return 0;
}

B - Prefix and Suffix

题目信息 📚

【题目描述】

You are given two strings $S$ and $T$ consisting of lowercase English letters. The lengths of $S$ and $T$ are $N$ and $M$, respectively. (The constraints guarantee that $N \leq M$.)

$S$ is said to be a prefix of $T$ when the first $N$ characters of $T$ coincide with $S$.

$S$ is said to be a suffix of $T$ when the last $N$ characters of $T$ coincide with $S$.

If $S$ is both a prefix and a suffix of $T$, print $0$.

If $S$ is a prefix of $T$ but not a suffix, print $1$.

If $S$ is a suffix of $T$ but not a prefix, print $2$.

If $S$ is neither a prefix nor a suffix of $T$, print $3$.

【输入】

The input is given from Standard Input in the following format:

$N$ $M$
$S$
$T$

【输出】

Print the answer according to the instructions in the problem statement.

【数据范围】

$1 \le N \le M \le 100$
$S$ is a string of length $N$ consisting of lowercase English letters.
$T$ is a string of length $M$ consisting of lowercase English letters.

【输入样例1】

3 7
abc
abcdefg

【输出样例1】

【输入样例2】

3 4
abc
aabc

【输出样例2】

【输入样例3】

3 3
abc
xyz

【输出样例3】

【输入样例4】

3 3
aaa
aaa

【输出样例4】

【题目来源】

https://atcoder.jp/contests/abc322/tasks/abc322_b

题目解析 🍉

【题目分析】

B 字符串签到题，利用好 s.substr(pos, length) 即可 ✅

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n, m;
string s, t;

int main() {
    cin >> n >> m >> s >> t;

    bool is_pre = false, is_sur = false;
    if (t.substr(0, n) == s) is_pre = true;

    if (t.substr(m - n, n) == s) is_sur = true;

    if (is_pre && is_sur) cout << 0 << endl;
    else if (is_pre && !is_sur) cout << 1 << endl;
    else if (!is_pre && is_sur) cout << 2 << endl;
    else if (!is_pre && !is_sur) cout << 3 << endl;

    return 0;
}

C - Festival

题目信息 📚

【题目描述】

The AtCoder Kingdom holds a festival for $N$ days. On $M$ of these days, namely on the $A_1$-th, $A_2$-th, …, $A_M$-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival (In other words, $A_M = N$ is guaranteed).

For each $i = 1, 2, \ldots, N$, solve the following problem:

How many days later from the $i$-th day will fireworks be launched for the first time on or after the $i$-th day? If fireworks are launched on the $i$-th day, it is considered to be $0$ days later.

【输入】

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ … $A_M$

【输出】

Print $N$ lines.

The $i$-th line ($1 \leq i \leq N$) should contain an integer representing the number of days from the $i$-th day until fireworks are launched for the first time on or after the $i$-th day.

【数据范围】

$1 \leq M \leq N \leq 2 \times 10^5$
$1 \leq A_1 < A_2 < \ldots < A_M = N$
All input values are integers.

【输入样例1】

3 2
2 3

【输出样例1】

1
0
0

The kingdom holds a festival for $3$ days, and fireworks are launched on the $2$-nd and $3$-rd days.

From the $1$-st day, the first time fireworks are launched is the $2$-nd day of the festival, which is $1$ day later.
From the $2$-nd day, the first time fireworks are launched is the $2$-nd day of the festival, which is $0$ days later.
From the $3$-rd day, the first time fireworks are launched is the $3$-rd day of the festival, which is $0$ days later.

【输入样例2】

8 5
1 3 4 7 8

【输出样例2】

【题目来源】

https://atcoder.jp/contests/abc322/tasks/abc322_c

题目解析 🍉

【题目分析】

从后往前，逆序遍历数组。

设置一个指针，不断指向最近的节日，输出差值即可。

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, m, t, a[N], b[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入节日数据
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> t;
        b[t]++;
    }

    // 逆序扫描，不断更新指针
    int p = n;
    for (int i = n; i >= 1; i--) {
        if (b[i]) p = i;
        a[i] = p - i;
    }

    // 顺序输出答案
    for (int i = 1; i <= n; i++) cout << a[i] << endl;

    return 0;
}

D - Polyomino

题目信息 📚

【题目描述】

A polyomino is a puzzle piece in the shape of a connected polygon made by connecting several squares by their edges.

There is a grid with four rows and four columns, and three polyominoes that fit within the grid.
The shape of the $i$-th polyomino is represented by $16$ characters $P_{i,j,k}$ $(1 \le j,k \le 4)$. They describe the state of the grid when the $i$-th polyomino is placed on it. If $P_{i,j,k}$ is #, the square at the $j$-th row from the top and $k$-th column from the left is occupied by the polyomino; if it is ., the square is not occupied. (Refer to the figures at Sample Input/Output $1$.)

You want to fill the grid with all three polyominoes so that all of the following conditions are satisfied.

All squares of the grid are covered by the polyominoes.
The polyominoes must not overlap each other.
The polyominoes must not stick out of the grid.
The polyominoes may be freely translated and rotated but may not be flipped over.

Can the grid be filled with the polyominoes to satisfy these conditions?

【输入】

The input is given from Standard Input in the following format:

$P_{1,1,1}P_{1,1,2}P_{1,1,3}P_{1,1,4}$

$P_{1,2,1}P_{1,2,2}P_{1,2,3}P_{1,2,4}$

$P_{1,3,1}P_{1,3,2}P_{1,3,3}P_{1,3,4}$

$P_{1,4,1}P_{1,4,2}P_{1,4,3}P_{1,4,4}$

$P_{2,1,1}P_{2,1,2}P_{2,1,3}P_{2,1,4}$

$P_{2,2,1}P_{2,2,2}P_{2,2,3}P_{2,2,4}$

$P_{2,3,1}P_{2,3,2}P_{2,3,3}P_{2,3,4}$

$P_{2,4,1}P_{2,4,2}P_{2,4,3}P_{2,4,4}$

$P_{3,1,1}P_{3,1,2}P_{3,1,3}P_{3,1,4}$

$P_{3,2,1}P_{3,2,2}P_{3,2,3}P_{3,2,4}$

$P_{3,3,1}P_{3,3,2}P_{3,3,3}P_{3,3,4}$

$P_{3,4,1}P_{3,4,2}P_{3,4,3}P_{3,4,4}$

【输出】

If it is possible to fill the grid with the polyominoes to satisfy the conditions in the problem statement, print Yes; otherwise, print No.

【数据范围】

$P_{i,j,k}$ is # or ..
The given polyominoes are connected. In other words, the squares that make up a polyomino can be reached from each other by following only the squares up, down, left, and right.
The given polyominoes are not empty.

【输入样例1】

....
###.
.#..
....
....
.###
.##.
....
..#.
.##.
.##.
.##.

【输出样例1】

Yes

【输入样例2】

###.
#.#.
##..
....
....
..#.
....
....
####
##..
#...
#...

【输出样例2】

Yes

【输入样例3】

##..
#..#
####
....
....
##..
.##.
....
.#..
.#..
.#..
.#..

【输出样例3】

No

【输入样例4】

....
..#.
....
....
....
..#.
....
....
....
..#.
....
....

【输出样例4】

No

【输入样例5】

....
####
#...
#...
....
####
...#
..##
....
..##
..#.
..##

【输出样例5】

No

【输入样例6】

###.
.##.
..#.
.###
....
...#
..##
...#
....
#...
#...
#...

【输出样例6】

Yes

【题目来源】

https://atcoder.jp/contests/abc322/tasks/abc322_d

题目解析 🍉

【题目分析】

【C++代码】✅

E - Product Development

题目信息 📚

【题目描述】

AtCoder Inc. is planning to develop a product. The product has $K$ parameters, whose values are currently all zero. The company aims to raise all parameter values to at least $P$.

There are $N$ development plans. Executing the $i$-th development plan ($1 \leq i \leq N$) increases the value of the $j$-th parameter by $A_{i,j}$ for every integer $j$ such that $1 \leq j \leq K$, at the cost of $C_i$.

A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.

【输入】

The input is given from Standard Input in the following format:

$N$ $K$ $P$

$C_1$ $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,K}$

$C_2$ $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,K}$

$\ldots$

$C_N$ $A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,K}$

【输出】

If AtCoder Inc. can achieve its goal, print the minimum total cost required to achieve the goal; otherwise, print -1.

【数据范围】

$1 \leq N \leq 100$
$1 \leq K, P \leq 5$
$0 \leq A_{i,j} \leq P$ $(1 \leq i \leq N, 1 \leq j \leq K)$
$1 \leq C_i \leq 10^9$ $(1 \leq i \leq N)$
All input values are integers.

【输入样例1】

【输出样例1】

If you execute the first, third, and fourth development plans, each parameter will be $3+2+0=5,0+4+1=5,2+0+4=63+2+0=5,0+4+1=5,2+0+4=6$, all of which are at least 5, so the goal is achieved. The total cost in this case is $5+3+1=95+3+1=9$.

It is impossible to achieve the goal at a total cost of $8$ or less. Thus, the answer is $9$.

【输入样例2】

【输出样例2】

-1

You cannot achieve the goal no matter what you do. Thus, print -1.

【题目来源】

https://atcoder.jp/contests/abc322/tasks/abc322_e

题目解析 🍉

【题目分析】

【C++代码】✅

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000;
int main(){
  int N, K, P;
  cin >> N >> K >> P;
  vector<int> C(N);
  vector<vector<int>> A(N, vector<int>(K));
  for (int i = 0; i < N; i++){
    cin >> C[i];
    for (int j = 0; j < K; j++){
      cin >> A[i][j];
    }
  }
  vector<int> POW(K + 1);
  POW[0] = 1;
  for (int i = 0; i < K; i++){
    POW[i + 1] = POW[i] * (P + 1);
  }
  vector<vector<long long>> dp(N + 1, vector<long long>(POW[K], INF));
  dp[0][0] = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < POW[K]; j++){
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
      int j2 = 0;
      for (int k = 0; k < K; k++){
        int x = j / POW[k] % (P + 1);
        x = min(x + A[i][k], P);
        j2 += x * POW[k];
      }
      dp[i + 1][j2] = min(dp[i + 1][j2], dp[i][j] + C[i]);
    }
  }
  if (dp[N][POW[K] - 1] == INF){
    cout << -1 << endl;
  } else {
    cout << dp[N][POW[K] - 1] << endl;
  }
}

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, K, P;
    std::cin >> N >> K >> P;
    
    std::vector<int> pw(K + 1);
    pw[0] = 1;
    for (int i = 1; i <= K; i++) {
        pw[i] = pw[i - 1] * (P + 1);
    }
    
    std::vector dp(pw[K], -1LL);
    dp[0] = 0;
    
    for (int i = 0; i < N; i++) {
        int C;
        std::cin >> C;
        
        std::vector<int> A(K);
        for (int j = 0; j < K; j++) {
            std::cin >> A[j];
        }
        
        for (int s = pw[K] - 1; s >= 0; s--) {
            int t = 0;
            for (int j = 0; j < K; j++) {
                int a = s / pw[j] % (P + 1);
                int na = std::min(P, a + A[j]);
                t += na * pw[j];
            }
            if (dp[s] != -1 && (dp[t] == -1 || dp[t] > dp[s] + C)) {
                dp[t] = dp[s] + C;
            }
        }
    }
    std::cout << dp.back() << "\n";
    
    return 0;
}