高二了，最后一次参加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