题解：AtCoder AT_awc0080_e Paint Drop

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：E - Paint Drop

【题目描述】

Takahashi is playing a paint game on a grid canvas withH HHrows andW WWcolumns. The cell at thei ii-th row from the top and thej jj-th column from the left is called cell( i , j ) (i, j)(i,j).

Cell( i , j ) (i, j)(i,j)has a scoreA i , j A_{i,j}Ai,j​assigned to it. Initially, no cells are painted.

Takahashi will drop paint onto the canvasQ QQtimes.

In thet tt-th paint drop, all cells on the canvas whose Manhattan distance from cell( R t , C t ) (R_t, C_t)(Rt​,Ct​)is at mostD t D_tDt​are painted.

In other words, among all cells( i , j ) (i, j)(i,j)satisfying1 ≤ i ≤ H 1 \leq i \leq H1≤i≤Hand1 ≤ j ≤ W 1 \leq j \leq W1≤j≤W, all cells satisfying

∣ i − R t ∣ + ∣ j − C t ∣ ≤ D t |i - R_t| + |j - C_t| \leq D_t∣i−Rt​∣+∣j−Ct​∣≤Dt​

are painted.

When a cell that has not yet been painted becomes newly painted, Takahashi earns the score of that cell. No score is earned when paint reaches a cell that is already painted.

For each paint drop, find the total score newly earned by Takahashi from that paint drop.

高桥在一个有H HH行W WW列的网格画布上玩一个涂色游戏。从上往下第i ii行、从左往右第j jj列的单元格称为单元格( i , j ) (i, j)(i,j)。

单元格( i , j ) (i, j)(i,j)有一个分配的分数A i , j A_{i,j}Ai,j​。初始时，没有单元格被涂色。

高桥将在画布上滴下涂料Q QQ次。

在第t tt次涂料滴下时，所有距离单元格( R t , C t ) (R_t, C_t)(Rt​,Ct​)的曼哈顿距离不超过D t D_tDt​的单元格都会被涂色。

换句话说，在满足1 ≤ i ≤ H 1 \leq i \leq H1≤i≤H和1 ≤ j ≤ W 1 \leq j \leq W1≤j≤W的所有单元格( i , j ) (i, j)(i,j)中，所有满足

∣ i − R t ∣ + ∣ j − C t ∣ ≤ D t |i - R_t| + |j - C_t| \leq D_t∣i−Rt​∣+∣j−Ct​∣≤Dt​

的单元格都会被涂色。

当一个尚未被涂色的单元格新被涂色时，高桥获得该单元格的分数。当涂料到达一个已经涂色的单元格时，不会获得分数。

对于每次涂料滴下，求高桥从该次滴下中新获得的分数总和。

【输入】

H HHW WW
A 1 , 1 A_{1,1}A1,1​A 1 , 2 A_{1,2}A1,2​⋯ \cdots⋯A 1 , W A_{1,W}A1,W​
A 2 , 1 A_{2,1}A2,1​A 2 , 2 A_{2,2}A2,2​⋯ \cdots⋯A 2 , W A_{2,W}A2,W​
⋮ \vdots⋮
A H , 1 A_{H,1}AH,1​A H , 2 A_{H,2}AH,2​⋯ \cdots⋯A H , W A_{H,W}AH,W​
Q QQ
R 1 R_1R1​C 1 C_1C1​D 1 D_1D1​
R 2 R_2R2​C 2 C_2C2​D 2 D_2D2​
⋮ \vdots⋮
R Q R_QRQ​C Q C_QCQ​D Q D_QDQ​

• The first line contains the number of rowsH HHand the number of columnsW WWof the canvas, separated by a space.
• In the followingH HHlines, thei ii-th line contains the scoresA i , 1 , A i , 2 , … , A i , W A_{i,1}, A_{i,2}, \ldots, A_{i,W}Ai,1​,Ai,2​,…,Ai,W​separated by spaces.
• The next line contains the number of paint dropsQ QQ.
• In the followingQ QQlines, thet tt-th line contains the center rowR t R_tRt​, columnC t C_tCt​, and reach distanceD t D_tDt​of thet tt-th paint drop, separated by spaces.

【输出】

OutputQ QQlines.

Thet tt-th line should contain the total score newly earned by Takahashi from thet tt-th paint drop.

【输入样例】

3 4 1 2 3 4 5 6 7 8 9 10 11 12 4 2 2 1 1 4 0 3 1 2 2 3 7

【输出样例】

30 4 21 23

【算法标签】

#并查集

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;inth,w,q;// h: 矩阵行数，w: 矩阵列数，q: 查询次数vector<vector<int>>a;// 矩阵vector<vector<int>>nxt;// 并查集数组，记录每个位置的下一个可访问位置intans[N];// 存储查询结果intfind(introw,intcol)// 查找当前行col位置的下一个可访问位置{if(col>w)// 如果超出列范围returnw+1;// 返回w+1表示结束if(nxt[row][col]!=col)// 路径压缩nxt[row][col]=find(row,nxt[row][col]);returnnxt[row][col];// 返回下一个可访问位置}signedmain(){cin>>h>>w;// 输入矩阵行数和列数a.assign(h+1,vector<int>(w+1));// 初始化矩阵nxt.assign(h+1,vector<int>(w+2));// 初始化并查集数组for(inti=1;i<=h;i++)// 输入矩阵元素for(intj=1;j<=w;j++)cin>>a[i][j];for(inti=1;i<=h;i++)// 初始化并查集数组for(intj=1;j<=w+1;j++)nxt[i][j]=j;cin>>q;// 输入查询次数while(q--)// 处理每个查询{intr,c,d;// 查询中心(r, c)和半径dcin>>r>>c>>d;intsum=0;// 初始化总和for(inti=max(1LL,r-d);i<=min(h,r+d);i++)// 遍历行范围{intrem=d-abs(r-i);// 计算剩余半径intjL=max(1LL,c-rem);// 计算列范围左边界intjR=min(w,c+rem);// 计算列范围右边界intj=find(i,jL);// 找到第一个可访问位置while(j<=jR)// 遍历可访问位置{sum+=a[i][j];// 累加元素值nxt[i][j]=find(i,j+1);// 标记当前位置已访问j=find(i,j);// 查找下一个可访问位置}}cout<<sum<<endl;// 输出查询结果}return0;}

【运行结果】

3 4 1 2 3 4 5 6 7 8 9 10 11 12 4 2 2 1 30 1 4 0 4 3 1 2 21 2 3 7 23