Atcoder351(D-F)题解

D - Grid and Magnet

题意

有一个用字符类型表示的 行 列的地图 ，如果是字符 . 则代表这一格是空地，如果是 # 则代表这一格上有一个磁铁。现在身着铁甲的高桥从一个格子上出发，每次可以到达与之相邻（上、下、左、右）的四个格子，但如果有一个磁铁与之相邻（上下左右的四个格子中至少有一个磁铁）他就不能动了。求高桥从某一格出发，经过任意多次运动，可以到达的格子的最大数量(即最大连通块)。

解题思路

一个格子不可能同时出现两个不同的连通块中，由此我们可以通过枚举连通块：从未被搜索的格子出发，然后向四周扩展，将可达的格子打上标记(表示属于当前连通块)，并用记录可达格子的数量(即：连通块的大小)，最终答案，每个格子最多只能被搜索一次，由此时间复杂度为

解题代码

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
string s[N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int vis[N][N];
int now_cnt,now,ans;

bool valid(int x,int y)
{
  if(x<0||x>=n||y<0||y>=m) return false;
  return true;
}

bool is_move(int x, int y)
{
  for(int i=0;i<4;i++){
    int nxt_x=x+dx[i],nxt_y=y+dy[i];
    if(valid(nxt_x,nxt_y)&&s[nxt_x][nxt_y]=='#')
    return false;
  }
  return true;
}

void dfs(int x,int y){
  now_cnt++;
  vis[x][y]=now;
  if(!is_move(x,y)) return ;
  for(int i=0;i<4;i++){
    int nxt_x=x+dx[i],nxt_y=y+dy[i];
    if(!valid(nxt_x,nxt_y)) continue;
    if(vis[nxt_x][nxt_y]==now) continue;
    dfs(nxt_x,nxt_y);
  }
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m;
  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(s[i][j]=='.'&&!vis[i][j]){
        now_cnt=0,now++;
        dfs(i,j);
        ans=max(ans,now_cnt);
      }
    }
  }
  cout<<ans<<"\n";
  return 0;
}

E - Jump Distance Sum

题意

位置 (𝑥,𝑦) 可以一步跳到 (𝑥+1,𝑦+1) 、 (𝑥+1,𝑦−1) 、 (𝑥−1,𝑦+1) 或 (𝑥−1,𝑦−1),即：每一步只能沿对角线走

求解， 被定义为从点跳到点所需的最少跳跃次数(如果)

解题思路

由于只能沿着对角线移动，那么能从必须满足：和的奇偶性相同，因此我们只需将奇偶性相同的点分为一组，然后只需计算每组组内点的即可

不难发现：,然而这样就对转化的最值求和时间开销依然十分大

这里就不得不引入(切比雪夫距离与曼哈顿距离的互化)，来对时间复杂度进行优化

设平面中两点分别为

• 曼哈顿距离为：
• 切比雪夫距离为：

一个点 的坐标变为后，原坐标系中曼哈顿距离 =新坐标系中切比雪夫距离。

一个点 的坐标变为 后，原坐标系中的切比雪夫距离为新坐标系中的曼哈顿距离。

由此我们可以通过变换坐标系，将直角坐标系的点映射至新坐标系中点即可转化为曼哈顿距离来做，然后我们计算对新坐标系的的横纵坐标进行从小到大排序(达到：将绝对值符号去掉)，最后计算每个横纵坐标产生的贡献值，累加贡献值即为答案

解题代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;cin>>n;
  vector<int> a[4];
  for(int i=0;i<n;i++){
    int x,y;cin>>x>>y;
    //奇偶分类，切比雪夫距离转曼哈顿距离
    if((x+y)&1){
      a[0].push_back(x+y);
      a[1].push_back(x-y);
    }else {
      a[2].push_back(x+y);
      a[3].push_back(x-y);
    }
  }
  ll ans=0;
  for(int i=0;i<4;i++){
    sort(a[i].begin(),a[i].end());
    int sz=a[i].size();
    for(int j=0;j<sz;j++){
      ans+=1ll*(2*j+1-sz)*a[i][j];//a[i][j]的贡献数量为：+j-(sz-j-1)=2*j+1-sz
    }
  }
  cout<<ans/2<<"\n";
  return 0;
}

F - Double Sum

题意

对于非负整数序列，求解

解题思路

求解，可以分别开两个树状数组维护，需要注意的是：有可能比较大，因此需要对进行离散化

总的时间复杂度为

解题代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400010;
ll a[N],n;
ll ans;

struct BIT{
  ll d[N];
  void update(ll x,ll y){
    x++;
    while(x<N) d[x]+=y,x+=(x&(-x));
  }
  ll query(ll x){
    x++;
    ll sum=0;
    while(x) sum+=d[x],x-=(x&(-x));
    return sum;
  }
}bit1,bit2;

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n;
  vector<ll> new_a(n);
  for(int i=0;i<n;i++) cin>>a[i],new_a[i]=a[i];
  //离散化
  sort(new_a.begin(),new_a.end());
  new_a.erase(unique(new_a.begin(),new_a.end()),new_a.end());
  for(int i=0;i<n;i++){
    int x=lower_bound(new_a.begin(),new_a.end(),a[i])-new_a.begin();
    ans+=bit1.query(x)*a[i]-bit2.query(x);
    bit1.update(x,1);
    bit2.update(x,a[i]);
  }
  cout<<ans<<"\n";
}