时间戳

首页 > 技术文章 > Codeforces 780 D. Maximum Product Strikes Back (模拟)

Codeforces 780 D. Maximum Product Strikes Back (模拟)

A-sc 2022-04-01 16:13 原文

Codeforces 780 D. Maximum Product Strikes Back (模拟)

题目：

题目大意是给一个数组a[1...n] (-2 <= a[i] <= 2) ，问你从前面删除几个数，后面删除几个数，最后使得剩下数字的乘积最大。输出前后分别删除个数。注意：全部删除的空数组被认为乘积和为1。

思路：

在比赛中，我思考了一会脑子直接就想放弃。自己在分析问题的能力上存在问题，需要加强！！这道题首先如果有0，那0肯定不在最后的数组中，所以我们有一个初步的想法用数组中的0将数组划分成很多份。选择剩下数组块中乘积和最大的留下，其他数全部删了就行。

这样原问题就转变成另一个更具体的问题了，就是在一段没有0的数组中如何解题。有一个关键点：所有数的乘积要么是最大值要么是最小值。所以如果最后总成绩为正不用删除，如果为负我们只要删除一个负数及其一侧的值就行。现在问题更加具体了：删除左侧的第一个负数及其左侧值，还是删除右侧第一个负数及其右侧值。这里只需要两边都算一次比较一下就行了。

如果以前自己做这类题估计即使看了题解，也要参考别人代码才能完成。但是现在确实能力有所上升，能直接自己想出思路，然后完成。唯一遗憾的是在比赛时没法条理清晰地去思考，总是想着有什么结论，或者什么很妙的思路。

有几点在完成时需要注意：

  • 如果最大情况，就是2^200000的值，显然不能维护这个，贡献最后有效答案的其实只有2/-2，我们只需要维护含2的数量即可，再单独算一下负数数量。
  • 我们可以让a[n + 1] = 0,这样即使没有0进行分割也可以最后进行一个计算。使思路实现不需要单独再讨论一种情况

总体思路：

  • 不遇到0就加进sol向量数组中，遇到0时，将sol存的是前一个分块，计算其答案并维护最终左右分别删除个数的答案resl,resr
  • 遇到0
    • 遍历sol数组，统计绝对值分别为1，2个数，统计负数个数
    • 负数个数为为偶数个不需要删除，直接维护答案，更新下一个分块首位置：tpl
    • 负数个数为奇数个：
      • 分别考虑左右删除第一个负数后的答案，和维护答案进行比较更新即可
  • 输出resl, resr

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<set>
#include<fstream>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, int> PLI;
typedef pair<ll, ll> PLL;
const int N = 2e6 + 50;
const int mod = 998244353;
const double Pi = acos(- 1.0);
const ll INF = 1e12;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b, ll p) { ll res = 1; while(b){ if(b & 1) res = (res * a) % p; a = (a * a) % p; b >>= 1;} return res % p; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


int a[N];

void solve(){
    int n; scanf("%d",&n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d",&a[i]);
    }

    int res = 0, resl = n, resr = 0;
    int tpl = 1;
    vector<int> sol;
    a[n + 1] = 0;
    for(int i = 1; i <= n + 1; ++ i){
        if(a[i] == 0){
            int tt = sol.size();
            int fu = 0;
            int sum1 = 0, sum2 = 0;
            int sumlr2 = 0, sumrl2 = 0;
            int flaglr = 0;
            int idxlr = 0, idxrl = 0;
            for(int j = 0; j < tt; ++ j){
                if(abs(sol[j]) == 1) sum1 ++;
                else if(abs(sol[j]) == 2) {
                    sum2 ++;
                    if(!flaglr) sumlr2 ++;
                    sumrl2 ++;
                }
                if(sol[j] < 0) {
                    fu ++;
                    if(!flaglr) {
                        flaglr = 1;
                        idxlr = tpl + j;
                    }
                    if(abs(sol[j]) == 2) sumrl2 = 1;
                    else sumrl2 = 0;
                    idxrl = tpl + j;
                }
            }

            if(fu % 2 == 0){
                if(sum2 > res){
                    res = sum2;
                    resl = max(0, tpl - 1);
                    resr = n - (tpl + tt - 1);
                    tpl = i + 1;
                    sol.clear();
                    continue;
                }
            }
            else{
                if(sumlr2 <= sumrl2){
                    int tp = sum2 - sumlr2;
                    if(tp > res){
                        res = tp;
                        resl = idxlr;
                        resr = n - (tpl + tt - 1);
                        tpl = i + 1;
                        sol.clear();
                        continue;
                    }
                }
                else{
                    int tp = sum2 - sumrl2;
                    if(tp > res){
                        res = tp;
                        resl = max(0, tpl - 1);
                        resr = n - idxrl + 1;
                        tpl = i + 1;
                        sol.clear();
                        continue;
                    }
                }
            }
            sol.clear();
            tpl = i + 1;
        }
        else sol.push_back(a[i]);
    }
    printf("%d %d\n",resl, resr);
}

int main() {
    freopen("temp.in", "r", stdin);
    freopen("temp.out", "w", stdout);
    int T; scanf("%d",&T);
    while(T --) solve();
    return 0;
}

推荐阅读