sdutacm-期末考试 素数链表

素数链表
           

文章链接：http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2163/pid/3873.html

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

我们定义素数链表为元素全部是素数的链表。

给定一个初始含有 n 个元素的链表，并给出 q 次删除操作，对于每次操作，你需要判断链表中指定位置上的元素，如果元素存在且不是素数则删除。

在所有操作完成后你还需要检查一下最终链表是否是一个素数链表。

Input

输入数据有多组。第 1 行输入 1 个整数 T (1 <= T <= 25) 表示数据组数。

对于每组数据：

第 1 行输入 2 个整数 n (1 <= n <= 50000), q (1 <= q <= 1000) 表示链表初始元素数量和操作次数
第 2 行输入 n 个用空格隔开的整数（范围 [0, 1000]）表示初始链表
接下来 q 行，每行输入 1 个整数 i (1 <= i <= 50000)，表示试图删除链表中第 i 个元素
           

Output

对于每组数据：

先输出 1 行 "#c"，其中 c 表示当前是第几组数据
对于每次删除操作，根据情况输出 1 行：
    如果要删除的位置不存在元素（位置超出链表长度），则输出 "Invalid Operation"
    如果要删除的位置存在元素且此位置的元素是非素数，则删除元素并输出 "Deleted x"，其中 x 为成功删除的数（必须为非素数才能删除）
    如果要删除的位置存在元素且此位置的元素是素数，则输出 "Failed to delete x"，其中 x 为此位置上的数
删除操作全部进行完毕后，则还需判断该链表现在是否为一个素数链表。如果链表非空且是素数链表，则输出 "All Completed. It's a Prime Linked List"，否则输出 "All Completed. It's not a Prime Linked List"
           

所有输出均不包括引号。

Example Input

2

1 2

5

1

6 3

1 2 3 3 4 5

1

1

4

Example Output

1

Invalid Operation

Deleted 0

All Completed. It’s not a Prime Linked List

2

Deleted 1

Failed to delete 2

Deleted 4

All Completed. It’s a Prime Linked List

Hint

推荐直接复制粘贴输出语句字符串到你的代码中，以防手打敲错。

链表中第 1 个元素的位置为 1，第 2 个元素的位置为 2，以此类推。

Author

「2016级《程序设计基础(B)II》期末上机考试-第一场」bLue

学长题解：

http://paste.ubuntu.com/24541434/

题目坑点：因为这个题是链表题，所以卡时间卡的厉害，首先判断素数要用到开平方，其次链表在用完之后要释放这里容易 runtime error，还有初始链表时要一下子建下来，一个一个插入会超时，其次链表长度top要用引用值，不然无法直接改变，1,0不是素数要特判，与此类似的还有螺旋填数，要把矩阵初始为-1，否则一直wr，最好加一个打印函数，每进行一次操作就打印一次，尽量把操作都分解为函数。先写这些吧

下面是ac代码

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    struct node*next;
};
bool pan(int num)
{
    bool f = true;
    if(num<=)
        return false;
    for(int i=; i<=sqrt(num); i++)
    {
        if(num%i==)
        {
            f = false;
            break;
        }
    }
    return f;
}
void insert(node*head,int num)
{
    node*p;
    node *t = new node;
    p = head;
    while(p->next)
        p = p->next;
    t->data = num;
    t->next = NULL;
    p->next = t;
    //return head;

}
node* build(node*head,int n)
{

    int num;
    node*tail = head;
    while(n--)
    {
        cin>>num;
        node*p = new node;
        p ->data = num;
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    return head;
}
void show(node*head)
{

    node*p = head->next;
    while(p)
    {
        printf("%d",p->data);
        p = p->next;
    }
    cout<<endl;
}
void del(int num,int &top,node*head)
{
    node*p = head;
    node*q = head;
    while(num--)
    {
        if(num!=)
            q = q->next;
        p = p->next;
    }

    if(!pan(p->data))
    {
        printf("Deleted %d\n",p->data);
        q->next = p->next;
        free(p);
        top--;

    }
    else
        printf("Failed to delete %d\n",p->data);
    //show(head);
}
void zui(node*head,int n)
{
    if(n!=)
    {
        node*p = head;
        int f = ;
        while(n--)
        {
            p = p->next;
            if(p)
            {
                if(!pan(p->data))
                {
                    f = ;
                    break;
                }
            }
        }
        if(f)
            printf("All Completed. It's a Prime Linked List\n");
        else
            printf("All Completed. It's not a Prime Linked List\n");

    }
    else
        printf("All Completed. It's not a Prime Linked List\n");
}
int main()
{
    int t;
    int n,q;
    cin>>t;
    for(int o=; o<=t; o++)
    {
        cin>>n>>q;
        node*head;
        head = new node;
        head->next =NULL;
        head = build(head,n);
//        for(int i=; i<=n; i++)
//        {
//            int num;
//            scanf("%d",&num);
//            insert(head,num);
//        }
        //show(head);
        printf("#%d\n",o);
        int top = n;
        while(q--)
        {
            int num;
            cin>>num;
            if(num<||num>top)
            {
                printf("Invalid Operation\n");
            }
            else
            {
                del(num,top,head);

            }
        }
        zui(head,top);
        node*p = head->next;
        //node*q;
        while(p)
        {
            node*q = p;
            p = p->next;
            free(q);

        }

    }

    // show(head);




    return ;
}