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?x\%p=1\%p$，則稱$x$是$a$的逆元(1逆元)，記作$x=inv(a)$
如果我們把$\%p$去掉，此時$x=\frac{1}{a}$
模下除法必須用到1逆元
$\frac{a}{b}\%p=a?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}?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;  
}