我想问一下思路是否存在问题,如果思路存在,麻烦指出如果思路不存在问题,请求帮改一下代码
我的思路:求奇偶性相同且颜色格子的x∗numberx、x、numberx前缀和. 遍历奇偶相同且颜色相同的格子组成的数组,当遍历到k时[k+1,数组大小−1]内的格子与k一定满足题设条件。
代码如下,案例2没得到正确的答案......
#include <bits/stdc++.h>
//----mxcro----------------
#define MAXN int(2e3 + 5)
#define BASE 121
#define MOD 10007
#define endl '\n'
#define rep(i, starts, ends) for(int i = starts; i <= ends; ++i)
//----namespace------------
using namespace std;
//----struct---------------
struct node{
int id, color, number;
};
//----constxnt-------------
const double eps = 1e-4;
//----verious-------------
//----mathod-----------
void solve() {
int n, m;
cin >> n >> m;
node a[n + 1];
rep(i, 1, n) cin >> a[i].number;
rep(i, 1, n) {
cin >> a[i].color;
a[i].id = i;
}
// v[i][j]存储了颜色为j且及偶性相同的所有节点
vector<node> v[2][m + 1];
rep(i, 1, n) {
int index = i & 1;
v[index][a[i].color].push_back({a[i].id, a[i].color, a[i].number});
}
long long ans = 0;
for(int i = 0; i < 2; ++i) {
for(int j = 1; j <= m; ++j) {
int size = v[i][j].size();
if (size <= 1) continue;
long long sum_x_rx[size + 1] = {0};
long long sum_rx[size + 1] = {0};
long long sum_x[size + 1] = {0};
for(int k = 1; k <= size; ++k) {
sum_x_rx[k] = sum_x_rx[k - 1] + v[i][j][k - 1].number * 1L * v[i][j][k - 1].id;
sum_rx[k] = sum_rx[k - 1] + v[i][j][k - 1].number;
sum_x[k] = sum_x[k - 1] + v[i][j][k - 1].id;
}
for(int k = 0; k < size - 1; ++k) {
long long k_rk = v[i][j][k].number * 1L * v[i][j][k].id;
long long x_rx = sum_x_rx[size] - sum_x_rx[k + 1];
long long k_rx = v[i][j][k].id *1L * (sum_rx[size] - sum_rx[k + 1]);
long long x_rk = v[i][j][k].number * 1L * (sum_x[size] - sum_x[k + 1]);
ans += (k_rk + x_rx + k_rx + x_rk) % MOD;
ans %= MOD;
}
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
/*
int t;
cin >> t;
while(t-- > 0) {
solve();
}
*/
solve();
return 0;
}