思路求助
查看原帖
思路求助
1035847
Tomatos03楼主2024/3/4 22:09

我想问一下思路是否存在问题,如果思路存在,麻烦指出如果思路不存在问题,请求帮改一下代码

我的思路:求奇偶性相同且颜色格子的x∗numberx、x、numberxx * number_x 、x 、number_x前缀和. 遍历奇偶相同且颜色相同的格子组成的数组,当遍历到k时[k+1,数组大小−1][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;
}
2024/3/4 22:09
加载中...