YeXiaoRain Blog

發表於 更新於 分類於 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);
  }
}

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

C(math, 括号对)D(math,集合,数论,动归)E(并查集)

C

题目

https://atcoder.jp/contests/arc141/tasks/arc141_c

他给两个排列p和q, 长度2n

构造 长2n的括号字符串,含有n个左括号,n个右括号

使得p是所有 让 s[p[i]] 为合法括号序列中的字典序最小的

同时q是所有 让 s[q[i]] 为合法括号序列中的字典序最大的

范围

n<=2e5

2s

1024mb

题解

我的思路

显然开始和最后的位置分别是 左右括号

对于p, 当左右括号都可以选时,一定会选没有被选坐标最小的

当前缀完成匹配时, 只能选左括号, 这时选左括号坐标最小的

于是, 如果当前坐标以前的没有选完,那么说明当前位置是左括号,且没有被选的是右括号

对于q,类似的, 先选最大的, 左括号也是先选最大的

这样分别确定的右括号不少于 左括号个数

但是对于剩余没有填的位置怎么做,我没有思路了,因为它不只需要保证一个排列合法,它需要保证p和q都合法

官方

前面还是一样的, 但这里强调了是 奇数处出现, 因为 要前面匹配完,说明前面用了偶数个

而且不像我那样 需要 前缀未填完, 而只是 奇小于下一个偶, P[2i-1] < P[2i]

但说是 如果还是有多个候选的,那么就是没有方案

如果只有一个候选S,就看是否同时满足p和q

简单的来讲如果S或它的逆序是一个合法的括号序列, (一般情况也可以类似证明, 因为一般的S 可以表示成合法和 和 逆序合法的连接

令 L1 < L2 < L3 … < LN 分别是左括号的下标

R1 < R2 < R3 … < RN 分别是右括号的下标

既然S是合法的,那么有 Li < Ri

因此字典序最大的排列是$L_N,R_N,L_{N-1},R_{N-1},…,L_1,R_1$

因此 S是唯一的

并且确定的过程和上述描述的也是一致的

如果S的逆序是合法的

那么有

令 L1 < L2 < L3 … < LN 分别是左括号的下标

R1 < R2 < R3 … < RN 分别是右括号的下标

既然S的逆序列是合法的,那么有 Li > Ri

所以字典序最小的是$L_1,R_1,L_2,R_2,…,L_N,R_N$

并且确定的过程和上述描述的也是一致的

再对于一般序列来讲

又回到 括号序列的常用技巧,左括号+1,右括号-1

那么其实就是 一些在正平面的一些曲线和负平面的一些曲线,

显然由和0点隔开的 顺序上也相互独立(见官方youtube上画的图

这样 对于每一段来说,是正平面则由最大序列唯一确定, 是负平面则由最小序列

所以 整体都是唯一的

这样就是官方提接说的一般序列的 拼接类似

综上得证

代码

https://atcoder.jp/contests/arc141/submissions/32155305

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>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;} // read
int p[400010];
int q[400010];
char s[400010];
char sets(int i,char ch){
  return (s[i] && s[i] != ch) ? 0 : (s[i] = ch);
}
bool work(){
  int n = read() * 2; // 2e5 * 2
  rep(i,0,n) p[i] = read() - 1;
  rep(i,0,n) q[i] = read() - 1;
  for(auto [arr, cmp]:vector<pair<int *,int> > {{p, 1},{q,-1}}){
    rep(i,0,n-1) {
      if((arr[i] - arr[i+1]) * cmp <= 0) continue; // 出现反序列
      if(!sets(arr[i],'(') || !sets(arr[i+1],')')) return false;
    }
  }
  rep(i,0,n) if(!s[i]) return false; // 不唯一
  // check 可能一个合法 另一个不合法
  for(auto [arr,st,d]:vector<tuple<int*,int,int> >{{p,0,1},{q,n-1,-1}}){
    // 双指针
    int i0 = st; // 找所有值
    int i1 = st; // 只找左括号
    int cnt = 0;
    vector<bool> vis(n,false);
    rep(i,0,n){
      int pos ; // 选取的位置
      if(cnt == 0){
        while(vis[i1] || s[i1] != '(') i1+=d;
        pos = i1;
      }else{ // cnt > 0
        while(vis[i0])i0+=d;
        pos = i0;
      }
      if(arr[i] != pos) return false; // 和提供的不一致
      vis[pos] = true;
      cnt += s[pos] == '('?1:-1;
    }
    if(cnt) return false;
  }
  printf("%s\n",s);
  return true;
}
int main(){
  if(!work()) printf("-1\n");
  return 0;
}

D

题目

https://atcoder.jp/contests/arc141/tasks/arc141_d

对于一个集合S, 任意两个元素不成倍数关系,那么认为是一个好集合

给一个n个元素,元素值范围在[1,2m]之间的集合, 元素值不重复, 给值时从小到大

对于每个元素,判断是否存在一个S的子集,包含该元素且是好集合

范围

M<=N<2M

M 3e5

题解

我的想法

既然给值就是从小到大, 那么省去了排序

既然一定要a[i], 那么它的倍数和约数一定不可行,而约数是log级别的个数,

这里虽然问是否能恰好m个, 但如果>=m 合法,删掉多于m的依然合法

所以变成能否有不少于m个

对于即不是ai倍数,也不是ai约数的, 考虑最多能取多少个

于是集合被化分成(ai,ai约数,ai倍数) (其它), 那么包含ai的最大的个数是 1+max(其它)

首先 值的倍数从均摊上讲 也是 log级别的, 因为 1/2+1/3+1/4… 在小的时候是 常数倍

但 剩下的如何尽可能多的取, 以及如果只是暴力去尝试的话, 显然 会达到至少 n平方

另一个就是互斥关系, 如果建立互斥关系的2-sat图, 跑tarjan ,能一次计算

注意到互斥关系不会变, 所以2-sat不会变, 但是怎么选一个而不选其它

官方

其实是个卡着边界的问题

考虑所有奇数的2的幂次倍

(1,2,4,8,16...),(3,6,12,24...),(5,10,20...)

注意到的是 ,一共有m组,且每组内部两两是倍数关系, 因此我们选的答案,不会同时出现在一组中, 所以 至多选m个

这个对答案也有帮助, 如果题目给的S, 在上述的2的幂次倍中 有的组不存在,那么显然达不到m

现在问题是跨组会不会有 倍数关系

假设 $x_1 < x_2$ 都是奇数, 选了 $x_1 2^{p_1},x_22^{p_2}$

那么如果成倍数一定是 $p_2 \ge p_1$ 且 $x_2$是$x_1$的倍数

换句话说, 要想合法, 那么一个数的约数对应的2的幂次要比它本身大

考虑 每个奇数的2的幂次的上下界, [Li,Ri]

直接动归转移方程

对于R[value] = min(R[value 的因子]) - 1 且存在于S

对于L[value] = max(L[value的倍数]) + 1 且存在于S

R1,R2,R3,...R,被选的值,L,...,L 将是合法解, [Li <= 被选的幂次 <= Ri]

因为前面的尽可能大,后面尽可能小且 被选值在范围中

综上 因为因子数和均摊倍数个数都是log级别,所以总的均摊代价就是log级别

代码

https://atcoder.jp/contests/arc141/submissions/32169715

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
#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;)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
bool exist[600010];
 
vector<int> ys[600010]; // 所有真奇数约数
 
int L[600010];
int R[600010];
int a[600010];
 
int n,m;
bool w(){
  n = read();
  m = read()*2;
  rep(i,0,n) {
    exist[a[i] = read()] = 1;
  }
  rep(i,1,m/2+1){
    if(i%2 == 0)continue;
    rep(t,3,m/2+1){
      if(t%2 == 0)continue;
      if(i*t > m)break;
      ys[i*t].push_back(i);
    }
  }
  // 先检查是否所有组都有
  rep(i,1,m+1){
    if(i%2==0)continue;
    bool found = false;
    int itr = i;
    while(itr <= m){
      if(exist[itr]){
        found = true;
        break;
      }
      itr*=2;
    }
    if(!found)return false;
  }
  // 计算R
  rep(i,1,m){
    if(i%2 == 0) continue;
    int pwr = 20;
    // 计算它因数对它的限制
    for(auto item:ys[i]){
      pwr = min(pwr,R[item]-1);
    }
    // 找一个范围内且存在的
    bool found = false;
    while(pwr >= 0){
      if(i * (1<<pwr) <= m){ // 小心 out bound
        if(exist[i * (1<<pwr)]){
          R[i] = pwr;
          found = true;
          break;
        }
      }
      pwr--;
    }
    // printf("L %lld => %d\n",i,pwr);
    if(!found) return false; // 不存在合法范围的值
  }
  // 计算L
  per(i,1,m){
    if(i%2 == 0) continue;
    int pwr = 0;
    // 计算它倍数对它的限制
    rep(k,3,m+1){
      if(k%2==0)continue;
      if(i*k > m)break;
      pwr = max(pwr,L[i*k]+1);
    }
    // 找一个范围内且存在的
    bool found = false;
    while( i*(1<<pwr) <= m){
      if(exist[i * (1<<pwr)]){
        L[i] = pwr;
        found = true;
        break;
      }
      pwr++;
    }
    if(!found) return false; // 不存在合法范围的值
    if(L[i] > R[i]) return false;
  }
  // 计算答案
  rep(i,0,n){
    int v = a[i];
    int pwr = 0;
    while(v%2 == 0){
      pwr++;
      v/=2;
    }
    printf("%s\n", L[v] <= pwr && pwr <= R[v]?"Yes":"No");
  }
  return true;
}
int main(){
  if(!w()) rep(i,0,n) printf("No\n");
  return 0;
}

E

题目

https://atcoder.jp/contests/arc141/tasks/arc141_e

n方个点, (1..n,1..n)

q 个询问

每个询问 a,b,c,d

会把 点((a+k)%n,(b+k)%n) 和 点((c+k)%n,(d+k)%n) 相连, 其中k取 0 到 n-1

询问之间是影响的, 是在上一次结果上继续连

每次回答一个询问操作后,剩下的联通块数

范围

n 2e5

q 2e5

题解

我的思路

首先, 其实让a,b,c,d 变成 a1=(a+n-a)%n,b1=(b+n-a)%n,c1=(c+n-a)%n,d1=(d+n-a)%n, 因为k取[0..n-1], 所以等价

变成 k,(b1+k)%n,(c1+k)%n,(d1+k)%n

画图, 会发现 (k,(b1+k)%n) 在一条45度角的一条斜线上,((c1+k)%n,(d1+k)%n) 也在一条45度角的一条斜线上

  1. 如果共线, 那么 如果原来不是一个联通块,则 减少了 n-1个联通块, 如果原来是多个联通, 那么对结果影响 = -(个数-1)

有了这个思路, 我们问题通过图像可以变一变

沿着+1,+1的45度, 形成n组点,每组点有个属性内部是否相连

考虑两组之间的关系,

1次连接, 那么这两组形成的是n个连通块, 且内部联通关系,一旦有一个联通则连通

而这个值其实 = gcd(偏移量间隔)

所以未连接和 连接一次的偏移量间隔为 n

而对两个组的影响是相同的

所以变成

哪些组属于一个并查集合, 它们自身内部的偏移量等价(一个值) 它们与根的偏移量等价

似乎就可以做了

但感觉在合并并查集时更新需要注意

然后 真的 我就AC了???? atcoder真的是数学场吗

代码

https://atcoder.jp/contests/arc141/submissions/32185372

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
#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
int gcd(int a,int b){
  while(b!=0){
    a=a%b;
    swap(a,b);
  }
  return a;
}

int fa[200010];
int a[4];
int inner[200010]; // 组内部最小间隔, 一定是n的因子
int tofa[200010]; // 跨组偏移距离
ll n;

int getfa(int i){
  if(i == fa[i]) return i;
  int newfa = getfa(fa[i]);
  tofa[i] = ((tofa[i] + tofa[fa[i]])%n)%inner[newfa];
  return fa[i] = newfa;
}

// new root u
// u and v is old root
void link(int u,int v,int off){
  fa[v] = u;
  inner[u] = gcd(inner[u],inner[v]);
  tofa[v] = off % inner[u];
}

int main(){
  n = read();
  ll q = read();
  ll ans = n*n;
  iota(fa,fa+n,0);
  fill(inner,inner+n,n);
  rep(i,0,q){
    rep(j,0,4) a[j] = read();
    per(j,0,4) (a[j] += n-a[0])%=n;
    int g1 = a[1] - a[0];
    int g2 = (a[3]-a[2]+n)%n;
    int off = a[2] - a[0];
    int f1 = getfa(g1);
    int f2 = getfa(g2);
    // 同组更新内部间隔
    if(f1 == f2){
      // ans -= inner[f1] - inner[f1];
      // printf("SAME %d[%d] => ",f1,inner[f1]);
      ans -= inner[f1];
      inner[f1] = gcd(inner[f1], 2*n + tofa[g1] - tofa[g2] + off); // 不是off
      ans -= -inner[f1];
      // printf("%d \n",inner[f1]);
    }else{ // 不同组 合并组
      // printf("DIFF %d[%d] + %d[%d] => ",f1,inner[f1],f2,inner[f2]);
      // g1->f1, g2->f2
      // f2->f1?
      // f1 - f2 = (f1 - g1) - (f2 - g2) + (g2 - g1)
      // ans -= inner[f1] + inner[f2] - inner[f1];
      ans -= inner[f1] + inner[f2];
      link(f1,f2, (2*n + tofa[g1] - tofa[g2] + off)%n);
      ans -=  - inner[f1];
      // printf("%d \n",inner[f1]);
    }
    printf("%lld\n",ans);
  }

  return 0;
}

总结

C

这个基本的能想到, 但是没有尝试更多数据, 去考虑它的唯一性, 还在想怎么填中间的

这方面要培养,有点像反过来想题目, 如果题目本身设计上有唯一性只是需要证明, 这个思路方向, 因为毕竟是确定有答案的题目而不是开放性问题

另外就是括号序列还是不熟悉, 如果熟悉常见+1,-1套路,画图去思考也会简单不少

虽然从逻辑上 我的 当前前面未填完,则当前(,未填都是), 数学上好像 更多信息, 但这里反而成了干扰

据说能用DP做?

D

这数学性好强啊, 知识点是属于集合论的和数论的,甚至有点抽屉原理,

能想到奇数与它的2的幂次倍数的分组是这个题的核心一点

这一想出后面就自然很多了

E

我这赛后没有看题解,竟然AC了 ??????

参考

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

官方youtube

0%