NOIP模拟测试12

T1 斐波那契

一道找规律题，被我做成了贼难的题。

观察图片可知x=f[i-1]+j。（j为x的父亲）且j<=f[i-1]，然后就二分找父亲没了。

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 const int mod=;

 ll f[];

 struct Hush{

     int head[],nxt[],cnt;

     ll to[];

     void insert(ll x)

     {

         int k=x%mod;

         to[++cnt]=x;

         nxt[cnt]=head[k];

         head[k]=cnt;

         return ;

     }

     bool find(ll x)

     {

         int k=x%mod;

         for(int i=head[k];i;i=nxt[i])if(to[i]==x)return ;

         return ;

     }

     void clear()

     {

         memset(head,,sizeof(head));

         cnt=;

     }

 }H;

 ll Getlca(ll a,ll b)

 {

     if(a>b)swap(a,b);

     H.clear();

     H.insert(a);

     while(a!=)

     {

         ll fa=lower_bound(f+,f+,a)-f;

         fa=a-f[fa-];

         H.insert(fa);

         a=fa;

     }

     if(H.find(b))return b;

     while(b!=)

     {

         ll fb=lower_bound(f+,f+,b)-f;

         fb=b-f[fb-];

         if(H.find(fb))return fb;

         b=fb;

     }

 }

 int main()

 {

     f[]=;f[]=;

     for(int i=;i<=;i++)f[i]=f[i-]+f[i-];

     int m;

     scanf("%d",&m);

     for(int i=;i<=m;i++)

     {

         ll a,b;

         scanf("%lld%lld",&a,&b);

         printf("%lld\n",Getlca(a,b));

     }

     return ;

 }

T2 水题不说了

T3 分组

一道好题。

k=1：

以前做过一道菜肴制作，然后就可以知道：区间越往后放，就越靠前。然后就维护最长的区间即可

k=2：

用扩展域并查集，直接维护，特判很恶心。

 #include<bits/stdc++.h>

 #define MAXN 333333

 using namespace std;

 int nxt[MAXN],a[MAXN],pf[MAXN],dr[MAXN],f[MAXN];

 bool vst[MAXN];

 vector<int>ans,cl;

 inline int find(int x)

 {

     return f[x]==x?x:f[x]=find(f[x]);

 }

 inline void merge(int x,int y)

 {

     int fa=find(x),fb=find(y);

     f[fa]=fb;

     return ;

 }

 void bcj_clear(int l,int r)

 {

     for(int i=l;i<=r;i++)f[a[i]]=a[i],vst[a[i]]=,dr[a[i]]=;

     cl.clear();

     return ;

 }

 int main()

 {

     int n,k,maxa=;

     scanf("%d%d",&n,&k);

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

             maxa=max(maxa,a[i]);

         }

         int ed=n;

         for(int i=;i<=;i++)pf[i]=i*i;

     if(k==)

     {

         for(int i=n;i>=;i--)

         {

             bool ok=;

             for(int j=sqrt(maxa*);j>=&&pf[j]>=a[i];j--)

                 if(vst[pf[j]-a[i]]){ok=;break;}

             if(!ok){

                 ed=i;

                 for(int k=;k<cl.size();k++)

                     vst[cl[k]]=;

                 cl.clear();

                 ans.push_back(i);

             }

             vst[a[i]]=;

             cl.push_back(a[i]);

         }

         if(!ans.size())printf("1\n");

         cout<<ans.size()+<<endl;

         for(int i=ans.size()-;i>=;i--)

             printf("%d ",ans[i]);

         return ;

     }

     else

     {

         int last=n;

         for(int i=;i<=maxa*;i++)f[i]=i;

         for(int i=n;i>=;i--)

         {

             bool ok=;

             for(int j=sqrt(maxa*);j>=&&pf[j]>=a[i];j--)

             {

                 if(vst[pf[j]-a[i]]&&!vst[a[i]])

                 {

 //                    cout<<i<<"---"<<endl;

                     int now=pf[j]-a[i];

                     if(find(a[i])==find(now)){ok=;break;}

                     if(!dr[now])dr[now]=a[i];

                     else if(dr[now]!=now)merge(dr[now],a[i]);

                     else {ok=;break;}

                     if(!dr[a[i]])dr[a[i]]=now;

                     else if(dr[a[i]]!=a[i])merge(dr[a[i]],now);

                     else {ok=;break;}

                 }

                 else if(vst[pf[j]-a[i]]&&a[i]==pf[j]-a[i])

                 {

 //                    cout<<i<<' '<<dr[a[i]]<<endl;

                     if(dr[a[i]]){ok=;break;}

                     else dr[a[i]]=a[i];

                     //cout<<i<<' '<<a[i]<<")S"<<endl;

                 }

             }

             if(!ok){

                 ed=i;

                 bcj_clear(i,last);

                 last=i;

                 ans.push_back(i);

             }

             vst[a[i]]=;

             cl.push_back(a[i]);

         }

         if(!ans.size()){printf("1\n");return ;}

         cout<<ans.size()+<<endl;

         for(int i=ans.size()-;i>=;i--)

             printf("%d ",ans[i]);

         return ;

     }

 }

主要反思一下：

考试策略不好，时间分配不合理，难度评估sb 认为T1最难，T3最水？？？？？？？？？

端正心态，不要去刚题，但也不要轻易放弃（暴力还是要打的）

巴特西

NOIP模拟测试12

最新文章

热门文章