pat乙级试题,C++算法题训练
¶素数
¶题目描述
令Pi表示第i个素数。现任给两个正整数M <= N <= 10000,请输出PM到PN的所有素数。
¶输入描述:
输入在一行中给出M和N,其间以空格分隔。
¶输出描述:
输出从PM到PN的所有素数,每10个数字占1行,其间以空格分隔,但行末不得有多余空格。
代码
#include
#include<math.h> using namespace std; class prime { int pri; public: void set_pri(int i) {pri=i;} int get_p() { int i; for(i=1;i<=sqrt(pri);i++) { if(pri%i==0&&i!=pri&&i!=1)return pri; } return 0; } }; int main() { prime a; int i,j=0,m,n; cin>>m>>n; for(i=2;i<=1000000;i++) { a.set_pri(i); if(a.get_p()==0) { j++; if(m<=j&&j<n&&(j-m+1)%10!=0)cout<<i<<" "; if(m<=j&&j<n&&(j-m+1)%10==0)cout<<i<<endl; if(j==n&&j!=m)cout<<i; if(j==m&&j==n)cout<<i; } if(j>n)break; } }
¶反转链表 (25)
时间限制 2000 ms内存限制 150400 KB代码长度限制 100 KB判断程序
¶题目描述
给定一个常数K以及一个单链表L,请编写程序将L中每K个结点反转。例如:给定L为1→2→3→4→5→6,K为3,则输出应该为
3→2→1→6→5→4;如果K为4,则输出应该为4→3→2→1→5→6,即最后不到K个元素不反转。
输入描述:
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N),即要求反转的
子链结点的个数。结点的地址是5位非负整数,NULL地址用-1表示。
接下来有N行,每行格式为:
Address Data Next
其中Address是结点地址,Data是该结点保存的整数数据,Next是下一结点的地址。
输出描述:
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
输入例子:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出例子:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
代码如下
|
有几个PAT(25)
时间限制 1000 ms内存限制 32768 KB代码长度限制 100 KB判断程序
¶题目描述
字符串APPAPT中包含了两个单词“PAT”,其中第一个PAT是第2位§,第4位(A),第6位(T);第二个PAT是第3位§,第4位(A),第6位(T)。
现给定字符串,问一共可以形成多少个PAT?
¶输入描述:
输入只有一行,包含一个字符串,长度不超过105,只包含P、A、T三种字母。
¶输出描述:
在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大,只输出对1000000007取余数的结果。
¶输入例子:
APPAPT
¶输出例子:
2
这题我本以为挺简单,用三个循环就可以完成了
后来用三个循环来做,对于短的字符串确实可以,但是对于长的字符创
比如长度为105,那么循环的次数会超大,所以直接段错误
后来看了大佬的算法,才发现原来可以这样
代码:
|