TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
原題:http://zerojudge.tw/ShowProblem?problemid=a569
AC:http://zerojudge.tw/Submissions? ... mp;account=lfs92002
解法:質數表
把質數表建出來後線性掃描即可,懶得IO優化,用STL亂做,用了100多MB的記憶體...
/**********************************************************************************/
/* Problem: a569 "2-絕對遞增的質數子數列" from 台北市101學年度軟體設計競賽*/
/* Language: CPP (731 Bytes) */
/* Result: AC(1.6s, 112.3MB) judge by this@ZeroJudge */
/* Author: lfs92002 at 2014-06-27 18:52:11 */
/**********************************************************************************/
#include<cstdio>
#include<algorithm>
#include<vector>
#include<sstream>
using namespace std;
char input[1000000];
bool isnp[10000001]={true,true,false};
int main()
{
stringstream ss;
int i=2,j;
long long tmp,last,sum,ans;
while(i<3163){
if(!isnp[i]){
j=i*i;
while(j<10000001){
isnp[j]=true;
j+=i;
}
}
++i;
}
while(gets(input)){
ss.clear();
ss<<input;
ans=sum=0;
last=-1;
while(ss>>tmp)
{
if(!isnp[tmp])
{
if(last==-1)last=tmp;
if(last<tmp)
{
sum+=tmp;
}
else
{
sum=tmp;
}
ans=max(sum,ans);
//printf("%d ",ans);
last=tmp;
}
else
sum=0;
}
printf("%lld\n",ans);
}
}
|
|