YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

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

D

https://codeforces.com/contest/1641/problem/D

n(1e5)个数组

每个数组长度为m(<=5), 包含值(<1e9), 每个数组有总代价w(<=1e9)

找出两个数组，让它们的值没有重复，且代价和最小，求最小代价

题解

  1. 随机映射到0-15,注意同一个数一定映射到相同数，不同数可能映射到相同数, 多次运行提高概率期望到2, orz(见YB Lin 的链接)

  2. 集合数学性质

一个集合属于A,又属于B，

如果该集合个数为奇数，则+1

如果该集合个数为偶数(包含空集合)，则-1

那么，如果A,B有公共元素，则结果为0，否则为1

然后维护一个Trie树，上面是所有子集

把原数组按照w排序

利用Trie树找到首个合法的组合i,j

因为要答案最小，所以 i < i’, 则有 j’< j

代码

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

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

// trie 树， 用index取代指针
// 集合按照从小到大 展开存成树节点
struct node {  // 只会新增不会移除， cnt为0 和 移除等价
  unordered_map<int, int> next;  // [值] => 树节点index
  int cnt;
};

vector<node> g;

int new_node() {
  g.push_back(node{{}, 0});
  return g.size() - 1;
}

// 新把数组变化 放入trie树
void add(const vector<int>& x,
         int c /* 1(加入) or -1(移除) */,
         int v = 0 /* trie 树 节点 index*/,
         int i = 0 /* 遍历数组下标 */) {
  if (i == x.size()) {
    g[v].cnt += c;  // 在trie树 的所有集合表示的位置都+1
    return;
  }
  // 不存在创建新节点
  if (!g[v].next.count(x[i]))
    g[v].next[x[i]] = new_node();
  add(x, c, v, i + 1);                // 不选择当前的情况
  add(x, c, g[v].next[x[i]], i + 1);  // 选择当前的情况
}

// 初始全是0
// 如果和 已经加入的 某个数组重合，那么与这个数组贡献的cnt 的结果为 0
// 如果和 已经加入的 某个数组不重合，那么与这个数组贡献的cnt 的结果为 1
// 而trie上的贡献是满足**累加**性质，所以与 trie树直接计算cnt
// 如果为0，则和所有数组现有的都冲突，否则存在一个数组和它没有重合
int get_cnt(const vector<int>& x, int v = 0, int i = 0) {
  if (i == x.size()) {
    return g[v].cnt;
  }
  int res = get_cnt(x, v, i + 1);  // 第i位 不选
  if (g[v].next.count(x[i]))       // 第i位 存在（集合存在） 并选择
    res -= get_cnt(x, g[v].next[x[i]] /* trie 树的下一个节点 */,
                   i + 1);  // 奇偶加减交替
  return res;
}

int main() {
  int n, k;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  vector<pair<int, vector<int>>> a = vector(n, make_pair(0, vector<int>(k, 0)));
  rep(i, 0, n) {
    rep(j, 0, k) {
      cin >> a[i].second[j];  // 读入每个数组
    }
    cin >> a[i].first;  // 数组权重
  }
  rep(i, 0, n) {  // 数组内按照值排序
    sort(all(a[i].second));
  }
  sort(all(a));  // 按权重排序
  new_node();    // trie 根节点 空集合
  int res = -1;
  int i = 0;
  // 和 trie 树中 任何一个重复 都会 让 get_cnt > 0
  while (i < n && !get_cnt(a[i].second)) {
    // 首个一定加入, 如果和现有所有数组都冲突，那么加入trie树
    // 如果存在一个不是和所有都冲突的 , 会触发 get_cnt 不为0
    add(a[i].second, 1);
    i += 1;
  }
  if (i >= n) {
    cout << -1 << "\n";
    return 0;
  }
  // i 是首个 与 [0...i-1]中某个不会冲突的
  int j = i;
  // 从i倒向查找
  while (get_cnt(a[i].second)) {  // 直到所有都冲突，找到一个最小的j
    j -= 1;
    add(a[j].second, -1);  // 每次从trie树中移除一个
  }
  // j < i 互相不冲突, 最小的i对应的最小的j
  res = a[i].first + a[j].first;
  // j' < j < i < i'
  for (i += 1; i < n && j > 0; ++i) {
    while (get_cnt(a[i].second)) {  // 循环直到 和 前面都冲突
      j -= 1;                       // 找一个 最小的j 让 i和j不冲突
      add(a[j].second, -1);         // 移除
    }
    // 不一定是有效值（可能i,j是冲突的），但是因为代价排序关系，保证不会影响最小值
    res = min(res, a[i].first + a[j].first);
  }
  cout << res << "\n";
  return 0;
}

总结

  1. 先按照价值排序，
  2. 再从小到大找到首个和前面某个不冲突的
  3. 找到前面最小的与当前不冲突的，确定一个合法j < i
  4. i增加，每次找更小的j与新的i不冲突的，或者找不到跳过这个i, 每次更新最小值

关键的核心就是,trie树保存的是两两冲突的数组的所有集合，而与trie树 做子集重合get_cnt运算，如果与已加入的所有都有重合则总结果为0，否则大于0, 相当于trie能帮助完成批量判断

ref

官方题解

YB Lin 概率映射 sosdp 乱搞

neweryyy

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

题目

https://projecteuler.net/problem=516

题意

求 n < 10^12, phi(n)的值仅包含质因数2,3,5的所有n的和，mod2^32

题解

欧拉函数

$\phi(n) = n(1-\frac{1}{p_0})(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots$

其中$p_i$均为$n$的质数因数

性质:

$\phi(x)\phi(y)=\phi(xy), gcd(x,y)==1$

$\phi(prime)\phi(x)=(prime-1)\phi(x), gcd(x,prime)==1$

题目转换

$n = 2^{q_0}3^{q_1}5^{q_2} p_0p_1p_2\cdots$

其中$p_i + 1$ 是只包含$2,3,5$ 质因子的数

广搜2,3,5

$x => 2x,3x,5x$

广搜小于$10^{12}$的所有只包含质因数$2,3,5$的数

质数判别

小于$2^{64}$里的质因数可以 Miller-Robin算法 常数级别 判别

二分

$n = 2^{q_0}3^{q_1}5^{q_2} p_0p_1p_2\cdots$

后面又可以拆分成$2^{q_0}3^{q_1}5^{q_2}$ 和 $p_0p_1p_2\cdots$

右边每个质数最多一次方，直接生成所有的积，左边还是上面求的

要两部分数组内容乘积小于n, 可以左侧枚举二分右侧，右侧枚举二分左侧都一样的, 通过前缀和辅助得到和

Ref

Euler’s totient function

發表於 更新於 分類於 ， Disqus： 文章字數： 4k 所需閱讀時間 ≈ 13 分鐘
B, DP,分治,前缀和,数学

题目

https://atcoder.jp/contests/agc056/tasks/agc056_b

一个长度为n的排列

对于q个查询构成的大小为q向量有多少种

其中每次查询排列[l..r] 中最大值的下标

n <= 300

查询不重复, 合法(l < r)

题解

考虑把数字从大到小放入排列的位置.

假设把N放在位置pos,那么有三类区间

  1. 包含pos的
  2. 完全在pos左侧
  3. 完全在pos右侧

那么显然对于所有查询区间包含pos的,返回都是pos

而对剩余的,如果把左侧位置的所有值保持相对顺序,右侧位置的所有值保持相对顺序, 然后调整值让左侧所有值大于右侧所有值, 对于输出的q维向量没有变化.(因为相对顺序不变,左侧和右侧内部,原来哪个位置大还是哪个大,且都在pos单侧互不影响), 因此不妨我们选定pos后如此调整

先不考虑重复

那么设计状态dp[i][j][pos] = 在[i..j]中, pos为最大值, 且属于[i..j]中某个完整区间的 方案数

那么注意到上面,当我们选定了pos, 就是把区间划分成[i..pos-1]pos[pos+1..j]

原题的答案变为 sum(dp[0][n-1][pos = 0..n-1])

其中注意到,我们在对于无效的pos结果为0, 例如 pos不属于[i..j]中任何一个完整区间, 其对应的情景是最大值不属于任何一个区间,那么 这个位置删掉都行 更不用考虑值了

那么上面的转移方程有

dp[0][n-1][pos] = sum(dp[0][pos-1][0..pos-1]) * sum(dp[pos+1][n-1][pos+1..n-1])

也就是 左侧 和 右侧分别独立计算.

而这个计算规则实际上和原问题是同一个问题. 因此可以看成是分治

dp[i][j][p] = sum(dp[i][p-1][i..p-1]) * sum(dp[p+1][j][p+1..j])

其中 sum为零时,记为1,属于空方案

引理: 分治中数值的大小无影响,只有输出有影响

因为隔离性,假设右侧不动,来考虑左侧的排列数值变化,但产出向量不变,对结果有什么影响.

假设左侧存在[1..2][3..4] 非重叠 或者 [1..2][2..3]重叠区间或其它任何状态, 那么可能不同的值,有相同的向量产生

一旦左侧的产出向量确定了, 注意到转移方程的剩余部分,一个是pos,那一定比左侧都大,而右侧根据它们的隔离性,比左侧都小,所以转移方程的任何剩余向量也不会受到影响.

所以, 转移方程只与单侧的向量产生相关, 与具体值无关

上面的东西,看上去搞个前缀和,再for(len)for(左端点i)for(最大值下标pos) 就搞完了

重复

基本的东西有了,下面是精确计算值

正如上面的例子[1..2][3..4]

如果是1234 输出是(2,4)

如果是3412 输出也是(2,4)

而对于dp来说,一个是按照 第4位 开始划分,一个是按照第2位开始划分的. 有重复的问题

同样,对于[1..2][2..3] 来说

如果312 和 213 也会重复.分别是第1位和第3位最大进行讨论的, 而它们的输出都是(1,3)

注意, 这里 132 和231 不会重复统计

一个办法是容斥(本文不会提到

另一个就是发现其数学性质

当在[i..j] 中 pos是最大值的下标 且属于其中某个完整区间时

如果[i..pos-1] 中的最大值 在idx, 且idx和pos 在[i..j] 中不属于任何同一个完整区间, 那么 让idx变为 [i..j]中的最大值, pos改为次大值,总输出向量不变

证明

因为前面假设过, value[pos] > 所有左侧值 > 所有右侧值,所以pos最大,idx次大

交换以后,value[idx] > value[pos] > 其它左侧值 > 所有右侧值

按情况讨论区间

  1. pos右侧的所有区间,因为包含的内容全在右侧值中,所以都不受影响
  2. 包含pos的所有区间, 原本输出pos, 因为不包括idx,现在pos次大,所以依然输出pos
  3. pos左侧所有区间, 只有idx变大了,但对于所有左侧区间来说,相对顺序都没有变化, 所以左侧的也都没有变

所以总的向量没有变

以上证明了,如果[i..pos-1]中的最大值和pos在[i..j]中不属于同一个完整区间,那么会被重复统计. 所以

dp[i][j][p] = sum(dp[i][p-1][i..p-1]) * sum(dp[p+1][j][p+1..j])

要改为

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

f(p) = 最小的 在[i..j]中和p属于同一个完整区间的

不漏从dp过程中已经保证了,上面我们只是提到了去重,而并不能说明所有重复都没有了.下面证明所有重复都没有了

即是证明 任何输出向量,只会被至多统计一次

不妨设某个 输出被统计了两次.

根据统计过程, 如果它在首次被不同的最大值下标统计了,那么

  1. 这两个下标属于同一个区间,和下标是最大值矛盾,一个区间只有一个下标是最大值
  2. 这两个下标不属于任何同一个区间,那么根据上面的变化, 只会统计在左侧为更大值

代码

基于 heno239 的代码 https://atcoder.jp/contests/agc056/submissions/27693073

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
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#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--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

struct modint {
  int n;
  modint() : n(0) { ; }
  modint(ll m) {
    if (m < 0 || mod <= m) {
      m %= mod;
      if (m < 0)
        m += mod;
    }
    n = m;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) {
  return a.n == b.n;
}
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod)
    a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0)
    a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((ll)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) {
  return a += b;
}
modint operator-(modint a, modint b) {
  return a -= b;
}
modint operator*(modint a, modint b) {
  return a *= b;
}
modint operator^(modint a, ll n) {
  if (n == 0)
    return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2)
    res = res * a;
  return res;
}

ll inv(ll a, ll p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) {
  return a * modint(inv(b, mod));
}
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}

vector<int> vle[305];       // [r pos] = {l pos...} 区间右端点到左端点
modint dp[305][305][305];   // [l][r][x] = [l..r-1] 最大的是x的方案数, 其中不论l取值多少,x与[l,r-1]至少属于[l,r-1]中的一个完整区间
modint rdp[305][305][305];  // rdp[l][r][i] =  dp[l][r][0..i-1] 的前缀和

// 默认 全false, 右端点在[l+1..r]之间，长度 <= r-l 的区间是否存在
bool exi[305][305];

int cl[305];  // 计算过程中[l..r-1] 中, cl[i] = 与i同属于完整区间属于[l..r-1]的 最左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l - 1);
  }
  // 同样右端点 左端点从小到大, 方便后面二分找满足条件的左端点
  rep(i, 0, n + 1) sort(all(vle[i]));
  rep(len, 1, n + 1) {    // 枚举 长度[1..n], 因为每次划分是 左右两个更短的范围
    rep(r, len, n + 1) {  // 右端点从小到大 [len..n]
      int l = r - len;    // 左侧端点 = 右端点-长度
      int nw = r; // 遍历过程中,当前属于[l..r-1]的完整区间的最小左端点
      per(j, l + 1, r + 1) {  // j（右端点）从大到小 [l+1,r] 范围内的每个右端点
        // 第一个大于或等于某个元素的位置, 二分查找
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) {  // [nw,j] 区间小于等于 len
          nw = min(nw, vle[j][t]);
        }
        // 右端点 [j..r] 中的区间的最小左端点, 不存在的情况 r > j - 1
        cl[j - 1] = nw;
      }
      if (nw == r) {  // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;  // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r) {    // [l..r-1]
        if (x < cl[x])  // 不存在 [l,r] 之间的小区间 包含 坐标x
          continue;
        // [l..x-1]x[x+1..r-1]
        // 存在右端在 [l+1..x], 长度小于 x-l 的区间,
        // sl = sum{dp[l][x][cl[x]..x-1]}
        // 注意这里, 当[l..x-1]不存在时是1, 而[l..x-1]存在时,因为防止重复统计可能[cl[x]..x-1]是0
        modint sl = exi[l][x] ? rdp[l][x][x] - rdp[l][x][cl[x]] : (modint)1;
        // 存在右端在 [x+2..r], 长度小于 r-x-l 的区间,
        // sr = sum{dp[x+1][r][x+1..r-1]}
        // 而对于右侧 似乎可以直接判断前缀和是否非零,但实际上因为是取mod运算,可能为mod的倍数,所以还是需要一个exi的辅助数组
        modint sr =
            exi[x + 1][r] ? rdp[x + 1][r][r] - rdp[x + 1][r][x + 1] : (modint)1;
        dp[l][r][x] = sl * sr;  // [l,r-1]中 最大的下标为x, 方案数
        // 下面由此输出
        // printf("%d %lld %lld => %d %d\n",l,r,x,(int)sl,(int)sr);
      }
      rep(j, l, r) {
        // [l..r-1]
        // rdp[l][r][j] = dp[l][r][0..j-1] 前缀和
        rdp[l][r][j + 1] = rdp[l][r][j] + dp[l][r][j];
      }
    }
  }
  printf("%d", (int)rdp[0][n][n]); // [0,n-1] 最大下标[0..n-1]的方案数
  return 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
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
//
// [l          x-1]x[x+1          ]r
// x 是最大值
// dp[l][r][x] = 左边方案数 x 右边方案数, 其中右边的长度覆盖了x
//             = sum{dp[l][x][cl[x]..x-1]} * sum{dp[x+1][r][x+1..r-1]}
//             = x 是最大值，对左侧的影响当前 最近的是 cl[x]
//
//
// 012345678
//  xx
//   xxx
//     xxx
//      xx
//        xx
//
/*
9 5
2 3
3 5
5 7
6 7
8 9
*/
/*
l r x ==sl*sr
[l r) 左闭右开,所以 实际区间是[l..r-1]

len = 2
1 3 1 => 1 1
1 3 2 => 1 1

5 7 5 => 1 1
5 7 6 => 1 1

7 9 7 => 1 1
7 9 8 => 1 1

len = 3
0 3 1 => 1 1
0 3 2 => 1 1 (0不属于完整区间,所以没有 0 3 0

1 4 1 => 1 1
1 4 2 => 1 1 (虽然3和属于[2..4]的完整区间,但这里的区间是[1..3],3 不属于这之间的任何完整区间, 所以也没有 1,3,3

2 5 2 => 1 1
2 5 3 => 1 1
2 5 4 => 1 1

4 7 4 => 1 2 (首次包含关系 区间,一个[4..6]一个[5..6],右侧 = dp[5][7][5] + dp[5][7][6] = 1+1 = 2, 也就是[4..6] 最大值在4时,不影响右侧不包含它的区间,右侧有两种值
4 7 5 => 1 1
4 7 6 => 1 1

5 8 5 => 1 1
5 8 6 => 1 1

6 9 7 => 1 1
6 9 8 => 1 1

len = 4
0 4 1 => 1 1
0 4 2 => 1 1

1 5 1 => 1 3 (同 上面 4 7 4
1 5 2 => 1 1 (这个和下面两个都是 1 1, 但实际上有些不同, 下面两个的左边的1, 如果按照上面右侧的统计法,应该是 2 而不是1, 注意到上面算sl和sr是有区别的,一个是[cl[x]..x-1], 一个是[x+1..r], 如果一致应该是[l..x-1]而不是[cl[x]..x-1], 说面 左侧最大值, 一定要和x属于同一组,如果不同组, 让左侧更大,其它平移补位, 总输出不变. 所以下面两个都是1.
1 5 3 => 1 1
1 5 4 => 1 1 

2 6 2 => 1 1
2 6 3 => 1 1
2 6 4 => 1 1

3 7 4 => 1 2
3 7 5 => 1 1
3 7 6 => 1 1

4 8 4 => 1 2
4 8 5 => 1 1
4 8 6 => 1 1

5 9 5 => 1 2
5 9 6 => 1 2
5 9 7 => 0 1
5 9 8 => 0 1

len = 5
0 5 1 => 1 3
0 5 2 => 1 1
0 5 3 => 1 1
0 5 4 => 1 1
1 6 1 => 1 3
1 6 2 => 1 1
1 6 3 => 1 1
1 6 4 => 1 1
2 7 2 => 1 4
2 7 3 => 1 4
2 7 4 => 1 2
2 7 5 => 1 1
2 7 6 => 1 1
3 8 4 => 1 2
3 8 5 => 1 1
3 8 6 => 1 1
4 9 4 => 1 4
4 9 5 => 1 2
4 9 6 => 1 2
4 9 7 => 0 1
4 9 8 => 0 1

len = 6
0 6 1 => 1 3
0 6 2 => 1 1
0 6 3 => 1 1
0 6 4 => 1 1
1 7 1 => 1 12
1 7 2 => 1 4
1 7 3 => 1 4
1 7 4 => 1 2
1 7 5 => 1 1
1 7 6 => 1 1
2 8 2 => 1 4
2 8 3 => 1 4
2 8 4 => 1 2
2 8 5 => 1 1
2 8 6 => 1 1
3 9 4 => 1 4
3 9 5 => 1 2
3 9 6 => 1 2
3 9 7 => 0 1
3 9 8 => 0 1

len = 7
0 7 1 => 1 12
0 7 2 => 1 4
0 7 3 => 1 4
0 7 4 => 1 2
0 7 5 => 1 1
0 7 6 => 1 1
1 8 1 => 1 12
1 8 2 => 1 4
1 8 3 => 1 4
1 8 4 => 1 2
1 8 5 => 1 1
1 8 6 => 1 1
2 9 2 => 1 8
2 9 3 => 1 8
2 9 4 => 1 4
2 9 5 => 1 2
2 9 6 => 1 2
2 9 7 => 0 1
2 9 8 => 0 1

len = 8
0 8 1 => 1 12
0 8 2 => 1 4
0 8 3 => 1 4
0 8 4 => 1 2
0 8 5 => 1 1
0 8 6 => 1 1
1 9 1 => 1 24
1 9 2 => 1 8
1 9 3 => 1 8
1 9 4 => 1 4
1 9 5 => 1 2
1 9 6 => 1 2
1 9 7 => 0 1
1 9 8 => 0 1

len = 9
0 9 1 => 1 24
0 9 2 => 1 8
0 9 3 => 1 8
0 9 4 => 1 4
0 9 5 => 1 2
0 9 6 => 1 2
0 9 7 => 0 1
0 9 8 => 0 1
*/

改版

对于上面代码改了主要几个部分

把[l,r]改为左右都是闭区间了,不用考虑加减1的描述范围

把所有下标按照题目变成1-index而不是上面的0-index,因为这样也方便前缀和不用单独处理下标0

去掉了 大佬的modint, 假设没有modint的实现的情况下,直接加mod运算

https://atcoder.jp/contests/agc056/submissions/27743665

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#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--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

vector<int> vle[305];   // [r pos] = {l pos...} 区间右端点到左端点
ll dp[305][305][305];   // [l][r][x] = [l..r] 最大的是x的方案数, 其中不论l取值多少,x与[l,r]至少属于[l,r]中的一个完整区间
ll rdp[305][305][305];  // dp 前缀和
bool exi[305][305];     // 默认 全false, 在[l..r]之间 是否存在完整区间
int cl[305];            // 右端点 in [i..最右侧] = 区间的最小左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l);
  }
  rep(i, 1, n+1) sort(all(vle[i]));
  rep(len, 2, n+1) {              // 枚举 长度
    rep(r, len, n+1) {            // 右端点 从小到大
      int l = r - len + 1;        // 左侧端点 = 右端点 - 长度 +1
      int nw = r + 1;             // 左端点, 在[l..r] 中
      per(j, l, r + 1) {          // j（右端点）从大到小 [l,r] 范围内的每个右端点
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) nw = min(nw, vle[j][t]);
        cl[j] = nw;
      }
      if (nw == r+1) {            // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;           // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r+1) {            // [l..x-1]x[x+1..r]
        if (x < cl[x]) continue;  // 不存在 [l,r] 之间的小区间 包含 坐标x
        ll sl = exi[l][x-1] ? rdp[l][x-1][x-1] - rdp[l][x-1][cl[x]-1] : 1;
        ll sr = exi[x+1][r] ? rdp[x+1][r][r] - rdp[x + 1][r][x] : 1;
        dp[l][r][x] = ((sl%mod) * (sr%mod))%mod;    // [l,r-1]中 最大的下标为x, 方案数
      }
      rep(j, l, r + 1) rdp[l][r][j] = (rdp[l][r][j-1] + dp[l][r][j])%mod;
    }
  }
  printf("%lld", (rdp[1][n][n]+mod)%mod); 
  return 0;
}

参考

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

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
E(线段树)

E

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

给你字符串只包含abc

给你q次操作,每次操作修改一个位置上的字符为’a’/‘b’/‘c’中的一种

每次操作后,问对于当前字符串,至少修改多少个字符,使字符串不包含abc子序列

子序列定义: 字符串任意位置删除任意个得到的剩余字符串

范围

字符串长度 1e5

询问次数 1e5

题解

一个可以过的方案是

seg(l,r,state) = 最少次数

其中l,r表示一个区间,通过线段树维护

state 是 5bit的状态分别对应a,b,c,ab,bc, 是否在区间中出现过

那么 线段树节点关系 是

f(根, mergestate(statel,stater)) = min(f(左节点,statel)+f(右节点,stater))

其中 产生abc的不更新 根节点状态

问题是 实现起来感觉有点卡常数 $q \cdot log(N) 32 \cdot 32 $ 的运算量 ,2464ms/3000ms 过的, 看到有些其它状态设计,状态如果更少会更快

tourist 300ms 过的

另一个想法是,实际上变成 [不存在a][不存在b][不存在c]的字符串就好了

那 操作代价(其实就是分别移除a,b,c) = count[a][0..i]+count[b][i+1..j]+count[c][j+1..end]

所以对count计算总是先a后b再c

变成了维护 f(l,r,startch, endch) = 最少代价

也就是 在区间[l,r]上 起始位置是计算startch,结束位置是计算endch

这样状态数最多3x3,根据a,b,c的顺序, 真实有效的只有6 个, 计算代价 常数就小很多

代码(前一种)

https://codeforces.com/contest/1609/submission/137409899

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

#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
const int INF = 0x3f3f3f3f;  // 无限大操作
int n, q;
char s[100010];

int t[400010][40];

// bits
// 0 a
// 1 b
// 2 c
// 3 ab
// 4 bc
void mergeState(int o) {
  rep(i, 1, (1 << 5)) { t[o][i] = INF; }
  rep(i, 1, (1 << 5)) {  // 左state
    if (t[o << 1][i] == INF)
      continue;
    rep(j, 1, (1 << 5)) {  // 右state
      // abc = 'a' + 'bc' or 'ab' + 'c'
      if (((i & (1 << 0)) && (j & (1 << 4))) ||
          ((i & (1 << 3)) && (j & (1 << 2)))) {
        continue;
      }
      // new bit state
      int k = i | j;
      // ab = 'a'+'b'
      if ((i & (1 << 0)) && (j & (1 << 1))) {
        k |= (1 << 3);
      }
      // bc = 'b' + 'c'
      if ((i & (1 << 1)) && (j & (1 << 2))) {
        k |= (1 << 4);
      }
      t[o][k] = min(t[o][k], t[o << 1][i] + t[o << 1 | 1][j]);
    }
  }
}

void calc(int o, int pos) {
  rep(i, 1, (1 << 5)) {  // 状态
    t[o][i] = (i & (1 << (s[pos] - 'a'))) ? 0 : INF;
  }
  rep(ch, 'a', 'c' + 1) {
    if (ch == s[pos])
      continue;
    // 一次修改
    rep(i, 1, (1 << 5)) {
      if (i & (1 << (ch - 'a'))) {  // 包含该bit
        t[o][i] = min(t[o][i], 1);
      }
    }
  }
}

void update(int o, int l, int r, int pos, char ch) {
  if (l == r) {
    s[pos] = ch;
    calc(o, l);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    update(o << 1, l, m, pos, ch);
  } else {
    update(o << 1 | 1, m + 1, r, pos, ch);
  }
  mergeState(o);
}

void build(int o, int l, int r) {
  if (l == r) {
    calc(o, l);
  } else {
    int m = (l + r) / 2;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    mergeState(o);
  }
}

int main() {
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  build(1, 0, n - 1);
  rep(i, 0, q) {
    int pos;
    char ch;
    scanf("%d %c", &pos, &ch);
    update(1, 0, n - 1, pos - 1, ch);
    int ans = INF;
    rep(i, 1, (1 << 5)) { ans = min(ans, t[1][i]); }
    printf("%d\n", ans);
  }

  return 0;
}

可能包含改成恰好包含快了不少

https://codeforces.com/contest/1609/submission/137444815

1216 ms/3000 ms

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

#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
const int INF = 0x3f3f3f3f;  // 无限大操作
int n, q;
char s[100010];

int t[400010][40];

// bits
// 0 a
// 1 b
// 2 c
// 3 ab
// 4 bc
void mergeState(int o) {
  rep(i, 1, (1 << 5)) { t[o][i] = INF; }
  rep(i, 1, (1 << 5)) {  // 左state
    if (t[o << 1][i] == INF)
      continue;
    rep(j, 1, (1 << 5)) {  // 右state
      // abc = 'a' + 'bc' or 'ab' + 'c'
      if (((i & (1 << 0)) && (j & (1 << 4))) ||
          ((i & (1 << 3)) && (j & (1 << 2)))) {
        continue;
      }
      // new bit state
      int k = i | j;
      // ab = 'a'+'b'
      if ((i & (1 << 0)) && (j & (1 << 1))) {
        k |= (1 << 3);
      }
      // bc = 'b' + 'c'
      if ((i & (1 << 1)) && (j & (1 << 2))) {
        k |= (1 << 4);
      }
      t[o][k] = min(t[o][k], t[o << 1][i] + t[o << 1 | 1][j]);
    }
  }
}

void calc(int o, int pos) {
  rep(i, 1, (1 << 5)) {  // 状态
    t[o][i] = INF;
  }
  rep(ch, 'a', 'c' + 1) {
    if (ch == s[pos]){
      t[o][1<<(ch-'a')] = 0;
    }else{
      t[o][1<<(ch-'a')] = 1;
    }
  }
}

void update(int o, int l, int r, int pos, char ch) {
  if (l == r) {
    s[pos] = ch;
    calc(o, l);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    update(o << 1, l, m, pos, ch);
  } else {
    update(o << 1 | 1, m + 1, r, pos, ch);
  }
  mergeState(o);
}

void build(int o, int l, int r) {
  if (l == r) {
    calc(o, l);
  } else {
    int m = (l + r) / 2;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    mergeState(o);
  }
}

int main() {
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  build(1, 0, n - 1);
  rep(i, 0, q) {
    int pos;
    char ch;
    scanf("%d %c", &pos, &ch);
    update(1, 0, n - 1, pos - 1, ch);
    int ans = INF;
    rep(i, 1, (1 << 5)) { ans = min(ans, t[1][i]); }
    printf("%d\n", ans);
  }

  return 0;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
D(树上DP,子树点乘代价合并,总代价为n方), E(细节题，不会依然不会)

D

https://atcoder.jp/contests/arc130/tasks/arc130_d

给一个树,对节点赋值1~n,两两互不相同,

限制:树上的点要么小于它直接相邻所有点的值,要么大于它直接相邻所有点的值

求方案数.

题解

显然任意选一个为根, 大于和方案和小于的方案对称性,可以只算一个然后乘2

也可以,看成二分图,但是是求满足拓扑序的赋值方案数

注意到大于和小于关系,只需要颠倒就能实现,所以这里我们只讨论 根节点大于所有直接相邻的子节点

我们考虑树上DP

状态设计为 ans[i][j] = 节点i在它和它的所有子树节点中,排序从小到大刚好为j的方案数

对于一个选定的节点,有子树T1,T2,T3,T4,…

设它们的根节点为r1,r2,r3,r4,…

设它们的节点个数为s1,s2,s3,s4,…

那么, 我们考虑维护合并这些子树.

因为 我们这里考虑的是 当前节点要大于所有子树的根节点

所以 合并的时候维护 dp[i] = 已合并的子树中,根节点最大值恰好为i的方案数

以T1和T2为例

分成两种, T1的根更大,和T2的根更大(可以对称处理)

下面讨论 T1根更大

设r1在T1 中的位置为i(1-index)

合并后的序列为(i-1个T1中的点 和 j个T2中的点) r1 ((s1-i)个T1中的点 和 (s2-j)个T2中的点)

注意在两个子树分别的内部,顺序已经固定, 所以只有交叉的顺序不定

方案为 $C((i-1)+j,i-1) \cdot C((s1-i)+(s2-j),s1-i) \cdot ans[r1][i]$

再考虑, T2中的r2的位置,因为T1根更大,所以r2只能在前j个中

$dp[i+j] += C(i+j-1,i-1) \cdot C(s1+s2-i-j,s1-i) \cdot ans[r1][i] \cdot (ans[r2][1]+\cdots +ans[r2][j])$

右边的和可以前缀和O(1),

组合数可以预处理递推O(1),

所以

我们通过 循环一遍T1的节点数,再一遍T2的节点数数,就能得到dp, 每个+= 是O(1)

这里总代价n2,而我错误估计以为n3就没写,哭了

乍看上去,所有节点处理一次,每个节点是子树之间合并,个数的乘积是n3复杂度

实际上,考虑贡献, 一次合并子树的两个子树节点个数乘积大小的代价, 相当于,两个子树之间的节点建立一个配对关系.又因为任何两个节点至多建立两次(讨论根更大)关系,所以总代价为$O(n^2)$

代码

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 998244353
#define rep(i, a, n) for (ll i = a; i < n; i++)
 
int n;  // <=3000
vector<int> p2[3010]; // 树连接关系
// [node i][从小到大第j个] = 方案数
vector<vector<ll> > ans(3010, vector<ll>(1, 0));
 
ll qC[3010][3010]; // 预处理组合数
 
void mergeTable(const vector<ll>& arr0,
                const vector<ll>& arr1,
                vector<ll>& res) {
 
  vector<ll> presum(arr1.size(), arr1[0]);
  rep(i, 1, arr1.size()) { presum[i] = (arr1[i] + presum[i - 1]) % MOD; } // 前缀和
  // arr0 根更大 , root(arr0) > root(arr1)
  // 虽然每次代价是 子树大小之和 x arr0.size()，看起来是三次方，
  // 但实际上,从贡献角度思考 总代价n2
  rep(i, 0, arr0.size()) {
    rep(j, 0, arr1.size()) {
      // arr0: i 个 左侧， arr0.size()-i-1 个 右侧
      // arr1: j+1 个 左侧, arr1.size()-j-1 个右侧
      // res: i+j+1 个左侧, arr0.size()+arr1.size()-i-j-2 个右侧
      // presum = presumof arr1
      // 就是表达式 加上了MOD
      (res[i + j + 1] +=
       (((arr0[i] * qC[i + j + 1][i]) % MOD *
         qC[arr0.size() + arr1.size() - i - j - 2][arr0.size() - i - 1]) %
        MOD * presum[j]) %
       MOD) %= MOD;
    }
  }
}
 
void dfs(int idx, int fa/*父节点*/, int g/*大于小于关系*/) {
  vector<ll> dp = {};  // [最大的子树 根节点 位置] = 方案数
  for (auto item : p2[idx]) {
    if (item == fa)
      continue;
    dfs(item, idx, g ^ 1);
    if (g) {  // 逆向
      // 只用一次也不需要恢复了
      reverse(ans[item].begin(), ans[item].end());
    }
    if (!dp.size()) {
      dp = ans[item];
    } else {
      vector<ll> res(dp.size() + ans[item].size(), 0);
      mergeTable(dp, ans[item], res); // dp 根更大
      mergeTable(ans[item], dp, res); // ans[item] 根更大
      dp = res;
    }
  }
  ans[idx] = vector<ll>(dp.size() + 1, 0);
  if (dp.size() == 0) {
    // 叶子节点
    ans[idx][0] = 1;
  } else {
    ll cnt = 0;
    rep(i, 0, dp.size() + 1) { // 实际上也是前缀和, 当前节点 大于 所有子树根节点
      ans[idx][i] = cnt;
      (cnt += dp[i]) %= MOD;
    }
  }
  if (g) {
    reverse(ans[idx].begin(), ans[idx].end());
  }
}
 
int main() {
  rep(i, 0, 3001) {
    rep(j, 0, i + 1) {
      qC[i][j] = j == 0 ? 1 : (qC[i - 1][j] + qC[i - 1][j - 1]) % MOD;
    }
  }
 
  scanf("%d", &n);
  rep(i, 0, n - 1) {
    int u, v;
    scanf("%d %d", &u, &v);
    p2[u].push_back(v);
    p2[v].push_back(u);
  }
  dfs(1, 0, 0);
  ll res = 0;
  rep(i, 0, n) { (res += ans[1][i]) %= MOD; }
  printf("%lld\n", (2 * res) % MOD); // 大于小于对称性 乘2
  return 0;
}

submissions

官方题解

总结

  1. 可以当作知识点的: 子树全部 节点数相乘的代价,总代价是$O(n^2)$
  2. 复杂度也可以在纸上不要脑补

E

https://atcoder.jp/contests/arc130/tasks/arc130_e

一个数组，每次选最小值中的一个+1，记录下标。

形成了一个下标数组。

现在给你下标数组，求满足下标数组的字典序最小的原数组

题解

题目样例为例

1 1 4 4 2 1

如果 我们能给他们分组

1 | 1 4 | 4 2 1

那么，很容易知道合法的最小结果

1 (操作前大小为1)| 1 4 (操作前大小为2) | 4 2 1 (操作前大小为3)

我们只关心

1 | 1 4 (操作后所有为3)

所以原数组为

3-2 3-0 3-0 3-1 = 1 3 3 2

所以核心问题变成去找这个层之间的分割线

见下面代码中的注释

last(pos) = 这个位置值相同的值的上一个位置

cur[value] = 位置，辅助计算last的数组

cnt 当前层的个数

mx 上一层至少的结束的位置/当前层至少的起始位置

f(pos)= pos是有效的层级分割值，或者-1

代码

jiangly 大佬的代码 加的注释的

https://atcoder.jp/contests/arc130/submissions/27614814

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
 
// 若按照 最后一次出现的顺序排序1~n
// 最优结果的起始最小值一定是1
// 那么所有最优结果 在所有操作后 一定满足 AN-1<=A1<=A2<=A3<=...<=AN
 
int main() {
  int N, K;
  scanf("%d %d", &N, &K);
 
  vector<int> i(K);
  rep(k, 0, K) {
    scanf("%d", &i[k]);
    i[k]--;  // (0-index)
  }
 
  vector<int> last(K);  // 这个位置上同一个数上一次出现的位置 last[pos] = oldpos
  vector<int> cur(N, -1);  // 最后一次出现的位置 cur[value] = pos
  rep(k, 0, K) {
    last[k] = cur[i[k]];
    cur[i[k]] = k;
  }
 
  vector<int> f(K + 1, 0);  // 相当于找有效分割线 = 分割线的层级，从0开始
  int cnt = 0;
  int mx = -1;
  rep(k, 0, K) {
    mx = max(mx, last[k]);  // 更新最近上一组数 的最大下标
    if (last[k] == -1) {    // 当前值首次出现
      cnt++;                // 属于组的个数+1
    }
    // -1 无效值
    // 最大位置 和 当前位置之间个数小于 cnt 则 无效
    // 上一个位置无效则 无效,
    // 因为如果当前是分割线，那么当前到上一个分割线的距离一定恰好是cnt
    f[k + 1] =
        (mx >= k + 1 - cnt || f[k + 1 - cnt] == -1) ? -1 : 1 + f[k + 1 - cnt];
  }
 
  int c = -1;    // 分割最小层数
  int len = -1;  //
  rep(k, mx + 1,
      K + 1) {  // 对于最后一组分割，最后一组里各不相同，且组长度 <= cnt
    // 上一个分割线有效
    // 尚无合法的，或当前层数小于等于 上一个方案
    if (f[k] >= 0 && (c == -1 || c >= f[k])) {
      c = f[k];  // 更新层数
      len = k;   // 最后一组的起点位置
    }
  }
  // 没有有效的最后一组
  if (c == -1) {
    cout << "-1\n";
    return 0;
  }
 
  // 从最后的结果反推初始值,
  // 这里排除了最后一组，所以在最后一组之前，所有值是相等的
  vector<int> A(N, c + 1);  // 最后的结果
  rep(k, 0, len) { A[i[k]]--; }
  rep(i, 0, N) { printf("%d%c", A[i], " \n"[i == N - 1]); }
 
  return 0;
}

总结

跳表什么都会，但是能把细节分析出来，感觉是熟练度而不是什么缺失的知识点。属于这次学会了，下次可能还是不会的题。

0%