AtCoder Beginner Contest 405（CD）

C - Sum of Product

翻译：

        给你一个长为N的序列。

        计算的值。

思路：

        可使用前缀和快速得到区间和，在遍历 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 列的单元格。
        每个单元格由以下字符之一表示 ：

• . :走廊单元格
• #：墙壁单元
• 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;
}

之后补题会在此增加题解。    

E题，想的动态规划，单看数据的大小搞不出来，如果有相关思路感谢告知T_T。

atcoder前两题的题解就算了，应该也没人想看吧。。。