首页 > 其他分享 >P7078 [CSP-S2020] 贪吃蛇 题解

P7078 [CSP-S2020] 贪吃蛇 题解

时间:2024-10-06 15:10:54浏览次数:9  
标签:q1 snack q2 return 题解 ll 贪吃蛇 P7078 front

P7078 [CSP-S2020] 贪吃蛇

这题好啊

题目传送门

看到题之后觉得有点像砍蚯蚓的那道题

看看题目

可以证明,若一条蛇在吃完之后不是最弱的那一条蛇,那么他一定会选择吃,证明如下

设蛇长为 \(a_{1, \dots ,n}\) 且依次递增,那么很明显的

因为

​ $$a_x>a_y>a_n>a_m$$
​ $$ a_x-a_m>a_y-a_n$$
也就是说,这条蛇吃掉后面的蛇之后产生的蛇永远都不会是最小的哪一个

而如果一条蛇在吃完了之后是最弱的蛇,那么他为了保命,会看自己吃了之后会不会被吃,也就是看下一条蛇的决策

而下一条蛇的决策过程和这一条蛇也是一样的,这种情况就可以 递归的来判断.

还要补充两点

  • 如何维护最强最弱的蛇?

可以用平衡树,set 等,但这种做法会带上一只 \(log\) ,所以一般会T

正确的做法是像砍蚯蚓的那道题一样,用双端队列维护

像这道题,用两个双端队列,一个维护所有原来的蛇,另一个维护吃完蛇后产生的蛇.

对于第二个双端队列的单调性的证明,就是我们一开始证的东西, 后吃的蛇所产生的蛇的长度一定 比 先吃的产生的长度小.

  • 处理一次第二种情况后就可以立即停止了

这是因为第二种情况若吃了,就说明下一条蛇不会吃,结束

若没吃,也结束

上代码!

点击查看代码

#include <bits/stdc++.h>
using namespace std;
struct snack
{
    int len, num;
    friend bool operator<(const snack &a, const snack &b)
    {
        if (a.len == b.len)
            return a.num < b.num;
        return a.len < b.len;
    }
    friend bool operator>(const snack &a, const snack &b)
    {
        if (a.len == b.len)
            return a.num > b.num;
        return a.len > b.len;
    }
    friend snack operator-(const snack &a, const snack &b)
    {
        snack tmp;
        tmp.len = a.len - b.len;
        tmp.num = a.num;
        return tmp;
    }
    void clear()
    {
        this->len = 0;
        this->num = 0;
    }
};
snack snac[10000100]; //蛇群们
int t, n, k;
deque<snack> q1, q2; //两个双端队列来维护
void clean_up()
{
    q1.clear();
    q2.clear();
}
snack get_min(bool delt)
{
    snack ll;
    if (q1.empty() && q2.empty())
    {
        snack insid;
        insid.len = -1;
        insid.num = -1;
        return insid;
    }
    else if (q1.empty())
    {
        ll = q2.front();
        if (delt)
            q2.pop_front();
        return ll;
    }
    else if (q2.empty())
    {
        ll = q1.front();
        if (delt)
            q1.pop_front();
        return ll;
    }
    else
    {
        if (q1.front() < q2.front())
        {
            ll = q1.front();
            if (delt)
                q1.pop_front();
            return ll;
        }
        else
        {
            ll = q2.front();
            if (delt)
                q2.pop_front();
            return ll;
        }
    }
}
snack get_max(bool del)
{
    snack ll;
    if (q1.empty() && q2.empty())
    {
        snack insid;
        insid.len = -1;
        insid.num = -1;
        return insid;
    }
    else if (q1.empty())
    {
        ll = q2.back();
        if (del)
            q2.pop_back();
        return ll;
    }
    else if (q2.empty())
    {
        ll = q1.back();
        if (del)
            q1.pop_back();
        return ll;
    }
    else
    {
        if (q1.back() > q2.back())
        {
            ll = q1.back();
            if (del)
                q1.pop_back();
            return ll;
        }
        else
        {
            ll = q2.back();
            if (del)
                q2.pop_back();
            return ll;
        }
    }
}
int lef = n, llef;
bool fight()
{
    snack min_, max_;
    if (llef == 2)
    {
        return 1;
    }
    min_ = get_min(1);
    max_ = get_max(1);
    if (max_ - min_ > get_min(0))
    {
        return 1;
    }
    else
    {
        llef--;
        q2.push_front(max_-min_);
        return !fight();
    }
}
int solve()
{
    for (int ww = 1; ww <= n; ww++)
    {
        q1.push_back(snac[ww]);
    }
    // case1;
    lef = n;
    snack new_, tmp;
    while (1)
    {
        if (lef == 2)
        {
            lef--;
        }
        if (lef == 1)
        {
            break;
        }
        new_ = get_min(1);
        tmp = get_max(1);
        // cout<<"get "<<new_.len<<" "<<tmp.len<<endl;
        //   cout<<(tmp-new_).len<<" 对 " <<get_min(0).len<<endl;
        if (tmp - new_ > get_min(0))
        {
          
            q2.push_front(tmp - new_);
            lef--;
        }
        else
        {
            q2.push_front(tmp - new_);
            break;
        }
    }
    if (lef == 1)
    {
        return lef;
    }
    // case2,判断完直接就结束了
    llef = lef;
    if (!fight())
    {
        lef--;
    }
    return lef;
}
int main()
{
    freopen("P7078_5.in","r",stdin);
    ios::sync_with_stdio(false);
    cin >> t;
    cin >> n;
    for (int yy = 1; yy <= n; yy++)
    {
        cin >> snac[yy].len;
        snac[yy].num = yy;
    }
    cout << solve() << "\n";
    for (int ww = 2; ww <= t; ww++)
    {
        clean_up();
        cin >> k;
        int a, b;
        for (int ww = 1; ww <= k; ww++)
        {
            cin >> a >> b;
            snac[a].len = b;
        }
        cout << solve() << "\n";
    }

    return 0;
}

标签:q1,snack,q2,return,题解,ll,贪吃蛇,P7078,front
From: https://www.cnblogs.com/sea-and-sky/p/18449088

相关文章

  • 鲁的智力 题解
    题意有\(n\)个人,\(m\)个学科,你第\(i\)门学科排在第\(a_i\)名,且每个人在每个学科得到的分数是一个\(0\)到\(1\)之间的一个实数,求你总分排名的最大、小值。题解先考虑排名最高的情况。我们可以每一科都这样构造:\[b_1=1\]\[b_2=1-\Deltax\]\[b_3=1-2\De......
  • 游览计划 题解
    题意给定一张无向图,选取四个点\(a\neb\nec\ned\),求\(f(a,b)+f(b,c)+f(c,d)\)的最大值,其中\(f(u,v)\)表示点\(u\)到点\(v\)的最短路长度。题解如果顺着枚举四个点\(a\)、\(b\)、\(c\)、\(d\),是一个\(n^4\)的复杂度,显然过不了。但是我们发现如果确定......
  • 洛谷 P3523 题解
    洛谷P3523[POI2011]DYN-Dynamite分析二分答案,问题转化为:对于给定的\(K\),选择尽可能少的节点,使得所有关键节点都被「覆盖」。对于一个关键节点,「覆盖」的定义为:存在一个被选择的点与这个关键节点的距离不大于\(K\)。方便起见,我们指定\(1\)号节点是这棵树的根节点。我们......
  • [题解]ABC374 A~E
    A-Takahashisan2直接判断字符串是否以san结尾即可。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ strings; cin>>s; intn=s.size(); if(s[n-1]=='n'&&s[n-2]=='a'&&s[n-3]=='s')cout<<&......
  • P11059 [入门赛 #27] 数字 (Hard Ver.)题解
    Solution先读题:在给定x的位数\(n\)和模数\(p\)后,要求构造一个\(x\)在满足\(x\modp\)的余数尽可能小的前提下使\(x\)的数字尽可能小。我们假设\(x\)的各位数字之和为\(m\),有\(1\lem\le9n\)。.(当\(x\)仅在最高位有1时\(m=1\),称为情况一,当x每位为9时\(m=9n\),称为情况二......
  • ABC374E 题解
    好题。爱做。标签:二分。求最大的最小值,考虑二分答案。然后问题就转化成了(求\(n\)次):有两种物品,每种物品有一个代价和价值,求获得不少于给定价值所需的最小代价。下文记物品的代价为\(w\),价值为\(v\),所拿的数量为\(cnt\)。假设有两种物品\(S\)与\(T\),\(S\)物品的性价比......
  • P10678 『STA - R6』月 题解
    Solution看了别的大佬的题解,感觉都是数学证明然后用树和图做的,看不懂啊。。。萌新瑟瑟发抖用vector模拟树,然后贪心摸索做出来了。注意到要求最深叶子结点和最浅叶子结点的距离最短时的情况,那么此时根节点应该是树中度数最大的点,把树尽可能的拓宽,深度换宽度。那么同理的根节点......
  • 题解:P11008 『STA - R7』异或生成序列
    Solution序列\(p\)是\(1\)~\(n\)的排列,因此考虑搜索回溯。由\(\sumn\le2\times10^6\)得知\(O(n^2)\)会炸,深感遗憾但仍考虑剪枝。坚信深搜过百万的蒟蒻。。。原\(b\)序列为长度\(n-1\)的序列:{\(b_1,b_2,b_3\cdotsb_n-1\)}将其前面插入一个元素\(......
  • 题解:AT_abc374_d [ABC374D] Laser Marking
    看到\(n\le6\),就知道这道题又是一道搜索了。题面有点长,信息也给的有点多,但稍微分析就可以得到只需要搜索印刷线段的顺序即可。具体的,我们在深搜函数里面传\(4\)个参数,分别代表已选线段的数量,当前位置的横纵坐标,以及当前时间。为了方便,我们表示的是已经印刷完当前线段后的时间......
  • P5593 题解
    题目分析首先考虑什么样的颜色能被链覆盖。容易想到当某种颜色恰巧在一条链上会被覆盖。所以只需要判断一种颜色是否能构成链即可,链的贡献也很好计算。算法考虑链的性质:有且仅有两个端点。凭借这个性质,可以判断一种颜色是否在一条链上。在dfs中考虑各种情况。假设一个......