题解：CF1042C Array Product

fly_bamboo · 2025-10-30 16:56:22 · 题解

一个不太简单的分类讨论。

容易发现，答案只用分讨负数数量和零数量的奇偶性， 因为正数总是要选的。

还有一个性质，题目说我们只能删除一个数字其实是假的，我们想删多少都可以，只要把这些数都乘在一起就可以了。

有些负数需要选，因为负负得正，众所周知。

零也有时候需要选，比如说答案是负数。

所以我们开始分类讨论：

• 有零

  • 奇数个负数

  我们把最大的负数和零合并在一起删掉，然后把其他正数和负数合并。

  • 偶数个负数

  把所有零删掉就可以了。

• 无零

  • 奇数个负数

  把多出去一个最大的负数删掉，然后合并其他所有数。

  • 偶数个负数

    不用删除，合并所有数。

综上，我们把所有数的下标塞到 3 个数组里面就行了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005];
vector<int> zero,num,b;
bool cmp(int q,int h)
{
    return a[q]>a[h];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0) zero.push_back(i);
        else if(a[i]<0) num.push_back(i); 
        else b.push_back(i);
    }//有0的情况
    if((int)zero.size()>0)
    {
        if((int)num.size()%2==0)//偶数
        {
            for(int i=1;i<zero.size();i++)
            {
                cout<<1<<" "<<zero[i-1]<<" "<<zero[i]<<"\n";
            }
            if(num.size()>0||b.size()>0) cout<<2<<" "<<zero[zero.size()-1]<<"\n";
            for(int i=1;i<num.size();i++)
            {
                cout<<1<<" "<<num[i-1]<<" "<<num[i]<<"\n";
            }
            if(num.size()>0&&b.size()>0) cout<<1<<" "<<num[num.size()-1]<<" "<<b[0]<<'\n';
            for(int i=1;i<b.size();i++)
            {
                cout<<1<<" "<<b[i-1]<<" "<<b[i]<<"\n";
            }
        }
        else//奇数
        {
            for(int i=1;i<zero.size();i++)
            {
                cout<<1<<" "<<zero[i-1]<<" "<<zero[i]<<"\n";
            }
            sort(num.begin(),num.end(),cmp);
            cout<<1<<" "<<zero[zero.size()-1]<<" "<<num[0]<<"\n";
            if(b.size()+num.size()-1>0) cout<<2<<" "<<num[0]<<"\n";
            for(int i=2;i<num.size();i++)
            {
                cout<<1<<" "<<num[i-1]<<" "<<num[i]<<"\n";
            }
            if(num.size()>1&&b.size()>0) cout<<1<<" "<<num[num.size()-1]<<" "<<b[0]<<'\n';
            for(int i=1;i<b.size();i++)
            {
                cout<<1<<" "<<b[i-1]<<" "<<b[i]<<"\n";
            }
        }
        return 0;
    }
    int q=0;
    sort(num.begin(),num.end(),cmp);
    if(num.size()%2==1)//多出的负数
    {
        cout<<2<<" "<<num[0]<<"\n";
        q=1;
    }
    for(int i=0;i<b.size();i++) num.push_back(b[i]);
    for(int i=q+1;i<num.size();i++) cout<<1<<" "<<num[i-1]<<" "<<num[i]<<"\n";
    return 0;
}