Silly Mistake题解

这是一个超时的做法，真的令人头秃。

//https://vjudge.net/problem/CodeForces-1253B#
//会超时 
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+1;
int bb[maxn];
int c,n;
struct node2{
    int num;
    struct node2 *next;
    node2(){
        num=0;
        next=NULL;
    }
};
struct node{
    int cnt;//表示层数
    node2 *b;
    int sum; 
    struct node *next;
    node(){
        sum = 0;
        cnt = 0;
        b=new node2;
        next=NULL;
    } 
}pepo;
node *pn;
node2 *p;
void delete_node2(node2 *p){
    if(p==NULL){
        return ;
    }else{
        delete_node2(p->next);
        delete p;
    }
    return ;
}
void delete_node(node *pn){
    if(pn==NULL){
        return ;
    }else{
        delete_node2(pn->b);
        delete_node(pn->next);
        delete pn;
    }
    return ;
}
void insert_a(int num){
    int i;
    node2 *pp=pn->b;
    for(i=0;i<pn->cnt;i++){
        if(num == pp->num){
//            cout<<num<<endl;
            c++;
            pp->next=NULL;    
            pn->next=new node;
            pn=pn->next;
            insert_a(num);
            return ;
        }
        pp=pp->next;
    }
    pn->sum+=num;
    pn->cnt++;
    pp->num=num;
    pp->next=new node2;
    pp=pp->next;

    return ;
}

int main(){
    c=1;//c表示有效天数 
    scanf("%d",&n);

    int num;
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&bb[i]);
    }
    pn=&pepo;
    p=pn->b;
    for(int i=0;i<n;i++)
        insert_a(bb[i]);
    pn=&pepo;
    int pp=c;
//        cout<<pn->b->next->next->num<<endl;
//cout<<c<<endl;
    p=pn->b;

    while(c--){
        if(pn->sum!=0){
            printf("-1\n");
            goto pwe;
        }
        pn=pn->next;
    }
    printf("%d\n",pp);
    pn=&pepo;
    while(pp--){
        printf("%d",pn->cnt);
        if(pp>=1){
            printf(" ");
        }else{
            printf("\n");
        }
        pn=pn->next;
    }

    pwe:;
    delete_node(pn); 
    return 0;
}

以下是不会超时的做法

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int M=1e6;
const int maxn = 1e6 + 10;

bool in[maxn];
int last[maxn];

vector<int>ans;

void fail(){
    printf("-1\n");
    exit(0);
}
//正负一对，以负的结尾
int main(){
    int n,ptr=0,tot=0;//ptr记录上一次截断的位置，tot记录这个时候是否成对的出现
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        if(x>0){
            if(in[x]) fail();//如果之前进入了，现在继续进入是不对的
            if(last[x]>ptr) fail();//这个是判断上一对是否和这一对会在一天，如果ptr<last[x]，则说明在同一天
            in[x]=1;//表示这个进入
            tot++;//表示对数+1
        }
        else {
            x=abs(x);
            if(!in[x]) fail();//如果从未进入过，则不能出去
            tot--;//合并
            in[x]=0;//表示已经出去
            last[x]=i;//表示这一对的结束位置，便于后面ptr的判断
        }
        if(tot==0){
            ans.push_back(i-ptr);//这个题目不要求最少的天数，所以直接加上去就可以了
            ptr=i;//ptr更新
        }
    }
    if(tot>0) fail();
    printf("%d\n",ans.size()*1);
    for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}