Atcoder abc280

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
G(切比雪夫距离,曼哈顿距离)Ex(后缀数组,SA,单调栈)

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

G - Do Use Hexagon Grid 2

六边形地图

(i,j) 和 (i+-1,j), (i,j+-1), (i+1,j+1) ,(i-1,j-1) 相邻

给你n个点

问有多少种方案能选一个非空点集, 使点集中两两距离不大于D

范围

n 300

xi,yi, [-1e9,1e9]

d [1,1e10]

3s

1024mb

我的思路

先想 1维, 就是sort, 然后定必定要选的点从左到右, 找区间长d中的点个数的2的幂次

然后不是六边形的 2维, 类似的定(左,下)角的点, 但问题是 其它点个数不能再2的幂次了

总觉得做过, 但是又完全不会

n=300 就可能 3次方的做法

题解

一样也是先考虑变形, dis(x=x0-x1,y=y0-y1) = max(|x|,|y|,|x-y|)

那么每个点也这样变形 (x,y,x-y), 问题变成点集 在一个 正方体 DxDxD中

然后怎么统计呢, 其实和一维一样的, 不过枚举的最小值,变成3个维度的最小(必选)

那么 所在的正方形就是 (x0..x0+D,y1..y1+D,z2…z2+D)

直接搞是O(n^4)

考虑 最后一个维度 滑窗 一下 就是O(n^3)

官方代码还搞了个cnt[8],花里胡哨的,感觉好复杂(如果真这样,就算我会写赛内也难调出), 通过指定点 而不是指定值 感觉会简单不少, 当两个点有坐标y相同时, 考虑用index更小的作为标识

代码

https://atcoder.jp/contests/abc280/submissions/37080844

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
using ll=long long;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
mint p2[310]={1}; // power 2
int main(){
  int n=read();
  ll d=read();
  rep(i,0,n) p2[i+1]=p2[i]*2;
  vector<array<ll,3> >a;
  rep(i,0,n){
    int x=read();
    int y=read();
    a.push_back({x,y,x-y});
  }
  sort(begin(a),end(a)); // 按照x排序

  mint ans=0;
  rep(iy,0,n) rep(iz,0,n) {// 最小y取i, 最小z取j 指定最小 y,z, 滑窗x, [y..y+d,z..z+d]
    auto ok=[&](int i,int j,int k)->bool{ // a[j][k] <= a[i][k] <= a[j][k]+d ?
      return (i>=j) ?
        (a[j][k]<=a[i][k] and a[i][k]<=a[j][k]+d):
        (a[j][k]< a[i][k] and a[i][k]<=a[j][k]+d); // 下标小于不能取等
    };
    auto oky=[&](int i){return ok(i,iy,1);};
    auto okz=[&](int i){return ok(i,iz,2);};
    if(!oky(iz) || !okz(iy)) continue;
    int cnt=0;
    int pos=0; // 双指针 后面的index
    rep(ix,0,n){ // 第i作为x最小
      auto okx=[&](int i){ return ok(i,ix,0); };
      while(pos<n&&a[pos][0]<=a[ix][0]+d){ // 双指针滑窗
        if(oky(pos)and okz(pos)) cnt++;
        pos++;
      }
      if(oky(ix) and okz(ix) and okx(iy) and okx(iz)) {
        int distinct=3-(int(ix==iy)+int(iy==iz)+int(iz==ix));
        if(distinct==0) distinct=1;
        ans+=p2[cnt-distinct];
      }
      if(oky(ix) and okz(ix))cnt--;
    }
  }
  printf("%d\n",ans.val());
  return 0;
}

Ex - Substring Sort

给n个小写英文字母字符串, $m = \sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$

那么有 m 个3元组(ki=字符串index,li 该字符串内子串起始下标,ri,该字符串内子串结束下标)

那么每个三元组 对应到一个子字符串, 现在把三元组按照子字符串的字典序排序, (如果两个不同三元组对应子串相同,那么这两个三元组的相对顺序任意)

q个询问 每次问 排序后第qi个 三元组的任意一个可能值, 输出任意一个可能的(k_qi,l_qi,r_qi)

范围

n 1e5

字符串总长 <= 1e5

2s

1024mb

我的思路

排序, 字符串里和排序有关的 感觉就SA

所有子串 又 感觉SAM

按照SA的思路

就是 把字符串通过 int(‘a’-1) 进行拼接

然后排后缀数组

那么 去计算每个字符串 在 三元组中的顺序, 似乎可以二分?

如何计算呢

假设排序后

s[i…], s[j…] 是相邻的, s[i..] 已经算出

那么能在它们之间的, 是 s[j…] 的前缀(注意不可能还有 不是前缀而 大于 s[i..] 小于s[j..] 的), 且不是 s[i…]的前缀

而有高度数组的话, 其实可选的字符串 就很明显了

然后问题是有多少个, 那么就要看从 s[j..] 在SA周后面高度数组连续的

这样似乎就可以算出 每个的下标? sa和高度数组h的时间复杂度肯定够, 但是 枚举前缀长度的话 这复杂度够吗???

但是实际上统计的时候 向后看h数组, 可以按照h 进行离散的算, 每个h只会影响到前面一个 具体的位置

似乎又可以算

如果算好了, 那么就到了二分到某个之间

如果再去查又是 我不会估计的复杂度

所以还是在上面计算h的时候, 把h插入到哪一个之间也记录下来, 这样每个被影响的里面也记录了有序的离散点可以继续二分似乎就没了?

还真就过了

代码

https://atcoder.jp/contests/abc280/submissions/37108436

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

// 0-index + vector + sort
// sa 下标按照顺序排列
// rank 下标对应顺序index
// h sa 中相邻后缀 最长公共前缀 h[0] = 0; h[i] = 最长公共前缀(s[sa[i]..],s[sa[i-1]..])
template<class T>
tuple<vector<int>,vector<int>,vector<int>> s_2_sa_rank_h(const vector<T>& arr){
  int n = arr.size();
  string s="";
  rep(i,0,n) s+= char(arr[i]);
  vector<int> rank(n);
  vector<int> sa(n);
  iota(sa.begin(),sa.end(),0);
  rep(i,0,n) rank[i]=arr[i];
  for(int w=1; w<=2*n; w*=2) { // width
    vector<pair<int,int>>val;
    rep(i,0,n)val.push_back({rank[i],i+w/2<n?rank[i+w/2]:-1});
    sort(sa.begin(),sa.end(), [&](int i,int j){ return val[i]<val[j]; });
    rank[sa[0]] = 0;
    rep(i,1,n) rank[sa[i]] = rank[sa[i-1]] + int(val[sa[i]]!=val[sa[i-1]]);
  }
  // height
  vector<int>h(n);
  int k = 0;
  rep(i,0,n) {
    if (rank[i] == 0) continue;
    if (k) --k;
    while (arr[i + k] == arr[sa[rank[i] - 1] + k]) ++k;
    h[rank[i]] = k;
  }
  return {sa,rank,h};
}

char tmp[100010];

int main(){
  int n=read();
  vector<int> s;
  vector<int> si;
  vector<ll> leni;
  rep(i,0,n){
    si.push_back(s.size());
    scanf("%s",tmp);
    int sz=strlen(tmp);
    leni.push_back(sz);
    rep(j,0,sz) s.push_back(tmp[j]);
    s.push_back('a'-1);
  }
  vector<int>sa,rank,h;
  tie(sa,rank,h)=s_2_sa_rank_h(s);
  h.push_back(0); // 减少边界逻辑
  int m=s.size();
  vector<pair<int,int>>se(m);// start end
  vector<int> stk; // 单调栈
  rep(i,0,m) if(s[sa[i]]!='a'-1){
    while(stk.size()){
      if(h[stk.back()] < h[i]) break;
      se[stk.back()].second = i-1;
      stk.pop_back();
    }
    se[i].first=stk.size()?stk.back():i-1;
    stk.push_back(i);
  }
  for(int i:stk)se[i].second=m-1;
  vector<array<ll,4> > sxen; // {start idx,max len, end idx, min len}
  rep(i,0,m) if(s[sa[i]]!='a'-1){
    sxen.push_back({se[i].first,h[i],se[i].second,max(h[se[i].first],h[se[i].second+1])+1}); // 区间的
    sxen.push_back({i,m,i,max(h[i],h[i+1])+1}); // 单个的
  };
  vector<array<ll,4> > next_sxen;
  auto saidx2sidx=[&](int i){ return int(lower_bound(begin(si),end(si),sa[i]+1)-begin(si))-1; }; // 没int会RE
  for(auto [starti,mxlen,endi,mnlen]:sxen){ // 去除无效的
    // si -> 计算在哪个字符串
    int sidx=saidx2sidx(starti);
    mxlen=min(mxlen,leni[sidx]-(sa[starti]-si[sidx]));
    if(mxlen>=mnlen) next_sxen.push_back({starti,mxlen,endi,mnlen});
  }
  sxen=next_sxen;
  sort(begin(sxen),end(sxen)); // 字典序排序

  int q=read();
  int idx=0; // < idx 积累的和
  ll cnt=0;
  while(q--){
    ll qi=read();
    for(;;){
      auto [starti,mxlen,endi,mnlen]=sxen[idx];
      ll next_cnt = cnt + (endi-starti+1)*(mxlen-mnlen+1); // qi 应该落在(cnt, next_cnt] 中
      if(next_cnt < qi){
        cnt=next_cnt;
        idx++;
      }else{
        int len=mnlen+(qi-cnt-1)/(endi-starti+1);
        int sidx=saidx2sidx(starti);
        int l=sa[starti]-si[sidx]+1;
        printf("%d %d %d\n",sidx+1, l, l+len-1);
        break;
      }
    }
  }
  return 0;
}

总结

G

平面距离还是不熟, 正常的(x,y) 距离就是变成 max(|x+y|,|x-y|) 去算的, 这里应该要能想到, 一旦有了这个,那么 上面的变化也就显然了

然后这个枚举最小值的1维的思路其实也很好, 看到这里n这么小, 应该也要想到 枚举一个对小值点, 变成枚举3个维度的最小值点啊

方向有点对,就是先想退化的例子,再推, 但是想出了部分退化,推没推成功

Ex

字符串类的常见工具

hash: 比较很长的字符是否相等

kmp: (最长前缀递归dp)给定字符串S, 在其余字符串 找任意位置的最长后缀 是S的前缀

ac自动机: trie树+kmp思想, 对多个字符串建立字典trie树, 用于查询一个字符串的每个位置子字符串,是否在字典中出现次数

SA: 一个字符串按后缀排序 以及 排序后相邻的高度数组

SAM: 输入一个原始字符串，产生一个自动机，能识别一个给的新字符串是否是原始字符串的后缀, 以及(不同子串个数, 某个子串出现次数

所以这题 我自己能搞出来 虽然编码花了不少时间, 但是从思路主干上看 完全不应该是铜牌题

参考

官方题解