第十六届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组部分题解

Kent_J_Truman

190人浏览 · 2025-05-03 15:00:54

Kent_J_Truman · 2025-05-03 15:00:54 发布

A

略

B

略

C

略

D

#include <bits/stdc++.h>
using namespace std;

string s[2] = {"RED", "BLACK"};

int dfs(int n, int k)
{
	if(n == 1 && k == 1) return 0;
	
	int fa;
	if(k % 2 == 0) fa = dfs(n-1, k/2);
	else fa = dfs(n-1, (k-1)/2);
	
	if(fa == 0)
	{
		if(k % 2 == 0) return 0;
		else return 1;
	}
	else
	{
		if(k % 2 == 0) return 1;
		else return 0;
	}
}
int main()
{
	int m;
	cin >> m;
	for(int i = 1; i <= m; i++)
	{
		int n, k;
		cin >> n >> k;
		k = pow(2, n-1) - 1 + k;
		cout << s[dfs(n, k)] << '\n';
	}
}

E

暴力 $O(n^{2})$

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

// 计算去重后的排列数：总排列数 / (重复数字的阶乘乘积)
long long calculatePermutations(vector<int>& nums) {
    map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }

    long long total = 1;
    int n = nums.size();
    for (int i = 1; i <= n; i++) {
        total *= i;
    }

    for (auto& [num, cnt] : freq) {
        for (int i = 1; i <= cnt; i++) {
            total /= i;
        }
    }

    return total;
}

int main() {
    int k;
    cin >> k;
    vector<int> a(k);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
    }

    long long ans = 0;
    int nm = k - 2;  // n * m = k - 2

    // 枚举所有可能的 (n, m) 组合
    for (int n = 1; n <= nm; n++) {
        if (nm % n != 0) continue;
        int m = nm / n;

        // 检查输入中是否有足够的 n 和 m
        vector<int> temp = a;
        bool has_n = false, has_m = false;
        for (int i = 0; i < temp.size(); i++) {
            if (temp[i] == n) {
                has_n = true;
                temp.erase(temp.begin() + i);
                break;
            }
        }
        for (int i = 0; i < temp.size(); i++) {
            if (temp[i] == m) {
                has_m = true;
                temp.erase(temp.begin() + i);
                break;
            }
        }

        if (!has_n || !has_m) continue;

        // 计算剩余数字的排列数
        ans = (ans + calculatePermutations(temp)) % MOD;
    }

    cout << ans << endl;
    return 0;
}

正解1主要针对反复求阶乘、反复求逆元、反复维护桶提出初始化优化

正解1 $O(n \cdot \sqrt n)$

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1000000007;
const int N = 5e5+10;

int buk[N];
ll fac[N], infac[N];
ll qmi(ll base, ll expo)
{
	ll retv = 1;
	while(expo)
	{
		if(expo & 1) retv = retv * base % mod;
		base = base * base % mod;
		expo >>= 1;
	}
	
	return retv;
}
ll inv(ll x)
{
	return qmi(x,mod-2);
}
void init(int n)
{
	fac[0] = infac[0] = 1;
	for(int i = 1; i <= n; i++)
		fac[i] = fac[i-1] * i % mod;
	for(int i = 1; i <= n; i++)
		infac[i] = inv(fac[i]);
}
int main()
{
	init(N-10);
	
	int k;
	cin >> k;
	int x;
	for(int i = 1; i <= k; i++)
	{
		cin >> x;
		buk[x]++;
	}
	
	int sz = k - 2;
	
	ll ans = 0;
	for(int n = 1; n <= sz / n; n++)
	{
		if(sz % n != 0 || !buk[n] || !buk[sz / n])
			continue;
		int m = sz / n;
		buk[n]--;
		buk[m]--;
		ll cur = fac[sz];
		for(int i = 1; i <= 5e5; i++)
			cur = cur * infac[buk[i]] % mod;
		if(n == m) ans = (ans + cur) % mod;
		else ans = (ans + cur * 2 % mod) % mod;
		buk[n]++;
		buk[m]++;
	}

	cout << ans;
}

正解2主要针对正解1中的不断乘以逆元进行优化，它指出，绝大部分的逆元都可以预先处理好。对于提取m,n引起的cnt[m]--,cnt[n]--，进而引起的逆元变化，涉及一类或者两类逆元（看m是否等于n），分别乘以对应的cnt[m] * (cnt[m] -1)或者cnt[m] * cnt[n]来解决即可

正解2 $O(n)$

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1000000007;
const int N = 5e5+10;

int buk[N], mx;
ll fac[N], infac[N];
ll qmi(ll base, ll expo)
{
	ll retv = 1;
	while(expo)
	{
		if(expo & 1) retv = retv * base % mod;
		base = base * base % mod;
		expo >>= 1;
	}
	
	return retv;
}
ll inv(ll x)
{
	return qmi(x,mod-2);
}
void init(int n)
{
	fac[0] = infac[0] = 1;
	for(int i = 1; i <= n; i++)
		fac[i] = fac[i-1] * i % mod;
	for(int i = 1; i <= n; i++)
		infac[i] = inv(fac[i]);
}
int main()
{
	init(N-10);
	
	int k;
	cin >> k;
	int x;
	for(int i = 1; i <= k; i++)
	{
		cin >> x;
		mx = max(mx, x);
		buk[x]++;
	}
	
	int sz = k - 2;
	ll ini = fac[sz];
	for(int i = 1; i <= mx; i++)
			ini = ini * infac[buk[i]] % mod;
		
    
	ll ans = 0;
	for(int n = 1; n <= sz / n; n++)
	{
		if(sz % n != 0 || !buk[n] || !buk[sz / n])
			continue;
		int m = sz / n;
		if(n == m) ans = (ans + ini * buk[m] % mod * (buk[m] - 1) % mod) % mod;
		else ans = (ans + ini * buk[m] % mod * buk[n] % mod * 2 % mod) % mod;
	}

	cout << ans;
}

F

枚举左右端点，枚举端点，暴力 $O(n^{3})$ 70%

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int fr[N], bc[N];

int main()
{
	string s;
	cin >> s;
	int n = s.size();
	
	fr[0] = 1;
	for(int i = 1; s[i]; i++)
	{
		fr[i] = 1;
		if(s[i] == s[i-1] || s[i] - s[i-1] == 1)
			fr[i] = fr[i-1] + 1;
	}
	
	bc[n-1] = 1;
	for(int i = n-2; i >= 0; i--)
	{
		bc[i] = 1;
		if(s[i+1] == s[i] || s[i+1] - s[i] == 1)
			bc[i] = bc[i+1] + 1;
	}
	
	int cnt = 0;
	for(int l = 0; l < n; l++)
		for(int r = l; r < n; r++)
		{
			if(l == r) {cnt++; continue;}
			for(int k = l; k+1 <= r; k++)
			{
				if(fr[k] >= k-l+1 && bc[k+1] >= r-k) {cnt++; break;}
			}
		}
		
	cout << cnt;
}

优化的对象是很明显的，就是枚举左右端点的过程

因此好串的计数一定不是一个一个算的，一定是一批一批算的

先将好串分类看看，挖掘一下怎么分批算

完全是连续非递减子串
至少存在一个断点，但是保证分割开的两个子子串一定是连续非递减子串

对于1，我们可以找到以r为结尾的最小的l（这个条件保证不会计数遗漏），使得s[l]~s[r]为以r结尾的（这个条件保证不会计数重复）最长连续非递减子串，打包的好串数量为 $r-l+1$

对于2，我们发散1的思维：我们维护一个断点计数器，如果断点>1，则收缩l，直到最多1个断点（注意，假设l为断点，那么l为断点当且仅当l-1也包含，这就是为什么l++，然后查更新后的l是否是断点，如果是，则说明这个断点已经不再是断点了）。同时这个这个断点是对所有的情况都作数的，因此我们只需要扫一遍即可，也就是r不回头，l也不回头，整个算法是 $O(n)$ 的。

参考：P12143 [蓝桥杯 2025 省 A] 好串的数目 - 洛谷 (luogu.com.cn)

主要是想好怎么分批算，还有理解好断点的性质，双指针 $O(n)$

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int main()
{
	string s;
	cin >> s;
	int n = s.size();
	
	int brk = 0;
	i64 ans = 0;
	for(int l = 0, r = 0; r < n; r++)
	{
		if(r && s[r] != s[r-1] && s[r] - s[r-1] != 1)
			brk++;
		while(brk > 1)
		{
			l++;
			if(s[l] != s[l-1] && s[l] - s[l-1] != 1)
				brk--;
		}
		
		ans += r - l + 1;
	}
	
	cout << ans;
}

这个用的是DP，道理类似

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    int n = s.size();

    std::vector<int> pre(n);
    for (int r = 1, l = 0; r < n; r++) {
        if (s[r] != s[r - 1] and s[r] != s[r - 1] + 1) {
            l = r;
        }
        pre[r] = l;
    }
    for (int i = n - 1; i > 0; i--) {
        pre[i] = pre[std::max(0, pre[i] - 1)];
    }

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        ans += i - pre[i] + 1;
    }
    std::cout << ans << "\n";
    
    return 0;
}

G

#include <bits/stdc++.h>
using namespace std;
using db = double;

const int N = 1e5+10;
const db pi = 3.141592653;
struct edge
{
	db l, r;
	bool operator < (const edge& t) const
	{
		return l < t.l;
	}
}e[N];
db n = pi / 2;
db cal(int x, int y)
{
	return sqrt(x*x + y*y);
}
int main()
{
	int m;
	cin >> m;
	for(int i = 1; i <= m; i++)
	{
		int x, y, r;
		cin >> x >> y >> r;
		db d = cal(x, y);
		db k = 1.0 * y / x;
		db ak = atan(k);
		db sin = r / d;
		db ag = asin(sin);
		e[i] = {max(0.0, ak - ag), min(n, ak + ag)};
	}
	
	sort(e+1, e+m+1);
	
	db l = e[1].l, r = e[1].r;
	db ans = n;
	for(int i = 2; i <= m; i++)
	{
		if(e[i].r < r) continue;
		else if(e[i].l < r && e[i].r > r) r = e[i].r;
		else if(e[i].l > r)
		{
			ans -= (r - l);
			l = e[i].l;
			r = e[i].r;
		}
	}
	ans -= (r - l);
	printf("%.3lf", ans / n);
}

H

乐奇 Rokid 开放社区

更多推荐

Word Embedding ：从分布式假设到神经网络语言模型

Word Embedding（词嵌入）是一种将离散的词汇符号映射到连续的低维稠密向量空间的技术。在这个向量空间中，语义相似的词在几何距离上彼此接近，从而实现了从"符号匹配"到"语义计算"的跨越。核心定义词嵌入是将单词（或多词短语）表示为固定维度的实值向量，这些向量之间的距离（例如余弦相似度）反映了单词之间的相关性，这种相关性基于单词通常出现的上下文。分布式假设（1954）↓统计共现分析（LSA/S

乐奇 Rokid 开放社区

镜游小导：运行在 Rokid AR 眼镜上的景区实景讲解智能体

项目以 RokidAIUI 开放智能体形态交付：页面用.ink描述，运行在眼镜端智能体运行时，直接调用系统能力。AGENTS.md身份镜游小导v1.0.0，景区 AR 实景讲解智能体；权限（Capabilities）microphonenetworkaudiogyroscope；技能（Skills）。