当前位置：首页 > backend >正文

AtCoder Beginner Contest 405（CD）

backend 2025/5/11 6:15:23

C - Sum of Product

翻译：

给你一个长为N的序列 $A=(A_1,A_2,...,A_N)$ 。

计算 $\sum\limits_{1\leq i <j\leq N} A_iA_j$ 的值。

思路：

$\sum\limits_{1\leq i <j\leq N} A_iA_j = \sum\limits_{i=1}^{N}(A_i*\sum\limits^N_{j=i+1}A_j) = \sum\limits_{i=1}^{N}(A_i*sum_{i+1,j})$ 可使用前缀和快速得到区间和，在遍历 i 即可。（前缀和）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;void solve(){ll n;cin>>n;vector<ll> a(n+1),pre(n+1,0);for (int i=1;i<=n;i++){cin>>a[i];pre[i]+=pre[i-1]+a[i];}ll ans = 0;for (int i=1;i<=n;i++) ans+=a[i]*(pre[n]-pre[i]);cout<<ans<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();solve();return 0;
}

D - Escape Route

翻译：

        给你一个 H 行 W 列的网格。让 (i,j) 表示从上往下第 i 行和从左往右第 j 列的单元格。
        每个单元格由以下字符之一表示 $S_{i,j}$ ：

. :走廊单元格
#：墙壁单元
E：紧急出口

        对于任何一个走廊单元 (i,j)，定义 d(i,j) 即到最近的紧急出口的距离如下：

从 (i,j)开始，沿四个基本方向（上、下、左、右）之一重复移动到相邻的非墙壁单元，直到到达紧急出口。d(i,j) 是所需的最少移动次数。

        可以保证 d(i,j) 对于给定网格中的每个走廊单元都是可定义的；也就是说，每个走廊单元 (i,j) 至少有一个紧急出口可以通过走廊单元到达。

        在每个走廊单元写一个箭头（向上、向下、向左或向右），使以下条件成立：

对于每个走廊单元 (i,j)，如果从 (i,j) 开始执行以下操作 d(i,j)次，就会到达一个紧急出口：
按照当前单元格中箭头的方向移动一个单元格。(不能移动到墙壁单元格或网格外）。

思路：

从每个E出发进行广度搜索，并记录到达走廊的步数，如果更小则更新到该点步数和箭头。（dfs）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;
struct Edge{int x,y;char d;
};
vector<Edge> direct;
void solve(){int n,m;cin>>n>>m;vector<vector<char>> grid(n+1,vector<char>(m+1));vector<vector<int>> vis(n+1,vector<int>(m+1,INT_MAX));queue<array<int,3>> pq;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){cin>>grid[i][j];if (grid[i][j]=='E'){vis[i][j] = 0;pq.push({0,i,j});}}}vector<vector<char>> ans(grid.begin(),grid.end());while (!pq.empty()){int now_x = pq.front()[1],now_y = pq.front()[2],step = pq.front()[0];pq.pop();for (auto& [xx,yy,d]:direct){int tmp_x = now_x+xx,tmp_y = now_y+yy;if (tmp_x>=1 && tmp_x<=n && tmp_y>=1 && tmp_y<=m && grid[tmp_x][tmp_y]=='.' && vis[tmp_x][tmp_y]>step+1){vis[tmp_x][tmp_y] = step+1;ans[tmp_x][tmp_y] = d;pq.push({step+1,tmp_x,tmp_y});}}}for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){cout<<ans[i][j];}cout<<'\n';}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();direct.push_back({1,0,'^'});direct.push_back({-1,0,'v'});direct.push_back({0,1,'<'});direct.push_back({0,-1,'>'});solve();return 0;
}