Andrew Stankevich’s Contest #1 (ZOJ2313~ZOJ2321)

围观到叉姐和shi哥都强力推荐大妈题。于是就切了一套。

【ZOJ2313】

给定n<=10^2000，求一个最大的k，使得满足1<=k<=n/2 && ( i*k mod n 能取遍所有0~n-1的值 )

如果要取遍的话，必须(k,n)=1。

分3种情况讨论：

n%2==1    答案是n/2 . (k,2*k+1),考虑他们的gcd为g，那么必须 g | k，看另外一边，必然有2*k % g + 1 % g ==0 即 1 % g ==0……

n%2==0 && (n/2)%2==0 答案是n/2-1,首先因为k | 2k，n/2显然不可行。然后试试n/2-1，围观(k,2(k+1))，因为n/2-1是奇数，所以2不能作公因子。然后必然 g | k，于是(2%g) * ( k%g+1%g ) % g == 0，即2*(1%g) % g == 0.于是g=1.

n%2==0 && (n/2)%2==1 答案是n/2-2……模仿上面证吧‍

代码：http://ideone.com/W6FjE

【ZOJ2314】

给出一个裸的无源汇上下界网络流模型，让你求一个可行流。

这个太裸直接套经典模型。

代码：http://ideone.com/t3Z6A

【ZOJ2315】

有一棵树，它的根节点不能涂色，让你给他的一些结点涂色，使得满足以下条件的情况下，涂的点最多，输出点数*1000和涂色方案。

1、每个结点只能有一个儿子被涂色。

2、如果本结点涂色了，那么该节点所有儿子都不能涂色。

直接树形dp……

代码：http://ideone.com/LTwye

【ZOJ2316】

给定一个无向图G=(V,E)，这个无向图对应一个N*M的矩阵A，对于矩阵中(i,j)这个格子，如果i是第j条边的其中一个端点，那么为1，否则为0。设另一M*N的矩阵B满足，B(i,j)=A(j,i)。令B * A=C，求C这个M*M的矩阵里所有元素的和是多少。

C[i,j]=Sum{ B[i,k]*A[k,j] }，他们必须都为1才能算进结果，并且只会令结果+1。那么但看中间k这个点而言，对答案的贡献显然是他度数的平方……于是水之。

代码：http://ideone.com/biWcr

【ZOJ2317】

一个N*M的矩阵(N<=10^100 M<=5)，里面每个格子要么涂白色要么涂黑色，假如矩阵里不存在2*2的子矩阵同色，那么是符合条件的。然后问，合法涂色方案有多少种。

状态压缩dp->矩阵乘法。

这个其实很水，但是常数很卡……一开始TLE到死去活来……

然后加了这个优化，还要注意变成unsigned int刚刚够（你们懂的）：

    Mat operator * (const Mat &oth) const{

        Mat ret;

        Clear(ret.d);

        int i,j,k;

        for (i=0;i

          for (j=0;j

            for (k=0;k

              ret.d[i][j]+=d[i][k]*oth.d[k][j];

        for (i=0;i

          for (j=0;j

            ret.d[i][j]%=Mod;

        return ret;

    }

5S TLE -> 300+MS

代码：http://ideone.com/l0UAc

【ZOJ2318】

COCO船长被众岛围观，他那只船是圆的，岛也是圆的，问能不能再不上岸的情况下跑出这个群岛。

首先显然COCO的半径可以加到岛的半径上……然后……

T_T，我直接用了ZOJ3476 The wall II的方法……引射线，然后枚举起点，拆点，DFS判能否形成圈即可。

然后围观shi哥，发现他用了另外一个判多边形的方法，一次Bellman-Ford判负权即可……

代码：http://ideone.com/p0SUv

【ZOJ2319】

给定n<=100000个元素，让你求最多能共存多少个元素，两元素能共存必须满足Si

排序+LIS不用解释的……但是要输出方案。n lg n的算法大家都知道最后在那个表里的不是LIS。但是当你插入到表中的时候，在你前面的那一个必然可以作为你得到当前这个F值的Father……这个很容易YY到。然后Father link回去就可以了。

代码：http://ideone.com/boTEV

【ZOJ2320】

给定n(n<=100)个数，每个数Ai<=10^9，然后这些数的素因子只能是前T个素数(T<=100)。问有多少个非空子集，子集内的数之积为完全平方数。

完全平方数实际上就是在每个素因子上总个数为偶数……由于只有奇偶性，可以用布尔变量表示……

然后可以根据这个列方程，每个变元Xi表示第i个数取还是不取，然后有T条方程，对应前T个素数与这n个数的奇偶关联。

一般我们guass消元的时候会发现无限解和无解的情况。无解很简单。平常的无限解就是某一步找不到主元了，这一个元其实是取true和false都可以‍，而且只对前面的方程有影响，也就是将答案*2。然后一直消下去，那么计算有多少个元酱油了，答案应该就是2^cnt。但是注意到要非空子集，而显然空的时候是符合方程的，所以将答案-1即可。

代码：http://ideone.com/I5M1q