2025年第十六届蓝桥杯软件赛省赛C/C++大学A组个人解题

https://www.dotcpp.com/oj/train/1166/

题目A

找到第2025个素数

#include <iostream>  
#include <vector>  using namespace std;  vector<int> primes = {2,3,5,7};  
void init_primes(int n) {  auto check_prime = [&](int x) {  return std::all_of(primes.begin(), primes.end(), [x](int p) {  return x % p != 0;  });  };  int ii = primes.size(), x = primes.back() + 2;  while (ii < n) {  if (check_prime(x)) primes.push_back(x), ++ii;  x += 2;  }  
}  int main() {  init_primes(2025);  cout << primes.back() << endl;  return 0;  
}

题目C：抽奖

顾名思义

#include <iostream>  
#include <vector>  
#include <algorithm>  using namespace std;  typedef long long ll;  vector<int> inputVecI(int n) {  vector<int> a(n);  for (int i = 0; i < n; ++i) {  cin >> a[i];  }  return a;  
}  ll get_score(vector<int> &v) {  if ((v[0] == v[1] and v[1] == v[2]) or (v[0] + 1 == v[1] and v[1] + 1 == v[2])) return 200;  
//    ranges::sort(v);  std::sort(v.begin(), v.end());  if ((v[0] == v[1] or v[1] == v[2]) or (v[0] + 1 == v[1] and v[1] + 1 == v[2])) return 100;  return 0;  
}  void solve() {  int n, m;  ll ans = 0;  cin >> n;  vector<int> a(n),b(n),c(n);  int ia = 0, ib = 0, ic = 0;  for (int i = 0; i < n; ++i) cin >> a[i];  for (int i = 0; i < n; ++i) cin >> b[i];  for (int i = 0; i < n; ++i) cin >> c[i];  cin >> m;  for (int i = 0; i < m; ++i) {  vector<int> v = inputVecI(3);  ia = (ia + v[0]) % n;  ib = (ib + v[1]) % n;  ic = (ic + v[2]) % n;  v[0] = a[ia], v[1] = b[ib], v[2] = c[ic];  ans += get_score(v);  }  cout << ans << endl;  
}  int main() {  solve();  return 0;  
}

题目D：红黑树

对于一颗红黑树具有的性质是：

• 下一层的左半行的颜色等于上一层。
• 每一层右半行的颜色和左半行的颜色相反。
• 左孩子和父结点颜色相同，右孩子和父节点颜色相反。

二叉树的性质：
对于一颗00开始编号的二叉树（顶点从0开始编号，行号从0开始编号），具有以下性质：

   01 2
3 4 5 6

其节点<i,j>（第i行，第j个）满足：

• 编号等于$2^i-1+j$
• 其父节点是<i-1,[j/2]>。如果j是偶数则是左孩子，奇数则是右孩子。

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <stack>  
using namespace std;  typedef long long ll;  void solve() {  int n, m;  cin >> n >> m;  --n, --m;  /*  * 思路：回溯到根结点，再根据每次的孩子方向迭代颜色  * 优化：如果以0表示向左，1表示向右，则0--0 => 0, 0--1 => 1, 1--0==>0, 1--1 => 1。这其实就是异或运算。  *///    stack<int> trace, direction;  int color = 0;  while (n >= 0) {  
//        trace.push(n);  
//        direction.push(m & 1);  color ^= m & 1;  --n;  m >>= 1;  }  cout << (color ? "BLACK" : "RED") << endl;  }  int main() {  int t;cin>>t;  while (t--) solve();  return 0;  
}

题目E：黑客

题意：
给一个长度为n+2的数组a，取a中的两个数作为矩阵长宽，求可以组合为多少种矩阵？

思路1：
我们二维的矩阵和它展开成一维是数组是1:1映射关系，因此我们只需要求，取两个长宽数后数组的排列数即可
首先将剩下的数组转为counter

枚举长宽，然后
根据排列组合原理计算排列数即可
例如我们有一个长度为9的数组

1 1 1， 2 2 2， 3， 4 4

它的排列数为
$$C_9^3+C_6^3+C_3^1+C_2^2$$

[!NOTE] 逆元
对于x满足 $a\ast x\%p=1\%p$，则称$x$是$a$的逆元(1逆元)，记作$x=inv(a)$
如果我们把$\%p$去掉，此时$x=\frac{1}{a}$
模下除法必须用到1逆元
$\frac{a}{b}\%p=a\ast inv(b)$

#include <iostream>  
#include <vector>  
#include <map>  
#include <algorithm>  
#include <cmath>  
using namespace std;  
//#define int long long  
typedef long long ll;  
const ll MOD = 1000000007;  template<typename T>  
T next() {  T _;  cin >> _;  return _;  
}  // 快速逆元(快速幂求逆元)  
ll quick_inv(ll a, ll b) {  ll res = 1;  while (b) {  if (b & 1) res = res * a % MOD;  a = a * a % MOD;  b >>= 1;  }  return res;  
}  vector<ll> fac, inv;     // 阶乘查询数组，逆元查询数组  
void init_fac_and_inv(int n) {  fac = vector<ll>(n+1), inv = vector<ll>(n+1);  fac[0] = inv[0] = 1;  for (int i = 1; i < n; ++i) {  fac[i] = fac[i-1] * i % MOD;  }  inv[n-1] = quick_inv(fac[n-1], MOD-2);  // 用费马小定理求逆元  for (int i = n - 2; i >= 1; --i) {  inv[i] = inv[i+1] * (i + 1) % MOD;  }  
}  // 求C(n,k) mod MOD  
ll quick_comb(ll n, ll k) {  if (k < 0 or k > n) return 0;  return fac[n] * inv[k] % MOD * inv[n-k] % MOD;  
}  // 计算组合数  
/*ll combination(ll n, ll m) {  if (m > (n >> 1)) m = n - m;    ll res = 1;    for (ll i = 0; i < m; ++i) res *= n--;    while (m > 1) res /= m--;    return res;}  
map<pair<ll,ll>, ll> cache_combination; // 缓存  
ll comb(ll n, ll m) {  pair<ll,ll> nm = make_pair(n,m);    if (cache_combination.find(nm) != cache_combination.end()) return cache_combination[nm];//    ll res = combination(n, m) % MOD;  ll res = quick_comb(n, m) % MOD;    cache_combination[nm] = res;    return res;}*/  // 计算一个counter的组合数  
ll comb_counter(const map<ll, ll> &counter, ll n) {  ll res = 1;  for (const auto &it: counter) {  // res *= comb(n, it.second);  res *= quick_comb(n, it.second);  n -= it.second;  res %= MOD;  }  return res;  
}  void solve() {  ll n;  ll ans = 0;  cin >> n;  init_fac_and_inv((int)n);  map<ll, ll> counter;  for (ll i = 0; i < n; ++i) ++counter[next<ll>()];  /*  * 二维转一维，将矩阵看成是数组。  */    n -= 2;     // n 为数组的实际长度  // 枚举矩阵可能的形状（r行c列）  ll r_max = (ll) sqrt(n);  for (ll r = 1; r <= r_max; ++r) {  
//        ll r = it.first;  if (n % r) continue;    // 不能被整除  ll c = n / r;  if (r == c) {  if (counter[r] >= 2) counter[r] -= 2;  else continue;  } else {  if (counter[r] >= 1 and counter[c] >= 1) --counter[r], --counter[c];  else continue;  }  
//        printf_s("matrix: %d %d\n", r, c);  ans += (r == c ? comb_counter(counter, n) : comb_counter(counter, n) << 1); // 如果行列数不相等，我们把行列互换也可以得到一个相等的结果  
//        printf_s(">  %lld\n", (r == c ? comb_counter(counter, n) : comb_counter(counter, n) << 1));  ans %= MOD;  ++counter[r], ++counter[c];  }  cout << ans << endl;  
}  int main() {  
//    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);  /*int t;cin>>t;    while (t--)*/ solve();  return 0;  
}

题目F：好串的数目

题意：
好串：能分割成2个非递减子串的串；长度为1的（1个字符）也是好串
给一个整数字符串，求它的子串是好串的数目。

思路：
排列组合原理
例如对于输入

1225568

我们先将它拆分成一个个非递减的子段

122 556 8

他们的长度分别是

3 3 1

对于这些子段：

• 我们取它的任意一个子串都是好串
  • 例如对于122，122 12 22 1 等都是好串。一共有$C_n^2$个（n是子段长度）
• 对于两个相邻的子段，我们将它们组合再掐头去尾，也是好串
  • 例如对于122 + 556， 12256 2556 等都是好串。一个有$n_{i-1}\cdot n_i$个（n是子段长度）

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <stack>  
using namespace std;  typedef long long ll;  void solve() {  string s;  cin >> s;  vector<ll> a;  ll ls = s[0] - '0', cnt = 0, ans = 0;  for (char i : s) {  int cur = i - '0';  if (cur == ls or cur == ls + 1) ++cnt;  else a.push_back(cnt), cnt = 1;  ls = cur;  }  a.push_back(cnt);  for (int i = 0; i < a.size(); ++i) {  if (i > 0) ans += a[i] * a[i-1];  ans += a[i] * (a[i] + 1) / 2;  }  cout << ans << endl;  
}  int main() {  /*int t;cin>>t;  while (t--)*/ solve();  return 0;  
}