简答题 偏难
#22095

策略游戏(game )

策略游戏(game )


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; #define MAXN 100001 #define int long long int n, m, q, l_1, r_1, l_2, r_2; int ans, ans1, ans2, ans3, ans4, ans5, ans6; struct Block {     #define MAXM 331  // 块的个数     int n, len, tot;     int a[MAXN], bl[MAXN];     int L[MAXM], R[MAXM];  // 每个块的左端点和右端点     int maxn[MAXM], minn[MAXM];  // 每个块的最大值和最小值     Block(int x) {  // 构造函数         n = x;     }     void init() {  // 初始化         len = sqrt(n);  // 块长         tot = (n - 1) / len + 1;  // 块的数量         R[0] = 0;         for (int i(1); i &lt;= tot; ++i) {  // 求 L,R             L[i] = R[i - 1] + 1;             R[i] = i * len;         }         R[tot] = n;  // 注意最后一个块的右端点         for (int i(1); i &lt;= tot; ++i) {             maxn[i] = LLONG_MIN;             minn[i] = LLONG_MAX;             for (int j(L[i]); j &lt;= R[i]; ++j) {                 bl[j] = i;  // j 在第 i 个块                 maxn[i] = max(maxn[i], a[j]);                 minn[i] = min(minn[i], a[j]);             }         }     }     int gmin(int l, int r) {         int p(bl[l]), q(bl[r]), res(LLONG_MAX);         if (p == q) {  // 当 l,r 处于同一个块时,暴力枚举             for (int i(l); i &lt;= r; ++i) {                 res = min(res, a[i]);             }             return res;         }         for (int i(l); i &lt;= R[p]; ++i) {             res = min(res, a[i]);  // 枚举第一个块         }         for (int i(p + 1); i &lt; q; ++i) {             res = min(res, minn[i]);  // 枚举中间的块         }         for (int i(L[q]); i &lt;= r; ++i) {             res = min(res, a[i]);  // 枚举最后一个块         }         return res;     }     int gmax(int l, int r) {  // 同gmin,求最大值         int p(bl[l]), q(bl[r]), res(LLONG_MIN);         if (p == q) {             for (int i(l); i &lt;= r; ++i) {                 res = max(res, a[i]);             }             return res;         }         for (int i(l); i &lt;= R[p]; ++i) {             res = max(res, a[i]);         }         for (int i(p + 1); i &lt; q; ++i) {             res = max(res, maxn[i]);         }         for (int i(L[q]); i &lt;= r; ++i) {             res = max(res, a[i]);         }         return res;     } }; int f(int x) {  // 模拟 B 的决策     if (x &gt;= 0) {         return ans6;     }     return ans5; } signed main() {     ios::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin &gt;&gt; n &gt;&gt; m &gt;&gt; q;     Block a(n), b(m), a2(n), a3(n);  // a2 为负数处理、a3 为非负数处理     for (int i(1); i &lt;= n; ++i) {         cin &gt;&gt; a.a[i];         a2.a[i] = a3.a[i] = a.a[i];         if (a.a[i] &lt; 0) {             a3.a[i] = LLONG_MAX;  // 非负数集合中排除负数         } else {             a2.a[i] = LLONG_MIN;  // 负数集合中排除非负数         }     }     for (int i(1); i &lt;= m; ++i) {         cin &gt;&gt; b.a[i];     }     a.init();    // 初始化块结构(不能在构造函数中初始化)     b.init();     a2.init();     a3.init();     while (q--) {         cin &gt;&gt; l_1 &gt;&gt; r_1 &gt;&gt; l_2 &gt;&gt; r_2;         // 获取区间最值         ans1 = a.gmax(l_1, r_1);         ans2 = a.gmin(l_1, r_1);         ans3 = a2.gmax(l_1, r_1);         ans4 = a3.gmin(l_1, r_1);         ans5 = b.gmax(l_2, r_2);         ans6 = b.gmin(l_2, r_2);         // 计算可能的最大值         ans = max(ans1 * f(ans1), ans2 * f(ans2));  // A取最大值和最小值的情况         if (ans3 != LLONG_MIN) {             ans = max(ans, ans3 * f(ans3));  // A取负数最大值         }         if (ans4 != LLONG_MAX) {             ans = max(ans, ans4 * f(ans4));  // A取非负数最小值         }         cout &lt;&lt; ans &lt;&lt; '\n';     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。