2025-06-10发表2025-07-01更新牛客7 分钟读完 (大约1019个字) 次访问

牛客赛

汇总牛客线上赛题目

牛客周赛Round-93

F

一个线性状态 DP

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

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

#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

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

最讨厌看到的显然成立

#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 的倍数一定是早就出现过的

#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;
}