高二了,最后一次参加noip了,AFO
人均过T1,只有我没有切掉qwq
,数组没有开到1e7,只开到了2e5,只得到了70pts
T2由于没有足够的dp能力,只想到了朴素的状压dp做法,得到了50pts
T3考场上也想不起来模拟退火的写法了,只写了非常水的随机化,只有20pts
T4码了蛮久的,中间还出现了一个小bug,就是一定要先走第3种边,再走1、2类型,否则会导致vis被标记了,而少走了一些点,期望得分44pts,
然而最后调试的时候清空vis用了memset,忘记把注释删掉了,最终会T掉,可能就会得到24pts。。。。。
期望得分:100+50+16+44=210 洛谷民间数据得分:70+50+16+24=160
AFO
P7960 [NOIP2021] 报数【民间数据】
直接埃氏筛即可,带一只log,但因为常数奇小,直接就能水过
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
struct query
{
int id,num,ans;
}q[maxn];
int T,is[maxn<<1];
void shai(int maxx)
{
for(int i=1;i<=maxx;i++)
{
int tmp=i;
if(!is[i])
{
while(tmp)
{
if(tmp%10==7) is[i]=1;
tmp/=10;
}
if(is[i])
for(int j=2;j*i<=maxx;j++)
is[i*j]=1;
}
}
}
bool cmp(query a,query b)
{
return a.num<b.num;
}
bool cmpp(query a,query b)
{
return a.id<b.id;
}
queue <int> pp;
bool check(int num)
{
if(num<=400000) return is[num];
int lim=sqrt(num),tmp=num;
while(tmp)
{
if(tmp%10==7) return 1;
tmp/=10;
}
tmp=num;
for(int i=2;i<=lim;i++)
if(tmp%i==0)
{
if(is[i]) return 1;
while(tmp%i==0) tmp/=i;
}
while(tmp)
{
if(tmp%10==7) return 1;
tmp/=10;
}
return 0;
}
int main()
{
// freopen("number.in","r",stdin);
// freopen("number.out","w",stdout);
scanf("%d",&T);
for(int i=1;i<=T;i++) scanf("%d",&q[i].num),q[i].id=i;
sort(q+1,q+T+1,cmp);
shai(q[T].num+5);
/*if(q[T].num>200000)
{
for(int i=1;i<=T;i++)
{
int now=q[i].num;
if(check(now)==1){q[i].ans=-1; continue;}
else{
while(1)
{
now++;
if(check(now)==0) {q[i].ans=now; break;}
}
}
}
sort(q+1,q+T+1,cmpp);
for(int i=1;i<=T;i++) printf("%d\n",q[i].ans);
return 0;
}*/
int now=0,pos=1;
while(pos<=T || pp.size())
{
while(pos<=T && q[pos].num<=now)
{
if(is[q[pos].num]) q[pos].ans=-1;
else pp.push(pos);
pos++;
}
now++;
if(!is[now])
{
while(!pp.empty())
{
q[pp.front()].ans=now;
pp.pop();
}
}
}
//for(int i=1;i<=200;i++) printf("%d:%d\n",i,is[i]);
//printf("[%d]",is[8006]);
sort(q+1,q+T+1,cmpp);
for(int i=1;i<=T;i++) printf("%d\n",q[i].ans);
return 0;
}
后续题解待补!2021
版权声明:本文为andyc_03原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。