首页 > 其他分享 >洛谷 P8818 [CSP-S 2022] 策略游戏

洛谷 P8818 [CSP-S 2022] 策略游戏

时间:2024-04-23 10:35:53浏览次数:29  
标签:begin 洛谷 int P8818 pow2 vector values 2022 dp

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

相关文章

  • 洛谷 P1719 最大加权矩形
    使用前缀和进行数据的预处理再使用遍历查找最大加权矩形#include<bits/stdc++.h>usingnamespacestd;intb[125][125];intmain(){//初始化最小值intn,ans=-99999999;cin>>n;for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){inta;......
  • 洛谷题单指南-动态规划1-P1064 [NOIP2006 提高组] 金明的预算方案
    原题链接:https://www.luogu.com.cn/problem/P1064题意解读:用固定钱数购买最大价值的物品。解题思路:背包问题,背包问题里的体积相当于物品价格,价值相当于价格*重要度物品分为主件、附件,主件最多有0/1/2个附件,要选附件必须选相应主件,因此在递推计算dp[j]总价格j能购买的最大价......
  • 洛谷题单指南-动态规划1-P3842 [TJOI2007] 线段
    原题链接:https://www.luogu.com.cn/problem/P3842题意解读:计算1-n的最短路,且每行要覆盖线段。解题思路:既然要每行覆盖线段,那往下一行走时,必然是从线段的端点往下,有可能是从左端点往下,也有可能是从右端点往下。当已知第i行,从1走到第i行的左端点且要覆盖第i行线段的路程可以计算......
  • 洛谷 P3353 在你窗外闪耀的星星
    题意:给定一个宽度w,n个数,每个数有一个权值。窗口可以变换位置,求该窗口能容纳的最大权值。思路:前缀和+滑动窗口硬算。总结:一开始感觉是fenwicktree,但是每次查询的区间固定,不需要fenwicktree,不如滑动窗口来的方便。voidsolve(){intn,w;cin>>n>>w;vector<in......
  • Windows Server 2022 OVF, updated Apr 2024 (sysin) - VMware 虚拟机模板
    WindowsServer2022OVF,updatedApr2024(sysin)-VMware虚拟机模板2024年4月版本更新,现在自动运行sysprep,支持ESXiHostClient部署请访问原文链接:WindowsServer2022OVF,updatedApr2024(sysin)-VMware虚拟机模板,查看最新版。原创作品,转载请保留出处。作......
  • Windows Server 2022 中文版、英文版下载 (updated Apr 2024)
    WindowsServer2022中文版、英文版下载(updatedApr2024)WindowsServer2022正式版,x64请访问原文链接:WindowsServer2022中文版、英文版下载(updatedApr2024),查看最新版。原创作品,转载请保留出处。作者主页:sysin.org此次发布更新了什么?答:版本号,当然还有…2021.09......
  • P8207 [THUPC2022 初赛] 最小公倍树 题解
    题目大意有编号为\([L,R]\)区间的点,连接两个点\(x,y\)边权的为\(LCM(x,y)\),求这张图的最小生成树。\[1\leqL\leqR\leq10^6,R-L\leq10^5\]解题思路我们有一个结论:对于张图\(G\)中的一个生成子图\(E\),\(E\)之中的一条边\(k\)如果不在\(E\)最小生成树中,那么\(......
  • 新手大白话 [HNCTF 2022 Week1]Challenge__rce RCE自增绕过
    今天遇到个RCE难题,挺另类的,这里做个复盘。进入题目直接给出了源码,可以发现就是个无字母RCE,且有长度限制不能使用url取反绕过,到这想到了以前的一个rce自增绕过方式,但是以前的没有长度限制。点击查看代码<?phperror_reporting(0);if(isset($_GET['hint'])){highlight_f......
  • 洛谷八皇后问题
    洛谷八皇后问题原题链接https://www.luogu.com.cn/problem/P1219简单dfs思路,g[n]存储的是可以作为选择的列下标输出的时候记着加一(从0开始)#include<iostream>#include<cstring>usingnamespacestd;constintN=15;intn;intnum;boollie[N],duijiao[2*N......
  • 洛谷 P4451 [国家集训队] 整数的lqp拆分
    洛谷传送门设\(G\)为斐波那契数列的生成函数,显然有\(F=F\timesG+1\)。那么\(F=\frac{1}{1-G}=1+\frac{x}{1-2x-x^2}\)。问题是如何展开\(\frac{x}{1-2x-x^2}\)。因为\(\frac{1}{1-ax}=\sum\limits_{i\ge0}(ax)^i\),所以考虑设\(\frac{x}{1-......