首页 > 其他分享 >【题解】P3210 [HNOI2010] 取石头游戏

【题解】P3210 [HNOI2010] 取石头游戏

时间:2024-08-27 12:40:24浏览次数:12  
标签:题解 ll large HNOI2010 P3210 && dif book

\(\large\mathfrak{1st.\ Preamble|}\) 前言

题目传送门:P3210 [HNOI2010] 取石头游戏)

主要是参考楼下大佬的题解,对于其中没讲到或比较难懂的地方进行讲解,以及配上了图。

\(\large\mathfrak{2nd.\ Solution|}\) 题解

楼下大佬的比喻十分形象生动地描绘了俩人去石头的过程:

取石子的过程可以转化为两端分别有一个栈,可以从栈顶取石子,中间有若干个双端队列,可以从其两端取石子。

我们可以根据俩人取石子的过程推算出先手积分减去后手积分的差值 \(dif\),然后根据总和就能求出最终俩人的积分。先手肯定希望 \(dif\) 尽可能大,后手肯定希望 \(dif\) 尽可能小。

Q:为什么是算差值而不是直接算积分?

A:因为差值好算呗!等会你就知道了。

为了方便计算,我们肯定希望每次的全局最大权值的位置都是可以直接取的。接下来我们分两个部分讨论这俩人取石子的过程。

注:接下来的递减、递增均指非严格递减和递增。

中间部分(双端队列)

对于每个中间区块(双端队列)中,权值递增、递减和下凹的情况都很好解决,如下图箭头所示,从其中一端或两端开始取就行。

然后我们来看看上凸该如何解决。

我们先来考虑最简单的三个位置的上凸情况:若存在 \(a_{i-1}\le a_i\) 并且 \(a_i\ge a_{i+1}\),若当前最优选择为 \(a_{i-1}\),则先手会选择 \(a_{i-1}\),接着后手会选择 \(a_i\),然后先手会选择 \(a_{i+1}\),最终 \(dif\) 会增加(或减少)\(a_{i-1}-a_i+a_{i+1}\),于是我们就可以把 \(a_{i-1}, a_i, a_{i+1}\) 三个位置打包成一个权值为 \(a_{i-1}-a_i+a_{i+1}\)​​ 的位置。反之同理。这也是为什么我们是算差值而不是直接算积分。

当我们把每个上凸都打包完,剩下就只剩下上面的三种情况,当前最大都是可以直接取到的。

两端(栈)

对于左边部分,我们希望是单调递增的(因为只能从中间往外取);反之,对于右边部分,我们希望是单调递减的。

左边部分中,若存在递减的部分,那我们可以像刚才一样,将其打包起来,即:若存在 \(a_i>=a_{i+1}\),且 \(a_{i+1}\) 为目前全局最优,因为先手只能从右侧开始选,所以先手比选 \(a_{i+1}\),后手必选 \(a_i\),于是我们可以把 \(a_i\) 和 \(a_{i+1}\) 打包成一个权值为 \(a_{i+1}-a_i\) 的位置。

右边部分同理。

实现方法

全部打包完后,接下来每次的全局最大值必定可以直接取到,所以我们可以直接将所有位置按权值从大到小排序,然后从大到小取即可。

\(\large\mathfrak{3rd.\ Code|}\) 代码

代码中过于简单的细节就不标注了。敢做黑题的相信一定能看懂。

#include <bits/stdc++.h>
#define ll long long
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FILE(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
#define pii pair<int,int>
#define pll pair<long long,long long>
// #define Clock
using namespace std;
const ll N=2e6+10;
ll n,a[N],sum,l[N],r[N],L,R,p[N],cnt,s,ans;
bool book[N];
inline bool cmp(ll a,ll b){return a>b;}
int main(){
    #ifdef Clock
        clock_t Start_Time=clock();
    #endif
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    // FILE("xxx");
    cin>>n; r[0]=1,l[n+1]=n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i],book[i]=a[i];
        l[i]=i-1,r[i]=i+1;
    }
    for(ll i=3;i<=n;i=r[i]){
        ll x=l[l[i]],y=l[i],z=i;
        while(book[x]&&book[y]&&book[z]&&a[y]>a[x]&&a[y]>a[z]){
            a[i]=a[x]+a[z]-a[y],r[l[x]]=i,l[i]=l[x];
            x=l[l[i]],y=l[i],z=i;
        }
    }
    L=r[0],R=l[n+1];
    while(a[L]>=a[r[L]]&&book[L]&&book[r[L]])s-=a[L]-a[r[L]],L=r[r[L]];
    while(a[R]>=a[l[R]]&&book[R]&&book[l[R]])s-=a[R]-a[l[R]],R=l[l[R]];
    for(ll i=L;i<=R;i=r[i])if(book[i])p[++cnt]=a[i];
    sort(p+1,p+cnt+1,cmp);
    p[++cnt]=s;
    for(ll i=1;i<=cnt;i++)ans+=(i%2?p[i]:-p[i]);
    cout<<(sum+ans)/2<<' '<<(sum-ans)/2;
    #ifdef Clock
        cout<<"\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\nRuntime: "<<clock()-Start_Time<<" ms\n";
        system("pause");
    #endif
    return 0;
}

\(\large\mathfrak{4th.\ Postscript|}\) 后记

第一天写的时候没过,那时还是紫题,并且不能写题解。第二天过完后发现变成了黑题,而且还可以写题解!于是遍欣喜若狂地写下了这篇题解。

标签:题解,ll,large,HNOI2010,P3210,&&,dif,book
From: https://www.cnblogs.com/Xlon-WU/p/18382441

相关文章

  • 题解:P10922 Happybob's Numbers (UBC001B)
    主要思路:贪心,构造。思路构造题,首先明确要删的就是小于\(n\)的数,因为若删了大于等于\(n\)的数就无法进行之后的操作了。那这道题就简单了,先从大到小排序,遇到小于当前长度\(k\)的数,就将这个数删掉,这时长度需减\(1\),毕竟顺序可以自己调,将下一个小于当前\(k\)的数,放到下一......
  • 题解:P5934 [清华集训2012] 最小生成树
    主要思路:网络流。思路先考虑最小生成树,如果一条边边权大于等于选中的边,那么这条边是否删去没有任何影响。按边权排序,对于边\((u,v,L)\),若要加上当且仅当\(u\)和\(v\)并不联通。把所有边权比选定的边的边权小的边拿出来连上,流量均为\(1\),最小割。最大树同理,连上边权比选......
  • 题解:P11007 『STA - R7』Odtlcsu
    评价:简单构造。思路注意题目中的“如果有多解输出任意一种即可”。由于\(a\)与\(a^{2}\)的奇偶性必定是一致的,所以我们可以将情况分为两种。当\(x\)与\(y\)奇偶性不一致时,但由于\(a\)与\(a^{2}\)的奇偶性必定是一致的,所以始终无法构造出正确的序列。但注意题目......
  • P4126 [AHOI2009] 最小割 题解
    DescriptionA,B两个国家正在交战,其中A国的物资运输网中有\(N\)个中转站,\(M\)条单向道路。设其中第\(i\(1\leqi\leqM)\)条道路连接了\(u_i,v_i\)两个中转站,那么中转站\(u_i\)可以通过该道路到达\(v_i\)中转站,如果切断这条道路,需要代价\(c_i\)。现在B国想找出一个......
  • 最大矩阵区间 题解
    题意简述给定\(n\)行\(m\)列矩阵\(A\)。对于每一行\(i\),选择非空区间\([l_i,r_i]\),满足\(\foralli\in[1,n)\),\([l_i,r_i]\)和\([l_{i+1},r_{i+1}]\)相交,即\(\max\{l_i,l_{i+1}\}\leq\min\{r_i,r_{i+1}\}\)。求所有选出区间的\(A_{i,j}\)值......
  • Luogu P4588 数学运算 题解 [ 绿 ] [ 线段树 ]
    LuoguP4588数学运算。虽然是一个很典的题,但里面的思想还是比较值得记录的。假做法一开始看到此题还以为是乘法逆元的模板题,但看到\(m\)与\(M\)不互质,就知道这种做法是假的了。注意exgcd虽然能求模数为合数的逆元,但是要是两数不互质就什么算法都搞不了了。因此,本题不能......
  • Luogu P7250 BalticOI 山峰 题解 [ 蓝 ] [ 模拟 ] [ 并查集 ] [ BFS ]
    LuoguP7250BalticOI山峰。一道大模拟,很暴力,也很难写。建议紫或蓝,标签为模拟、广度优先搜索、并查集。思路首先观察到答案取决于路线上的最低点,所以我们可以把所有点的高度丢进一个桶里,从大到小枚举,尝试更新答案。这应该是个挺经典的trick了。感性理解可以看作所有山都先......
  • 题解:P9256 [PA 2022] Muzyka pop 2
    题解:P9256[PA2022]Muzykapop2题目传送门题目重点从前往后比较,和数字比较一样,如:12345<12445。如果一个串是另一个串的前缀,那么不是前缀串的那个字典序小。题目思路我爱贪心贪心就行了,每次让x增加1,找出1的个数来实现。要求序列是字典序最小的,因此每次选择尽可......
  • 动态dp——P8820 [CSP-S 2022] 数据传输 题解
    P8820[CSP-S2022]数据传输可怜的cnblog被(昨天DDos+今天CC)攻击了(望周知!),只好先发在CSDN题面:题目描述小C正在设计计算机网络中的路由系统。测试用的网络总共有nn......
  • 【跨域问题解决】Access to XMLHttpRequest at xxx from origin xxx has been blocked
    这个错误是由于浏览器的同源策略(CORS,Cross-OriginResourceSharing)导致的。当从一个源(origin)向另一个源请求资源时,如果这两个源的协议、域名或端口号不同,就会触发CORS策略。解决方法要解决这个问题,你需要在你的后端服务中添加CORS支持,以便它允许来自你的请求。这通常......