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 ;
}