码农场
调教猫咪：有n只饥渴的猫咪，现有一组羞耻Play，由k个操作组成，全部选自：
1. g i 给第i只猫咪一颗花生
2. e i 让第i只猫咪吃光它的花生
3. s i j 交换猫咪i与猫咪j的花生
现将上述一组Play做m次后，求每只猫咪有多少颗花生？
3.4熟练掌握动态规划
矩阵的幂
难点在与怎么将这三种操作转换为矩阵的操作，以题目上的测试数据为例，定义表示猫咪的花生的向量A：
1 0 0 0
A[id]表示第id只猫的初始花生数量，初始时猫咪没有花生，所以都是0。当然，首个元素固定是1，这是为了做乘法用的。
定义单位初始方阵T：
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
定义 R = A * T，那么R[id]表示第id只猫的最终花生数量。上面向量A那个突兀的1就是为了取矩阵T第1行各个值的。
那么
g i := ++T[0][i]
e i := set T[i][i] = 0 即将矩阵的元素(i,i)置为0
s i j := swap(T[t][i], T[t][j]) (0<=t<=height) 即将矩阵的i列和j列互换。
T执行m次，结果R = A * Tm 。轮到矩阵的幂出场了，将上次的模板改改即可：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define LL long long
#define MAX_N 100 + 16
struct Matrix
{
LL val[MAX_N][MAX_N];
int height, width;
Matrix()
{}
Matrix(int height, int width) : height(height), width(width)
{
zero();
}
void zero()
{
memset(val, 0, sizeof(val));
}
void unit()
{
zero();
height = width = max(height, width);
for (int i = 0; i < height; ++i)
{
val[i][i] = 1;
}
}
Matrix operator*(const Matrix &m)
{
Matrix ret(this->height, m.width);
for (int i = 0; i < this->height; ++i)
{
for (int k = 0; k < this->width; ++k)
{
for (int j = 0; j < m.width; ++j)
{
ret.val[i][j] += this->val[i][k] * m.val[k][j];
}
}
}
return ret;
}
Matrix operator^(const LL k)
{
Matrix ret = create_identity((*this).width), base = (*this);
for (LL e = k; e; e >>= 1)
{
if (e & 1)
{
ret = ret * base;
}
base = base * base;
}
return ret;
}
void resize(int width, int height)
{
this->width = width;
this->height = height;
}
static Matrix create_identity(int size)
{
Matrix ret(size, size);
for (int i = 0; i < size; ++i)
{
ret.val[i][i] = 1;
}
return ret;
}
} A, T;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int a, b;
int n, m, k;
while (scanf("%d%d%d", &n, &m, &k) && n)
{
A.resize(n + 1, 1);
A.zero();
A.val[0][0] = 1;
T.resize(n + 1, n + 1);
T.unit();
for (int i = 0; i < k; ++i)
{
getchar();
char cmd = getchar();
if (cmd == 'g')
{
scanf("%d", &a);
++T.val[0][a];
}
else if (cmd == 'e')
{
scanf("%d", &a);
for (int i = 0; i <= n; ++i)
{
T.val[i][a] = 0;
}
}
else
{
scanf("%d%d", &a, &b);
for (int i = 0; i <= n; ++i)
{
swap(T.val[i][a], T.val[i][b]);
}
}
}
Matrix R = A * (T ^ m);
for (int i = 1; i <= n; i++)
{
printf("%lld ", R.val[0][i]);
}
puts("");
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
结果超时，原来是矩阵过于稀疏，而m非常大，于是做个判断就行了：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define LL long long
#define MAX_N 100 + 16
struct Matrix
{
LL val[MAX_N][MAX_N];
int height, width;
Matrix(){}
Matrix(int height, int width) : height(height), width(width)
{
zero();
}
void zero()
{
memset(val, 0, sizeof(val));
}
void unit()
{
zero();
height = width = max(height, width);
for (int i = 0; i < height; ++i)
{
val[i][i] = 1;
}
}
Matrix operator*(const Matrix &m)
{
Matrix ret(this->height, m.width);
for (int i = 0; i < this->height; ++i)
{
for (int k = 0; k < this->width; ++k)
{
if (this->val[i][k]) // 应付稀疏矩阵
{
for (int j = 0; j < m.width; ++j)
{
ret.val[i][j] += this->val[i][k] * m.val[k][j];
}
}
}
}
return ret;
}
Matrix operator^(const LL k)
{
Matrix ret = create_identity((*this).width), base = (*this);
for (LL e = k; e; e >>= 1)
{
if (e & 1)
{
ret = ret * base;
}
base = base * base;
}
return ret;
}
void resize(int width, int height)
{
this->width = width;
this->height = height;
}
static Matrix create_identity(int size)
{
Matrix ret(size, size);
for (int i = 0; i < size; ++i)
{
ret.val[i][i] = 1;
}
return ret;
}
}A, T;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int a, b;
int n, m, k;
while (scanf("%d%d%d", &n, &m, &k) && n)
{
A.resize(n + 1, 1);
A.zero();
A.val[0][0] = 1;
T.resize(n + 1, n + 1);
T.unit();
for (int i = 0; i < k; ++i)
{
getchar();
char cmd = getchar();
if (cmd == 'g')
{
scanf("%d", &a);
++T.val[0][a];
}
else if (cmd == 'e')
{
scanf("%d", &a);
for (int i = 0; i <= n; ++i)
{
T.val[i][a] = 0;
}
}
else
{
scanf("%d%d", &a, &b);
for (int i = 0; i <= n; ++i)
{
swap(T.val[i][a], T.val[i][b]);
}
}
}
Matrix R = A * (T ^ m);
for (int i = 1; i <= n; i++)
{
printf("%lld ", R.val[0][i]);
}
puts("");
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
| 13707396 | hankcs | 3735 | Accepted | 972K | 141MS | C++ | 2989B | 2014-12-12 16:50:50 |
知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3735 Training little cats 题解 《挑战程序设计竞赛》
看过几篇您的文章，感觉代码十分啰嗦。。。