[题解] ZOJ Monthly, September 2012

=_____=拖了好久啊，我是渣渣。

ZOJ 3644 Kitty’s Game

有一只喵身上有个记分牌，她每沿着边走一步，记分牌上的数字就会变为$$lcm(x, x_i)$$，其中$$x_i$$表示这一步的终点的一个给定值。问从起点S走到终点T，最后记分牌上写着k的方案有多少种。

因为最后记分牌到达到k，而记分牌上数字唯一的变化操作是lcm，所以中间过程必须是k的约数，注意到这点就可以只对有效状态dp了。复杂度$$O(\sqrt{k} * (V + E))$$

#include 
#include 
#include 
#include 
#include 
#include 
#include 

ZOJ 3645 BiliBili

定义11维空间中点与点的距离为$$\sqrt{\sum (a_i – b_i)^2}$$。先给出一个未知点与另外12个点的距离，问这个未知点的坐标。

把$$(a_i – b_i)^2$$展开，得$$a_i^2 + b_i^2 + 2a_ib_i$$，然后对12个方程两两作差，得出11个11元线性方程。用gauss解之即可。
需要注意的是，答案不要输出-0.00，否则会WA的。

#include 
#include 
#include 
#include 
#include 
using namespace std;

int n=11;

double a[15][15];
double x[15];

void guass(){
    int i,j,k; double sum,rate;
    for (k=1;kfabs(a[j][k])?i:j;
        for (i=k;i<=n+1;i++) swap(a[j][i],a[k][i]);
        for (i=k+1;i<=n;i++)
          for (rate=a[i][k]/a[k][k],j=k;j<=n+1;j++)
            a[i][j]-=a[k][j]*rate;    
    }
    for (i=n;i>=1;i--){
        for (sum=0,j=i+1;j<=n;sum+=a[i][j]*x[j],j++);
        x[i]=(a[i][n+1]-sum)/a[i][i];
    }
}

double mat[15][15];
double result[15];

double Fix(double y){
	if (fabs(y)<5e-3) return 0;
	return y;
}

int main(){
	int Tc;
	scanf("%d",&Tc);
	while (Tc--){
		for (int i=1;i<=12;i++){
			for (int j=1;j<=11;j++)
				scanf("%lf",&mat[i][j]);
			scanf("%lf",&result[i]);
			result[i]=result[i]*result[i];
			for (int j=1;j<=11;j++){
				result[i]-=mat[i][j]*mat[i][j];
				mat[i][j]*=-2;
			}
		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++)
				a[i][j]=mat[i][j]-mat[i+1][j];
			a[i][n+1]=result[i]-result[i+1];
		}
		guass();
		for (int i=1;i<=n;i++){
			if (i!=1) printf(" ");
			printf("%.2lf",Fix(x[i]));
		}
		printf("\n");
	}
}

ZOJ 3646 Matrix Transformer

给定一个矩阵，里面包含了U和D，你可以随意交换任意列以及任何行，问最后能否使得矩阵主对角线上的元素都是U。

把这个矩阵看成邻接矩阵，U为1，然后做最大匹配即可。最后第i对匹配占领第i行第i列，就成了一个对角线全是U的矩阵。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

ZOJ 3647 Gao the Grid

问一个网络内点在整点上的非退化三角形的数目。

就是求C((n + 1)*(m + 1), 3) - 共线三角形的数目。共线的话，不妨先假设斜率 > 0。然后线段的右上角的端点减左下角的端点就会得到一个向量，这个向量一样的线段，都是本质相同的。枚举这个向量，再用gcd求中间整点的个数，就可以得解。根据对称性不难得出斜率 < 0的情况。 = 0的再特判一下就好了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

ZOJ 3648 Gao the Grid II

问一个网络内点在整点上的非退化锐角三角形的数目。

对三角形占领的最小矩形范围分类，然后分别算出来输出即可。(相当于打表，累加一下即可) 分别算的时候注意非锐角三角形满足$$a^2 + b^2 \leq c^2$$ 就很简单了。

#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 101;
const double EPS = 1e-10;

long long f[maxn][maxn];
int n, m;
int x, y;

long long gao(int m, int n, int & a, int & b) {
	// x*x - m*x + n > 0
	// 0 < x < m, x, m, n: integer
	// return: number of solution(x)
	long long d = (long long) m * m - 4LL * n;
	if (d < 0) return (m-1 > 0) ? m-1 : 0;
	if (d == 0) {
        if (m & 0x1) return (m-1 > 0) ? m-1 : 0;
        a = b = m / 2;
        return (m-2 > 0) ? m-2 : 0;
    }
	a = (int)floor((m + sqrt(d)) / 2.0);
	b = (int)ceil((m - sqrt(d)) / 2.0);
	return b-1 + m-1-a;
}

void init() {
	memset(f, 0, sizeof(f));
	//   a*a - m*a + n*b > 0
	//   b*b - n*b + m*a > 0
	for (int i = 2; i < maxn; i++) { // n
		for (int j = i; j < maxn; j++) { // m
			for (int k = 1; k < j; k++) { // a
				// k*k - m*k + n*b > 0 --> n*b > k*(m-k)
				// b*b - n*b + m*k > 0
				x = y = 0;
				long long ret = gao(i, j*k, y, x); // b in (0, x) + (y, i)
				int c = k*(j-k) / i; // b > c
				if (x == 0 && y == 0) {
                    f[i][j] += max(i-1-c, 0);
                    continue;
                }
				if (c < x) f[i][j] += max(x-1-c, 0) + max(i-1-y, 0); // b in (c, x) + (y, i)
				else {
					if (c < i && c > y) f[i][j] += max(i-1-c, 0);
					if (c < i && c <= y) f[i][j] += max(i-1-y, 0);
				}
			}
			f[j][i] = f[i][j];
        }
	}
}

long long count(int n, int m) {
	long long ret = 0;
	ret = 2 * (gao(n, m*m, x, y) + gao(m, n*n, x, y)) + 4 * f[n][m];
	return ret;
}

int main() {
	init();
	
	while (scanf("%d%d", &n, &m) == 2) {
		long long ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				long long ret = count(i, j);
				ans += ret * (n-i+1) * (m-j+1);
			}
		}
		printf("%lld\n", ans);
	}
		
	return 0;
}

ZOJ 3649 Social Net

每次问一棵最大生成树上，把x->y的边拿出来按顺序放在一个list里面，求$$\max(a_j - a_i) j \geq i, 0 \leq i, j \leq n$$

先最大生成树然后使用倍增算法。算出向根走$$2^k$$步这一段区间的max, min, 正向ans, 反向ans。询问的时候把路径上的若干段取出来然后先取里面的ans，再考虑段与段间的max, min即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

ZOJ 3650 Toy Blocks

在数轴上给定若干多米诺骨牌，然后每次你可以选择一个未推倒的骨牌把他向左或者向右推倒，推倒条件为$$| X_i - X_j | \leq H_i $$，问你最少要推几次。

先用线段树预处理出这个牌向左倒能推到哪里，向右能推到哪里。最后再用线段树优化dp的转移即可。dp的状态是f[i]表示前i个牌全倒了的方案数，转移就是像左推以及向右推。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

ZOJ 3651 Cipher Lock

n个拥有a, b属性的物品放成一圈，相邻物品要求$$a_i = a_{i + 1}$$或者$$b_i = b_{i + 1}$$。再限定8个位置的物品属性，问可能的不同属性分布的方案数。

mask dp + 矩阵乘法。mask的意思是前一个值等不等于接下来的u，以及后一个值等不等于接下来的v。这两个2进制位压成一个<4的数字dp即可。 注意那8个是可能重复的= =b，注意判断。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

ZOJ 3652 Maze
蘑菇题。。。略过吧-.-，就记录那几维，mask+bfs就好了。

#include 
#include 
#include 
#include 
#include 
#include 
#include