蓝桥杯 算法提高 盾神与条状项链

算法少女 2018-02-06

题目如下:

蓝桥杯 算法提高 盾神与条状项链蓝桥杯 算法提高 盾神与条状项链

本来自己写了个链表,但是写的有问题,通不过后3组数据,后来在同学的提示下,用数组模拟链表,然后我就用2元数组模拟双向链表,因为此题颜色不重复,所以模拟较为简单,代码如下:

#include<stdio.h>
typedef struct Color
{
    int pre;
    int next;
}color;
color c[100001];
int m,n;
int main()
{
    int i,j,cr,p0=0,n0,P,Q;
    char s[4];
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        scanf("%d",&cr);
        n0=cr;
        c[p0].next=n0;
        c[n0].pre=p0;
        p0=n0;
    }
    c[p0].next=-1;
    while(m)
    {
        scanf("%s",s);
        if(s[0]=='A')
        {
            scanf("%d%d",&P,&Q);
            p0=c[P].pre;
            c[p0].next=Q;
            c[Q].pre=p0;
            c[Q].next=P;
            c[P].pre=Q;
            n++;
        }
        if(s[0]=='D')
        {
            scanf("%d",&P);
            p0=c[P].pre;
            n0=c[P].next;
            c[p0].next=n0;
            c[n0].pre=p0;
            n--;
        }
        m--;
    }
    printf("%d\n",n);
    i=0;
    while(c[i].next!=-1)
    {
        printf("%d ",c[i].next);
        i=c[i].next;
    }
    return 0;
}

此代码已通过评测,因为查找删除添加时间都是O(1),所以比链表强很多。(如果颜色允许重复的话,可能会复杂点,但类似哈希的做法应该也比单纯的链表强很多)

蓝桥杯 算法提高 盾神与条状项链