放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

POJ 3735 Training little cats​ 题解 《挑战程序设计竞赛》

目录

POJ 3735 Training little cats

调教猫咪有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​ 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机