HDU5892~HDU5901 2016网络赛沈阳

时间:2021-01-24 04:05:24

A、题意: 有一个n×n的格子, 有50种怪物. 有m个操作, 每次操作会往一个矩形区域放怪物, 每个格子放相同数目的怪物, 或者查询当前50种怪物的奇偶性.

分析:用2^50表示怪物的奇偶,然后就是二维区间异或问题,用二维树状数组

考虑一维情况,给一段区间[L,R]^X,询问[1,P]

       对于树状数组C[L..R],每个位置异或X的次数是奇、偶交错的的,而异或相同的一个数偶数次等于没异或,异或相同的一个数奇数次相当于异或一次

即将与L同奇偶的位置都异或一次(只有一次!)

     这就好比将原来的数组分成两部分(偶数位置和奇数位置),对一个数组的一段数字异或一个数字,询问的时候采取前缀异或和相减的做法,也就是区间修改,单点询问, 一维树状数组完全可以胜任。

扩展到二维,则需要四个数组,表示x的奇偶,y的奇偶

注意一点,一维时候对[l,R]来说,修改是L位置和R+1位置,询问是L-1位置和R位置,二维也是类似。

B、题意:一棵无根树,两种操作:改变路径上的颜色,和询问路径上有多少段颜色

分析:bzoj2243染色

此题是边权,也很好处理,将所有边的权赋给它下面的点,作为下面点的点权

树链剖分+线段树lazy标记

唯一注意的一点就是树链剖分两边上移的时候,因为要考虑一段与另一段是否有颜色衔接,所以不能简单的按同样法则上移(一般写法是比较x,y深度大小,深的上移,减少代码量),这里就两边分别上移,记录各边的情况。

C、题意:一个大小为 n 的环,选 m 个位置涂黑,要求相邻两个黑点之间至少间隔 kk个白点,问方案数 

分析:设xi表示第i个人和第i+1个人之间的间隔数(特别的Xm表示第m个人和第一个人之间的间隔)

易得x1+...+xm=n-m

      x1,x2...,xm>=k

设上面式子的整数解个数为X

那么ans=X*N/M(因为位置不一样,所以不同构,对于一组解可以绕着环转n下,但每个人当排头的情况都有重复,所以要除以M)

至于X的求法也是经典的求法了,X=C(n-m-m*(k-1)-1,m-1)

D、题意:看题

分析:指数循环节:

a^b mod c=a^(b mod φ(c)+φ(c)) mod c (b>φ(c))

这就可以让我们对g(n*y)直接取模了

现在如果能知道g(n)的通项,那就解决了

f(n)=f(n-2)+2*f(n-1)

f(n)*f(n-1)=f(n-2)*f(n-1)+2*f(n-1)*f(n-1);

2*f(n-1)*f(n-1)=f(n)*f(n-1)-f(n-2)*f(n-1);

              连加得到g(n)=f(n)*f(n+1)/2;
              接下来矩阵快速幂就行了
              还有一个问题,因为模数不是质数,是你输入的,所以分母的2^x可能在模(s+1)下没有逆元
              这里就要采取一个技巧
              a/b mod c=x
              a/b=kc+x
              a=bkc+bx
              a mod (bc)=bx
              x=(a mod (bc))/b
              这样就不会出现分母了!
E、 题意:给定一个n, 问有多少n个点的无向无重边无自环图满足有环
      分析:ans=2^[(n-1)n/2]-f(n)
              f(n)表示n个点组成的森林数,g(n)表示n个点组成的树的个数,明显g(n)=n^(n-2)
              于是有f(n)=g(n)+sigma(C(n-1,i-1)*f(n-i)*g(i)) (1<=i<=n-1)
              注:n个点构成的森林必然是n这个点和某些点构成树,剩下的构成森林
             接下来就是除一下成卷积然后NTT(蒟蒻不会……)
F、
G、题意:一个数字,它每个数位上的奇数都形成偶数长度的段,偶数位都形成奇数长度的段他就是好的。问[L , R]的好数个数
     分析:数位dp
             dp[i][j][k][l]表示第i位 前一位奇偶性为j,连续了k位,l表示是否有前导零
H、
I、题意:n 个pair<int , int>,每次可以选相邻两个pair。如果他们的first不互质就可以把它们都删掉,并且获得second之和的分数,问最大得分
    分析:先n^3弄出一个f[i][j]表示i...j能否完全消掉
             f[i][j]|=f[i][k]&f[k+1][j] f[i][j]|=f[i+1][j-1]&(gcd(first[i],first[j])>1)
             dp[i][j]=max(dp[i][k]+dp[k+1][j],dp[i+1][j-1]+second[i]+second[j](f[i+1][j-1]==1)
J、题意:求1e11内素数有多少个
    分析:论文题http://codeforces.com/contest/665/problem/F