鼠鼠我鸭
没学过前缀和的自己去补一下，这里不过多赘述（其实是我不想写）
以第二组数据为例：
| 类型 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|
| 体重 | 2 | 5 | 6 | 5 |
先计算出不使用魔法时鸭鸭的重量，当作基础值\(ori=5\)。
然后来看看对一段区间使用魔法会造成什么效果：
| 类型 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|
| 体重 | 2 | 5 | 6 | 5 |
| 变化a | +2 | -5 | +6 | +5 |
比如，如果选择了区间\([1,2]\)，我们得到的答案就是\(ans=ori+2-5=2\)。
于是这个问题就变成了对\(a\)数组求最大子段和。
特别地，如果最大子段和为负，答案是前面算的基础值。
我们已知可以利用前缀和快速求出一段区间的和，就像这样\(fix=prefix[r]-prefix[l-1]\)。
所以现在需要做的事情就是找到这个区间的两端\(l\)和\(r\)。
可以采用以下这种方法：
枚举区间的右端点，此时\(prefix[r]\)就确定下来了。
那么要让\(fix\)最大，就要让\(prefix[l-1]\)最小。
\(\mathscr{finish}\)
void solve()
{
int n;cin >> n;
for (int i = 1; i <= n; ++ i)std::cin >> a[i];
for (int i = 1; i <= n; ++ i)std::cin >> w[i];
ll ori = 0;//不使用魔法的结果
for (int i = 1; i <= n; ++ i) ori += a[i] * w[i];
ll mn = 0, fix = 0;//mn表示min(prefix[j]),0 <= j < i
for (int i = 1; i <= n; ++ i)
{
prefix[i] = prefix[i - 1] + (a[i] ? -1 : 1) * w[i];
fix = std::max(fix, prefix[i] - mn);
mn = std::min(mn, prefix[i]);
}
std::cout << ori + fix << '\n';
}
二维前缀和
这个题其实也可以用\(n\)个一维前缀和，我做的数据没有刻意卡这种做法，但是这样每次查询的复杂度是\(O(n)\)，真到比赛的时候想卡掉其实也不难。
定义一个二维数组\(prefix\)，其中\(prefix[i][j]\)存储从\((1,1)\)到\((i,j)\)这个矩阵所有元素的和。
查询的过程可能有点抽象，这里贴张图
比如，要查询红色矩阵中所有元素的和\(sum_红=绿-蓝-黄+紫\)。（注意紫色部分减了两次，要加一次）
这样就结束了
void solve()
{
int n, m, q;std::cin >> n >> m >> q;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
std::cin >> a[i][j];
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
while(q --)
{
int x1, x2, y1, y2;
std::cin >> x1 >> y1 >> x2 >> y2;
ll ans = p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1];
std::cout << ans << '\n';
}
}
我们需要0
这个题单纯考一点异或的性质，不会直接百度，直接上计算过程，以\(n\)为\(5\)举例：
-
\(b_1\oplus b_2\oplus b_3\oplus b_4\oplus b_5=0\)
-
\(a_1\oplus x\oplus a_2\oplus x\oplus a_3\oplus x\oplus a_4\oplus x\oplus a_5\oplus x=0\)
-
\(a_1\oplus a_2\oplus a_3\oplus a_4\oplus a_5\oplus x\oplus x\oplus x\oplus x\oplus x=0\)
-
\(a_1\oplus a_2\oplus a_3\oplus a_4\oplus a_5\oplus x=0\)
-
\(a_1\oplus a_2\oplus a_3\oplus a_4\oplus a_5=x\)
已经说明\(n\)为奇数，所以推最后一定会剩一个\(x\)，也就是这样\(a_1\oplus a_2\oplus a_3...\oplus x=0\)。
所以\(x\)一定存在且唯一，没有输出-1的情况。
void solve()
{
int n;std::cin >> n;
ll ans = 0;
for (int i = 1; i <= n; ++ i)
{
int x;cin >> x;
ans ^= x;
}
std::cout << ans << '\n';
}