Atcoder abc234

發表於 更新於 分類於 ， Disqus： 文章字數： 961 所需閱讀時間 ≈ 3 分鐘
G(单调栈)Ex(分块)

https://atcoder.jp/contests/abc234/tasks

G - Divide a Sequence

长n数组A

2^{n-1}种方式切割成非空顺序数字

f(切割) = $\prod$每个子数组的 (max-min)

求 $\sum$ f(所有切割)

mod 998244353

范围

2s 1024mb

我的思路

dp搞一搞

考虑最后一个数组长度
dp[i] = dp[i-len] * ((max-min)([i-len+1..i]))

但这样就O(n) 状态, n^2转移了

然后,算的时候,max和min可以拆开, 但是如果 两两不等的话, 即使用了 区间sum dp * max, 也可能max需要一个一个枚举,也是n^2

问题变成说

dp[i] = sum max(a[i-len+1..i]) * dp[i-len] - min(a[i-len+1..i]) * dp[i-len]

考虑相邻转移

i-1: sum max(a[j+1..i-1]) * dp[j]

  1. a[i]是[j+1..i]的最大值, 那么找最小的j, 这之家你的贡献 = a[i] * sum dp[j..i-1]
  2. a[i]不是[j+1..i]的最大值, 那么这贡献 = sum max(a[j+1..i])*dp[j] = sum max(a[j+1..i-1])*dp[j]

因此相邻的dp虽然没有直接关系, 但是可以利用上次的计算

dp[i] = a[i] * sum(dp[j..i-1]) + sum f(0..j)

min同理

似乎就没了

代码

https://atcoder.jp/contests/abc234/submissions/34662212

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

int a[300010];
mint pdp[300010] = {1}; // 未选择, 乘积和 = 1 presum dp
int main(){
  int n = read();
  rep(i,1,n+1) a[i] = read(); // 需要前缀和 1-index
  std::vector<std::pair<int,mint> > maxi = {};
  std::vector<std::pair<int,mint> > mini = {};

  rep(i,1,n+1){
    while(maxi.size() && a[maxi.back().first] <= a[i]) maxi.pop_back();
    maxi.push_back({i,(maxi.size()?maxi.back().second:0) + a[i] * (pdp[i-1]  - (maxi.size()?pdp[maxi.back().first-1]:0))});

    while(mini.size() && a[mini.back().first] >= a[i]) mini.pop_back();
    mini.push_back({i,(mini.size()?mini.back().second:0) + a[i] * (pdp[i-1]  - (mini.size()?pdp[mini.back().first-1]:0))});
    pdp[i] = pdp[i-1] + (maxi.back().second - mini.back().second);
  }
  printf("%d\n",(pdp[n] - pdp[n-1]).val());
  return 0;
}

Ex - Enumerate Pairs

平面N个点, 整数k

输出所有几何距离<=k的点对, 按字典序

保证结果 <= 4e5

范围

n 2e5

k 1.5e9

xi,yi [0,1e9]

4s

1024mb

我的思路

最无脑就是n^2暴力, 除了会TLE就是对的

如果是长方形还好, 可以 二维线段树, 但是圆形并不会

剩下想法分块和二分?

题解

每个点分配到(xi/k,yi/k) 中

这样每个点在它的块 的8临块 中找可匹配点

暴力即可, 充分性显然

复杂度证明! O(N+M)

对于块有x个点, 显然其内部距离小于k的点对是 x^2级别的,(证明,4等分成4个正方形子块, 至少一个块的数量级是x,而其内部两两距离小于k)

因此 所有块的 x^2 和的级别 <= M

因此块间 x1x2 <= max(x1,x2)^2 <= M

得证

代码

https://atcoder.jp/contests/abc234/submissions/34662441

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;}
const ll MAXY = 2e9;
int dx[] = {-1,-1,-1, 0, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1,-1, 0, 1,-1, 0, 1};
ll enc(ll x,ll y){ return x*MAXY+y;} // 编码
int main(){
  int n = read();
  ll k = read();
  vector<pair<ll,ll>> pts(n+1);
  map<ll,vector<int>> mp;
  rep(i,1,n+1){
    ll x = read() + k; // 平移 保证8邻的坐标也是非负, 题解这里有问题?x,y可能为负数?
    ll y = read() + k;
    pts[i] = {x,y};
    mp[enc(x/k,y/k)].push_back(i);
  }
  vector<pair<int,int>> res;
  rep(i,1,n+1){
    auto [x,y] = pts[i];
    rep(t,0,9) for(int j: mp[enc(x/k+dx[t],y/k+dy[t])]) if(i<j) { // 自己和八邻块
      auto [xj,yj] = pts[j];
      if((x-xj)*(x-xj) + (y-yj)*(y-yj) <= k*k) res.push_back({i,j});
    }
  }
  sort(res.begin(),res.end());
  printf("%d\n",(int)res.size());
  for(auto [i,j]: res) printf("%d %d\n",i,j);
  return 0;
}

总结

G

dp,前缀和,单调栈,没啥难的

Ex

分块, 神奇的分块, 不会证明,

参考

官方题解