首页 > 代码库 > HDU5104-BC18简单粗暴的题

HDU5104-BC18简单粗暴的题

/*
	今天掉排名快哭了,做题做不对就算了,Hack都错了无数……
	
	以后做题记得涨经验:
		一:自己判定最大的数据量。此题count=1229
		二:时间复杂度。开始的超时代码肯定会超时:因为枚举量为count^3。必须超时啊……
		三:交题之前不着急。多写数据给自己测试,尤其是边界和大数据。也方便自己后来的Hack
			不要因为想抢一两分钟的时间,而罚分罚时影响心情
		四:每次BC的第一题其实看了题解都不难,自己的第一思路也对,注意代码细节处理
		五:把自己的初始目标定低:只要求对,不要求时间,更是为了FT准备
			自己不清楚有多少次是渣渣代码运气好过了初测然后9点之后看排名就是最后,看分数就是 0 
		六:之后要做总结:
			首先要把没有读懂的题再看看,很多时候ACM就是考阅读理解 
			总结对了的题:思路是不是最好;实现有没有更简单的;代码能不能更加简单易懂;
						  有没有认真分析其时间空间复杂度(确保不是碰运气) 
			总结有思路做不了的题:某些听过很熟悉或是会用的知识点不精通。
								  这是通过这道题学习一个新的专题的最好机会
								  像今天的BC18-4,看着就是线段树,自己没法动笔
			能够看懂题没思路:尽能力去学吧 
			
	言归正传:HDU5014
	思路:枚举前两个。那么只需满足的条件是:第三个数是素数且比第二个素数大即可计数!
	
*/ 

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define MAXN 100000

int tot=0;
int tag[MAXN],p[MAXN];

void getprime(int n)//线性筛素数模版 
{
	for(int i=2;i<n;i++)
	{
		if (!tag[i]) p[tot++]=i;
		for(int j=0;j<tot&&p[j]*i<n;j++)
		{
			tag[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}
}

int check(int x)
{
	for(int i=2;i*i<=x;i++)
		if (x%i==0) return 0;
	return 1;
}

int main() 
{
	int i,j,k,n;
	getprime(10000);
	while(cin>>n)
	{
		int ans=0;
		For2(i,0,tot-1) //枚举第一层 
		if (p[i]<n)
			For2(j,i,tot-1)//枚举第二层 
			if (p[i]+p[j]<n&&n-p[i]-p[j]>=p[j])//判断 
				if (check(n-p[i]-p[j])) ans++;
		printf("%d\n",ans);
	}
	return 0;
}

HDU5104-BC18简单粗暴的题