https://www.luogu.com.cn/problem/P8818
什么玩意儿。。这种策略题不就是你来我往的,你如果选那个我就选这个,到了最后俩人都做不了决策,一直在博弈吗
放个示例跑不过去的代码
真不想调,这种题就是恶心啊,你说说怎么调呢
针对一方的选择,另一方总能选出更优的策略来。然后这一方针对另一方的更优策略,总能改变为更优的策略。往复循环,无底洞啊。
constexpr int INF = 0x3f3f3f3f;
struct Data{
int maxn;
int minn;
int negmax;
int posmin;
bool has_zero;
Data():maxn(INF), minn(-INF), negmax(INF), posmin(-INF), has_zero(false){}
};
void solve(){
int n, m, q;
cin >> n >> m >> q;
vector<int> a(n + 1);
vector<int> b(m + 1);
for (int i = 1; i <= n; ++i){
cin >> a[i];
}
for (int i = 1; i <= m; ++i){
cin >> b[i];
}
auto construct = [](vector<int>& s)->vector<vector<Data>>{
int n = s.size() - 1;
int p = upper_bound(pow2_values.begin(), pow2_values.end(), n) - pow2_values.begin() - 1;
vector<vector<Data>> dp(n + 1, vector<Data>(p + 1));
for (int i = 1; i <= n; ++i){
dp[i][0].maxn = dp[i][0].minn = s[i];
dp[i][0].has_zero = (s[i] == 0);
if (s[i] > 0){
dp[i][0].posmin = min(dp[i][0].posmin, s[i]);
}
if (s[i] < 0){
dp[i][0].negmax = max(dp[i][0].negmax, s[i]);
}
}
for (int k = 1; k <= p; ++k){
for (int i = 1; i + (1 << k) - 1 <= n; ++i){
dp[i][k].maxn = max(dp[i][k - 1].maxn , dp[i + (1 << (k - 1))][k - 1].maxn );
dp[i][k].minn = max(dp[i][k - 1].minn, dp[i + (1 << (k - 1))][k - 1].minn);
dp[i][k].has_zero = dp[i][k - 1].has_zero || dp[i + (1 << (k - 1))][k - 1].has_zero;
auto& left = dp[i][k - 1];
auto& right = dp[i + (1 << (k - 1))][k - 1];
dp[i][k].posmin = min(left.posmin, right.posmin);
dp[i][k].negmax = max(left.negmax, right.negmax);
}
}
return dp;
};
auto dp_l = construct(a);
auto dp_q = construct(b);
while (q--){
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int p1 = upper_bound(pow2_values.begin(), pow2_values.end(), r1 - l1 + 1) - pow2_values.begin() - 1;
int p2 = upper_bound(pow2_values.begin(), pow2_values.end(), r2 - l2 + 1) - pow2_values.begin() - 1;
int maxn1 = max(dp_l[l1][p1].maxn, dp_l[r1 - (1 << p1) + 1][p1].maxn);
int minn1 = min(dp_l[l1][p1].minn, dp_l[r1 - (1 << p1) + 1][p1].minn);
int posmin = max(dp_l[l1][p1].posmin, dp_l[r1 - (1 << p1) + 1][p1].posmin);
int negmax = min(dp_l[l1][p1].negmax, dp_l[r1 - (1 << p1) + 1][p1].negmax);
bool has_zero = dp_l[l1][p1].has_zero || dp_l[r1 - (1 << p1) + 1][p1].has_zero;
int maxn2 = max(dp_q[l1][p2].maxn, dp_q[r1 - (1 << p2) + 1][p2].maxn);
int minn2 = min(dp_q[l1][p2].minn, dp_q[r1 - (1 << p2) + 1][p2].minn);
if (minn2 >= 0 && maxn1 >= 0){
cout << 1ll * minn2 * maxn1 << '\n';
}
else if (minn2 >= 0 && maxn1 <= 0){
cout << 1ll * maxn2 * minn1 << '\n';
}
else if (maxn2 <= 0 && minn1 <= 0){
cout << 1ll * maxn2 * minn1 << '\n';
}
else if (maxn2 <= 0 && minn1 >= 0){
cout << 1ll * minn2 * minn1 << '\n';
}
else{
if (has_zero){cout << 0 << '\n';}
else if (maxn1 <= 0){cout << 1ll * negmax * maxn2 << '\n';}
else if (minn1 >= 0) {cout << 1ll * posmin * minn2 << '\n';}
else{
cout << max({1ll * negmax * maxn2, 1ll * posmin * minn2}) << '\n';
}
}
}
}
标签:begin,洛谷,int,P8818,pow2,vector,values,2022,dp
From: https://www.cnblogs.com/yxcblogs/p/18152271