这道题还是挺有意思，本人比赛时候上没做出来（英语不好漏看一个条件......）
题意描述：
给定一个数组（可能有正数，负数和0），可以进行如下两种操作：
1.选择两个位置 $ i $ ， $ j $ ， $ i $ 在 $ j $ 左边。把 $ j $ 处的数字 $ a[j]*=a[i] $ ，并把 $ a[i] $ 删除掉。
2.选择一个位置 $ x $ ，将这个位置的数字 $ a[x] $ 删除掉。该操作只能用一次。
显然，通过这两个操作，可以把数组中的数字处理到只剩一个。要求使最后的这个数字尽量大。
输出操作的序列。
$ (1 i j) $ 表示操作1
$ (2 x) $ 表示操作2
题解：
开到这一题的时候有点慌，但是想了想就发现，有一些很方便的性质：
·正数直接乘到一起
·如果有0的话，直接删掉就好。
·如果有偶数个负数，无需考虑删去，直接一个一个乘起来就好，最终得到的结果是正数；
·如果有奇数个负数，那么就选择「绝对值最小的负数」也就是「最大的负数」删去，剩下的仍然是偶数个负数，且这样结果最大。
以上就是我在比赛时候想到的......过了样例直接拿去交，然后就WA掉了......QAQ
比赛结束后旁边的dalao告诉我「删除操作只能用一次诶」
好吧是我英语不好没看懂。
然后怎么做？
考虑要删除一些位置的数，我们可以先把这些位置由小到大排序，再通过操作1，把这些数集中到最末的一位上，然后对最后一个位置进行操作2删除就可以了。
迎刃而解。
代码实现：
准备工作
set<int>removed;//记录某个位置的元素是否被删除了
int n,a[200050];//输入
struct ope{//operation，操作
int c,l,r;//操作种类和位置
ope(int c=0,int l=0,int r=0):
c(c),l(l),r(r){
}
};
ope os[200050];//记录操作
int cnt=0;
void v1(int l,int r){//操作1
cnt++;
os[cnt]=ope(1,l,r);
removed.insert(l);
}
void v2(int x){//操作2
cnt++;
os[cnt]=ope(2,x,0);
removed.insert(x);
}
int num_fu=0;//负数的个数
int max_fu_pos=0,max_fu=0;//用来找最大的负数的位置
int tr[200050],cnt2=0;//tr=to_remove，预先将所要删除的位置放在这里
void rm(int x){//将某个位置丢进to_remove中
cnt2++;
tr[cnt2]=x;
}
bool cmp(int x,int y){//排序用
return x<y;
}
读入，检查负数个数，判断是否删去最大负数，删去0和最大负数（如果需要）
scanf("%d",&n);
for(int i(1);i<=n;i++){
scanf("%d",&a[i]);
if(a[i]<0){//如果是负数
num_fu++;
//更新最大负数位置
if(max_fu==0)max_fu=a[i],max_fu_pos=i;
else if(a[i]>max_fu)max_fu=a[i],max_fu_pos=i;
}
if(a[i]==0)rm(i);//删去0
}
if(num_fu%2){//如果需要删去最大负数
rm(max_fu_pos);
}
if(cnt2){//因为有可能出现cnt2==0，即「不需要删去什么」的情况
sort(tr+1,tr+1+cnt2,cmp);//从小到大排序
for(int i(1);i<=cnt2-1;i++)v1(tr[i],tr[i+1]);//从前往后合并
v2(tr[cnt2]);//删除最末一个
}
合并剩下的负数和正数，记录操作
int lst=0;//指向上一个的位置
for(int i(1);i<=n;i++){
if(removed.count(i))continue;//如果这一位已经被删了（0或最大负数），跳过
if(lst==0){
lst=i;
continue;
}
v1(lst,i);
lst=i;//更新指针
}
注意：数据可能会出现一种情况，就是「删去所有0和最大负数后，数组已经空了」
比如：
4
0 -10 0 0
这样的话，如果把所有要删除的合并，然后删掉最末一个，就会出现「一个也不留」的情况。
所以在合并所有数字之后，输出操作序列之前，要加一个特判：
如果是「一个也不留」的情况，就不执行「删除最末一个」的操作，留下一个0作为答案。
bool flag=1;//是否全为0
for(int i(1);i<=n;i++){
if(a[i]!=0 and !removed.count(i)){//如果有一个数非零且没有被删掉，
flag=0;
break;
}
}
最后是输出答案：
for(int i(1);i<=cnt;i++){
if(os[i].l==0)continue;
if(os[i].c==1)printf("%d %d %d
",os[i].c,os[i].l,os[i].r);
else if(!flag)printf("%d %d
",os[i].c,os[i].l);//如果是上述情况就不输出操作2
}
到此结束。
完整代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#define LL long long
using namespace std;
set<int>removed;
int n,a[200050];
struct ope{
int c,l,r;
ope(int c=0,int l=0,int r=0):
c(c),l(l),r(r){
}
};
ope os[200050];
int cnt=0;
void v1(int l,int r){
cnt++;
os[cnt]=ope(1,l,r);
removed.insert(l);
}
void v2(int x){
cnt++;
os[cnt]=ope(2,x,0);
removed.insert(x);
}
int num_fu=0;
int max_fu_pos=0,max_fu=0;
int tr[200050],cnt2=0;
void rm(int x){
cnt2++;
tr[cnt2]=x;
}
bool cmp(int x,int y){
return x<y;
}
int main(){
scanf("%d",&n);
for(int i(1);i<=n;i++){
scanf("%d",&a[i]);
if(a[i]<0){
num_fu++;
if(max_fu==0)max_fu=a[i],max_fu_pos=i;
else if(a[i]>max_fu)max_fu=a[i],max_fu_pos=i;
}
if(a[i]==0)rm(i);
}
if(num_fu%2){
rm(max_fu_pos);
}
if(cnt2){
sort(tr+1,tr+1+cnt2,cmp);
for(int i(1);i<=cnt2-1;i++)v1(tr[i],tr[i+1]);
v2(tr[cnt2]);
}
int lst=0;
for(int i(1);i<=n;i++){
if(removed.count(i))continue;
if(lst==0){
lst=i;
//printf("ans init=%d
",ans);
continue;
}
v1(lst,i);
//printf("ans*=%d
",a[i]);
lst=i;
}
bool flag=1;
for(int i(1);i<=n;i++){
if(a[i]!=0 and !removed.count(i)){
flag=0;
break;
}
}
//printf("ans=%d
",ans);
for(int i(1);i<=cnt;i++){
if(os[i].l==0)continue;
if(os[i].c==1)printf("%d %d %d
",os[i].c,os[i].l,os[i].r);
else if(!flag)printf("%d %d
",os[i].c,os[i].l);
}
return 0;
}