2021-07-07新高二一期暑假集训2

发表于

前言

这次考试是 dpdp 场，题都挺妙的，我一道都不会。

[Bracketの模拟器日常]生于黑夜

标签

dp + 性质 + 背包

先用背包得出使哨兵血量下降 ww 的最小花费。
考虑对范围进行 dpdp ， 即求出当知道哨兵血量在某个范围内时的最优期望.
先考虑暴力做法。

设 f[i][j]f[i][j] 表示已知当前哨兵的血量在 ii 到 jj 范围内时的最优期望 , 枚举另哨兵下降多少血量，进行转移。 具体的说，在使血量下降后， 原来的范围会被分成几段，对于每一段的期望求和，并进行转移。这里枚举下降的血量时一定要保证下降后范围的左端点大于 00。

这样做的复杂度是 O(an4)O(a_n^4) 的, 先给它优化到 O（an3)O（a_n ^3) ， 对于分成的几段，中间的完整段可以用前缀和进行优化。

恭喜你，凭借这个复杂度可以得到 00 分的好成绩

然后考虑优化到 O(an2)O(a_n^2)

发现如果转移后没有跨越一些状态，那么已知的范围大小不会缩小，也就是不会获得更多信息，也就一定不会更优，所以我们可以强制转移后的范围跨过一些状态或者到达状态 11。

那么接下来就可以去除一下无用的状态，设 f[i][j][0]f[i][j][0] 表示已知血量在状态 ii 中的长度为 jj 的前缀区间中， 设 f[i][j][1]f[i][j][1] 表示已知血量在状态 ii 中的长度为 jj 的后缀区间中。

枚举消耗的血量进行转移，稍微有一些麻烦。注释 ： renamoerenamoe 说可以记忆化搜索，感觉确实会好写很多。

转移不是很难，主要是把状态想出来。

Code

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 <iostream>
#include <cstdio>
#include <cstring>
#define int long long
#define ll long long

using namespace std;

const int N = 2100;

int T, n, m, a[N], w[N];
ll v[N];
ll f[N][N][2], val[N], sum[N];
int pos[N];

ll getk(int i, int j, int k)
{
  int p = pos[a[i - 1] + 1 - k];
  ll tmp = f[p][1 + a[p] - (a[i - 1] + 1 - k)][1];
  int p1 = pos[a[i - 1] + j - k];
  ll tmp1 = f[p1][(a[i - 1] + j - k) - a[p1 - 1]][0];
  return val[k]  * j+ (tmp + tmp1) + sum[p1 - 1] - sum[p + 1 - 1];
}

ll geti(int i, int j, int k)
{
  int p = pos[a[i] - j + 1 - k];
  ll tmp = f[p][1 + a[p] - (a[i] - j + 1 - k)][1];
  int p1 = pos[a[i] - k];
  ll tmp1 = f[p1][(a[i] - k) - a[p1 - 1]][0];
  return val[k]  * j+ (tmp + tmp1) + sum[p1 - 1] - sum[p + 1 - 1];
}

signed main()
{
  scanf("%lld", &T);
  while (T--)
  {
    scanf("%lld%lld", &n, &m);
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
      scanf("%lld", &a[i]);
      for (int j = a[i - 1] + 1; j <= a[i]; ++j)
      {
        pos[j] = i;
      }
    }
    for (int i = 1; i <= m; ++i)
    {
      scanf("%lld%lld", &v[i], &w[i]);
    }
    memset(val, 0x3f, sizeof(val));
    val[0] = 0;
    for (int i = 1; i <= m; ++i)
    {
      for (int j = w[i]; j <= a[n]; ++j)
      {
        val[j] = min(val[j], val[j - w[i]] + v[i]);
      }
    }
    
    for (int i = 0; i <= a[n]; ++i)
    {
      val[i] = val[i];
    }
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= a[1]; ++i)
    {
      f[1][i][0] = f[1][i][1] = 0;
    }
    for (int i = 2; i <= n; ++i)
    {
      for (int j = 1; j <= a[i] - a[i - 1]; ++j)
      {
        for (int k = 1; k <= a[i - 1] + 1 - 1; ++k)
        {
          if (pos[a[i - 1] + 1 - k] != pos[a[i - 1] + j - k])
          {
            f[i][j][0] = min(f[i][j][0], getk(i, j, k));
          }
          if (pos[a[i - 1] + j - k] == 1) f[i][j][0] = min(f[i][j][0], val[k] * j);
        }
      }
      for (int j = 1; j <= a[i] - a[i - 1]; ++j)
      {
        for (int k = 1; k <= a[i] - j + 1 - 1; ++k)
        {
          if (pos[a[i] - j + 1 - k] != pos[a[i] - k])
          {
            f[i][j][1] = min(f[i][j][1], geti(i, j, k));
          }
          if (pos[a[i] - k] == 1) f[i][j][1] = min(f[i][j][1], val[k] * j);
        }
      }
      sum[i] = sum[i - 1] + f[i][a[i] - a[i - 1]][0];
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
      ans += f[i][a[i] - a[i - 1]][1];
    }
    cout << ans << endl;
  }
  return 0;
}

区间dp

标签

线段树

思路

O(n2)O(n^2)

只要模拟就好啦，枚举值域的右端点，再枚举值域的左端点，记录一下当前有多少个区间。如果当前点左右两边都被标记过，那么区间数减 11 ，如果当前点（枚举的左端点）的左右两边有一个被标记过，那么区间数不变，如果当前点的左右两边都没有被标记过，区间数加 11， 并标记当前点。

O(nlg⁡n)O(n \lg n)

考虑优化掉枚举左端点的复杂度，我们需要枚举值域右端点，并维护每一个点作为左端点和当前右端点构成的值域区间的对应的区间个数。如果区间个数是 11 或 22 就对答案产生贡献

设当前点（枚举的右端点）左边的点值为 pp ，右边的点值为 qq
分类讨论，分为 55 类.

  1. p>r∧q>rp > r \land q > r
    对于区间 [1,r][1, r] 加 11

  2. p<r∧q>rp < r \land q > r
    对于区间 [p+1,r][p + 1, r] 加 11

  3. p>r∧q<rp > r \land q < r
    对于区间 [q+1,r][q + 1, r] 加 11

  4. p<r∧q<r∧p<qp < r \land q < r \land p < q
    对于区间 [1,p][1, p] 减 11
    对于区间 [q+1,r][q + 1, r] 加 11

  5. p<r∧q<r∧q<pp < r \land q < r \land q < p
    对于区间 [1,q][1, q] 减 11
    对于区间 [p+1,r][p + 1, r] 加 11

Code

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
177
178
179
180
181
182
183
184
185
186
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

using namespace std;

const int N = 3e5 + 10;

int n, p[N];
int ad[N];

struct Node
{
  int val[N * 4], tag[N * 4], fi[N * 4], se[N * 4], cntf[N * 4], cnts[N * 4], siz[N * 4];

  Node ()
  {
    memset(fi, 0, sizeof(fi));
    memset(se, 0x3f, sizeof(se));
  }

  void update(int u)
	{
    fi[u] = min(fi[ls(u)], fi[rs(u)]);
    if (fi[ls(u)] < fi[rs(u)]) 
    {
      fi[u] = fi[ls(u)];
      cntf[u] = cntf[ls(u)];
      if (se[ls(u)] < fi[rs(u)])
      {
        se[u] = se[ls(u)];
        cnts[u] = cnts[ls(u)];
      }
      else if (se[ls(u)] == fi[rs(u)])
      {
        se[u] = se[ls(u)];
        cnts[u] = cnts[ls(u)] + cntf[rs(u)];
      }
      else
      {
        se[u] = fi[rs(u)];
        cnts[u] = cntf[rs(u)];
      }
    }
    else if (fi[ls(u)] == fi[rs(u)])
    {
      fi[u] = fi[ls(u)];
      cntf[u] = cntf[ls(u)] + cntf[rs(u)];
      if (se[ls(u)] < se[rs(u)])
      {
        se[u] = se[ls(u)];
        cnts[u] = cnts[ls(u)];
      }
      else if (se[ls(u)] == se[rs(u)])
      {
        se[u] = se[ls(u)];
        cnts[u] = cnts[ls(u)] + cnts[rs(u)];
      }
      else
      {
        se[u] = se[rs(u)];
        cnts[u] = cnts[rs(u)];
      }
    }
    else
    {
      fi[u] = fi[rs(u)];
      cntf[u] = cntf[rs(u)];
      if (se[rs(u)] < fi[ls(u)])
      {
        se[u] = se[rs(u)];
        cnts[u] = cnts[rs(u)];
      }
      else if (se[rs(u)] == fi[ls(u)])
      {
        se[u] = se[rs(u)];
        cnts[u] = cnts[rs(u)] + cntf[ls(u)];
      }
      else
      {
        se[u] = fi[ls(u)];
        cnts[u] = cntf[ls(u)];
      }
    }
  }

  void build(int u, int l, int r)
	{
    if (l == r)
    {
      fi[u] = 0, se[u] = 0x3f3f3f3f, cntf[u] = 1, cnts[u] = 0;
      return ;
    }
    int mid = (l + r) >> 1;
    build(ls(u), l, mid);
    build(rs(u), mid + 1, r);
    update(u);
  }

  void add(int u, int v)
	{
    fi[u] += v;
    tag[u] += v;
    se[u] += v;
  }

  void push_down(int u)
	{
    if (!tag[u]) return ;
    add(ls(u), tag[u]);
    add(rs(u), tag[u]);
    tag[u] = 0;
  }

  void change(int x, int y, int v, int u = 1, int l = 1, int r = n)
	{
    if (y < x) return ;
    if (x <= l && r <= y) return add(u, v);
    int mid = (l + r) >> 1;
    push_down(u);
    if (x <= mid) change(x, y, v, ls(u), l, mid);
    if (y > mid) change(x, y, v, rs(u), mid + 1, r);
    update(u);
  }

  int query(int x, int y, int u = 1, int l = 1, int r = n)
	{
    if (x <= l && r <= y)
    {
      int res = 0;
      if (fi[u] == 1 || fi[u] == 2)
      {
        res += cntf[u];
      }
      if (se[u] == 1 || se[u] == 2)
      {
        res += cnts[u];
      }
      return res;
    }
    int mid = (l + r) >> 1;
    push_down(u);
    int res = 0;
    if (x <= mid) res += query(x, y, ls(u), l, mid);
    if (y > mid) res += query(x, y, rs(u), mid + 1, r);
    return res;
  }

}tr;


signed main()
{
  scanf("%lld", &n);
  int ans = 0;
  for (int i = 1; i <= n; ++i) scanf("%lld", &p[i]), ad[p[i]] = i;
  tr.build(1, 1, n);
  for (int i = 1; i <= n; ++i)
  {
    if (p[ad[i] - 1] > i && p[ad[i] + 1] > i)
    {
      tr.change(1, i, 1);
    }
    else if (p[ad[i] - 1] > i && p[ad[i] + 1] < i)
    {
      tr.change(p[ad[i] + 1] + 1, i, 1);
    }
    else if (p[ad[i] - 1] < i && p[ad[i] + 1] > i)
    {
      tr.change(p[ad[i] - 1] + 1, i, 1);
    }
    else
    {	
      int x0 = min(p[ad[i] - 1], p[ad[i] + 1]);
      int x1 = max(p[ad[i] - 1], p[ad[i] + 1]);
      tr.change(1, x0, -1);
      tr.change(x1 + 1, i, 1);
    }
    ans += tr.query(1, i);
  }
  cout << ans - n << endl;
  return 0;
}

成绩单

标签

dp + 区间dp

思路

太妙了，到现在我都不知道是怎么想出来的。

设 g[l][r]g[l][r] 表示把区间 [l,r][l,r] 全部取走的最小代价，显然可以从 g[l][k]和g[k+1][r]g[l][k] 和 g[k + 1][r] 合并得到，但是操作支持取走中间一段，这个很难进行转移。

考虑退一步，引入一个新的状态 f[l][r][i][j]f[l][r][i][j] 表示在区间 [l,r][l,r] 中，只剩余值域在 [i,j][i,j] 的数的最小花费，那么 g[l][r]=min⁡(f[l][r][i][j]+a+b×(j−i))g[l][r] = \min(f[l][r][i][j] + a + b \times (j - i)) , 接下来就只用考虑 ff 的转移了。

一个显然的转移是 f[l][r][i][j]=min⁡(f[l][k][i][j]+f[k][r][i][j])f[l][r][i][j] = \min(f[l][k][i][j] + f[k][r][i][j]) , 然后考虑如何处理取走中间的操作，如果要满足所有数都在 [i,j][i,j] 那么就要把 [i,j][i,j] 之外的数都取走，所以找到最左端在 [i,j][i,j] 之外的点 pp 和最右端在 [i,j][i,j] 之外的点 qq . f[l][r][i][j]=min⁡(g[p][q])f[l][r][i][j] = \min(g[p][q])

综上所述一共有一下转移:
f[l][r][i][j]=min⁡(g[p][q],f[l][k][i][j]+f[k+1][r][i][j])f[l][r][i][j] = \min(g[p][q], f[l][k][i][j] + f[k + 1][r][i][j])

g[l][r]=min⁡(f[l][r][i][j]+a+b×(j−i))g[l][r] = \min(f[l][r][i][j] + a + b \times (j-i))

Code：

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;
int n;
int a, b;
int w[N], v[N], tmp[N];
int f[N][N][N][N], g[N][N];
int maxx[N][N], minn[N][N];

int main()
{
  cin >> n;
  cin >> a >> b;
  for (int i = 1; i <= n; ++i)
  {
    cin >> w[i];
    v[i] = w[i];
  }
  sort(v + 1, v + n + 1);
  int m = unique(v + 1, v + n + 1) - v - 1;
  for (int i = 1; i <= n; ++i)
  {
    int t = w[i];
    w[i] = lower_bound(v + 1, v + m + 1, w[i]) - v;
    tmp[w[i]] = t;
  }
  for (int i = 1; i <= n; ++i)
  {
    g[i][i] = a;
    for (int l = 1; l <= m; ++l)
    {
      for (int r = l; r <= m; ++r)
      {
        if (w[i] < l || w[i] > r)
        {
          f[i][i][l][r] = a;
        }
      }
    }
  }
  for (int len = 2; len <= n; ++len)
  {
    for (int l = 1; l <= (n - len + 1); ++l)
    {
      int r = l + len - 1;
      g[l][r] = 0x3f3f3f3f;
      for (int i = 1; i <= m; ++i)
      {
        for (int j = i; j <= m; ++j)
        {
          int p = 0, q = 0;
          for (int k = l; k <= r; ++k)
          {
            if (w[k] < i || w[k] > j)
            {
              p = k;
              break;
            }
          }
          for (int k = r; k >= l; --k)
          {
            if (w[k] < i || w[k] > j)
            {
              q = k;
              break;
            }
          }
          f[l][r][i][j] = g[p][q];
          for (int k = l; k < r; ++k)
          {
            f[l][r][i][j] = min(f[l][r][i][j], f[l][k][i][j] + f[k + 1][r][i][j]);
          }
          g[l][r] = min(g[l][r], f[l][r][i][j] + a + b * (tmp[j] - tmp[i]) * (tmp[j] - tmp[i]));
        }
      }
    }
  }
  cout << g[1][n] << endl;
    
}

记得离散化

周期性字符串计数问题

标签

dp + 记忆化搜索 + 莫比乌斯反演 + 计数 + 性质

性质1

对于任意一个周期性字符串，一定由且仅由一个非周期性字符串复制得到。

假设一个周期性字符串可以由两个不同的非周期性字符串分别复制得到.

那么如下图

由图可以感性发现，两个串一定是循环串，接着感性证明一下

对于一个串上的每一个点，它在另一个串上的出现频率是一定的，这不难理解。
那么考虑所有点，发现所有点的出现频率是一样的，那么另一个串就一定是周期性字符串。
接着就是套路了。

思路

设 f[n]f[n] 表示长度为 ii 的非周期串个数.

f[n]=26n−∑d∣nf[d]+f[n]f[n] = 26^n - \sum_{d|n} f[d] + f[n]

+f[n]+f[n] 是为了排除由自己复制得到的情况， 因为对于任意一个周期性字符串，一定由且仅由一个非周期性字符串复制得到。所以长度为 nn 的周期串个数就是长度为 dd 的非周期串的个数的和， 这样可以做到不重不漏。
接着有两个做法

做法1

把两边的 f[n]f[n] 消掉得到 ∑d∣nf[d]=26n\sum_{d|n}f[d] = 26^n ， 这个式子显然可以反演。得到

f[n]=∑d∣nμ(nd)26df[n] = \sum_{d|n} \mu(\frac{n}{d}) 26^d

做法2

因为 1e91e9 以内约数最多的数的约数个数不超过 14001400， 所以涉及到的状态很少，可以用记忆化搜索.

做法 11 的复杂度最优可以是 O(nln⁡ln⁡n)O(\sqrt n\ln\ln n), 比 22 要好

Code(我写的做法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
#include <iostream>
#include <cstdio>
#include <map>
#define int long long

using namespace std;

const int mod = 1e9 + 7, N = 1000000;
int n;
map<int, int> f, g;
int p[N], tot;

int qpow(int a, int b)
{
  int res = 1;
  while (b)
  {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}

int dfs(int n)
{
  if (g[n]) return g[n];
  int res = 0;
  for (int i = 1; i <= tot; ++i)
  {
    if (n % p[i] == 0 && n != p[i])
    {
      res = (res + dfs(p[i])) % mod;
    }
  }
  f[n] = res;
  g[n] = (qpow(26, n) - f[n] + mod) % mod;
  return g[n];
}

signed main()
{
  scanf("%lld", &n);
  for (int i = 1; i * i <= n; ++i)
  {
    if (n % i == 0)
    {
      p[++tot] = i;
      if (i *i != n)
      p[++tot] = n / i;
    }
  }
  dfs(n);
  cout << f[n] << endl;
  return 0;
}