@noi.ac - 490@ game

港控/mmm° 2021-11-09 13:30 214阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

小 Q 和小 T 正在玩一种双人游戏。m 张木牌从左往右排成一排，第 i 张木牌上写着一个正整数 bi。小 Q 和小 T 轮流行动总计 m 轮，小 Q 先手。在每一轮中，行动方需要选择最左或者最右的一张木牌并将其拿走。游戏最后每个人的得分即为他拿走的木牌上写着的数字之和，得分较大的一方胜利。小 Q 和小 T 都是博弈老手，他们一定会按照最优策略去行动，即都希望自己的得分比对方的得分尽可能地高。

给定 n 张木牌上的数字 a1,a2,…,an，这些木牌从左往右排成一排。小 Q 和小 T 将会依次进行 q 局独立的游戏。在第 i 局游戏开始前，他们会选定两个正整数li,ri(1≤li≤ri≤n)，然后将第 li 到第 ri 张木牌拿出来，在这 ri−li+1 张木牌上进行这一局游戏。每局游戏结束后，他们又会重新整理好这些木牌，把木牌按照 a1,a2,…,an 的样子恢复原状。

作为旁观者的你不免感到每局游戏有些漫长，于是你决定写一个程序来预测最终的游戏结果。

请写一个程序，对于每局游戏计算小 Q 先手且双方都采取最优策略的情况下，游戏结束时先手和后手的得分分别是多少。

**input**  
第一行包含两个正整数 n,q，分别表示木牌的数量以及游戏的局数。

第二行包含 n 个正整数 a1,a2,…,an，依次表示每张木牌上写着的数字。

接下来 q 行，每行两个正整数 li, ri，依次描述每局游戏。

**output**  
对于每局游戏，输出一行两个整数，即该局游戏结束时先手和后手的得分。

**sample input**  
5 4  
7 9 3 5 2  
1 5  
3 5  
2 4  
1 2  
**sample output**  
12 14  
5 5  
12 5  
9 7

对于100%的数据，1≤li≤ri≤n≤100000，所有 ai 都在 \[1,10^9\] 中随机产生，q≤200000。

## @solution@ ##

这道题最简单的解法就是 O(n^2) 的区间 dp，但显然。。。

首先我们可以将问题转换为先手分数减后手分数的最大值，又可以知道先手分数与后手分数的和（区间总和），分别解出先手分数与后手分数。

然后，嗯其实它是一道结论题。

（1）如果遇到相邻的三个数 A, B, C，满足 A <= B 且 B >= C（形成山峰状）时，可以将它合成一个数 A + C - B。  
为什么？题解里大致写了会儿，但我没懂其中的逻辑。我大致BB一下：  
假如此时 Q 先手，Q 此时可以拿取 A 与最右端的某个数。如果 Q 此时分析得到拿取 A 比拿最右更有优势：  
则 T 如果拿最右，说明最右更有优势，故 Q 一开始会拿最右。故 T 必须拿 B。  
如果 Q 此时拿最右，则 Q 可以在第一时刻拿最右，如此操作就会比先拿 A 获得更大优势。  
（以上全是感性证明）

（2）将原数列按照（1）中所做后，得到的新数列要么递增，要么递减，要么先递减后递增（形成山谷状）。  
递增与递减是对称的，我们只需要考虑一种。可以归纳法验证先手总是先选取最大的是最优的方案。  
山谷状时，两边总比中间高，故先手也总可以选取最大的数，一样归纳法验证。  
故可以将新数列排序。

（3）因为数是随机生成的，所以新数列最多 O(log n) 个数（注定了这是一道神仙题）  
题解里没说。我也不会证。但我会写代码验证：

#include<cstdio>
    #include<cstdlib>
    #include<ctime>
    typedef long long ll;
    const int MAXN = 1E6;
    ll a[MAXN + 5]; int cnt = 0;
    int main() {
        ll sum = 0;
        for(int T=1;T<=1000;T++) {
            srand(time(NULL)); cnt = 0;
            for(int i=1;i<=MAXN;i++) {
                a[++cnt] = rand();
                while( cnt >= 3 && a[cnt-2] <= a[cnt-1] && a[cnt-1] >= a[cnt] )
                    a[cnt-2] = a[cnt] + a[cnt-2] - a[cnt-1], cnt = cnt - 2;
            }
            //printf("%d\n", cnt);
            sum += cnt;
        }
        printf("avg : %lf\n", 1.0*sum/1000);
    }

实现上，可以使用分治，每次处理跨越 mid 的区间。没有跨越 mid 的区间分成左右两个子问题。  
跨越 mid 的区间 \[l, r\] 拆成 \[l, mid-1\] 与 \[mid, r\]。预处理 \[1...mid-1, mid-1\] 的新数列，然后从 mid 开始向右扫描并维护。  
如果遇到询问，就暴力合并。

所以这道题肯定是离线搞啊怎么可能在线。

## @accepted code@ ##

#include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int MAXN = 200000 + 5;
    const int MAXQ = 200000 + 5;
    struct query{
        int l, r, n;
        query(int _l=0, int _r=0, int _n=0):l(_l), r(_r), n(_n){}
    }qry[MAXQ], tmp[MAXQ];
    int l[MAXQ], r[MAXQ]; ll ans[MAXQ];
    ll a[MAXN], s[MAXN];
    vector<ll>vec[MAXN], tmp2, tmp3;
    vector<query>Q[MAXN];
    void insert(vector<ll>&v, ll x) {
        v.push_back(x);
        while( v.size() >= 3 && v[v.size()-2] >= v[v.size()-1] && v[v.size()-2] >= v[v.size()-3] ) {
            ll x = v[v.size()-1] + v[v.size()-3] - v[v.size()-2];
            v.pop_back(), v.pop_back(), v.pop_back(), v.push_back(x);
        }
    }
    void solve(int L, int R, int le, int ri) {
    //  printf("%d %d %d %d\n", L, R, le, ri);
        if( L > R || le > ri ) return ;
        int mid = (L + R) >> 1, p = le, q = ri;
        for(int i=mid;i<=R;i++)
            Q[i].clear();
        for(int i=le;i<=ri;i++)
            if( qry[i].r < mid ) tmp[p++] = qry[i];
            else if( qry[i].l > mid ) tmp[q--] = qry[i];
            else Q[qry[i].r].push_back(qry[i]);
        vec[mid].clear();
        for(int i=mid-1;i>=L;i--)
            vec[i] = vec[i+1], insert(vec[i], a[i]);
        for(int i=L;i<mid;i++)
            reverse(vec[i].begin(), vec[i].end());
        tmp2.clear();
        for(int i=mid;i<=R;i++) {
            insert(tmp2, a[i]);
            for(int j=0;j<Q[i].size();j++) {
                tmp3 = vec[Q[i][j].l];
                for(int k=0;k<tmp2.size();k++)
                    insert(tmp3, tmp2[k]);
                sort(tmp3.begin(), tmp3.end());
                for(int k=tmp3.size()-1,f=1;k>=0;k--,f*=-1)
                    ans[Q[i][j].n] += tmp3[k]*f;
            }
        }
        for(int i=le;i<=ri;i++)
            qry[i] = tmp[i];
        solve(L, mid - 1, le, p - 1);
        solve(mid + 1, R, q + 1, ri);
    }
    int main() {
        int n, q; scanf("%d%d", &n, &q);
        for(int i=1;i<=n;i++) {
            scanf("%lld", &a[i]);
            s[i] = s[i-1] + a[i];
        }
        for(int i=1;i<=q;i++) {
            scanf("%d%d", &l[i], &r[i]);
            qry[i] = query(l[i], r[i], i);
        }
        solve(1, n, 1, q);
        for(int i=1;i<=q;i++)
            printf("%lld %lld\n", (s[r[i]]-s[l[i]-1]+ans[i])/2, (s[r[i]]-s[l[i]-1]-ans[i])/2);
    }

## @details@ ##

康复计划 - 5。

推导一晚上，代码一小时。

神仙题与只给结论不带（详细）证明就跑的题解。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11080656.html