五十中东校信息学集训冬令营第 \(1\) 次课作业题解
作者：\(\text{DoubleQBarcaLzn}\)
抓娃娃
本题考察前缀和的运用。
本题的突破口在于 \(\max\{r_i-l_i\}<\min\{R_i-L_i\}\)。
思考一个可以覆盖区间 \([l_i,r_i]\) 的区间需要满足的性质。
由于需要满足一半，对于任意一个区间 \([l_i+k,l_i+k+(r_i+l_i-1)\div 2]\) 且 \(l_i+k+(r_i+l_i-1)\div 2\le r_i\)，必将覆盖线段的中点。
因此，考虑进行前缀和，求答案即可。
时间复杂度：\(O(n+q+w)\)
空间复杂度：\(O(w)\)
#include <bits/stdc++.h>
using namespace std;
int sum[2000005];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,q;cin >> n >> q;for (int i = 1;i <= n;i++){int l,r;cin >> l >> r;l *= 2,r *= 2;sum[(l + r) / 2]++;}for (int i = 1;i <= 2000000;i++) sum[i] += sum[i - 1];for (int i = 1;i <= q;i++){int l,r;cin >> l >> r;l *= 2,r *= 2;cout << sum[r] - sum[l - 1] << '\n';}return 0;
}
消灭怪兽
我们考虑暴力，如果使用前缀和，则对于任意 \(l,r\) 要符合条件，有：
- \(sum_r-sum_{l-1}\bmod k=0\)
换言之，\(sum_r\) 与 \(sum_{l-1}\) 对 \(k\) 同余。
所以，我们可以存储所有 \(sum_i\) 对 \(k\) 取模，然后计算从任意 \(sum_i\) 中选取 \(2\) 个数，即 \(C^2_{sum_i}\)。
时间复杂度：\(O(n+k)\)
空间复杂度：\(O(n+k)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000005],f[1000005],n,k,x;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> k;int s = 0,ans = 0;for (int i = 1;i <= n;i++){cin >> x;s = s + x;if (s % k == 0) ans++;f[s % k]++;}for (int i = 0;i < k;i++) ans = ans + (f[i] * (f[i] - 1) / 2); cout << ans;return 0;
}
区间反转区间异或和
本题中，翻转是 无意义的。
所以，我们统计异或前缀和，并且考虑到 \(x\oplus x=0\)，所以统计所有数出现次数 \(a\) 中，答案加上 \(C^2_a\) 即可。
记得加上 \(f_0(xo_0=0)\)。
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100005],xo[100005];
unordered_map<int,int> f;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];f[0]++;for (int i = 1;i <= n;i++) {xo[i] = (xo[i - 1] ^ a[i]);f[xo[i]]++;}int ans = 0;for (auto k : f) ans += k.second * (k.second - 1) / 2;cout << ans;return 0;
}
挖矿
本题中，我们可以以 \(0\) 为分界，存下 \(0\) 左边与 \(0\) 右边的矿洞数量，并作前缀和统计。
随后，我们可以枚举折返长度 \(i\)。分两种情况。
- 先往数轴左边方向，可以得到 \(l_i\)。如果 \(m>2\times i\)，额外得到 \(r_{m-2\times i}\)。
- 先往数轴左边方向，可以得到 \(r_i\)。如果 \(m>2\times i\)，额外得到 \(l_{m-2\times i}\)。
最终加上在 \(0\) 的矿石数量即可。
时间复杂度：\(O(n+m)\)
空间复杂度：\(O(m)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,l[2000005],r[2000005];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m,x;cin >> n >> m;int s = 0;while (n--){cin >> x;if (x < 0) l[-x]++;if (x > 0) r[x]++;if (x == 0) s++;}for (int i = 1;i <= m;i++) l[i] += l[i - 1],r[i] += r[i - 1];int ans = 0,is = 0;for (int i = 1,t;i <= m;i++){is = 0;t = l[i];if (m - i * 2 > 0)is = 1;if (is) ans = max(ans,t + is * r[m - i * 2]);else ans = max(ans,t);t = r[i];if (is) ans = max(ans,t + is * l[m - i * 2]);else ans = max(ans,t);}cout << ans + s;return 0;
}
领地选择
考察二维前缀和，由于是模板题，这里我重复一次原理。
理论上，应该还是 \(sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}\)。
但是我们可以发现，这样的查询 不准确。我们考虑容斥。
因为 \(S_{i-1,j-1}\) 被重复计算，所以在递推时减掉即可。
最后考虑如何查询，即为
最后枚举右下角，查询输出即可。
时间复杂度：\(O(nm)\)
空间复杂度：\(O(nm)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int s[1005][1005],a[1005][1005];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m,c,ma = INT_MIN,x,y;cin >> n >> m >> c;for (int i = 1;i <= n;i++){for (int j = 1;j <= m;j++) cin >> a[i][j];}for (int i = 1;i <= n;i++){for (int j = 1;j <= m;j++) s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];}for (int i = c;i <= n;i++){for (int j = c;j <= m;j++){int t = s[i][j] - s[i - c][j] - s[i][j - c] + s[i - c][j - c];if (t > ma){ma = t;x = i - c + 1,y = j - c + 1;}}}cout << x << ' ' << y;return 0;
}
激光炸弹
类似于上一题，仅仅改变输入输出。
时间复杂度：\(O(n+w^2)\)
空间复杂度：\(O(n+w^2)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int s[5005][5005],a[5005][5005];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m,c,ma = INT_MIN,x,y;cin >> n >> c;while (n--){int s;cin >> x >> y >> s;++x,++y;a[x][y] += s;}for (int i = 1;i <= 5000;i++){for (int j = 1;j <= 5000;j++) s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];}for (int i = c;i <= 5000;i++){for (int j = c;j <= 5000;j++){int t = s[i][j] - s[i - c][j] - s[i][j - c] + s[i - c][j - c];if (t > ma){ma = t;x = i - c + 1,y = j - c + 1;}}}cout << ma;return 0;
}