复习dddddddd

1.

思路：用队列先进先出的特性

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <list>
#include <map>
#include <set>using namespace std;int main() {int n; cin >> n;queue<pair<int, int>>arr; // 下标，值n = pow(2, n);for (int i = 1; i <= n; i++) {int temp;cin >> temp;arr.push({ i,temp });}while (arr.size() > 2) {auto l = arr.front();arr.pop();auto r = arr.front();arr.pop();if (l.second > r.second)arr.push({ l.first,l.second });else arr.push({ r.first,r.second });}auto l = arr.front();arr.pop();auto r = arr.front();if (l.second > r.second)cout << r.first;else cout << l.first;return 0;
}

 2.

思路：二叉树的数组定义来写

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <list>
#include <map>
#include <set>using namespace std;struct Node {int l, r;
}s[1000001];
int tt = -1;void dfs(int n,int coun) {if (n==0)return;tt = max(tt, coun);dfs(s[n].l, coun + 1);dfs(s[n].r, coun + 1);
}int main() {int n; cin >> n;for (int i = 1; i <= n; i++)cin >> s[i].l >> s[i].r;dfs(1,1);cout << tt << endl;return 0;
}

 3.

思路： 用递归的方法来分出左右子树，以及以其为子节点为节点的左右子树，直到叶子节点

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <list>
#include <map>
#include <set>using namespace std;void func(string& s1, string& s2) {char root = s1[0];int l = s2.find(root), r = s1.size() - l - 1;if (l) {string str1 = s1.substr(1, l), str2 = s2.substr(0, l);func(str1, str2);}if (r) {string str1 = s1.substr(l + 1), str2 = s2.substr(l + 1);func(str1, str2);}cout << root;}int main() {string s1, s2;cin >> s2 >> s1;func(s1, s2);return 0;
}

4.

思路：广搜探索所有的组成方式

#include <iostream>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;typedef pair<string, string> Rule;int bfs(const string& A, const string& B, const vector<Rule>& rules) {if (A == B) return 0;  queue<pair<string, int>> q; q.push({A, 0});unordered_set<string> visited;  visited.insert(A);while (!q.empty()) {auto current = q.front();q.pop();string currentStr = current.first;int steps = current.second;if (currentStr == B) {return steps;}if (steps >= 10) {continue;}for (const auto& rule : rules) {const string& from = rule.first;const string& to = rule.second;size_t pos = currentStr.find(from);while (pos != string::npos) {string newStr = currentStr;newStr.replace(pos, from.length(), to);if (visited.find(newStr) == visited.end()) {visited.insert(newStr);q.push({newStr, steps + 1});}pos = currentStr.find(from, pos + 1);}}}return -1; 
}int main() {string A, B;cin >> A >> B;vector<Rule> rules;string a, b;while (cin >> a >> b) {rules.push_back({a, b});}int result = bfs(A, B, rules);if (result != -1) {cout << result << endl;} else {cout << "NO ANSWER!" << endl;}return 0;
}

 5.算阶

 思路：二进制枚举每个位置上能否放1，经过整个流程后还是1，则则这个位置是1，同时整个的值也要小于m才是ans

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <list>
#include <map>
#include <set>using namespace std;pair<string, int> operations[100005];
int n, m;int calc(int bit, int now) {for (int i = 1; i <= n; i++) {int x = operations[i].second >> bit & 1;if (operations[i].first == "AND") now &= x;else if (operations[i].first == "OR") now |= x;else now ^= x;}return now;
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {char str[5]; int num;scanf("%s%d", str, &num);operations[i] = make_pair(str, num);}int val = 0, ans = 0;for (int bit = 29; bit >= 0; bit--) {int res0 = calc(bit, 0);int res1 = calc(bit, 1);if ((val + (1 << bit)) <= m && res0 < res1) {val += 1 << bit; ans += res1 << bit;}else {ans += res0 << bit;}}cout << ans << endl;return 0;
}

6.

思路：

解题思路

1. 唯一分解定理：
   将 a 分解为素数的乘积：

   a=p1k1​​⋅p2k2​​⋅⋯⋅pnkn​​

   则 ab 的因子和为：

   σ(ab)=(1+p1​+p12​+⋯+p1k1​⋅b​)⋅(1+p2​+p22​+⋯+p2k2​⋅b​)⋅⋯⋅(1+pn​+pn2​+⋯+pnkn​⋅b​)

2. 等比数列求和：
   对于每个素数 pi​，其对应的等比数列和为：

   Si​=1+pi​+pi2​+⋯+piki​⋅b​=pi​−1piki​⋅b+1​−1​

3. 模运算性质：
   由于结果需要对 9901 取模，我们需要在计算过程中对每一步结果取模，避免溢出。

4. 快速幂算法：
   计算 piki​⋅b+1​ 时，使用快速幂算法提高效率。

5. 逆元计算：
   在计算等比数列和时，分母 pi​−1 可能不为 1，因此需要计算 pi​−1 在模 9901 下的逆元。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;const int MOD = 9901;// 快速幂算法
long long fastPow(long long base, long long exp, long long mod) {long long result = 1;while (exp > 0) {if (exp & 1) {result = (result * base) % mod;}base = (base * base) % mod;exp >>= 1;}return result;
}// 扩展欧几里得算法求逆元
int extendedEuclidean(int a, int m, int& x, int& y) {if (m == 0) {x = 1;y = 0;return a;}int x1, y1;int gcd = extendedEuclidean(m, a % m, x1, y1);x = y1;y = x1 - (a / m) * y1;return gcd;
}// 计算 a 在模 m 下的逆元
int modularInverse(int a, int m) {int x, y;int gcd = extendedEuclidean(a, m, x, y);if (gcd != 1) {return -1; // 逆元不存在} else {return (x % m + m) % m; // 确保结果为正}
}// 分解质因数
vector<pair<int, int>> primeFactorization(int n) {vector<pair<int, int>> factors;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {int count = 0;while (n % i == 0) {n /= i;count++;}factors.push_back({i, count});}}if (n > 1) {factors.push_back({n, 1});}return factors;
}// 计算 a^b 的因子和对 MOD 取模
int sumOfDivisors(int a, int b) {if (a == 0) return 0; // 0^b 的因子和为 0if (b == 0) return 1; // a^0 的因子和为 1// 分解质因数vector<pair<int, int>> factors = primeFactorization(a);long long result = 1;for (const auto& factor : factors) {int p = factor.first;int k = factor.second;// 计算等比数列和 S = (p^(k*b + 1) - 1) / (p - 1)long long numerator = (fastPow(p, k * b + 1, MOD) - 1 + MOD) % MOD;long long denominator = (p - 1) % MOD;// 如果 p == 1，等比数列和为 k * b + 1if (p == 1) {result = (result * (k * b + 1)) % MOD;continue;}// 计算分母的逆元int inv = modularInverse(denominator, MOD);if (inv == -1) {// 如果分母为 0，等比数列和为 k * b + 1result = (result * (k * b + 1)) % MOD;} else {// 计算 S 并对 MOD 取模long long S = (numerator * inv) % MOD;result = (result * S) % MOD;}}return result;
}int main() {int a, b;cin >> a >> b;cout << sumOfDivisors(a, b) << endl;return 0;
}

 7.逆元

逆元是数论中的一个重要概念，尤其在模运算中广泛应用。它的核心思想是解决模意义下的“除法”问题。因为模运算中除法并不直接定义，而是通过乘法逆元来实现。

---

1. 逆元的定义

给定一个整数 a 和一个模数 m，如果存在一个整数 x，使得：

a⋅x≡1(modm)

则称 x 是 a 在模 m 下的乘法逆元，记作 a−1。

---

2. 将模等式转化为常规等式

模等式 a⋅x≡1(modm) 可以转化为常规等式：

a⋅x+m⋅k=1

其中 k 是某个整数。这个等式表明，a⋅x 与 1 的差是 m 的倍数。

---

3. 逆元的存在条件

a 在模 m 下的逆元存在的充要条件是 a 和 m 互质，即：

gcd(a,m)=1

如果 a 和 m 不互质，则 a 在模 m 下没有逆元。

---

4. 逆元的计算方法

(1) 扩展欧几里得算法

扩展欧几里得算法可以求解方程 a⋅x+m⋅k=1。如果 gcd(a,m)=1，则 x 就是 a 在模 m 下的逆元。

步骤：

1. 使用扩展欧几里得算法求解 gcd(a,m) 以及 x 和 k。
2. 如果 gcd(a,m)=1，则 x 是 a 的逆元。
3. 将 x 调整为正数（通过取模）。

#include <iostream>
using namespace std;// 扩展欧几里得算法
int extendedEuclidean(int a, int m, int& x, int& y) {if (m == 0) {x = 1;y = 0;return a;}int x1, y1;int gcd = extendedEuclidean(m, a % m, x1, y1);x = y1;y = x1 - (a / m) * y1;return gcd;
}// 计算 a 在模 m 下的逆元
int modularInverse(int a, int m) {int x, y;int gcd = extendedEuclidean(a, m, x, y);if (gcd != 1) {return -1; // 逆元不存在} else {return (x % m + m) % m; // 确保结果为正}
}int main() {int a, m;cout << "请输入 a 和 m: ";cin >> a >> m;int inv = modularInverse(a, m);if (inv == -1) {cout << a << " 在模 " << m << " 下没有逆元。" << endl;} else {cout << a << " 在模 " << m << " 下的逆元是: " << inv << endl;}return 0;
}

 

(2) 费马小定理

如果模数 m 是素数，且 a 不是 m 的倍数，则根据费马小定理：

a^m−1≡1(modm)

因此，a 的逆元为：

a−1≡a^m−2(modm)

#include <iostream>
using namespace std;// 快速幂算法
long long fastPow(long long a, long long b, long long mod) {long long result = 1;while (b > 0) {if (b & 1) {result = (result * a) % mod;}a = (a * a) % mod;b >>= 1;}return result;
}// 计算 a 在模 m 下的逆元（费马小定理）
int modularInverse(int a, int m) {return fastPow(a, m - 2, m);
}int main() {int a, m;cout << "请输入 a 和 m: ";cin >> a >> m;if (m <= 1 || a % m == 0) {cout << a << " 在模 " << m << " 下没有逆元。" << endl;} else {int inv = modularInverse(a, m);cout << a << " 在模 " << m << " 下的逆元是: " << inv << endl;}return 0;
}

逆元运用

5. 逆元的应用

1. 模意义下的除法：
   • 在模运算中，a/b 等价于 a⋅b−1(modm)。
2. 线性同余方程：
   • 解方程 a⋅x≡b(modm) 时，需要用到 a 的逆元。
3. 组合数学：
   • 计算组合数 C(n,k) 时，通常需要用到模意义下的除法。
4. 密码学：
   • RSA 加密算法中，逆元用于计算私钥。