素数链表 SDUT

M - 素数链表

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” 所有输出均不包括引号。

Sample Input

2 1 2 0 5 1 6 3 1 2 3 3 4 5 1 1 4

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，以此类推。

#include<bits/stdc++.h> using namespace std; struct node { int data; node *next; }; int n; int f(int k) { if(k==1||k==0) return 0; else if(k==2) return 1; else { int i; int book=0; for(i=2; i<=sqrt(k); i++) { if(k%i==0) { book=1; break; } } if(book) return 0; else return 1; } } node *creat(int n) { node *head,*tail,*p; head=new node; head->next=NULL; tail=head; int i; for(i=1; i<=n; i++) { p=new node; cin>>p->data; p->next=tail->next; tail->next=p; tail=p; } return head; } void del(node *head,int k) { if(k>n) printf("Invalid Operation\n"); else { node *p,*tail; p=head->next; tail=head; while(k-1) { k--; p=p->next; tail=tail->next; } if(f(p->data)) printf("Failed to delete %d\n",p->data); else { printf("Deleted %d\n",p->data); tail->next=p->next; free(p); p=tail->next; n--; } } } void pan(node *head) { node *p; p=head->next; int cnt=0; while(p!=NULL) { if(!f(p->data)) { cnt=1; break; } else p=p->next; } if(cnt) printf("All Completed. It's not a Prime Linked List\n"); else printf("All Completed. It's a Prime Linked List\n"); } int main() { int t; while(cin>>t) { int x=0; while(t--) { x++; printf("#%d\n",x); int q; cin>>n>>q; node *head; head=creat(n); while(q--) { int k; cin>>k; del(head,k); } if(n) pan(head); else printf("All Completed. It's not a Prime Linked List\n"); } } return 0; }