虽然最近打了很多场CF，也涨了很多分，但是好久没写CF的题解了。

前几次刚刚紫名的CF，太伤感情了，一下子就掉下来了，不懂你们Div.1。

珂学的那场我只做了第一题……悲伤。

这次的打的还可以，虽然吧没有涨分（因为我是紫色的啊）。

做了前4题，后面3题也比较简单，陆续也做完了。

所以心情好，来写一篇题解！

【A】花园

题意：

长度为\(k\)的线段，用若干个长度为\(a_i\)的线段，正好覆盖。（\(a_i|k\)）

给定\(n\)个\(a_i\)，求出最小的\(k/a_i\)，前提是\(a_i|k\)。

题解：

大模拟。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
             
            
           
          
         
        
       
      
     

【B】浏览器

题意：

看样例解释猜题意。

对于浏览器顶部的标签，你有这样的操作：关闭这个标签左/右侧的所有标签，把鼠标移到左/右一个标签。

给定标签数目\(n\)，鼠标现在所在的标签\(p\)，问你留下标签区间\([l,r]\)的最少操作次数。

题解：

大模拟，注意看左边/右边到底有没有标签。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
             
            
           
          
         
        
       
      
     

【C】数位重排

题意：

给定两个数\(a,b\)，求出把\(a\)在十进制下数位重排后不超过\(b\)的最大数，不能有前导零。

题解：

暴力DFS。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
             
            
           
          
         
        
       
      
     

【D】几乎无环图

题意：

给定一个有向图，问能否删掉一条边后，这个图变成无环图。\(2\leq n\leq 500,1\leq m\leq min(n(n-1),1000000)\)

题解：

先找到一个环（找不到就YES）。

找环用DFS/拓扑排序，我写的时候脑子不好，用了恶心的DFS。

这个环上最多\(n\)条边，对每条边都试一次，看看还有没有环。

为什么要先找到一个环？

拓扑排序/DFS的复杂度是\(O(n+m)\)的。

那么如果直接对每条边试着删除的话，总复杂度\(O((n+m)^2)\)，就T飞了。

先找到一个环的话，总复杂度\(O(n(n+m))\)，能过。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
              
             
            
           
          
         
        
       
      

【E】体育课

题意：

震惊，Alex发现自己虽然是个ACMer，但是他还是得参加体育期末考！【多么的讽刺啊……】

Alex要算出自己到期末的\(n\)天中，还有多少天能上体育课？

可惜学校时常更改一段时间的有/无上课的状态，可能把一整段区间都变成不上课或者上课。

你需要算出每一次更改后的答案。\(1\leq n\leq 10^9,1\leq q\leq 3\cdot 10^5\)。

题解：

离散化，线段树，没什么好说的。

1 #include
     
       2 #include
      
        3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 using namespace std; 5 int n,q; 6 int x[300001],y[300001],opt[300001]; 7 int sq[600001],cnt; 8 int siz[600001]; 9 int sz[2097155],dat[2097155],lzy[2097155];10 void build(int i,int l,int r){11     if(l==r) {sz[i]=siz[l]; return;}12     int mid=l+r>>1;13     build(i<<1,l,mid), build(i<<1|1,mid+1,r);14     sz[i]=sz[i<<1]+sz[i<<1|1];15 }16 void init(){17     scanf("%d%d",&n,&q);18     F(i,1,q) scanf("%d%d%d",x+i,y+i,opt+i), sq[++cnt]=x[i]-1, sq[++cnt]=y[i];19     sort(sq+1,sq+cnt+1);20     int Cnt=cnt, lst=-1; cnt=0;21     F(i,1,Cnt) if(sq[i]!=lst) sq[++cnt]=sq[i], lst=sq[i];22     F(i,1,cnt-1) siz[i]=sq[i+1]-sq[i];23     F(i,1,q) x[i]=lower_bound(sq+1,sq+cnt+1,x[i]-1)-sq, y[i]=lower_bound(sq+1,sq+cnt+1,y[i])-sq-1;24     cnt--;25 }26 inline void pushdown(int i){27     if(lzy[i]==1) dat[i<<1]=sz[i<<1], dat[i<<1|1]=sz[i<<1|1], lzy[i<<1]=lzy[i<<1|1]=1;28     if(lzy[i]==2) dat[i<<1]=dat[i<<1|1]=0, lzy[i<<1]=lzy[i<<1|1]=2;29     lzy[i]=0;30 }31 void M(int a,int b,int i,int l,int r,int typ){32     if(a<=l&&r<=b) {dat[i]=(typ==1?(sz[i]):0); lzy[i]=typ; return;}33     if(r
       
        
         >1;36     M(a,b,i<<1,l,mid,typ), M(a,b,i<<1|1,mid+1,r,typ);37     dat[i]=dat[i<<1]+dat[i<<1|1];38 }39 int main(){40     init();41     build(1,1,cnt);42     F(i,1,q){43         if(opt[i]==1) M(x[i],y[i],1,1,cnt,1);44         else M(x[i],y[i],1,1,cnt,2);45         printf("%d\n",n-dat[1]);46     }47     return 0;48 }
        
       
      
     

【F】海棠数组树的失衡度

题意：

给你一棵树，节点有权值，计算\(\sum_{i=1}^n\sum_{j=i}^nI(i,j)\)。

\(I(i,j)\)表示\(i\)到\(j\)的路径上的最大点权-最小点权。

题解：

考虑最大最小分开计算，最后最大减最小。

以最大点权为例，如何计算？

假设这个点是\(x\)，考虑计算与\(x\)直接或间接联通的点中，到\(x\)的路径中的点权都不比\(x\)大的点。

通过这些点的个数来计算答案。

可以证明，这些点和\(x\)形成的图是一棵树。

我们以\(x\)为根，\(x\)对答案的贡献是\(val_x\cdot[siz_x^2-\sum_{k=x.son}siz_k^2]\)。

那么怎么找到到\(x\)的路径上的点权都不比\(x\)大的点呢？

考虑按照\(val\)为顺序加入点，用并查集维护连通性，就能算答案了。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define F(i,a,b) for(int i=(a);i<=(b);++i) 5 #define F2(i,a,b) for(int i=(a);i<(b);++i) 6 #define dF(i,a,b) for(int i=(a);i>=(b);--i) 7 #define eF(i,u) for(int i=h[u];i;i=nxt[i]) 8 int n,a[1000001],I[1000001],siz[1000001]; 9 inline bool cmp(int p1,int p2){
   return a[p1]
        
         >1);36     return 0;37 }
        
       
      
     

【G】互质数组

题意：

我们说数组\(a\)是互质的，当且仅当\(gcd(a_1,a_2,a_3,\cdots,a_n)=1\)。

给定\(k\)，对于每个\(i\;(1\leq i\leq k)\)，求出长度为\(n\)，且其中元素为\(1\)到\(i\)中的正整数的互质数组的个数。

答案对1000000007取模，再通过玄学的方式算出最终答案。

题解：

容斥+数论（莫比乌斯函数）。

考虑容斥，先计算所有的个数，再扣掉元素是\(2\)的倍数的数组的个数，\(3\)的倍数……

\(4\)的倍数不用扣掉，因为\(2\)已经扣掉过了。

但是\(6\)的倍数被\(2\)和\(3\)扣掉了两遍，要加回来。

对于是\(x\)的倍数，容斥系数就是\(\mu(x)\)——\(x\)的莫比乌斯函数。

对于\(i\)的答案，是\(\sum_{j=1}^{i}\mu(j)(\left\lfloor\frac{i}{j}\right\rfloor)^n\)。

对于每个\(i\)，我们使用差分的技巧统计答案。

1 #include
     
       2 #define Mod 1000000007 3 int n,k,Ans; 4 bool isnprime[2000001]={
   1,1}; 5 int mobius[2000001]={
   0,1}; 6 int primes[1000001],pnum; 7 int ans[2000001]; 8 int pows[2000001]; 9 void Mobius(int num){10     for(int i=2;i<=num;++i){11         if(!isnprime[i])12             primes[++pnum]=i, mobius[i]=-1;13         for(int j=1;j<=pnum&&i*primes[j]<=num;++j){14             isnprime[i*primes[j]]=1;15             if(i%primes[j]==0) break;16             mobius[i*primes[j]]=-mobius[i];17         }18     }19 }20 inline int Pow(int base,int exp){21     int sum=1;22     while(exp){23         if(exp&1) sum=(long long)sum*base%Mod;24         base=(long long)base*base%Mod; exp>>=1;25     } return sum;26 }27 int main(){28     scanf("%d%d",&n,&k);29     Mobius(k);30     pows[0]=0;31     for(int i=1;i<=k;++i) pows[i]=Pow(i,n);32     for(int i=1;i<=k;++i){33         if(!mobius[i]) continue;34         for(int j=1;j*i<=k;++j){35             ans[j*i]-=mobius[i]*pows[j-1];36             ans[j*i]+=mobius[i]*pows[j];37             ans[j*i]=((ans[j*i]%Mod)+Mod)%Mod;38         }39     }40     for(int i=1;i<=k;++i) ans[i]=(ans[i-1]+ans[i])%Mod, Ans=(Ans+(ans[i]^i))%Mod;41     printf("%d",Ans);42     return 0;43 }