YeXiaoRain Blog

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘

G(倍增)

G

题目

https://atcoder.jp/contests/abc254/tasks_print

n个楼, 每个楼高都是1..1e9

有m个电梯, 每个电梯在一个楼里,负责[li,ri] 之间

可以允许这个楼里, [li,ri] 范围中的移动

跨楼同楼层移动代价1

同楼电梯内移动,代价 高度差

q个询问, ai楼bi层 到 ci楼di层最小代价, 或它们不可达

范围

n 2e5

m 2e5

q 2e5

6s

1024mb

题解

我的思路

显然 同楼层答案是1或0

不同楼层,只会单调移动,不会先上再下这种, 答案 = 距离+跨楼数, 需要最小化跨楼数

而每次移动贪心距离, 这样模拟可做, 但是复杂度无法接受

显然同楼的重叠电梯可以合并

官方

显然上下还满足对称性, 那么只考虑从下向上

合并同楼重叠电梯(这样做了以后剩下的线段就不用考虑属于哪个楼了? 因为是一旦重叠肯定不重楼

如果 ai楼内bi移动到最高位置, ci 楼内 di 移动到最低位置, 合法提前输出

dp[i][j] 当前建筑第i层,用j个电梯后最高能到达的楼层

考虑 离散+倍增

代码

我写的按右断点跳右端点的map不知道为什么WA了除了测试点, 调了七八个小时,atcoder还没数据, 放弃了

下面是一个别人的代码,我改了部分格式,靠清理了一些线段,保持左右端点都严格单调递增, 然后用线段跳线段来做的, 我觉得完全一样啊, 吐了, 搞不动了,心态炸了

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
#define pb push_back

int read(){int r;scanf("%d",&r);return r;} // read

vector<array<int,2> > ilr[200010];
vector<array<int, 2>> segs;
vector<vector<int>> jump;

int N;
int lg = 20;

int n, m, q;

int query(){
  int i0, f0, i1, f1;
  i0 = read() - 1;
  f0 = read();
  i1 = read() - 1;
  f1 = read();

  if(f0 == f1) return i0 != i1;

  if (f0 > f1) {
    swap(i0, i1);
    swap(f0, f1);
  }

  int ans = f1 - f0;
  auto it =
    lower_bound(ilr[i0].begin(), ilr[i0].end(), array<int, 2>{f0 + 1, -1});
  if (it != ilr[i0].begin()) f0 = max(f0,(*--it)[1]);

  it = lower_bound(ilr[i1].begin(), ilr[i1].end(), array<int, 2>{f1 + 1, -1});
  if (it != ilr[i1].begin()) {
    it--;
    if (f1 <= (*it)[1]) {
      f1 = (*it)[0];
    }
  }

  if (f0 >= f1) return ans + (i0 != i1);
  // 跳到一个右端点 保证f0 是右端点
  ans++;
  int idx = lower_bound(segs.begin(), segs.end(), array<int, 2>{f0 + 1, -1}) - segs.begin();
  // 未被覆盖到
  if (!idx) return -1;
  idx--;
  if (f0 > segs[idx][1]) return -1;
  if (segs[idx][1] >= f1) return ans + 1;
  if (segs[jump[idx][lg]][1] < f1) return -1;
  per(k,0,lg+1){
    if (segs[jump[idx][k]][1] >= f1) continue;
    idx = jump[idx][k];
    ans += 1 << k;
  }
  idx = jump[idx][0];
  return ans + 2;
}

int main() {
  n = read();
  m = read();
  q = read();
  rep(i,0,m){
    int a, b, c;
    a = read() - 1;
    b = read();
    c = read();
    ilr[a].push_back({b, c});
  }
  // 每组内部 排序 与 合并
  rep(i,0,n){
    sort(ilr[i].begin(), ilr[i].end());
    vector<array<int, 2>> temp;
    for (auto [l, r] : ilr[i]) {
      if (!temp.empty() && l <= temp.back()[1]) {
        temp.back()[1] = max(temp.back()[1], r);
      } else {
        temp.push_back({l, r});
      }
    }
    ilr[i] = temp;
    for (auto s : temp) segs.push_back(s);
  }

  sort(segs.begin(), segs.end());

  vector<array<int, 2>> temp;
  for (auto [l, r] : segs) {
    if (!temp.empty() && r <= temp.back()[1]) { //
      continue;
    }
    if (!temp.empty() && l == temp.back()[0]) {
      temp.pop_back();
    }
    temp.push_back({l, r});
  }
  segs = temp;

  N = segs.size();
  jump = vector<vector<int>>(N, vector<int>(lg + 1));

  // jump[段id][pwr] = 段id
  for (int i = 0, j = 0; i < N; i++) {
    while (j + 1 < N && segs[j + 1][0] <= segs[i][1]) {
      j++;
    }
    jump[i][0] = j;
  }
  rep(j,0,lg){
    rep(i,0,N){
      jump[i][j + 1] = jump[jump[i][j]][j];
    }
  }


  while(q--) printf("%d\n", query());
  return 0;
}

我的代码 不知道WA在哪里了

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
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n,m,q;

vector<pair<int,int> > ilr[200010]; // 每个楼

vector<pair<int,int> > segs; // 所有楼
vector<int> maxr = {0}; // 前缀 最大r
map<int,vector<int>> jump = {}; // jump[结束位置][2**i次跳跃] = 最高位置

const int lg = 20;

int query(){
  int i0 = read();
  int f0 = read();
  int i1 = read();
  int f1 = read();
  // 同楼层
  if(f0 == f1) return i0 != i1;

  // 从低到高 f0 < f1
  if(f0 > f1){
    swap(i0,i1);
    swap(f0,f1);
  }
  int ans = f1-f0;

  // 注意不在区间的情况不会跳
  int itr0 = lower_bound(ilr[i0].begin(),ilr[i0].end(),make_pair(f0+1,-1)) - ilr[i0].begin();
  if(itr0 > 0) f0 = max(f0, ilr[i0][itr0-1].second);

  int itr1 = lower_bound(ilr[i1].begin(),ilr[i1].end(),make_pair(f1+1,-1)) - ilr[i1].begin();
  if(itr1 > 0 && ilr[i1][itr1-1].second >= f1) f1 = ilr[i1][itr1-1].first;

  if(f1 <= f0) return ans + (i0 != i1);

  // next0 可能不是某个右端点, 不可能一次跳到, 否则 perv1 <= next0, 所以直接贪心去最大可达右端点
  // 跳一次 保证f0 是右端点
  int idx = lower_bound(segs.begin(),segs.end(),make_pair(f0+1,-1)) - segs.begin();
  if(idx == 0 || maxr[idx] < f0) return -1; // 未被覆盖到
  f0 = maxr[idx]; // 当不可达时可能是比它小的右端点, 但是不影响结果逻辑
  ans ++;
  if(f1 <= f0) return ans + 1;

  // ? 需要吗 TODO
  // if(!h.count(f0)) return -1;

  if(jump[f0][lg] < f1) return -1;

  per(pwr,0,lg+1){
    if(jump[f0][pwr] >= f1) continue;
    f0 = jump[f0][pwr];
    ans += (1<<(pwr));
  }
  assert(f0 < f1 && jump[f0][0] >= f1);
  // printf("%d\n",ans+1 +1); // 分别是跳到比f1 大的和跳到恰好f1
  return ans + 2; // 分别是跳到比f1 大的和跳到恰好f1
}

int main(){
  n = read();
  m = read();
  q = read();
  rep(i,0,m) {
    // 注意g++ 函数处理顺序问题
    // ilr[read()].pb(make_pair(read(),read()));
    int pos = read();
    int l = read();
    int r = read();
    ilr[pos].pb({l,r});
  }
  // 合并同楼 重叠
  rep(i,1,n+1){
    sort(ilr[i].begin(),ilr[i].end());
    vector<pair<int,int> > tmp = {}; // 合并辅助
    for(auto [l,r]: ilr[i]){
      if(tmp.size() == 0 || l > tmp.back().second){ // 不连续 [l0,r0] .. [l1..r1]
        tmp.pb({l,r});
      }else{
        tmp.back().second = r;
      }
    }
    ilr[i] = tmp;
    for(auto o:tmp) segs.pb(o);
  }
  sort(segs.begin(),segs.end()); // 所有楼的
  for(auto item:segs) maxr.pb(max(maxr.back(), item.second));
  // 倍增
  for(auto item:segs){
    auto r = item.second;
    if(jump.count(r)) continue;
    jump[r] = vector<int>(lg+1,r);
    // [...r] [r+1...
    int idx = lower_bound(segs.begin(),segs.end(),make_pair(r+1,-1)) - segs.begin();
    jump[r][0] = maxr[idx]; // 初始化跳2^0 = 1次
  }
  rep(pwr,1,lg+1){
    for(auto item:segs){ // 会重复计算,不影响
      auto r = item.second;
      jump[r][pwr] = jump[jump[r][pwr-1]][pwr-1];
    }
  }

  while(q--) printf("%d\n", query());
  return 0;
}

总结

G

倍增, 编码速度也是问题, 写几个小时还在wa,哎

参考

官方题解 https://atcoder.jp/contests/abc254/editorial

發表於 更新於 分類於 Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘

主要问题不在算法,在自己写bug

题目

https://www.codechef.com/submit-v2/PRFSUFDSTNCT

一个数组, 的前缀i个数,不重复的数值个数为pi

后缀i到结束,不重复的数值个数为si

给你p和s,问是否存在数组满足, 返回是否即可

范围

n 1e5

1s

题解

我的思路

首先最直接的,

p[0] = s[n-1] = 1

p[n-1] = s[0]

然后 p的增量为0/1,s的增量为0/-1

再因为每个值至少贡献1次

所以如果p[i] + s[i+1] == p[n-1], 那么说明 i 和i+1 可以切开,并且这位置p增量为1,s增量为-1

对于切开后的每一段 找到变化的位置(增量为1/-1)的位置

分别跑后缀的前缀 应该小于等于前缀(与前缀首个的差)

和 前缀的后缀 应该小于等于后缀(与后缀最后一个的差)

官方

反而没有切割的操作,上面几个倒是有

官方 判断了个a[i]+b[i] <= a[n-1] 跟我切割操作有点像,但是 不是错位的判断

原理和我那个也是类似,所有数贡献一次,左右统计的第i个两侧都有贡献,所以至少是a[n-1]+1

–

分析的是同一位的(p[i]-p[i-1],s[i]-s[i+1]) 的四种情况

1,1 原数组中唯一的值, 不需要额外判断, 甚至可以考虑原数组删除它

0,1 和 1,0 是对称的, 如果全部都是这两个

那么1,0 的出现意味着 右侧会有一个0,1 也就是从后缀上这个数首次出现的

可以看成1,0左括号,0,1右括号做括号匹配, 但不完全是相邻位置的, 如 (()), 可以1和3,2和4配

0,0 说明没有变化,应该被包含在某个值中, 如果记作.

那么(.)(.)是好的, 而().(),0,0无值可选

如此检查

(.)(.) 如

1
2
p 111222
s 222111

正好一个答案是111222

().()如

1
2
11122
22111

再换句 (, 上面+1, 右括号下面后一个-1, 所以考虑上下的总和变化, 出现问题就是 a[i]+b[i] <= a[n-1]

看了一下应该是有真的代码被我判否了, 因为我把答案逻辑塞到我代码后面return false也不对

最后发现是因为我代码 if 的l和r复制漏改了

代码

按照我的逻辑AC的代码

https://www.codechef.com/viewsolution/66653363

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll p[100010]; // a 前缀 [..i] 不同的个数
ll s[100010]; // a 后缀 [i..] 不同的个数

bool p0[100010];
bool p1[100010];
// 只用 yes or no
int n;

// 保证范围 单增 单减 , 跨度 0/1
bool check(int l,int r){
  // [st..en]
  if(l > 0 && p[l] != p[l-1]+1) return false;
  if(r < n - 1 && p[r] != p[r+1]-1) return false;

  if(l > 0 && s[l] != s[l-1]-1) return false;
  if(r < n - 1 && s[r] != s[r+1]+1) return false; // 这里写成l了

  if(p[r] - p[l] != s[l] - s[r])return false;

  // 计算变化的点
  rep(i,l,r+1){
    if(i == r || p[i] != p[i+1]){
      p0[i] = true;
    }
  }
  rep(i,l,r+1){
    if(i == l || s[i] != s[i-1]){
      p1[i] = true;
    }
  }

  // 跑前缀 <= 前缀
  {
    int cur = 0;
    rep(i,l,r+1){
      cur += p1[i];
      if( cur > p[i] - p[l]+1) return false;
    }
  }
  {
    int cur = 0;
    per(i,l,r+1){
      cur += p0[i];
      if( cur > s[i] - s[r]+1) return false;
    }
  }

  return true;
}

bool w(){
  // 清空
  n = read();
  fill(p0,p0+n,0);
  fill(p1,p1+n,0);
  rep(i,0,n) p[i] = read();
  rep(i,0,n) s[i] = read();
  // p [n-1] 不同的总数
  if(p[n-1] != s[0]) return false;
  if(p[0] != s[n-1]) return false;
  if(p[0] != 1) return false;
  // 跨度 0/1
  rep(i,1,n)if(p[i] < p[i-1] || p[i] > p[i-1] + 1)return false;
  rep(i,1,n)if(s[i] > s[i-1] || s[i] < s[i-1] - 1)return false;
  int itr = 0;
  rep(i,0,n-1){
    if(p[i] + s[i+1] == p[n-1]){
      if(!check(itr,i)) return false;
      itr = i+1;
    }else if(p[i] + s[i+1] < p[n-1]){
      // ???
      return false;
    }
  }
  return check(itr,n-1);
}

int main(){
  int t = read();
  while(t--) printf("%s\n",w()?"YES":"NO");
  return 0;
}

总结

BUG 是我AC失败一个重大阻碍

题解的转化我也是没想到的学习了

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 3.7k 所需閱讀時間 ≈ 12 分鐘
D(数学,跳点) E(数学,构造,min-max容斥,kmin/kmax容斥)

D

$f(x) = $比x大的最小平方数

$g(x) = $比x小的最大平方数

如果 $x - g(x) < f(x) - x$ 那么$x$是好的

给长度$n$的单调数组$a$, 求最小非负$k$,使得$a_i+k$ 全为好的

范围

$n \le 10^6$

$a_i \le 2\cdot 10^6$

2s

256MB

题解

我的思路

先做点数学变形

易知对于任意$x=a_i$, 如果$\exists w, x \in [w^2,w^2+w]$ 那么$x$是好的

然后 真不会了

閱讀全文 »

發表於 更新於 分類於 ， Disqus： 文章字數： 271 所需閱讀時間 ≈ 1 分鐘
F(贡献统计,组合数,树)

题目

https://codeforces.com/contest/1691/problem/F

树,n个点,点上1~n

给定k

对于点r, 树的一个k个点的子点集S, 令f(r,S) = 根为r, 且包含所有S中点的原树的子树最少的点的个数

你需要计算 所有 r和S的组合 求 所有f(r,S)的和

答案mod 1e9+7

范围

n 2e5

3s

512MB

题解

我的思路

看数据范围n方都不行, 既然又是求和

那么估计又是算贡献一类

从树的结构讲, 与其算贡献不如算不被贡献

一个点u,连接了很多点v0,v1,v2,v3

如果要u不被贡献, 那么r和S的所有点一定在某个vi的联通块内,不会是不同vi的联通块内

而选择来讲, 对于S, 就是C(联通块大小,k), 对于r就是联通块大小

注意联通块 < k时 方案为0

感觉就过了???不想写代码

代码

鸽

总结

感觉给时间, 就这样随便搞一搞就完了?

参考

无

發表於 更新於 分類於 Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘

前情提要

在之前做Project Euler 216 的时候

学了一下 如何利用别人的答案,在log n时间内判断n是否是一个 64位以内的质数的 Miller-Rabin 判别法

但如果这个数不是质数, 如何能拆解还没有解决

方法

方法1

回到最初的起点, for一遍 那也是$\sqrt(n)$

而众所周知, $\sqrt {2^{64}} = 2^{32} = $ 4.2e9

单独算一次的时间复杂度都接受不了

方法2

相信随机的力量, 先特判是否质数

在不停的随一个判断是否gcd != 1 来找因数

问题是, 生日悖论(一个房间里有23个人，则他们中有两人生日相同的概率超过一半)

换句话说, 反复生成随机数,有很高几率生成了不少一样的

Pollard 的伪随机数

问题变成 我们希望它概率上看起来随机,值上有不重复得不那么随机

$x_{n+1} = f(x_n) = (x_n^2 + c) mod N$

但也不一定如期望, 例如 x = 0, c= 24,N = 9400, 很有规律, 因为这个递推式说白了就是下一项由上一项决定,肯定有循环,只是循环的早晚

低空间,低时间判断环? 那不是经典面试题双指针吗?(floyd判环算法)

初始$x_1 = y_1$

$x_{n+1} = f(x_n)$

$y_{n+1} = f(f(y_n))$

每次判断$gcd(|x_n - y_n|,N) > 1$, 和是否到达环, 成环则换一个c来跑

性质 |i-j| 是p的倍数,则 |f(i)-f(j)| 也是p的倍数

如果看作环上指针, 也就意味这两个指针距离相等时,其它距离和这个距离相等的两个指针之差,都是p的倍数,

而快慢指针每次会让距离+1, 而对于环上的视角, 其实追上慢指针相当于逐渐减少

实现和细节

据说$O(n^{\frac{1}{4}}\log n)$

$N = 4,N = 1$ 需要特判

素数平方提前判断

让x=0

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

typedef __int128_t lll;
ll quick_p(lll b, ll p,ll mod){
  lll r = 1;
  while(p){
    if(p%2)(r*=b)%=mod;
    (b*=b)%=mod;
    p/=2;
  }
  return r % mod;
}

bool miller_robin(ll v, ll base, ll startpwr){
  lll r = quick_p(base,startpwr,v);
  for(ll p = startpwr; p < v-1; p *=2){
    if(r == v-1) return true; // -1 开始的序列
    if(r == 1) return p == startpwr; // 全1序列
    (r*=r)%=v;
  }
  return false;
}

bool is_prime_64(ll v){
  if(v == 2)return true;
  if(v < 2 || v % 2 == 0)return false;
  ll p = v-1;
  while(p % 2 == 0) p /= 2;
  for(auto base:{2, 325, 9375, 28178, 450775, 9780504, 1795265022}){
    if(base % v == 0) continue; // don't break may cause 4033 bug
    // 需要所有都能找到-1开始, 或奇数次开始 全1
    if(!miller_robin(v,base,p)) return false;
  }
  return true;
}

ll my_sqrt(ll v){
  if(v <= 1) return v;
  ll l = 1; // 左ok
  ll r = v; // 右not ok
  while(r - l > 1){
    ll m = (l+r)/2;
    (v/m < m ? r : l) = m; // 防止 overflow
  }
  return l;
}
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);

ll randll(ll low,ll hi){
  return low + (rand_num() % static_cast<ll>(hi - low + 1));
}

ll Pollard_Rho(ll N) { // 返回一个> 1的因数
  assert(N > 1);
  if (N == 4) return 2;
  lll ret = my_sqrt(N); // 质数平方 效率低 提前判断
  if(ret * ret == N) return ret;
  while(true) {
    ll c = randll(1, N - 1); // 生成随机的c
    auto f = [=](lll x) { return ((lll)x * x + c) % N; }; // ll 表示__int128，防溢出
    ll t = 0, r = 0; // 初始两个相同
    do{
      t = f(t); // 1倍速度
      r = f(f(r)); // 2倍速度
      ll d = gcd(abs(t - r), N);
      if (d > 1 && d < N) return d;
    }while (t != r);
  }
}

// 分解x为质因数, sorted
vector<ll> fenjie(ll x) {
  vector<ll> res = {};
  deque <ll> arr = {x};
  while(arr.size()){
    ll v = arr.front();
    arr.pop_front();
    if(v == 1) continue;
    if(is_prime_64(v)) {
      res.pb(v);
      continue;
    }
    ll divisor = Pollard_Rho(v);
    arr.push_back(divisor);
    arr.push_back(v/divisor);
  }
  sort(res.begin(),res.end());
  return res;
}

固定128距离

减少求gcd的次数, 128次 或者 即将乘起来是N的倍数

大概是$O(n^{\frac{1}{4}})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ll Pollard_Rho(ll N) {
  assert(N!=1);
  if (N == 4) return 2;
  if (is_prime(N)) return N;
  if (is_prime_square(N)) return prime_square(N);
  while(true){
    ll c = randint(1, N - 1);
    auto f = [=](ll x) { return ((lll)x * x + c) % N; };
    ll t = 0, r = 0, p = 1, q;
    do {
      for (int i = 0; i < 128; ++i) { // 令固定距离C=128
        t = f(t), r = f(f(r));
        if (t == r || (q = (lll)p * abs(t - r) % N) == 0) break; // 如果发现环，或者积即将为0，退出
        p = q;
      }
      ll d = gcd(p, N);
      if (d > 1) return d;
    } while (t != r);
  }
}
0%