(0条未读通知) 牛客2025秋季算法编程训练联赛3-基础组_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A 牛牛的DRB迷宫I

image-20251109231116472

对于这个题目，我上来想到的就是用DFS来暴力求解（因为我当时并不清楚DFS的时间复杂度），导致TLE。现在，我需要对DFS在二维矩阵中的时间复杂度做个总结：

对于本题，最坏情况就是所有位置都是’B’，也就是每个位置都有两种选择。

路径长度：从（1,1）到（n,m）需要走(n-1)+(m-1)=n+m-2步

路径数量： $2^{n+m-2} $

时间复杂度：O(2n+m−2)O(2^{n+m-2})

当n=m=50时：

  • 路径长度 = 98步
  • 路径数量 ≈ 2^98 ≈ 3.17 × 10^29

超过了10^8的时间复杂度，必然会TLE

总结：DFS在二维矩阵中时间复杂度为O(路径数量)O(路径数量) = O(2路径长度)O(2^{路径长度})

​ 在n+m>40时完全不可行。

随后，我又想到以前写过一道动态规划基础题和这个类似，概括下就是从（1,1）开始只能向右或向下走，问走到终点一共有几种方法。有用了这个题的思路，就把本题给写出来了。

B 牛牛的k合因子数

image-20251109231129512

看到这题时候，我本想着直接顺着题目的意思模拟，但是因为时间复杂度问题而写不出来。

初始思路：用筛法把1-n所有合数（非素数）全部标记；循环m次，每次读入一个k，遍历1-n，对于每个数a[i]遍历其所有因子，如果因子是合数就让内计数器+1，如果最后内计数器==k那就让外计数器+1，最后输出外计数器值。

按照这个思路，时间复杂度应该是：O(nmlogn)O(nmlogn)以这题的数据规模，必然超时。

我们试着改变下顺序，先把所有的k保存起来（可以使用map键值对来保存，因为n较大），遍历1-n，计算每个数a[i]是t合因子数（判断是否是合数部分可以在循环前初始化筛法），再将键t对应的值++即可。

这样时间复杂度就缩减成了O(nlogn)O(nlogn)

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

using namespace std;

const int N = 1e5 + 10;

int n, m;

bool is_prime[N]; 
//素数为0，合数为1(由于1既不是合数也不是素数，因为本题求的是合数，当做素数处理)

int k[N];

map<int, int> mp;

void prime()
{
	for (int i = 2; i <= n + 5; i++)
		if (!is_prime[i])
			for (int j = 2 * i; j <= n + 5; j += i)
				is_prime[j] = 1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	
	
	cin >> n >> m;
	
	prime(); //prime函数不能放在输入前面哈，找了半天才发现错误
	
	for (int i = 1; i <= m; i++)
		cin >> k[i];

	for (int i = 1; i <= n; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= i / j; j++)
			if (i % j == 0)
			{
				if (is_prime[j])
					cnt++;
				if (i / j != j && is_prime[i / j])
					cnt++;
			}
		mp[cnt]++;
	}
	
	for (int i = 1; i <= m; i++)
		cout << mp[k[i]] << endl;
	
	return 0;
}

image-20251109231142456

使用前缀和将两层循环缩减到一层循环

a[0] a[1] a[2] a[3] a[4]

计算到a[4]贡献时候，a[4]-a[0]+a[4]-a[1]+a[4]-a[2]+a[4]-a[3] = 4*a[4]-(a[0]+a[1]+a[2]+a[3])

若sum[i]表示a[0]+a[1]+…+a[i]

则，对于a[i]，其贡献为(i-1)*a[i]-sum[i-1] 注意取模