模拟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的，反正我调了一晚上。。。。

1 #include
      
         2 #define mod 1000000007  3 #define ll long long  4 using namespace std;  5 int n,fi[300005],ne[600005],to[600005],b[300005],du[300005],tot,p,siz[300005],tt,sum[30000005],r[300005],lc[30000005],rc[30000005];  6 ll f[300005],js[300005],ans,ni[300005],ff[300005],fc[300005];  7 vector
       
        h[300005];  8 bool v[300005];  9 inline int read(){ 10     int x=0; 11     char ch=getchar(); 12     while(ch<'0'||ch>'9')ch=getchar(); 13     while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-48,ch=getchar(); 14     return x; 15 } 16 inline ll qpow(ll x,ll y){ 17     ll ans=1; 18     while(y){ 19         if(y&1)ans=ans*x%mod; 20         x=x*x%mod; 21         y>>=1; 22     } 23     return ans; 24 } 25 inline void add(int x,int y){ 26     ne[++tot]=fi[x]; 27     fi[x]=tot; 28     to[tot]=y; 29 } 30 ll dfs(int x,int fa){ 31     ff[x]=1;siz[x]=1; 32     for(int i=fi[x];i;i=ne[i]){ 33         int y=to[i]; 34         if(y!=fa){ 35             ff[x]=ff[x]*dfs(y,x)%mod; 36             siz[x]+=siz[y]; 37         } 38     } 39     ff[x]=ff[x]*js[fa?du[x]-1:du[x]]%mod; 40     return ff[x]; 41 } 42 void insert(int &x,int l,int r,int pos,int val){ 43     if(!x)x=++tt; 44     if(l==r){ 45         sum[x]+=val; 46         return; 47     } 48     int mid=(l+r)>>1; 49     if(pos<=mid)insert(lc[x],l,mid,pos,val); 50     else insert(rc[x],mid+1,r,pos,val); 51     sum[x]=sum[lc[x]]+sum[rc[x]]; 52 } 53 int query(int x,int l,int r,int pos){ 54     if(pos<=0)return 0; 55     if(l==r)return sum[x]; 56     int mid=(l+r)>>1; 57     if(pos<=mid)return query(lc[x],l,mid,pos); 58     return query(rc[x],mid+1,r,pos)+sum[lc[x]]; 59 } 60 bool check(int x,int l,int r,int pos){ 61     if(l==r)return sum[x]; 62     int mid=(l+r)>>1; 63     if(pos<=mid)return check(lc[x],l,mid,pos); 64     return check(rc[x],mid+1,r,pos); 65 } 66 bool dfs2(int x,int fa){ 67     int la=p+1,num=fa?du[x]-1:du[x]; 68     fc[x]=0;p++; 69     ll t=0; 70     sort(h[x].begin(),h[x].end()); 71     for(int i=fi[x];i;i=ne[i]) 72         if(to[i]!=fa) 73             insert(r[x],1,n,to[i],1); 74     while(p-la!=siz[x]-1){ 75         num--;int y=b[p+1]; 76         ff[x]=ff[x]*qpow(num+1,mod-2)%mod; 77         fc[x]=(fc[x]+query(r[x],1,n,b[p+1]-1)*ff[x])%mod; 78         if(!check(r[x],1,n,b[p+1])){ 79             p=siz[x]+la-1; 80             return false; 81         } 82         insert(r[x],1,n,b[p+1],-1); 83         ff[x]=ff[x]*qpow(ff[y],mod-2)%mod; 84         if(!dfs2(b[p+1],x)){ 85             p=siz[x]-1+la; 86             fc[x]=(fc[x]+fc[y]*ff[x])%mod; 87             return false; 88         } 89         fc[x]=(fc[x]+fc[y]*ff[x])%mod; 90     } 91     return true; 92 } 93 int main(){ 94 //    freopen("t.in","r",stdin); 95     n=read();js[0]=1;ni[0]=1; 96     for(int i=1;i<=n;i++) 97         b[i]=read(); 98     for(int i=1,x,y;i
       
      

模拟23

　T1.

　　简单dp,没了.

T2.

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

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

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

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

1 #include
      
        2 #define cri const register int 3 using namespace std; 4 const int zx[4]={
    1,-1,0,0},zy[4]={
    0,0,-1,1}; 5 int n,m,a[305][305],res[305][305],tim; 6 int vv[305][305],tot; 7 char v[305][305]; 8 bool dfs2(cri x,cri y,cri val){ 9     if(a[x][y]>=val)return true;10     vv[x][y]=tim;11     for(int i=0;i<=3;i++){12         int ax=x+zx[i],ay=y+zy[i];13         if(ax<0||ay<0||ax>n+1||ay>n+1)return false;14         if(v[ax][ay]&&a[ax][ay]+res[ax][ay]
       
        =val)continue;16         if(vv[ax][ay]!=tim){17             if(!dfs2(ax,ay,val))return false;18         }19     }20     return true;21 }22 inline bool check(int x,int y,int val){23     tim++;24     return dfs2(x,y,val);25 }26 void dfs(cri x,cri y,cri val){27     res[x][y]=max(val-a[x][y],0);28     v[x][y]=true;29     if(a[x][y]>=val)return;30     for(int i=0;i<=3;i++){31         int ax=x+zx[i],ay=y+zy[i];32         if(v[ax][ay]||ax<=0||ay<=0||ax>n||ay>m)continue;33         dfs(ax,ay,val);34     }35 }36 struct keng{37     int x,y,a;38     friend bool operator < (keng a,keng b){39         return a.a
        
         >1;53                 if(check(aa[i].x,aa[i].y,mid))ans=max(ans,mid),l=mid+1;54                 else r=mid-1;55             }56             dfs(aa[i].x,aa[i].y,ans);57         }58     }59     for(int i=1;i<=n;i++){60         for(int j=1;j<=m;j++)61             printf("%d ",res[i][j]);62         puts("");63     }64     return 0;65 }
        
       
      

T3,

　　容斥好题

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

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