ACM OJ 题目解题报告.docVIP

hdu 2138 How many prime numbers（求素数） 补充素数知识： 第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不必再用其他的数去除。第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明：如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2。如果d1和d2均大于√N，则有：N＝d1×d2√N×√N＝N。而这是不可能的，所以，d1和d2中必有一个小于或等于√N。 #includestdio.h #includemath.h #include queue #includealgorithm #include iostream #include string.h using namespace std; bool prime(int n) { int i; for(i=2;i=sqrt(n*1.0);i++) { if(n%i==0)return 0; } return 1; } int main() { int t; while(~scanf(%d,t)) { int ans=0; while(t--) { int temp; scanf(%d,temp); if(prime(temp))ans++; } printf(%d\n,ans); } return 0; } hdu 1052 Tian Ji -- The Horse Racing(贪心) 开始自己想了多种思路，但最终证明思路有误，于是去网上看了一下被人的思路，以下是仿照别人的思路写的 贪心思想（转载）： 1.当田忌最慢的马比齐王最慢的马快，赢一场先2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场3.当田忌最快的马比齐王最快的马快时，赢一场先。4.当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场。5.当田忌最快的马和齐王最快的马相等时，拿最慢的马来和齐王最快的马比. #includestdio.h #includemath.h #include queue #includealgorithm #include iostream #include string.h using namespace std; const int N=1005; int num1[N]; int num2[N]; int main() { int n; while(~scanf(%d,n)n) { int i,j; for(i=0;in;i++)scanf(%d,num1[i]); for(i=0;in;i++)scanf(%d,num2[i]); int ans=0; int tk=0; int kk=0; int tm=n-1; int km=n-1; sort(num1,num1+n,greaterint()); sort(num2,num2+n,greaterint()); for(i=0;in;i++) { if(num1[tk]num2[kk]) { ans++; tk++; kk++; } else if(num1[tk]num2[kk]) { ans--; kk++; tm--; } else { if(num1[tm]num2[km]) { ans++;