PAT basic level 1001-1019 解题笔记

1002 写出这个数

采用字符串输入数据，再对每位减去字符‘0’，得到该位相应的整数

    int len=s.length();//字符串的长度

    int t=;

    for(int i=;i<len;i++)//每位减去‘0’，逐位相加

    {

        t=t+s[i]-'';

    }

根据题意，所得数应小于1000，获取每位的数字采用整除取余的方法

==================================

1003 我要通过

这道题好坑爹，自己没有做出来，看了网上的程序。根据题意，字符串中有且必须有至少PAT各一个，P和T只能出现一次。aPbTc成立，则aPbATca成立，这里最坑爹，一直理解错误，实际这里的意思是，a,b,c只能是A，a与c中A的数目相同。而且对aPbATc(这里包括了前面说的aPbTc形式)，记a,b,c中A的次数分别为t1,t2,t3，则应满足t3=t2*t1。

参考的程序采用了string类的find_first_not_of();函数记录位置。最后判断是否满足上述关系。

===================================

1004 成绩排名

采用了动态数组。判断成绩项的大小，最后输出即可。

=======================================

1005 继续3n+1猜想

思路：利用一个缓存容器存放每个元素计算kalatz数列的结果，并与输入数列全部元素比较，如果有重合的则置零。比较过程中，遇到0不比较。比较结束后，将输入数列中的0元素删除得到“关键”元素，最后排序并输出。p.s. 其实感觉这种方法挺复杂的，不怎么好，智商捉急啊。

实现涉及到容器的删除：

ptr=v.erase(ptr);

=========================================

1007 素数对猜想

这个题目首先得得到素数，关于素数的求法网上有总结，利用素数的特征可以简化求取的过程。

chara1.只能被自己和1整除（1不是素数）

chara2.所有的偶数都不是素数（显然的，但是这条性质理解容易，编程的时候想到不易，且编且珍惜~~~~）

chara3.对数n，只需验证数sqrt(n)之前的素数是否能够整除即可

简化的方法有两种，一种是分10，100,10000，这样的区间去求，这种方法应该是所有方法中在数字比较大的时候最高效的，因为每次需要验证的数都少了很多。另外一种“筛法”，这种方法好理解，但是经验证在数据超过10000的时候就变得很慢，速度不及前一种方法。(果然还有更简单的方法 http://blog.csdn.net/cstopcoder/article/details/18795823)

至于满足题给条件的素数对，只需逐一验证即可。

==========================================

1008 数组循环右移

简单，先给出了数组的长度n和右移的位数m，只需要先从输入中获取n-m位数据A，再获取m位数据B，再把两组数据接起来就行了BA。

=====================================

1009 说反话

思路也简单，只需要以单词为单元，把单词倒序输出。实现上需要前后空格的位置，采用同1003的方法，把单词逐个压入栈中，最后输出即可（用top函数）。

p.s. 一开始把题目看错了，以为是把每个单词中的字母顺序反过来，费了大半天功夫实现发现不和题意。可见认真审题的重要性啊！

======================================

1010 一元多项式求导

这里需要判断回车，之前采用string类先整体输入，再删除空格，然后转化为数字的方法，但是实现起来相当麻烦。网上搜了半天找到了如下的办法：

    vector<int> v;

    vector<int>::iterator ptr;

    char c;

    int temp;

    while((c=cin.get())!='\n')//判断输入是否为回车

    {

        cin.unget();//若不是则将字符放回流中

        cin>>temp;

        v.push_back(temp);

    }

另外，还需要考虑最后把常数项求导结果删除，采用-1作为特征数，把-1和前面的0删除。还需注意幂为负数的情况。

======================================

1011 A+B和C

看起来很简单，但是两个int型相加有可能会超出int的范围，采用double型数据规避这个问题，不知还有没有好方法……

刷了11道basic level 感觉简单的倒是挺简单的，可以很快搞出来，但是需要注意详细审题，把各种情况考虑周全。难的题最多的可能花了一天才搞出来，这还何谈advanced level 90分以上啊！！路漫漫啊！加油！

======================================

1012 数字分类

这道题不难，只需要对每个数字对5取余，按情况分类即可。其中用到了switch,比较基础。另外用到了输出的精度设置。精度的设置需要使用iomanip头文件下的setprecision 函数，在流对象中，setprecision(n)设置有效数字位数为n，如果需要固定小数点后的位数则需另外加上fixed，如

float num=1245.234567；

cout<<num<<endl

      <<setprecision()<<num<<endl

      <<fixed<<setprecision()<<num<<endl;

输出依次为1245.23，1.25e+003，1245.234，这里没设置精度时默认输出六位有效数字。

==========================================

1013 数素数

按理说，在1007的基础上这道题不难解，但是，按照分段求的方法，需要控制求素数的范围以提高效率。这样就需要知道各段内的素数个数，虽然这样最后实现了，但是程序还是一如既往的乱，绕得晕头转向。最后借鉴了别人的求素数的方法，如1007最后加的连接。

=======================================

1014 福尔摩斯的约会

这道题比较坑，跟PAT那道一样，需要仔细审题，把题目中的意思详细理解清楚。比如第一个求星期那里，需要限制字符A-Z，在这里栽了很多次。

================================

1015 德才论

这道题需要做两件事情，第一是统计总分，第二件是归类。我的思路是先按总分排序，然后依次输出符合每类条件的信息。这样做就有排序按什么排的问题。一开始利用冒泡排，有三个点过不去。后来看了别人的博客，这里有两点需要注意的，第一是排序的方法，最好使用O(nlgn)的算法。STL中自带的sort，可以按照输入待排序数据的个数合理选择方法。另外还有qsort()函数。sort()函数默认是升序排序，如果需要降序可以编写自己的compare函数，如果需要控制排序对象的排序规则，也可以编写自己的compare函数实现。

===============================

1016-1019 都比较简单

================================

1020 月饼

这道题要求算出最大的利润，开始还以为是线性规划，搞得觉得做不出来，变量太多。看了别人的解释，发现自己太没有生意头脑了……至于解的过程是比较简单的的，只要按照单价由高到低购买，直到满足总的采购量为止，算法用了O(n2)的，在1000个数据以内应该没啥问题。没有想出来更好的算法。