首页 > 代码库 > 喵哈哈村的狼人杀大战(4)
喵哈哈村的狼人杀大战(4)
http://qscoj.cn/problem/33/
描述
喵哈哈村最近热衷于玩一个叫做狼人杀的游戏!
徐元帅同学今天他抽到的是女巫的身份,按照他的一贯玩法,他喜欢一开始就把自己毒死。
于是他早早的就出去了。
他很无聊,于是出了一道题给自己玩。
他从怀里面掏出了一个数字n。
他想知道有多少组三元组(a,b,c),满足a<=b<=c,且a,b,c都是素数,而且a+b+c=n。
本题包含若干组测试数据。
每组测试数据只含有一个整数n。
1<=n<=10000
输出三元组的数量。
3 9
0 2
一直在想着打表,但打表后依然TLE,哎算了,还是积累方法吧。
#include<iostream> #include<cstring> #include<cmath> using namespace std; int n,i,j,k,sum,a[1300],b[20000],c[20000]; int prime(int x)//判断一个数是否是素数 { int i,o; if(x==1 || x==4) return 1; if(x==2 || x==3) return 0; o=sqrt(x); for(i=2;i<=o;++i) { if(x%i==0) return 1; else if(i>=o) return 0; } } int main() { int count=0; for(i=1;i<=10000;++i) { if(!prime(i)) a[count++]=i; } while(cin>>n) { k=0; memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(i=0;i<count;i++) { if(n>a[i]) { b[n-a[i]]++;//存对应a+b的值; c[n-a[i]]=a[i];//相当于存c; } else { break; } } for(i=0;i<count;i++) { for(j=i;j<count;j++) { sum=a[i]+a[j]; if(a[j]<=c[sum]) { k=k+b[sum];//查表 } else if(sum>n) { break; } } } cout<<k<<endl; } return 0; }
PS:相似题
Given S, a set of integers, ?nd the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.
Input Several S, each consisting of a line containing an integer 1 ≤ n ≤ 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between 536870912 and +536870911 inclusive. The last line of input contains ‘0’.
Output
For each S, a single line containing d, or a single line containing ‘no solution’.
Sample Input
5
2
3
5
7
12
5
2
16
64
256
1024
0
Sample Output
12
no solution
#include<iostream> #include<algorithm> using namespace std; int main() { long long n,a[1010],m,sum,k,i,j,o; while(cin>>n) { o=0; if(!n) return 0; for(i=0;i<n;i++) cin>>a[i]; sort(a,a+n); for(i=n-1;i>=0;i--) { for(j=n-1;j>=0;j--) { sum=a[i]-a[j]; if(j==i) continue; m=0; k=j-1; while(m<k) { if(a[m]+a[k]==sum) { o=1; cout<<a[i]<<endl; break; } else if(a[m]+a[k]>sum) k--; else m++; } if(o==1) break; } if(o==1) break; } if(o==0) cout<<"no solution"<<endl; } return 0; }
喵哈哈村的狼人杀大战(4)