P2671. 求和

发表于 分类于 阅读次数： Waline： 本文字数： 465 阅读时长 ≈ 2 分钟

考点

  • 模拟

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50, mod = 10007;
int n, m, ans, color[maxn], num[maxn], cnt[maxn][2], sum[maxn][2];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> num[i];
  for (int i = 1; i <= n; ++i) cin >> color[i];
  for (int i = 1; i <= n; ++i) {
    ++cnt[color[i]][i & 1];
    sum[color[i]][i & 1] = (sum[color[i]][i & 1] + i) % mod;
  }
  for (int c, t, i = 1; i <= n; ++i) {
    c = color[i];
    if (cnt[c][i & 1] >= 2) {
      t = 1ll * num[i] * (sum[c][i & 1] + 1ll * i * (cnt[c][i & 1] - 2) % mod) %
          mod;
      ans = (ans + t) % mod;
    }
  }
  cout << ans;
  return 0;
}

思路

根据题意，y - x = z - y得到(x + z) / 2 = y，且x、y、z三者均为整数；

那么x和z的奇偶性必须相同，因为奇 + 奇或偶 + 偶才会等于偶数啊；题目还说colorx和colorz也要相同。

有个大概思路，使用二维数组，行代表颜色，列代表奇偶性来对编号进行分类。

假设有编号1-5：

  • 1、3、5颜色等于A
  • 2颜色等于A
  • 4颜色等于B

数组情况如下：

奇数 偶数
颜色A 1、3、5 2
颜色B 4

根据题目要求，即求1、3、5三个编号中两两对(x + z) * (numberx + numberz)的和。

拆开来看，答案等于下列三个式子相加： $$ ans \[\begin{cases} 1number_1+1number_3+3number_1+3number_3\\ 1number_1+1number_5+5number_1+5number_5\\ 3number_3+3number_5+5number_3+5number_5\\ \end{cases}\]

\

\ \[ 合并同类项，发现规律： \] ans \[\begin{cases} \left( 1+1+3+5 \right) number_1\\ \left( 3+1+3+5 \right) number_3\\ \left( 5+1+3+5 \right) number_5\\ \end{cases}\]

\

\ $$ 其中1 + 3 + 5是同颜色同奇偶集合内的编号和，设为\(sum\left[ color_i \right] \left[ i\&1 \right]\)

设\(cnt\left[ color_i \right] \left[ i\&1 \right]\)是同颜色同奇偶集合内的个数

那么每个i对结果的贡献就是： \[ number_i\times \left\{ \left( cnt\left[ color_i \right] \left[ i\&1 \right] -2 \right) \times i+sum\left[ color_i \right] \left[ i\&1 \right] \right\} \]