第三周
DAY 1
在家里偷懒 （也是生病了） ，所以没来，就没写了。
DAY 2
解方程
为了解决这个问题，我们需要在给定的区间内找到多项式方程的整数解。由于多项式的系数可能非常大（高达10^10000），直接计算是不现实的。因此，我们采用模运算的方法，通过多个质数来验证可能的解，从而高效地筛选出整数解。
方法思路
- 问题分析：给定一个多项式方程，我们需要在区间[1, m]内找到所有整数解。多项式的系数可能非常大，直接计算每个x的值是不可行的。
- 模运算筛选：选择多个质数，对每个质数计算多项式在模意义下的值。如果对于某个x，多项式在所有质数下取模的结果都为0，则认为x是一个可能的解。
- 秦九韶算法：使用秦九韶算法高效计算多项式在模意义下的值，该算法将多项式从高次项到低次项逐步计算，减少计算量。
- 系数处理：将大系数字符串转换为每个质数模下的整数，处理负号情况，确保系数在模意义下为非负数。利用模运算和秦九韶算法，避免了直接处理大系数，确保在较大范围内快速找到所有整数解。
- 解验证：遍历区间[1, m]内的每个整数x，检查x在所有质数下是否满足多项式取模为0。满足条件的x即为解。
- 字符串转模函数）：将大整数字符串转换为在给定质数模下的整数。处理负号情况，确保结果非负。
解决代码
#include<bits/stdc++.h>
#define int long long
using namespace std;int str2mod(const string& s, int mod) {int res = 0;int start = 0;if (s[0] == '-') {start = 1;}for (int i = start; i < s.size(); i++) {res = (res * 10 + (s[i] - '0')) % mod;}if (s[0] == '-') {res = (mod - res) % mod;}return res;
}
signed main() {vector<int> pr = {10007, 10009, 10037, 10039, 10061};//选择5个质数（10007, 10009, 10037, 10039, 10061）用于模运算验证。int n, m;cin >> n >> m;vector<string> a(n + 1);for (int i = 0; i <= n; i++) {cin >> a[i];}vector<vector<int>> mo(n + 1, vector<int>(5, 0));for (int j = 0; j < 5; j++) {for (int i = 0; i <= n; i++) {mo[i][j] = str2mod(a[i], pr[j]);}}vector<vector<bool>> flag(5);for (int j = 0; j < 5; j++) {flag[j].resize(pr[j], false);}for (int j = 0; j < 5; j++) {int P = pr[j];for (int r = 0; r < P; r++) {int res = 0;for (int i = n; i >= 0; i--) {res = (res * r + mo[i][j]) % P;}if (res % P == 0) {flag[j][r] = true;}}}//对每个质数，使用秦九韶算法计算多项式在0到质数-1范围内每个整数的模值。如果结果为0，标记该值为解。vector<int> ans;for (int x = 1; x <= m; x++) {bool v = true;for (int j = 0; j < 5; j++) {int P = pr[j];int r = x % P;if (!flag[j][r]) {v = false;break;}}if (v) {//遍历区间[1, m]内的每个整数x，检查x在所有质数下是否均被标记为解。满足条件的x存入结果数组。ans.push_back(x);}}cout << ans.size() << endl;for (int x : ans) {cout << x << endl;}return 0;
}
Large Queue
为了解决这个问题，我们需要高效地处理一个序列的两种操作：在序列末尾添加多个相同元素，以及从序列开头移除多个元素并计算它们的和。由于操作次数和元素数量可能非常大（高达 (2 \times 10^5) 次操作和 (10^9) 个元素），直接存储每个元素是不现实的。因此，我们采用分段存储的方法，将连续相同的元素视为一段，从而显著减少存储和操作的开销。
方法思路
- 分段存储：使用双端队列（
deque）存储序列，每个元素是一个对(x, c)，表示连续c个值为x的元素。使用deque存储序列段，每个段为(x, c)对，表示c个值为x的元素。 - 添加操作（类型1）：将新元素添加到队尾。如果新元素的值与队尾元素的值相同，则合并到队尾段中；否则，新建一个段添加到队尾。
- 移除操作（类型2）：从队头开始移除元素。如果队头段的元素数量不足
k，则整个移除该段并累加其和；否则，移除部分元素并累加相应和，更新队头段的剩余元素数量。 - 高效处理：通过分段存储和合并操作，确保每个段最多被处理一次（完全移除或部分移除），使得总时间复杂度为 (O(Q))，其中 (Q) 是操作次数。
- 初始化：少了存储和计算开销，能够高效处理大规模操作，符合题目要求的时间和空间复杂度。
解决代码
#include<bits/stdc++.h>
#define int long long
using namespace std;signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int Q;cin >> Q;deque<pair<int,int> > dq;while (Q--) {int type;cin >> type;if (type == 1) {//读取 `c` 和 `x`，表示添加 `c` 个值为 `x` 的元素。//如果队尾段的值与 `x` 相同，则合并到队尾段（增加 `c` 到队尾段的计数）；否则，新建一个段添加到队尾。int c, x;cin >> c >> x;if (!dq.empty() && dq.back().first == x) {dq.back().second += c;} else {dq.push_back(make_pair(x, c));}} else {//读取 `k`，表示要移除的元素数量。//初始化 `sum` 为 0，用于累加被移除元素的和。//环处理队头段，直到移除 `k` 个元素：//如果队头段的元素数量 `c` 小于或等于 `k`，则累加整个段的和（`x * c`），从队列中移除该段，并减少 `k` 的值。否则，累加部分元素的和（`x * k`），更新队头 段的剩余元素数量（`c - k`），并设置 `k` 为 0。//输出累加和 `sum`。int k;cin >> k;int sum = 0;while (k > 0) {auto& front = dq.front();if (front.second <= k) {sum += front.first * front.second;k -= front.second;dq.pop_front();} else {sum += front.first * k;front.second -= k;k = 0;}}cout << sum << '\n';}}return 0;
}
Make Geometric Sequence
为了解决这个问题，我们需要判断给定的整数序列是否可以重排成一个等比数列。等比数列要求存在一个实数公比 ( r )，使得序列中任意相邻两项满足 ( B_{i+1} = r \times B_i )。由于序列中的元素都是整数，公比 ( r ) 必须是有理数，且重排后的序列必须满足整数条件。
方法思路
-
特殊情况处理：
- 如果序列长度为 2，则一定可以重排成等比数列（公比为 ( B_1 / B_0 )，且 ( B_0 ) 和 ( B_1 ) 均不为零）。
- 如果序列中所有元素相同，则公比为 1，可以构成等比数列。
- 处理了序列重排问题，通过分组和条件验证确保在给定的约束下正确判断序列是否可以重排成等比数列。
-
分组处理：
- 将序列中的元素按绝对值分组，因为相同绝对值的元素可能以正数或负数的形式出现。
- 对于每组相同绝对值的元素：
- 如果组内只有正数或只有负数，则直接将这些元素按顺序放入候选序列。
- 如果组内同时存在正数和负数，则检查正数和负数的数量差是否不超过 1。如果是，则按交替符号的方式排列元素（数量较多的符号先出现）；否则，无法形成等比数列。
- 将元素按绝对值分组，统计每组中正数和负数的数量。
- 如果组内只有正数或负数，直接按顺序放入候选序列。
- 如果组内同时存在正负数且数量差不超过 1，则按交替符号排列；否则，标记为无效。
-
构造候选序列：
- 将分组处理后的元素按绝对值从小到大的顺序排列，形成候选序列。
-
验证等比数列条件：
- 相邻三项条件：对于候选序列中的每个中间项 ( B_i )，检查是否满足 ( B_i^2 = B_{i-1} \times B_{i+1} )。
- 符号模式条件：
- 根据序列的前两项确定公比的符号（正或负）。
- 如果公比为正，则序列中所有元素符号必须一致。
- 如果公比为负，则序列中元素的符号必须交替出现（以第一项的符号开始）。
- 验证等比数列条件：
- 相邻三项条件：检查候选序列中每个中间项的平方是否等于其前后两项的乘积。
- 符号模式条件：根据前两项的乘积符号，验证整个序列的符号是否符合公比符号的规律（全同号或交替出现）。
解决代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while (T--) {//读取测试用例的数量 \( T \)，并处理每个测试用例。int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}//特殊情况处理：如果序列长度为 2，直接输出 "Yes"。//如果序列中所有元素相同，输出 "Yes"。if (n == 2) {cout << "Yes\n";continue;}bool ai = true;for (int i = 1; i < n; i++) {if (a[i] != a[0]) {ai = false;break;}}if (ai) {cout << "Yes\n";continue;}map<int, vector<int>> g;for (int x : a) {int key = abs(x);g[key].push_back(x);}vector<int> b;bool tot = true;for (const auto& p : g) {int base = p.first;const vector<int>& vec = p.second;int count_pos = 0;int count_neg = 0;for (int x : vec) {if (x > 0) count_pos++;else if (x < 0) count_neg++;}if (count_neg == 0) {for (int i = 0; i < vec.size(); i++) {b.push_back(base);}} else if (count_pos == 0) {for (int i = 0; i < vec.size(); i++) {b.push_back(-base);}} else {if (abs(count_pos - count_neg) > 1) {tot = false;break;}int total = vec.size();int num = (count_pos >= count_neg) ? 1 : -1;if (num == 1) {for (int i = 0; i < total; i++) {if (i % 2 == 0) {b.push_back(base);} else {b.push_back(-base);}}} else {for (int i = 0; i < total; i++) {if (i % 2 == 0) {b.push_back(-base);} else {b.push_back(base);}}}}}if (!tot) {cout << "No\n";continue;}if (b.size() != n) {cout << "No\n";continue;}bool tot2 = true;if (n >= 3) {for (int i = 1; i < n - 1; i++) {if ((int) b[i] * b[i] != (int) b[i - 1] * b[i + 1]) {tot2 = false;break;}}}if (tot2 && n >= 2) {if ((int) b[0] * b[1] > 0) {for (int i = 0; i < n; i++) {if ((b[0] > 0 && b[i] < 0) || (b[0] < 0 && b[i] > 0)) {tot2 = false;break;}}} else {for (int i = 0; i < n; i++) {if (i % 2 == 0) {if ((b[0] > 0 && b[i] < 0) || (b[0] < 0 && b[i] > 0)) {tot2 = false;break;}} else {if ((b[0] > 0 && b[i] > 0) || (b[0] < 0 && b[i] < 0)) {tot2 = false;break;}}}}}if (tot2) {cout << "Yes\n";} else {cout << "No\n";}}return 0;
}