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