ATC ABC176

A - Takoyaki Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

Problem Statement

Takahashi loves takoyaki - a ball-shaped snack.

With a takoyaki machine, he can make at most $X$ pieces of takoyaki at a time, taking $T$ minutes regardless of the number of pieces to make.

How long does it take to make $N$ takoyaki?

Constraints

$1 \leq N,X,T \leq 1000$
All values in input are integers.

Takahashi一次可以做$X$个章鱼烧，需要花费$T$分钟，求出做$N$个章鱼烧Takahashi需要的时间。

我们只需求出Takahashi需要做几次章鱼烧（即$\left(N-1)\right/X+1$次），再将次数$\times T$就好了。

#include <bits/stdc++.h>

using namespace std;

int n,x,t;

int main()

{

    scanf("%d%d%d",&n,&x,&t);

    printf("%d\n",((n-1)/x+1)*t);

    return 0;

}

B - Multiple of 9 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

Problem Statement

An integer $N$ is a multiple of $9$ if and only if the sum of the digits in the decimal representation of $N$ is a multiple of $9$. Determine whether $N$ is a multiple of $9$.

Constraints

$0 \leq N < 10^{200000}$
$N$ is an integer.

一个整数是$9$的倍数当且仅当它的各个数位之和为$9$的倍数。判断整数$N$是不是$9$的倍数。

题解题面已给出~

#include <bits/stdc++.h>

using namespace std;

int ans;

string s;

int main()

{

    cin >> s;

    for(int i=0,len=s.size();i<len;i++)

        ans += s[i]-'0';

    printf(ans%9 ?"No\n":"Yes\n");

    return 0;

}

C - Step Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

Problem Statement

$N$ persons are standing in a row. The height of the $i$-th person from the front is $A_i$.

We want to have each person stand on a stool of some heights - at least zero - so that the following condition is satisfied for every person:

Condition: Nobody in front of the person is taller than the person. Here, the height of a person includes the stool.

Find the minimum total height of the stools needed to meet this goal.

Constraints

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$
All values in input are integers.

$N$个人站成一排，$A_i$表示第$i$个人的高度，每个人都站在高度至少为$0$的凳子上使得每个人的水平高度不小于前一个人的水平高度。求出最小凳子高度总和。

每个人的水平高度不小于前一个人的水平高度说明数组是单调递增的，所以$A_i+H_{stool_i}$必然$\geq \max (A_0+H_{stool_0}, A_1+H_{stool_1}, \cdots , A_{i-1}+H_{stool_{i-1}})$，如果$A_i < maxn$，只要让$H_{stool_i} = maxn-A_i$就好了。

#include <bits/stdc++.h>
using namespace std;
    
int n,a[200050],maxn;
long long ans;
     
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",a+i);
        maxn=max(maxn,a[i]);
        ans += max(maxn-a[i],0);
    }
    printf("%lld",ans);
    return 0;
}

D - Wizard in Maze Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

Problem Statement

A maze is composed of a grid of $H \times W$ squares - $H$ vertical, $W$ horizontal.

The square at the $i$ $i$ -th row from the top and the $j$-th column from the left - $(i,j)$ - is a wall if $S_{ij}$ $S_{i j}$ is '#' and a road if $S_{ij}$ is '.'.

There is a magician in $(C_h,C_w)$ $(C_{h}, C_{w})$ . He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.
Move B: Use magic to warp himself to a road square in the $5 \times 5$ area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach $(D_h,D_w)$?

Constraints

$1 \leq H,W \leq 10^3$
$1 \leq C_h,D_h \leq H$
$1 \leq C_w,D_w \leq W$
$S_{ij}$ is '#' or '.'.
$S_{C_hC_w}$ and $S_{D_hD_w}$ are '.'.
$(C_h,C_w) \neq (D_h,D_w)$

迷宫由$H \times W$个格子组成。其中，'#' 代表墙（不可行），'.' 代表路（可行）。一位魔法师站在$(C_h,C_w)$的格子上，可以做以下两种动作：

移动A：往上下左右的任一方向走一个格。

移动B：使用魔法传送到以自己为中心的$5 \times 5$区域的不为墙（也不越界）的任一格子。

求出魔法师至少用几次魔法（移动B）才能到达$(D_h,D_w)$。若不能，输出$-1$。

我们只需$DFS$求出连通分量，再进行一次$BFS$，把起点放入队列。因为在连通分量中，我们能不使用魔法就能走到每个点，所有我们将当前节点的连通分量中所有没有访问过的点放入队列（权值等于当前节点的权值），再将当前节点$5 \times 5$区域中没访问过（不包括即将访问）的点放入队列（权值等于当前节点权值$+1$）。每个点都只访问过一次，所以时间复杂度为$O(n)$。

只需要判断$value_u$是否为初始值就能判断是否为访问过（如果初始值设为$-1$就不用特判不能达到的情况），因为$BFS$是宽度优先遍历，保证了$value_i$最小。

代码中我将$(x,y)$简化为$x \times maxn+y$，不简化用$pair$就能实现了。如果想简化代码，可以考虑用$value$表示整个连通分量的权值。

#include <bits/stdc++.h>

using namespace std;

const int maxn=1050,dx[]={1,0,-1,0},dy[]={0,1,0,-1};

int n,m,sx,sy,gx,gy,cnt,idx[maxn*maxn],val[maxn*maxn];

bool vis[maxn*maxn];

vector<int> con[maxn*maxn];

string s[maxn];

void dfs(int x,int y)

{

    if(x<0 || y<0 || x >= n || y >= m || s[x][y] != '.' || idx[x*maxn+y])

        return;

    con[cnt].push_back(x*maxn+y);

    idx[x*maxn+y]=cnt;

    for(int i=0;i<4;i++)

        dfs(x+dx[i],y+dy[i]);

}

inline void bfs()

{

    queue<int> q;

    memset(val,-1,sizeof(val));

    vis[idx[sx*maxn+sy]]=true;

    for(auto v : con[idx[sx*maxn+sy]])

{

        val[v]=0;

        q.push(v); 

}

    while(!q.empty())

{

        int u=q.front();

        q.pop();

        if(u == gx*maxn+gy)

            return;

        for(int i=-2;i <= 2;i++)

            for(int j=-2;j <= 2;j++)

{

                int x=u/maxn+i,y=u%maxn+j;

                if(x >= 0 && y >=0 && x<n && y<m && s[x][y] == '.' && !vis[idx[x*maxn+y]])

{

                    vis[idx[x*maxn+y]]=true;

                    for(auto v : con[idx[x*maxn+y]])

{

                        val[v]=val[u]+1;

                        q.push(v);

}

}

}

}

}

int main()

{

    scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&gx,&gy);

    sx--,sy--,gx--,gy--;

    for(int i=0;i<n;i++)

        cin >> s[i];

    for(int i=0;i<n;i++)

        for(int j=0;j<m;j++)

            if(!idx[i*maxn+j] && s[i][j] == '.')

{

                cnt++;

                dfs(i,j);

}

    bfs();

    printf("%d\n",val[gx*maxn+gy]);

    return 0;

}

E - Bomber Editorial

Time Limit: 3 sec / Memory Limit: 1024 MB

Problem Statement

We have a two-dimensional grid with $H \times W$ squares. There are $M$ targets to destroy in this grid - the position of the $i$-th target is $(h_i,w_i)$.

Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.

Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

Constraints

All values in input are integers
$1 \leq H,W \leq 3 \times 10^5$
$1 \leq M \leq \min (H \times W,3 \times 10^5)$
$1 \leq h_i \leq H$
$1 \leq w_i \leq W$
$(h_i,w_i) \neq (h_j,w_j)(i \neq j)$

有一个二维网格由$H \times W$个格子组成。其中有$M$个要摧毁的目标$(h_i,w_i)$。Takahashi将选择一个格子，并放一枚十字炸弹（可以摧毁同行同列的所有目标）。求出Takahashi最多能摧毁的目标数量。

我们很容易想到炸弹处在的格子必然在目标最多的行和目标最多的列，当炸弹在目标上就要少炸一个目标。所有我们只要求出是否所有在目标最多的行和目标最多的列的格子都有目标就行了。

用$mr,mc$分别记录一行和一列的最多目标数，$cr,cc$分别记录最多目标行、列的个数，$cnt$记录目标在最多目标行、列的个数。最多目标行、列有$cr \times cc$种组合方式，所以当且仅当$cr \times cc = cnt$，所有在目标最多的行和目标最多的列的格子都有目标，这时$ans-1$。

#include <bits/stdc++.h>
using namespace std;
  
int n,m,t,x[300050],y[300050],r[300050],c[300050],rm,cm,cr,cc,cnt;
   
int main()
{
    scanf("%d%d%d",&n,&m,&t);  
    for(int i=0;i<t;i++)
    {
        scanf("%d%d",x+i,y+i);
        r[x[i]-1]++;
        c[y[i]-1]++;
    }
    for(int i=0;i<300050;i++)
    {  
        if(r[i]>rm)
        {
            cr=1;
            rm=r[i];
        }
        else
            if(r[i] == rm)
                cr++;
        if(c[i]>cm)
        {
            cc=1;
            cm=c[i];
        }
        else
            if(c[i] == cm)
                cc++;
    } 
    for(int i=0;i<t;i++)
        if(r[x[i]-1] == rm && c[y[i]-1] == cm)
            cnt++;
    printf("%d\n",rm+cm-(cr*cc == cnt));
    return 0;
}

F - Brave CHAIN Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

Problem Statement

We have $3N$ cards arranged in a row from left to right, where each card has an integer between $1$ and $N$ (inclusive) written on it. The integer written on the $i$ $i$ -th card from the left is $A_i$.

You will do the following operation $N-1$ times:

Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain $1$ point.

After these $N-1$ operations, if the integers written on the remaining three cards are all equal, you will gain $1$ additional point.

Find the maximum number of points you can gain.

Constraints

$1 \leq N \leq 2000$
$1 \leq A_i \leq N$

给你$3N$张卡牌，每张牌上的数为$A_i$。进行以下$N-1$次操作:

将前五张牌以任意顺序排序，抽出前三张牌，如果它们上的数相等，得到一分。

进行$N-1$次操作后如果剩余的三张牌上的数相等，得到额外的一分。求出最大能得到的积分。

本题作为ABC的F题首次难度破红，成为ABC史上第二难题（第一为ABC025D，难度到了可怕的Cu），也是ABC唯一没有部分分的红题（以及红题以上难度），具体思想为DP，没有题解。

搜索此博客

Lcyanstars's blog

ATC ABC176

Problem Statement

Constraints

Problem Statement

Constraints

Problem Statement

Constraints

Problem Statement

Constraints

Problem Statement

Constraints

Problem Statement

Constraints

评论

发表评论