调教猫咪:有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 题解 《挑战程序设计竞赛》
看过几篇您的文章,感觉代码十分啰嗦。。。