DeepResearch解题?未成功。
2025-05-25 11:22:38
发布于:浙江
16阅读
0回复
0点赞
试试使用OpenAI的DeepResearch解题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = (1<<17) + 5;
static ll diff_arr[MAXN];
static int fc[2*MAXN], tc_[2*MAXN];
static int a_[MAXN];
static int n, m, Tc;
static char tmp[MAXN];
static int D[MAXN];
static int A_[MAXN], c_[MAXN];
static int K;
// dfs1: compute for each node x in tournament tree the champion index (tc_) and
// a threshold value (fc). Leaves (h=0) are players with abilities a_[idx].
void dfs1(int x, int h) {
if (h == 0) {
int idx = x - (1 << K) + 1;
fc[x] = a_[idx];
tc_[x] = idx;
return;
}
dfs1(x<<1, h-1);
dfs1(x<<1|1, h-1);
if (!D[x] && fc[x<<1] >= h) {
tc_[x] = tc_[x<<1];
} else {
tc_[x] = tc_[x<<1|1];
}
// Determine which subtree contributes champion ability
int choose = (D[x] ^ (fc[x<<1] < h));
fc[x] = fc[(x<<1) | choose];
}
// dfs2: traverse the subtree x with height h, given a minimum host ability hi and
// a range [L,R) of prefix sizes. Accumulate contributions to diff_arr for leaf indices.
void dfs2(int x, int hi, int h, int L, int R) {
if (h == 0) {
int v = x - (1 << K) + 1;
if (L < min(R, v)) {
diff_arr[L] += v;
diff_arr[min(R, v)] -= v;
}
if (a_[v] >= hi && max(v, L) < R) {
diff_arr[max(v, L)] += v;
diff_arr[R] -= v;
}
return;
}
if (!D[x]) {
dfs2(x<<1, max(hi, h), h-1, L, R);
dfs2(x<<1|1, hi, h-1, L, (fc[x<<1] >= h ? min(R, tc_[x<<1]) : R));
} else {
dfs2(x<<1, hi, h-1, L, (fc[x<<1|1] >= h ? min(R, tc_[x<<1|1]) : R));
dfs2(x<<1|1, max(hi, h), h-1, L, R);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> A_[i];
}
for (int i = 1; i <= m; i++) {
cin >> c_[i];
}
// Compute smallest K such that 2^K >= n
K = 0;
while ((1 << K) < n) K++;
// Read draw (D array) for each node of the tournament tree
for (int d = K-1; d >= 0; d--) {
cin >> tmp;
for (int i = 0; i < (1 << d); i++) {
D[i + (1<<d)] = tmp[i] - '0';
}
}
// Number of test cases
cin >> Tc;
while (Tc--) {
int X[4];
cin >> X[0] >> X[1] >> X[2] >> X[3];
// Compute actual abilities by XOR transform
for (int i = 1; i <= n; i++) {
a_[i] = A_[i] ^ X[i & 3];
}
// First DFS to compute fc and tc for each node
dfs1(1, K);
// Reset diff array
for (int i = 0; i <= n; i++) {
diff_arr[i] = 0;
}
// For each block of prefix sizes [L,R), do a DFS to accumulate possible champions
for (int d = 0; d <= K; d++) {
int x = 1 << (K - d);
int L = (d == 0 ? 1 : (1 << (d-1)) + 1);
int R = (1 << d) + 1;
dfs2(x, 0, d, L, R);
}
// Build prefix sums to get answer for each prefix size
for (int i = 1; i <= n; i++) {
diff_arr[i] += diff_arr[i-1];
}
ll ans = 0;
// Compute final XOR of i * A_i for queries
for (int i = 1; i <= m; i++) {
ans ^= (ll)i * diff_arr[c_[i]];
}
cout << ans;
if (Tc) cout << "\n";
}
return 0;
}
结果:
全部评论 2
太贵了!!!
2025-05-25 来自 浙江
0200$
2025-05-25 来自 浙江
0
顶!
2025-05-25 来自 浙江
0
有帮助,赞一个