发表更新牛客13 分钟读完 (大约2009个字)  次访问

牛客赛(日常比赛)

汇总牛客线上赛题目

牛客周赛Round-93

F

一个线性状态 DP

这个题目的思路比较简单，但是其实实现是有一点考验码量的，那个奇偶性的判断。就是一个线性DP

这个位置与只与上一个位置有关系，所以自然可以想到动态规划，但是这个题目的码量有一点要求，整体思维难度不大。

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

#define int long long
const int mod = 1e9 + 7;

signed main(){
    int n;
    cin >> n;
    vector<vector<int>> a(n + 1, vector<int>(n + 1, -1));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cin >> a[i][j];
        }
    }
	vector<vector<vector<int>>> dp(2, vector<vector<int>>(n + 3, vector<int>(n + 3, 0)));
	
	if(n % 2 == 0){
		int t1 = n / 2, t2 = n / 2 + 1; 
		for(int i = 1; i <= t1; i++){
			if(a[t1][i] == a[t2][i]) dp[0][i][i]++;
			if(a[t1][i] == a[t2][i + 1]) dp[0][i][i + 1]++;
		}
		int temp = 1;
		for(int d = 1; d < n / 2; d++){
			for(int i = 1; i <= n; i ++){
				for(int j = 1; j <= n; j++){
					dp[d & 1][i][j] = 0;
				}
			}
			temp &= 1;
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= n; j++){
					if(a[t1 - d][i] == a[t2 + d][j]){
						dp[d & 1][i][j] = (dp[(d - 1) & 1][i][j]+dp[d & 1][i][j]) % mod;
                        dp[d & 1][i][j] = (dp[(d - 1) & 1][i + 1][j] +   dp[d & 1][i][j])% mod;
                        dp[d & 1][i][j] = (dp[(d - 1) & 1][i][j - 1] + dp[d & 1][i][j])% mod;
                        dp[d & 1][i][j] = (dp[(d - 1) & 1][i + 1][j - 1] + dp[d & 1][i][j])% mod;
					}
				}
			}
		}
		int ans = 0;
		for(int i = 1; i <= n; i++){
			ans = (ans + dp[(n + 1) / 2 - 1 & 1][1][i]) % mod;
		}
		cout << ans << endl;
	}else{
		int t1 = (n / 2) + 1;
		for(int i = 1; i <= t1; i++){
			dp[0][i][i] = 1;
		}
		int temp = 1;
		for(int d = 1; d <= n / 2; d++){
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= n; j++){
					dp[d & 1][i][j] = 0;
				}
			}
			temp &= 1;
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= n; j++){
					if(a[t1-d][i] == a[t1 + d][j]){
						dp[d & 1][i][j] = (dp[(d - 1) & 1][i][j]+dp[d & 1][i][j]) % mod;
                        dp[d & 1][i][j] = (dp[(d - 1) & 1][i + 1][j] +   dp[d & 1][i][j])% mod;
                        dp[d & 1][i][j] = (dp[(d - 1) & 1][i][j - 1] + dp[d & 1][i][j])% mod;
                        dp[d & 1][i][j] = (dp[(d - 1) & 1][i + 1][j - 1] + dp[d & 1][i][j])% mod;
					}
				}
			}
		}
		int ans = 0;
		for(int i = 1; i <= n; i++){
			ans = (ans +  dp[(n + 1)/2 - 1 & 1][1][i]) % mod;
		}
		cout << ans << endl;
	}

    }




牛客周赛Round-94

这一场我感觉偏推理场吧，主要被前面的题目唬到了，然后后面做起来有点害怕，看到了那个类似 成都赛场上面没做出来的一个签到题目，感觉心里很慌。

2024成都区域赛A-Arrow a Row

这个好像不是一个拓扑排序的题目，是一个构造题！

最讨厌看到的显然成立

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

#define int long long 
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;

void slove(){
	string s;
	cin >> s;
	int n = s.size();
	/*
	 - 的位置要 小于倒数第三个位置 相近的 - 之间的距离必须大于 4
	  存储每一对的位置 - 的左右
	*/
	bool ex = true;
	for(int i = 0; i < n; i++){
		if(s[i] == '-'){
			ex = false;
			 break;
		}
	}
	if(ex){
		cout << "No" << endl;
		return;
	}
	int d[4] = {0, n - 1, n - 2, n - 3};
	for(int i = 0; i < 4; i++){
		if(s[d[i]] != '>'){
			cout << "No" << endl;
			return;
		}
	}
	
	vector<pair<int, int>> ans;
	int i;
	for( i = n - 3; i > 1; i--){
		if(s[i] == '>'){
			ans.push_back({0, i + 3});
		}else break;
	}
	for(int j = 1; j < i; j++){
		if(s[j] == '>'){
			ans.push_back({j, i + 3 - j + 1});
		}
	}
	cout << "Yes" << " " << ans.size() << endl;
	for(auto[x, y] : ans){
		cout << x + 1 << " " << y << endl;
	}
}

signed main(){
	int t;
	cin >> t;
	while(t--) slove();
	return 0;
}

E-小苯的数字操作

知识点：对于一个数字的二进制形式，$\times$ 2 相当于在二进制后面新增0，$\div$ 2 相当于删除二进制的最后一位

有一个坑：如果当 n 为 1的时候，是不要进行特判里面的，因为如果为 1 的时候，他的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
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;
signed main(){
	int t;
	cin >> t;
	while(t--){
		int n, k;
        cin >> n >> k;
        int ans = k + 1;
        for(int i = 1; i <= k; i++){
            if(n % 2 != 0 && n != 1){
                ans += (k - i);
            }
            ans ++;
            n /= 2;
            if(n == 0){
                break;
            }
        }
        cout << ans << endl;
	}
	return 0;
}



F-小苯的小球分组

有一个结论

结论
定义小球集合$\Bbb S$的函数 $f(\Bbb S)$，表示将小球集合 $\Bbb S$ 分为若干组，满足以下所有条件的最少分组个数：

  • 每组最多有 2 个球

  • 组内有 2 个球的组，这 2 个球的颜色不同。
    这个的最小分组个数为 ：$max(a_{max},(sum/2)_{向上取整}）$

牛客周赛Round-105

E-小苯的xor图

反思:这道题目经验不足,思考方向不对,怎么会不往二进制的角度去想问题呢?按理来说,题目中遇见或,异或,与等问题,我们都应该往二进制的角度去想问题,我一直从如何三个节点的路径上想问题是完全错误的

三个节点的异或值可以从节点的每一位去观察,因为你三个节点在某一位上的情况很少,只有 001,011,010…

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

#define int long long 
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;
const int mod = 998244353;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> v(n + 1, 0);
	for(int i = 1; i <= n; i++) cin >> v[i];
	vector<vector<int>> a(n + 1);
	for(int i = 0; i < m; i++){
		int u, v;
		cin >> u >> v;
		a[u].push_back(v); a[v].push_back(u);
	}
	int ans = 0;
	for(int i = 0; i <= 32; i++){
		for(int u = 1; u <= n; u++){
			int cnt0 = 0, cnt1 = 0, falg = (v[u] >> i & 1);
			for(auto x : a[u]){
				int tt = (v[x] >> i & 1);
				cnt0 += (tt == 0);
				cnt1 += (tt == 1);
			}
			int ans1 = (1 << i);
			if(falg == 0){
				ans1 = ans1 * (cnt1 * cnt0 % mod) % mod;
			}else{
				ans1 = ans1 * ((cnt0 * (cnt0 - 1) / 2) % mod + (cnt1 * (cnt1 - 1) / 2) % mod) % mod;
			}
			ans = (ans + ans1) % mod;
		}
	}
	cout << ans << endl;
	return 0; 
}

2025牛客暑期多校训练营3

E-Equal

针对于这个题目,其实最重要的是一个知识点,就是因数分解的知识点

常见的因数分解一个数字是:O(n)

1
2
3
4
5
6
for(int i = 2; i <= n; i++) {
    while(n % i == 0) {
        factors.push_back(i);
        n /= i;
    }
}

但是针对于一些时间复杂度严苛的题目,这个算法便是不可行的,于是就有了预处理的解决办法

解决思路: 一个数的因式分解 == 这个数字的最小质因数 * (m),这样可以将 m 不断分解成最小质因数,这样的乘机也是因式分子

一个数字的时间复杂度为 O(log(n))

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
const int N = 5e6 + 10;
vector<int> prime(N + 1, 0);

void init(){
	for(int i = 2; i <= N; i++){
		if(prime[i] == 0){
			prime[i] = i;
		}
		for(int j = 2; j * i <= N; j++){
			if(prime[j * i] == 0){
				prime[j * i] = prime[i];
			}
		}
	}
}
signed main(){
	init();
	map<int, int> mp;
	for(int i = 1; i <= n; i++){
		while(a[i] > 1){
			int t = prime[a[i]]; mp[t]++;
			// cout << t << endl;
			a[i] /= t;
		}
	}
}

牛客周赛Round-107

F

这个题目是一个离线处理的题目,也是一个很好又很经典的离线题目

题意:

我一开始是想通过DP来找到这个位置的最早被覆盖的位置,其实和题目的想法差不多,但是我这么写的话就是没有这么简单…

思路: 一个很明显的递推关系,就是如果这个点被X覆盖了,那么比X大的覆盖图的大小只会比X的覆盖图更大(这个也是我想使用DP的原因,因为有一个很明显的递推关系),但是DP不行,因为没有一个明显的递推公式,所以通过离线处理,通过对X进行排序,在前面的基础上进行扩展

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

/*
需要记录的笔记:
1. 离线思维题:
ex: 一个数组,每次删除 一个数,求每一次删除后的gcd
2. 针对于 priority_queue的自定义排序
*/

struct node{
	int val, x, y;
	bool operator < (const node &n) const{
		return val > n.val;
	}
};

int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
signed main(){
	int n, m, q;
	cin >> n >> m >> q;
	vector dj(n + 1, vector<int>(m + 1, 0));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> dj[i][j];
		}
	}
	vector<array<int,2>> t1(q);
	for(int i = 0; i < q; i++){
		cin >> t1[i][0];
		t1[i][1] = i + 1;
	}
	sort(t1.begin(), t1.end(), [&](array<int,2> p1, array<int,2> p2){
		return p1[0] < p2[0];
	});
	vector<int> ans(q + 1, 0);
	vector vis(n + 1, vector<bool> (m + 1, 0));
	int cnt = 0;
	// deque<int> q1;
	priority_queue<node> h;
	for(int i = 1; i <= m; i++){
		h.push({dj[1][i], 1, i});
	}
	for(int i = 0; i < q; i++){
		auto temp = t1[i];
		while(!h.empty() && temp[0] >= h.top().val){
			auto X = h.top(); h.pop();
			// cout << X.x << " " << X.y << endl;
			if(vis[X.x][X.y]) continue;
			vis[X.x][X.y] = 1; cnt++;
			for(int i = 0; i < 4; i++){
				int tx = X.x + dx[i], ty = X.y + dy[i];
				if(tx <= n && ty <= m && tx >= 1 && ty >= 1){
					if(!vis[tx][ty]) h.push({dj[tx][ty], tx, ty});
				}
			}
		}
		ans[temp[1]] = cnt;
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << " ";
}








牛客赛(日常比赛)

http://whalefall.fun/2025/06/10/牛客赛/

作者

Jiely

发布于

2025-06-10

更新于

2025-09-01

许可协议

#

评论

目录

×