2023年10月14日模拟赛

2023年10月14日模拟赛

混氏新子 蒟蒻
  2023-10-14 22:12:29 2023-10-14 22:12:29 创建   2023-10-14 23:34:21 2023-10-14 23:34:21 更新    2.2k 字  10 分钟  

前情提要

题目链接

今天这个题目非常有趣，感觉不难，但是一道题也没有拿满。好在我暴力技巧高超，才得以拿下还不错的分数。

题解

T1

[[数学]]

这道题考场上想出了的方法，但是看起来最后一个点并不能过。

我考场上想的大于的部分是两位，用整数分块，这个分块用法我感觉很神奇，感觉以后一定能派上大用场。记录一下： #未雨绸缪

正解是 1000 以内的暴力，以上的发现不超过三位数，暴力枚举，和不超过32，二次方程求解即可，

暴力：

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
#include <bits/stdc++.h>
using namespace std;
int t;
int n, k;
inline int getsum(int n, int b) {
  int tot = 0;
  while (n) {
    tot += n % b;
    n /= b;
  }
  return tot;
}
int main() {
  freopen("base.in", "r", stdin);
  freopen("base.out", "w", stdout);
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &k);
    if (k == n) {
      puts("1");
      continue;
    }
    int tmp = sqrt(n);
    int ans = __builtin_popcount(n);
    if (k == n - 1) ans = min(ans, 2);
    for (int i = 3; i <= tmp && i <= k && ans != 1; ++i) {
      if (n % i >= ans) continue;
      ans = min(ans, getsum(n, i));
    }
    for (int l = tmp + 1, r; l <= k && ans != 1; l = r + 1) {
      r = min(n / (n / l), k);
      ans = min(ans, n / r + n % r);
    }
    printf("%d\n", ans);
  }
  return 0;
}

正解：

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int t;
int n, k;
int ans;
inline int getsum(int n, int b) {
  int tot = 0;
  while (n) {
    tot += n % b;
    n /= b;
  }
  return tot;
}
int main() {
  freopen("base.in", "r", stdin);
  freopen("base.out", "w", stdout);
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &k);
    if (k == n) {
      puts("1");
      continue;
    }
    ans = __builtin_popcount(n);
    if (k == n - 1) ans = min(ans, 2);
    for (int i = 3; i <= 1000 && i <= k && ans != 1; ++i) {
      ans = min(ans, getsum(n, i));
    }
    for (int a = 0; a <= ans; ++a) {
      for (int b = 0; a + b <= ans; ++b) {
        for (int c = 0; a + b + c <= ans; ++c) {
          if (a + b == 0) continue;
          if (a + b + c >= n) break;
          if (a == 0) {
            if ((n - c) % b != 0) continue;
            int tmp = (n - c) / b;
            if (tmp > k || tmp <= a || tmp <= b || tmp <= c) continue;
            ans = min(ans, a + b + c);
          } else {
            ll delta = (ll)b * b - 4ll * a * (c - n);
            if (delta < 0) continue;
            ll sqr = sqrt(delta);
            if (sqr * sqr != delta) continue;
            delta = sqr;
            int x = -b + delta;
            if (x % (2 * a) != 0) continue;
            x = x / 2 / a;
            if (x > k || x <= min({a, b, c})) continue;
            ans = min(ans, a + b + c);
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

T2

[[dp]] [[容斥]]

这道题还挺有趣的。考场上先想出了一个很暴力的，然后又想出了的 dp，就是一次 dp 最大不超过一个数的数量。

正解也是按照这个来的，不过是使用的容斥，推出了组合式子，因此能快速计算。

考试的时候也想过容斥，可能今天脑子不太好用，所以没有想出来。

这里有两种方法推出这个式子，第一种来源于 UKER 方法的简化，第二种是我经常用的。但是两种方法的第一步都是一样的。

首先就是还是依次找到不超过的的数量。这里用了个转化，我没有想到，积累一下。就是把这串数字看成一串1和一个0组合的形式，记为这一段的长度，可以是0个1，现在再在这串数后面补一个0，就转化成将拆成几个数相加的形式。最大的数小于等于，然后做一个差分就能得到答案。

那么假设我们现在求不超过，用总数减去超过的。超过的枚举有多少段大于，然后容斥。获取大于的段可以把这些段减去，然后再来处理。此时记大于的段数为，为分成了多少段。运用插板法可得到数量为

我们发现外层最后只是 log 级别的，但是内层和无法快速相消，因此我们需要对内层进行变形求和。

众所周知，

所以说：

现在就可以计算这坨式子了！

然后讲我的式子是怎么推的。上面的思路还是差不多的，也是算不超过，然后枚举有个超过的数。

然后呢，我们形象地考虑是如何拆分的。我们先抽象出个点，然后每个点有两种状态，第一种是空，啥也不干，第二种是连一条边指向前一个点。显然第一个点只能是第一种。我们会发现，这样刚好是对应上面所说的拆分的。

我们在考虑如何去算个大于的情况数，我们会发现如下结构：
png
这代表一串大于长度一段的结尾，后面还要添加一个空的点防止后面的点连向这一段。

但是现在对于这段中最后一段就有两种情况：

  • 有最后那个空点
  • 没有最后那个空点，直接就是结尾。

我们先来考虑第一种情况：

首先把第一个点（第一个点是不变的）和这段这种结构放好，发现还剩下，个点，有个空隙可以插下没有被安排的点，而这几个空隙是可以没有这些没被安排的点的。同样使用插板法，发现有种差法，而这几个点可以是两种状态的任意一种，即种，也就是
这么多种。

第二种情况类似，不过最后一段没有最后那个点，空隙也会少掉最后一个只剩下个，同样的方法计算剩下的个点，方案数是

两个加起来就是答案，和上面算出的结果一模一样。

是不是很有趣呢？

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
#include <cstdio>
#define mod 1000000007ll
#define N 1000010
using namespace std;
using ll = long long;
ll qp(ll x, ll y) {
  ll ans = 1;
  while (y) {
    if (y & 1) ans = ans * x % mod;
    y >>= 1;
    x = x * x % mod;
  }
  return ans;
}
int n;
ll gb[N];
ll *g;
ll fact[N], invf[N];
ll *tm;
ll tmb[N];
ll c(ll x, ll y) {
  return x < y ? 0 : fact[x] * invf[y] % mod * invf[x - y] % mod;
}
int main() {
  freopen("sequence.in", "r", stdin);
  freopen("sequence.out", "w", stdout);
  g = gb + 1;
  tm = tmb + 1;
  scanf("%d", &n);
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fact[i] = fact[i - 1] * i % mod;
  }
  invf[n] = qp(fact[n], mod - 2);
  for (int i = n - 1; ~i; --i) {
    invf[i] = invf[i + 1] * (i + 1) % mod;
  }
  tm[0] = 1;
  for (int i = 1; i <= n; ++i) 
    tm[i] = tm[i - 1] * 2 % mod;
  for (int i = 1; i <= n + 1; ++i) {
    g[i] = tm[n];
    for (int j = 1; j * (i + 1) <= n + 1; ++j) {
      ll tmp = (c(n - j * i, j) * tm[n - j * i - j] % mod + c(n - j * i, j - 1) * tm[n - j * i - j + 1]) % mod;
      if (j & 1) g[i] -= tmp;
      else g[i] += tmp;
      if (g[i] < 0) g[i] += mod;
      if (g[i] >= mod) g[i] -= mod;
    }
  }
  for (int i = 1; i <= n + 1; ++i) {
    ll ans = g[i] - g[i - 1];
    if (ans < 0) ans += mod;
    printf("%lld ", ans);
  }
  return 0;
}

T3

[[区间dp]] [[回文串]]

突然发现这道题很简单，就是一个简单的区间 dp。
可能是之前回文串和区间 dp 的题目练得比较少，所以不熟悉。
考试得时候我发现我当中得有一些思路是和区间 dp 很相近的，只不过不知道如何去实现。
现在才知道。所以我发现积累的经验可以帮助我们在面对一个问题时更快得、条例清晰地找出解决的办法，而不是像脑子里面一堆浆糊一样去想题，似懂非懂，还要从自己的想法中去提炼正确的解决方案。

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
#include <bits/stdc++.h>
using namespace std;
#define N 310
int n;
char s[N];
int a[N], f[N][N][N];
int sum[N][2];
int ans;
int main() {
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; ++i) {
		a[i] = s[i] ^ 48;
		sum[i][1] = sum[i - 1][1] + a[i];
		sum[i][0] = sum[i - 1][0] + 1 - a[i];
	}
	if (n % 2 == 0 && sum[n][1] % 2 == 1) {
		puts("-1");
		return 0;
	}
	ans = n >> 1;
	if (n & 1) {
		for (int i = 1; i <= n; ++i) {
			f[i][i][0] = a[i] == (sum[n][1] & 1);
		}
	}
	for (int l = n; l; --l) {
		for (int r = l + 1; r <= n; ++r) {
			for (int k = 0; k <= (r - l + 1) / 2; ++k) {
				f[l][r][k] = max(f[l + 1][r][k], f[l][r - 1][k]);
				if (a[l] == a[r] && k >= a[l] && (n % 2 == 0 || f[l + 1][r - 1][k - a[l]] & 1)) {
					f[l][r][k] = max(f[l + 1][r - 1][k - a[l]] + 2, f[l][r][k]);
				}
			}
		}
	}
	int n1 = sum[n][1] >> 1, n0 = sum[n][0] >> 1;
	for (int l = 1; l <= n; ++l) {
		for (int r = l; r <= n; ++r) {
			for (int k = 0; k <= (r - l + 1) / 2; ++k) {
				if (sum[l - 1][1] + k < n1 || sum[l - 1][0] + f[l][r][k] / 2 - k < n0) continue;
				ans = max(ans, n / 2 + (f[l][r][k] + 1) / 2);
			}
		}
	}
	printf("%d", n - ans);
	return 0;
}

T4

[[线段树]]

这道题看了题解，貌似是线段树，也有了一点思路，再去想想。

后记

千锤万凿出深山，烈火焚烧若等闲。
粉身碎骨全不怕，要留清白在人间。

咬定青山不放松，立根原在破岩中。
千磨万击还坚劲，任尔东西南北风。

  • 标题: 2023年10月14日模拟赛
  • 作者: 混氏新子
  • 创建于 : 2023-10-14 22:12:29
  • 更新于 : 2023-10-14 23:34:21
  • 链接: https://blog.huasushis.cn/2023/2023年10月14日模拟赛/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
6.29 测试 6.29 测试 7.4 测试 7.4 测试 6.26 测试 6.26 测试
推荐阅读
6.29 测试 6.29 测试 7.4 测试 7.4 测试
评论
此页目录
2023年10月14日模拟赛
  1. 前情提要
  2. 题解
    1. T1
    2. T2
    3. T3
  3. T4
  4. 后记