Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我来个最详细的解题报告

Posted by zoujing1978 at 2017-07-10 00:54:27 on Problem 3735 and last updated at 2017-07-10 19:39:29
/*
题意:有n只猫咪,开始时每只猫咪有花生0颗,现有一组操作,由下面三个中的k个操作组成:
1. g i:给i只猫咪一颗花生米;
2. e i:让第i只猫咪吃掉它拥有的所有花生米;
3. s i:j 将猫咪i与猫咪j的拥有的花生米交换。
现将上述一组操作做m次后,问每只猫咪有多少颗花生?

思路:m达到10^9,显然不能直接算。
因为k个操作给出之后就是固定的,所以想到用矩阵,矩阵快速幂可以把时间复杂度降到O(log m)。问题转化为如何构造转置矩阵?
有一个很好的办法就是添加一个辅助,使初始矩阵变为一个n+1元组,编号为0到n,下面以3个猫为例:
定义初始矩阵A = [x y z 1],最后一个元素固定为1,0~n-1分别为对应的每一只猫所拥有的花生数。
再定义一个n+1维的方阵Mat,初始化为单位矩阵,即Mat最初为:
|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|0 0 0 1|
,最后一行的前n个元素表示3只猫所拥有的花生数x、y、z,最开始的时候,3只猫都没有花生米,则Mat转化为:
|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|0 0 0 1|
,对于第一种操作g i,给i只猫咪一颗花生米,在单位矩阵基础上使Mat[n][i]变为1,例如g 1,表示给第0只猫咪一颗花生米:
|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|1 0 0 1|
,显然
                    |1 0 0 0|
A*Mat = [x y z 1] * |0 1 0 0| = [x+1 y z 1]
                    |0 0 1 0|
                    |1 0 0 1|
;对于第二种操作e i,让第i只猫咪吃掉它拥有的所有花生米,在单位矩阵基础上使Mat[i][i] = 0, 例如e 2,让第1只猫咪吃掉它拥有的所有花生米,需要使Mat[1][1]为0:
|1 0 0 0|
|0 0 0 0|
|0 0 1 0|
|0 0 0 1|
,显然
                    |1 0 0 0|
A*Mat = [x y z 1] * |0 0 0 0| = [x 0 z 1]
                    |0 0 1 0|
                    |0 0 0 1|
;对于第三种操作s i j,将猫咪i与猫咪j的拥有的花生米交换,在单位矩阵基础上使第i列与第j互换,例如s 2 3,让第1只猫咪和第2只猫咪的花生互换,需要在Mat矩阵中将第1列和第2列互换:
|1 0 0 0|
|0 0 1 0|
|0 1 0 0|
|0 0 0 1|
,显然
                    |1 0 0 0|
A*Mat = [x y z 1] * |0 0 1 0| = [x z y 1]
                    |0 1 0 0|
                    |0 0 0 1|
。现在,对于每一个操作都可以得到一个操作矩阵,把k个操作矩阵相乘可以得到一个新的矩阵T。
A * T 表示我们经过一组操作,类似我们可以得到经过m组操作的矩阵为 A * (T ^ m), 最终矩阵的[n][0~n-1]即为答案。
上述的做法比较直观,但是实现过于麻烦,因为要构造k个不同矩阵。
观察以下矩阵相乘的结果:
            |1 0 0 0|
[p q r 1] * |0 1 0 0| = [p+x  q+y  z+r  1]
            |0 0 1 0|
            |x y z 1|
相乘的结果是把p平移了x,q平移了y,r平移了z。
假设x、y、z分别表示某个操作前,3只猫咪已有的花生数,将A矩阵改为[0 0 0 1] ,
再将Mat矩阵改为
|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|x y z 1|
则:
                    |1 0 0 0|
A*Mat = [0 0 0 1] * |0 1 0 0| = [x y z 1]
                    |0 0 1 0|
                    |x y z 1|
相当于是获取了Mat矩阵的最后一行。再观察下面的矩阵相乘:
此时,
对于第一种操作g i,给i只猫咪一颗花生米,例如g 1,表示给第0只猫咪一颗花生米,可以用下面的矩阵相乘表示:
|1 0 0 0|   |1 0 0 0|   | 1  0  0  0|   
|0 1 0 0| * |0 1 0 0| = | 0  1  0  0|
|0 0 1 0|   |0 0 1 0|   | 0  0  1  0|
|x y z 1|   |1 0 0 1|   |x+1 y  z  1|
相当于给相乘前第一个矩阵的最后一行的第i-1列的元素加1,结果矩阵的最后一行的前n个元素表示执行g 1操作后n只猫咪各自拥有的花生数。
对于第二种操作e i,让第i只猫咪吃掉它拥有的所有花生米,例如e 2,让第1只猫咪吃掉它拥有的所有花生米,可以用下面的矩阵相乘表示:
|1 0 0 0|   |1 0 0 0|   | 1  0  0  0|
|0 1 0 0| * |0 0 0 0| = | 0  0  0  0|
|0 0 1 0|   |0 0 1 0|   | 0  0  1  0|
|x y z 1|   |0 0 0 1|   | x  0  z  1|
相当于给相乘前第一个矩阵的第i-1列的所有元素清0,结果矩阵的最后一行的前n个元素表示执行e 2操作后n只猫咪各自拥有的花生数。
对于第三种操作s i j,将猫咪i与猫咪j的拥有的花生米交换,例如s 2 3,让第1只猫咪和第2只猫咪的花生互换,可以用下面的矩阵相乘表示:
|1 0 0 0|   |1 0 0 0|   | 1  0  0  0|
|0 1 0 0| * |0 0 1 0| = | 0  0  1  0|
|0 0 1 0|   |0 1 0 0|   | 0  1  0  0|
|x y z 1|   |0 0 0 1|   | x  z  y  1|
相当于给相乘前第一个矩阵的第i-1列和第j-1列互换,结果矩阵的最后一行的前n个元素表示执行s 2 3操作后n只猫咪各自拥有的花生数。
这样实现的话,我们始终在处理一个矩阵,免去构造k个矩阵的麻烦。

样例说明:初始状态|0 0 0 1|,

|1 0 0 0|       |1 0 0 0|       |1 0 0 0|       |1 0 0 0|         |0 1 0 0|       |0 1 0 0|       |0 0 0 0|
|0 1 0 0|       |0 1 0 0|       |0 1 0 0|       |0 1 0 0|         |1 0 0 0|       |1 0 0 0|       |1 0 0 0|
|0 0 1 0|->(g 1)|0 0 1 0|->(g 2)|0 0 1 0|->(g 2)|0 0 1 0|->(s 1 2)|0 0 1 0|->(g 3)|0 0 1 0|->(e 2)|0 0 1 0|
|0 0 0 1|       |1 0 0 1|       |1 1 0 1|       |1 2 0 1|         |2 1 0 1|       |2 1 1 1|       |2 0 1 1|
最后3只猫咪各自拥有的花生数是2、0、1。
*/

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
using namespace std;

class Matrix
{
protected:
	//long long ** arr;
	long long arr[105][105];
	int m;
	int n;
public:
	Matrix(int m, int n, int** a = NULL);
	Matrix(const Matrix& rhs);
	virtual ~Matrix();
	long long * operator[](int i);
	Matrix& operator = (const Matrix& rhs);
	Matrix operator * (const Matrix& rhs) const;
};

Matrix::Matrix(int m, int n, int** a) : m(m), n(n)
{
	//arr = new long long *[m];
	//for (int i = 0; i < m; i++)
	//{
	//	arr[i] = new long long [n];
	//	if (a && a[i])
	//	{
	//		for (int j = 0; j < n; j++)
	//		{
	//			arr[i][j] = a[i][j];
	//		}
	//	}
	//}
}

Matrix::Matrix(const Matrix& rhs) : m(rhs.m), n(rhs.n)
{
	//arr = new long long*[m];
	//for (int i = 0; i < m; i++)
	//{
	//	arr[i] = new long long[n];
	//}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			arr[i][j] = rhs.arr[i][j];
		}
	}
}

Matrix::~Matrix()
{
	//for (int i = 0; i < m; i++)
	//{
	//	delete[] arr[i];
	//}
	//delete[] arr;
}

long long* Matrix::operator[](int i)
{
	return arr[i];
}

Matrix& Matrix::operator = (const Matrix& rhs)
{
	//for (int i = 0; i < m; i++)
	//{
	//	delete[] arr[i];
	//}
	//delete[] arr;
	m = rhs.m;
	n = rhs.n;
	//arr = new long long *[m];
	//for (int i = 0; i < m; i++)
	//{
	//	arr[i] = new long long [n];
	//}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			arr[i][j] = rhs.arr[i][j];
		}
	}
	return *this;
}

Matrix Matrix::operator * (const Matrix& rhs) const
{
	Matrix result(this->m, rhs.n);
	for (int i = 0; i < this->m; i++)
	{
		for (int j = 0; j < rhs.n; j++)
		{
			result.arr[i][j] = 0;
		}
	}
	for (int i = 0; i < this->m; i++)
	{
		for (int j = 0; j < this->n; j++)
		{
			if (arr[i][j] != 0) // 必须这么写,否则超时,因为是稀疏矩阵
			{
				for (int k = 0; k < rhs.n; k++)
				{
					result.arr[i][k] += arr[i][j] * rhs.arr[j][k];
				}
			}
		}
	}
	return result;
}

class SMatrix : public Matrix
{
public:
	SMatrix(int n, int** a = NULL);
	SMatrix Exp(int k);
	void MakeE();
	SMatrix operator * (const SMatrix& rhs) const;
};

SMatrix::SMatrix(int n, int** a) : Matrix(n, n, a)
{
}

void SMatrix::MakeE()
{
	for (int i = 0; i < this->n; i++)
	{
		for (int j = 0; j < this->n; j++)
		{
			if (i == j)
			{
				arr[i][i] = 1;
			}
			else
			{
				arr[i][j] = 0;
			}
		}
	}
}

SMatrix SMatrix::operator * (const SMatrix& rhs) const
{
	SMatrix result(this->n);
	for (int i = 0; i < this->n; i++)
	{
		for (int j = 0; j < rhs.n; j++)
		{
			result.arr[i][j] = 0;
		}
	}
	for (int i = 0; i < this->n; i++)
	{
		for (int j = 0; j < this->n; j++)
		{
			if (arr[i][j]) // 必须这么写,否则超时
			{
				for (int k = 0; k < rhs.n; k++)
				{
					result.arr[i][k] += arr[i][j] * rhs.arr[j][k];
				}
			}
		}
	}
	return result;
}

SMatrix SMatrix::Exp(int k)
{
	if (k == 1)
	{
		return *this;
	}
	SMatrix result(this->n);
	// 先构造一个单位矩阵
	result.MakeE();
	if (k == 0)
	{
		return result;
	}
	SMatrix p(*this);
	while (k > 0)
	{
		if (k & 1) // 如果k为奇数
		{
			result = (p * result);
			//cout << "result\n";
			//result.Print();
		}
		p = p * p;
		k >>= 1;
	}
	return result;
}

class TrainingCat
{
protected:
	SMatrix* matrix;
	//SMatrix matrix;
	int n; // 猫咪数
	int m; // 重复次数
	int k; // 每一次有k个操作
	void Once();
public:
	void Solve();
};

void TrainingCat::Once()
{
	matrix->MakeE();
	//matrix.MakeE();
	while (k-- > 0)
	{
		char oper[5];
		scanf("%s", oper);
		if (oper[0] == 'g')
		{
			int x = 0;
			scanf("%d", &x);
			x--;
			(*matrix)[n][x]++;
			//matrix[n][x]++;
		}
		else if (oper[0] == 's')
		{
			int x = 0, y = 0;
			scanf("%d %d", &x, &y);
			x--;
			y--;
			if (x != y)
			{
				for (int i = 0; i < n + 1; i++)
				{
					swap((*matrix)[i][x], (*matrix)[i][y]);
					//swap(matrix[i][x], matrix[i][y]);
				}
			}
		}
		else
		{
			int x = 0;
			scanf("%d", &x);
			x--;
			for (int i = 0; i < n + 1; i++)
			{
				(*matrix)[i][x] = 0;
				//matrix[i][x] = 0;
			}
		}
	}
}

void TrainingCat::Solve()
{
	while (~scanf("%d %d %d", &n, &m, &k))
	{
		if (n == 0 && m == 0 && k == 0)
		{
			break;
		}
		matrix = new SMatrix(n + 1);
		//SMatrix matrix(n + 1);
		Once();

		SMatrix ans = matrix->Exp(m);
		//SMatrix ans = matrix.Exp(m);
		for (int i = 0; i < n; i++)
		{
			printf("%I64d ", ans[n][i]);
		}
		printf("\n");
		delete[] matrix;
	}
}

int main()
{
	TrainingCat obj;
	obj.Solve();
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator