2017-10-28 noip模拟赛by WISCO 信息组

第一次做模拟赛，自我感觉良好（大概是这套题比较简单）

T1 名称为“数据结构”，这也太坑了点……233

要维护一个数列（初始为零），支持区间加与查询。

查询的是一个区间中有多少数满足min<=(a[i]*i%mod)<=max，其中min、max、mod是一开始给出来的，a[i]表示这个数的值，i表示这个数的编号

n<=80000，一开始修改与查询个数<=1e6，后面会跟不超过1e7个查询

我看到这道题，想到了线段树，主要觉得这样好查询一个区间内有多少满足条件的

可是，由于条件比较诡异，所以菜鸡的我只能单点修改……最后查询呢，每一次logn

这样得了50分

正解：差分！

首先看到题目后面会接一堆查询吗，那可以用前缀和维护啊！（用线段树每次都logn，前缀和只需提前处理一下然后O(1)就好了，我是何苦啊……）

前面的，就是差分了。每次区间加时a[l]+=x,a[r+1]-=x就可以了，查询时每个点这时的值就是a[1]+...+a[i]

这有些类似树状数组中的区间加诶，但前面的查询是一个点一个点查，所以不用树状数组，直接数组就行了

代码：

（特别注意：有的地方要转long long啊，幸亏样例良心，否则我要go die 了）

 #include<cstdio>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const int MAXN = ;

 ll a[MAXN];

 int b[MAXN];

 int n,opt,mod,Min,Max,Q;

 int main()

 {

     int i,y,l,r,ans;

     ll sum,x;

     char ch;

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

     scanf("%d%d%d",&mod,&Min,&Max);

     while(opt--){

         cin>>ch;

         if(ch=='A'){

             scanf("%d%d%lld",&l,&r,&x);

             a[l]+=x;a[r+]-=x;

         }

         else{

             scanf("%d%d",&l,&r);

             sum=;ans=;

             for(i=;i<=r;i++){

                 sum+=a[i];

                 if(i>=l)

                 {

                     y=(sum*i)%mod;

                     if(y>=Min && y<=Max) ans++;

                 }

             }

             printf("%d\n",ans);

         }

     }

     sum=;

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

         sum+=a[i];

         y=sum*i%mod;

         if(y>=Min && y<=Max) b[i]=b[i-]+;

         else b[i]=b[i-];

     }

     scanf("%d",&Q);

     while(Q--){

         scanf("%d%d",&l,&r);

         printf("%d\n",b[r]-b[l-]);

     }

     return ;

 }

T2 “答案错误”

非常有趣的一道数学题~

凭借多年积累的找规律技巧，构造出了答案（YEAH）

具体题目及证明略……

但是提交上去竟只有90分！！有一个点被卡常了（悲伤）

回来看看，发现是找规律没太彻底，多了两个if语句，下次要注意了……

代码：

 #include<cstdio>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 int n,Q;

 ll k;

 int main()

 {

     int ans,r;

     ll x;

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

     while(Q--){

         scanf("%lld",&k);

         x=k-;

         ans=;

         while(x){

             if(x%==) ans++;

             x>>=;

         }

         if(ans%==) printf("X\n");

         else printf("Z\n");

     }

     return ;

 }

T3 “部落冲突”

n个部落，n-1条双向边形成一棵树，相邻部落有时会打仗，有时会停战

打仗时两个部落间的道路不能通行

在某个时间，查询某两个部落是否可以互相到达

看完题，想到这就是一道树链剖分吗，兴高采烈地写了一遍。结果90分，被卡常了一个点（悲伤）

正解：树上差分！

每一次两个点间的路径拆成两个点分别到lca的路径

维护一下每个点到根节点的链中有几条路打仗

判断是就看S(u)+S(v)-2*S(lca(u,v))是否为零就好啦

怎么维护呢？

按dfs序来，对于每一条打仗的边，从进这个点的时间戳开始+1，出这个点的时间戳开始-1，维护前缀和

边边点点的要想清楚！！！

前缀和用树状数组维护，每次查询logn

代码：

 #include<cstdio>

 #include<iostream>

 using namespace std;

 const int MAXN = ;

 struct node{

     int v;

     node *next;

 }pool[*MAXN],*h[MAXN];

 int cnt;

 void addedge(int u,int v){

     node *p=&pool[++cnt],*q=&pool[++cnt];

     p->v=v;p->next=h[u];h[u]=p;

     q->v=u;q->next=h[v];h[v]=q;

 }

 int vis[MAXN],fa[MAXN],dep[MAXN],size[MAXN],son[MAXN];

 int top[MAXN],rk[MAXN],w[MAXN],tot;

 void dfs1(int u){

     int v,sonnum=,Mson=;

     size[u]=;

     vis[u]=;

     for(node *p=h[u];p;p=p->next){

         v=p->v;

         if(!vis[v]){

             fa[v]=u;

             dep[v]=dep[u]+;

             dfs1(v);

             size[u]+=size[v];

             if(size[v]>sonnum) sonnum=size[v],Mson=v;

         }

     }

     son[u]=Mson;

 }

 void dfs2(int u){

     int v;

     v=son[u];

     if(v){

         top[v]=top[u];

         rk[v]=++tot;

         dfs2(v);

     }

     for(node *p=h[u];p;p=p->next){

         v=p->v;

         if(fa[v]==u && v!=son[u]){

             top[v]=v;

             rk[v]=++tot;

             dfs2(v);

         }

     }

     w[u]=++tot;

 }

 int lca(int x,int y){

     int f1=top[x],f2=top[y];

     while(f1!=f2){

         if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);

         x=fa[f1];f1=top[x];

     }

     if(dep[x]>dep[y]) swap(x,y);

     return x;

 }

 struct Bit{

     int c[MAXN*];

     int lowbit(int x){

         return x&(-x);

     }

     int sum(int x){

         int ret=;

         while(x>){

             ret+=c[x];

             x-=lowbit(x);

         }

         return ret;

     }

     void add(int x,int y){

         while(x<=MAXN*){

             c[x]+=y;

             x+=lowbit(x);

         }

     }

 }d;

 int hisnum,his[MAXN];

 int main()

 {

     int n,m,x,y,i,l,f;

     char ch;

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

     for(i=;i<n;i++) scanf("%d%d",&x,&y),addedge(x,y);

     dep[]=;dfs1();

     top[]=;rk[]=;tot=;dfs2();

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

         cin>>ch;

         if(ch=='C'){

             scanf("%d%d",&x,&y);

             if(y==fa[x]) swap(x,y);

             his[++hisnum]=y;

             d.add(rk[y],);

             d.add(w[y],-);

         }

         else if(ch=='U'){

             scanf("%d",&x);

             y=his[x];

             d.add(rk[y],-);

             d.add(w[y],);

         }

         else{

             scanf("%d%d",&x,&y);

             l=lca(x,y);

             f=d.sum(rk[x])+d.sum(rk[y])-*d.sum(rk[l]);

             if(f==) printf("Yes\n");

             else printf("No\n");

         }

     }

   //  system("pause");

     return ;

 }

总结：

1.不要把思路老局限在一个东西上，比如第一题

2.灵活变通，不要学死

比如，树上差分也可以完成许多树链剖分可完成的东西啊！

3.前缀和是一个好东西，要学会用它

4.差分也是个好东西，要学会用它

5.写完代码后，记得修改一下耗时多的地方，再将代码完美一下。不要像第二题一样……（好心痛）

6.学会分析复杂度

第一题后面那些查询用前缀和我竟没想到……66

7.注意开long long

巴特西

2017-10-28 noip模拟赛by WISCO 信息组

最新文章

热门文章