Codeforces Round 778

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
E(按类别分治),F(神奇的逐位排序, 基数排序, 后缀数组)

E

https://codeforces.com/contest/1654/problem/E

给一数列,修改尽量少的值让整个数列等差

范围

n <= 1e5

1<= ai <= 1e5

5s

1GB

题解

实际上是二维点(i,ai),找直线经过最多的点

考虑增量 小于 sqrtn,那么选中斜率, 计算每个点沿着斜率与y轴交点 出现的最多次即可, 不要用map,用数组和清理数组实现

考虑增量 大于 sqrtn,以每个点作为起点,那么最多尝试这个点向后n/sqrt(n) 个点, 把这些点计算出现最多次数的斜率, 数量不多,可以用map

代码

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

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

const int N = 100000;
int a[N+10];

int used[32000010];
int n;

int work(){
  int SQRT = 316;
  int ans = 0;
  // 增量 <= SQRT;
  rep(i,0,SQRT+1){
    vector<int> rm;
    rep(j,0,n){
      // 非负便宜量
      int v = a[j] + SQRT*N- j*i; // max = 31600000+100000
      if(!used[v])rm.push_back(v);
      ans = max(ans,++used[v]);
    }
    // clear
    for(auto v:rm){
      used[v] = 0;
    }
  }
  // 增量 大于 SQRT
  rep(j,0,n){ // 下标
    map<int,int> kcnt;
    rep(i,j+1,n){ // 增量
      if(a[j] + (i-j) * SQRT > N) break;
      if( (a[i] - a[j]) % (i-j) == 0){
        kcnt[(a[i] - a[j]) / (i-j)]++;
      }
    }
    for(auto [k,cnt]:kcnt){
      // printf("a[%lld] = %d : k=%d cnt = %d\n",j,a[j],k,cnt+1);
      ans = max(ans, cnt+1);
    }
  }
  return ans;
}

int main(){
  cin>>n;
  rep(i,0,n){
    scanf("%d",a+i);
  }
  int ans = work();
  // 翻转
  rep(i,0,n/2){
    swap(a[i],a[n-1-i]);
  }
  printf("%d\n",n - max(ans,work()));
  return 0;
}

总结

按照一个值,分段处理,每一段都是性能满足的

参考

官方题解

F

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

给一个字符串,长度$2^n$

找一个$j <= 2^n$, 让s[i^j] 字典序最小

范围

n <= 18

3s

512MB

题解

我的尝试

我想到,j的位是0或1实际上意味着 原字符串 的长度2^k 区间是否交换

而判断是否交换,可以局部贪心

问题是,存在字符相等的情况, 不知道怎么记录, 试了一下random 并不能骗分哈哈

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
// n => 2^n length lowercase letters
//
// t[i] = s[i ^ j]
//
// find j => minimal string
// n <= 18
// 2^n <= 262144
// bit1 ,一个一组,相邻交换
// bit2 ,2个一组,相邻交换
// bit3 ,3个一组,相邻交换
// bit4 ,4个一组,相邻交换
 
// ans(0..x)
// => min(ans(0..x/2),ans(x/2+1...x)) 最小的作为前缀
// 3**18 => 387420489
 
int n;
char s[270010];
int ans[270010][20];
 
int cmp(int p,int pwr,int l,int r){
  // 自己所在的那一节
  rep(i,0,(1<<pwr)){
    if(s[(p + i) ^ l] < s[(p + (1<<pwr) + i) ^ r]) return -1;
    if(s[(p + i) ^ l] > s[(p + (1<<pwr) + i) ^ r]) return 1;
  }
  // 对手那一行
  rep(i,0,(1<<pwr)){
    if(s[(p + (1<<pwr) + i) ^ l] < s[(p + i) ^ r]) return -1;
    if(s[(p + (1<<pwr) + i) ^ l] > s[(p + i) ^ r]) return 1;
  }
  return 0;
}
 
ll tryRand(){
  rep(i,1,n+1){
    for(int p = 0;p < (1<<n); p += (1<<i)){
      int lans = ans[p][i-1];
      int rans = ans[p+(1<<(i-1))][i-1];
      int res = cmp(p,i-1,lans,rans);
      // TODO 相等的情况??????
      if(res == 0){
        // printf("fuck?\n");
        if(rand()%2){
          ans[p][i] = lans;
        }else{
          ans[p][i] = (rans | (1<<(i-1)));
        }
      } else if(res == -1){
        ans[p][i] = lans;
      }else{
        ans[p][i] = (rans | (1<<(i-1)));
      }
    }
  }
  return ans[0][n];
}
 
int main(){
  srand(time(NULL));
  cin>>n;
  scanf("%s",s);
  int j = tryRand();
  rep(t,0,180){
    int k = tryRand();
    rep(i,0,(1<<n)){
      if(s[i ^ j] < s[i ^ k])break;
      if(s[i ^ j] == s[i ^ k])continue;
      j = k;
      break;
    }
  }
  rep(i,0,(1<<n)){
    printf("%c", s[i ^ j]);
  }
  printf("\n");
  return 0;
}

正解

实际上可以看成, 把 0~n-1排序

而排序是按照f(s,i)的字典序来比较大小的

这里的问题是 如果两两比较 依然复杂度完成不了, 如何减少比较和处理相等

考虑样例1: acba

1
2
3
4
0: acba
1: caab
2: baac
3: abca

最终期望得到

1
2
3
4
3: abca
0: acba
2: baac
1: caab

然而注意到,

首位的比较 就是 s[i]

第2位的比较 就是 s[i ^ (1<<0)]

第3位的比较 就是 s[i ^ (1<<1)]

第4位的比较 就是 s[i ^ (1<<2)]

而 一旦首位有非相等的大小关系了,之后也就不会改变相对顺序, 不想等时 才考虑后续排序

于是, 按首位排序

1
2
3
4
0: a
1: c
2: b
3: a

变为

1
2
3
4
0: a
3: a
2: b
1: c

记录大小顺序

1
2
3
4
0: a(0)
3: a(0)
2: b(1)
1: c(2)

按照第二位排序

1
2
3
4
0: ?c
1: ?a
2: ?a
3: ?b

得到

1
2
3
4
1: ?a
2: ?a
3: ?b
0: ?c

整体变为(注意首位不相等的要保持顺序)

1
2
3
4
3: ab
0: ac
2: ba
1: ca

记录大小顺序

1
2
3
4
3: ab(0)
0: ac(1)
2: ba(2)
1: ca(3)

这样所有位排序, 更新顺序即可

换句话说就是类似基数排序, 每次是对前缀相等的一系列值的下一位 进行排序

这里注意到看上去字符串长度,有1 << n, 但是实际上,上述排序只需要考虑2的幂次的

因为,[2..3] 的排序 实际是 ([0..1]^2)得到的排序

因为,[4..7] 的排序 实际是 ([0..3]^4)得到的排序

所以 虽然是基数排序,但是 能通过幂次 和记录大小的排序值 优化比较次数

代码

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

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

const int N = 1 << 18;
int n, a[N], val[N], tmp[N], now;
char s[N];

// x 在 y 前面
bool cmp(int x, int y) {
  return (val[x] == val[y]) ?
    val[x ^ now] < val[y ^ now] :
    val[x] < val[y];
}

int main() {
  cin>>n;
  scanf("%s", s);
  rep(i,0,1<<n){
    val[i] = s[i] - 'a'; // [0,26), 实际表示的是以 (1<<pwr) 跨度排序 的 顺序下标,
    a[i] = i; // 相当于 0 ~ 2^n-1 中 让s字典序最小的
  }
  rep(pwr,0,n) {
    now = 1 << pwr; // 比较区间长度
    sort(a, a + (1 << n), cmp);
    int num = 0; // 离散化顺序值
    rep(j,0,1<<n){
      if (j > 0 && cmp(a[j - 1], a[j])) num ++; // f(a[j-1]) < f(a[j]) => num++; 明确j比前一个大
      tmp[a[j]] = num;
    }
    rep(j,0,1<<n){
      val[j] = tmp[j]; // 记录的是 now*2 长度 的 排序 序号
    }
  }

  rep(i,0,1<<n){
    putchar(s[i ^ a[0]]);
  }

  return 0;
}

pwr = 0, now = 1

如果字符 更小,则排在前面

如果字符 相等,则它^1位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前两位 在所有i 中的 顺序

pwr = 1, now = 2

注意到上面val意义已经变化

val[i] 表示的是 i 引起的转换 的前两位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它^2位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前4位 在所有i 中的 顺序

pwr = 2, now = 4

val[i] 表示的是 i 引起的转换 的前4位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它^4位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前8位 在所有i 中的 顺序

pwr = n, now = 2**n

val[i] 表示的是 i 引起的转换 的前now位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它xor now 位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前now*2位 在所有i 中的 顺序

总结

每次排序,再记录顺序, 方便后续比较,而不仅仅排序就完了, 这个记录顺序很重要

参考

官方题解