NOIP模拟21+22

模拟21确实毒瘤。。。考场上硬刚T3 2.5h，成功爆零

T1.数论

　　看这题目就让人不想做，考场上我比较明智的打完暴力就弃掉了，没有打很久的表然后找规律。

　　正解貌似是乱搞，我们考虑一个比较显然的结论：

　　对于一个质数 p,我们考虑所有仅包含小于 p 的质因子的正整数集 G。不难发现:
　　• 若 x ∈ G,且在 G 中已经有超过 K 个小于 x 的整数约数个数多于 x,即 x 一定不是良好的,
　　则 xp^c (c ≥ 0) 也一定不可能是良好的。

　　于是我们可以利用已知的良好的数筛出接下来“可能良好”的数，再在这些数里面排除，除去确定的不是良好的数，即可得到所有良好的数。

T2.

　　大概是这三道题里最水的？

　　思路卡壳点：最终的答案与c的大小无关，只与c二进制位中1的个数有关。

　　发现了这个结论，我们就可以很愉快的dp了。

T3.

　　我们可以采取逐位确定的方法，首先求出以每个点为根时dfs序的总方案数，接下来：

　　设当前点所要对应b数列中的p位置，若当前点<b[p],那么直接累加随便走的方案数;若当前点>b[p]，break;否则，p++，去当前点的子树中寻找进行同样的过程。

　　说起来很容易，实际操作挺shi的，反正我调了一晚上。。。。

 #include<bits/stdc++.h>

 #define mod 1000000007

 #define ll long long

 using namespace std;

 int n,fi[],ne[],to[],b[],du[],tot,p,siz[],tt,sum[],r[],lc[],rc[];

 ll f[],js[],ans,ni[],ff[],fc[];

 vector<int>h[];

 bool v[];

 inline int read(){

     int x=;

     char ch=getchar();

     while(ch<''||ch>'')ch=getchar();

     while(ch>=''&&ch<='')x=(x<<)+(x<<)+ch-,ch=getchar();

     return x;

 }

 inline ll qpow(ll x,ll y){

     ll ans=;

     while(y){

         if(y&)ans=ans*x%mod;

         x=x*x%mod;

         y>>=;

     }

     return ans;

 }

 inline void add(int x,int y){

     ne[++tot]=fi[x];

     fi[x]=tot;

     to[tot]=y;

 }

 ll dfs(int x,int fa){

     ff[x]=;siz[x]=;

     for(int i=fi[x];i;i=ne[i]){

         int y=to[i];

         if(y!=fa){

             ff[x]=ff[x]*dfs(y,x)%mod;

             siz[x]+=siz[y];

         }

     }

     ff[x]=ff[x]*js[fa?du[x]-:du[x]]%mod;

     return ff[x];

 }

 void insert(int &x,int l,int r,int pos,int val){

     if(!x)x=++tt;

     if(l==r){

         sum[x]+=val;

         return;

     }

     int mid=(l+r)>>;

     if(pos<=mid)insert(lc[x],l,mid,pos,val);

     else insert(rc[x],mid+,r,pos,val);

     sum[x]=sum[lc[x]]+sum[rc[x]];

 }

 int query(int x,int l,int r,int pos){

     if(pos<=)return ;

     if(l==r)return sum[x];

     int mid=(l+r)>>;

     if(pos<=mid)return query(lc[x],l,mid,pos);

     return query(rc[x],mid+,r,pos)+sum[lc[x]];

 }

 bool check(int x,int l,int r,int pos){

     if(l==r)return sum[x];

     int mid=(l+r)>>;

     if(pos<=mid)return check(lc[x],l,mid,pos);

     return check(rc[x],mid+,r,pos);

 }

 bool dfs2(int x,int fa){

     int la=p+,num=fa?du[x]-:du[x];

     fc[x]=;p++;

     ll t=;

     sort(h[x].begin(),h[x].end());

     for(int i=fi[x];i;i=ne[i])

         if(to[i]!=fa)

             insert(r[x],,n,to[i],);

     while(p-la!=siz[x]-){

         num--;int y=b[p+];

         ff[x]=ff[x]*qpow(num+,mod-)%mod;

         fc[x]=(fc[x]+query(r[x],,n,b[p+]-)*ff[x])%mod;

         if(!check(r[x],,n,b[p+])){

             p=siz[x]+la-;

             return false;

         }

         insert(r[x],,n,b[p+],-);

         ff[x]=ff[x]*qpow(ff[y],mod-)%mod;

         if(!dfs2(b[p+],x)){

             p=siz[x]-+la;

             fc[x]=(fc[x]+fc[y]*ff[x])%mod;

             return false;

         }

         fc[x]=(fc[x]+fc[y]*ff[x])%mod;

     }

     return true;

 }

 int main(){

 //    freopen("t.in","r",stdin);

     n=read();js[]=;ni[]=;

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

         b[i]=read();

     for(int i=,x,y;i<n;i++){

         x=read(),y=read();

         add(x,y);add(y,x);

         du[x]++,du[y]++;

     }

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

         js[i]=js[i-]*i%mod,ni[i]=qpow(js[i],mod-);

     f[]=js[du[]];

     for(int i=;i<=n;i++)f[]=f[]*js[du[i]-]%mod;

     for(int i=;i<=b[];i++)

         f[i]=f[]*ni[du[i]-]%mod*js[du[i]]%mod*ni[du[]]%mod*js[du[]-]%mod;

     for(int i=;i<=b[];i++){

         if(i<b[]){

             ans=(ans+f[i])%mod;

         }

         if(i==b[]){

             p=;

             dfs(i,);

             dfs2(i,);

             ans=(ans+fc[i])%mod;

         }

     }

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

     return ;

 }

模拟23

　T1.

　　简单dp,没了.

T2.

　　这题做法非常的多,我可能是唯一一个二分AC的,细节很多,考试时少剪一个枝T成了60

　　对于每一个点他的积水高度显然单调,我们可以二分这个高度,然后从这个点开始dfs,若成立,将与该点相连的所有高度小于ans的全部改成这个高度,注意不要重复遍历同一点,会将复杂度从n^2变成n^3

　　二分挺恶心的,不重复遍历特判错了很容易wa,重复遍历就会T

　　总复杂度nmlognm,复杂度还是正确的.

 #include<bits/stdc++.h>

 #define cri const register int

 using namespace std;

 const int zx[]={,-,,},zy[]={,,-,};

 int n,m,a[][],res[][],tim;

 int vv[][],tot;

 char v[][];

 bool dfs2(cri x,cri y,cri val){

     if(a[x][y]>=val)return true;

     vv[x][y]=tim;

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

         int ax=x+zx[i],ay=y+zy[i];

         if(ax<||ay<||ax>n+||ay>n+)return false;

         if(v[ax][ay]&&a[ax][ay]+res[ax][ay]<val)return false;

         if(v[ax][ay]&&a[ax][ay]>=val)continue;

         if(vv[ax][ay]!=tim){

             if(!dfs2(ax,ay,val))return false;

         }

     }

     return true;

 }

 inline bool check(int x,int y,int val){

     tim++;

     return dfs2(x,y,val);

 }

 void dfs(cri x,cri y,cri val){

     res[x][y]=max(val-a[x][y],);

     v[x][y]=true;

     if(a[x][y]>=val)return;

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

         int ax=x+zx[i],ay=y+zy[i];

         if(v[ax][ay]||ax<=||ay<=||ax>n||ay>m)continue;

         dfs(ax,ay,val);

     }

 }

 struct keng{

     int x,y,a;

     friend bool operator < (keng a,keng b){

         return a.a<b.a;

     }

 }aa[];

 int main(){

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

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

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

             scanf("%d",&aa[++tot].a),aa[tot].x=i,aa[tot].y=j,a[i][j]=aa[tot].a;

     sort(aa+,aa+tot+);

     for(int i=;i<=tot;i++){

         if(!v[aa[i].x][aa[i].y]){

             int l=,r=1e9,ans=-1e9;

             while(l<=r){

                 int mid=(l+r)>>;

                 if(check(aa[i].x,aa[i].y,mid))ans=max(ans,mid),l=mid+;

                 else r=mid-;

             }

             dfs(aa[i].x,aa[i].y,ans);

         }

     }

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

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

             printf("%d ",res[i][j]);

         puts("");

     }

     return ;

 }

T3,

　　容斥好题

　　我是看题解做的,主要解释一下f (i) = ∑ d μ(d)g(d)

　　算了不想打公式了,自己反演去吧

巴特西

NOIP模拟21+22

最新文章

热门文章