Spreadsheet Tracking-UVa512

文章目录
  1. 1. Spreadsheet Tracking 电子表格程序追踪
  2. 2. 思考过程
  3. 3. 题后反思
  4. 4. 代码

Spreadsheet Tracking 电子表格程序追踪

vj链接:Spreadsheet Tracking

题目大意:给你一个r行c列的表格(只给行列,不给实际数据),并且给你一连串的操作,操作包含IR(插入行),IC(插入列),DR(删除行),DC(删除列),和EX(交换两个单元格),操作完成后开始连续query,问你操作前的单元格(r1,c1)在经过上述所有操作后所在的位置。

其实就是一道有一些编码量的水题。

注意事项

  1. 题目中提到,对于删除操作(插入操作也同理,需要一并插入),不是一行一行(或一列一列)地删除,而是同时选中多行(多列),一起删除。如果写码的时候写成删除了一行再删除下一行的话,就会遇到删除越界行的情况,因为前面的删除动作会改变表格的大小。
  2. 对于不同表格之间的输出要空一行,最后一组输出后不能有空行

思考过程

一开始看到题,最先想到的就是模拟出表格,然后模拟各种操作,这样就变成了写一个维护二维线性表的程序,就是一维线性表的增删改查的扩展。

然后想到了表格中的数据可以用 行号*100+列号来代替,也就是sheet[i][j]=i*100+j,因为题目说了行列最大就50,用这种方式可以追踪最后某个单元格的位置。

然后关于如何优雅地处理DC、DR、IC、IR、EX函数的调用,想了想,可以分成两类函数,一类是只需要单个参数的DC、DR、IC、IR,二类是需要多个参数的EX,对于一类函数,可以开个函数指针数组map,然后以map[(('D' << 8) + 'I') % 31] = DI函数地址,的方式,把这四种操作的函数扔到一个大小为25(观察可知四种操作的字符串处理后最大不超过20)的数组,用的时候只需要把操作作为字符串读进来,然后void (*fun)(int) = map[((c1 << 8) + c2) % 31],再fun(i) 调用就行,其中c1 c2即为操作对应的字符1和字符2,如数据给的操作是DC的话,那么c1=’D’,c2=’C’。而对于EX的调用,特判一下就行。

关于同时删除多行数据的问题,按照传统的二维线性表操作写法是不能处理同时删除多行的情况的,我提前处理了一下操作序列,以DR(delete row)为例,假如有个数据是DR 2 a1 a2,其中2代表后面有两个数据,实际要处理的操作序列就是a1 a2,当a1 < a2时,a2会受到前面a1的影响,因为删除a1行的时候表的行数改变了,导致本来的a2变成了a2-1,以此类推,对于每个ai,都要减去它前面a1~a(i-1) 中,比 ai小的项的数量,而插入操作则是相反,减变成加,因为插入后行号会“膨胀”。

写完ac后搜了下其他人的题解,发现其他人用的是开两个表来互相复制的方式实现的同时删除、插入多行数据,这样实现简单一些,但是也有一定的编码量。另外看到的更优的解法是缓存下所有操作,然后只用询问到的数据去做一遍模拟。

题后反思

多维线性表的操作还是得多练。。读英文题面还是要认真、仔细一些。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 55;

int r, c;
int sheet[maxn][maxn];

void genSheet()
{
    memset(sheet, 0, sizeof(sheet));
    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            sheet[i][j] = i * 100 + j;
}

void DC(int col) // delete column
{
    --col; //把1-base的参数转成物理下标
    for (int i = 0; i < r; ++i)
        for (int j = col; j < c - 1; ++j)
            sheet[i][j] = sheet[i][j + 1];
    --c;
}

void DR(int row) //delete row
{
    --row;
    for (int i = row; i < r - 1; ++i)
        for (int j = 0; j < c; ++j)
            sheet[i][j] = sheet[i + 1][j];
    --r;
}

void IC(int col) //insert column
{
    --col;
    for (int i = 0; i < r; ++i)
        for (int j = c; j > col; --j)
            sheet[i][j] = sheet[i][j - 1];
    for (int i = 0; i < r; ++i)
        sheet[i][col] = -1;
    ++c;
}

void IR(int row) //insert row
{
    --row;
    for (int i = 0; i < c; ++i)
        for (int j = r; j > row; --j)
            sheet[j][i] = sheet[j - 1][i];
    for (int i = 0; i < c; ++i)
        sheet[row][i] = -1;
    ++r;
}

void EX(int r, int c, int tr, int tc)
{
    --r, --c, --tr, --tc;
    int tmp = sheet[r][c];
    sheet[r][c] = sheet[tr][tc];
    sheet[tr][tc] = tmp;
}

bool findCell(int rr, int cc, int &tr, int &tc)
{
    --rr, --cc;
    int t = rr * 100 + cc;

    for (tr = 0; tr < r; ++tr)
        for (tc = 0; tc < c; ++tc)
            if (sheet[tr][tc] == t)
                return true;

    return false;
}

bool isFirst = true;

int main()
{
    //freopen("../in.txt", "r", stdin);

    void (*map[25])(int);
    memset(map, 0, sizeof(map));
    map[(('D' << 8) + 'R') % 31] = DR;
    map[(('D' << 8) + 'C') % 31] = DC;
    map[(('I' << 8) + 'R') % 31] = IR;
    map[(('I' << 8) + 'C') % 31] = IC;

    int rnd = 0;
    while (scanf("%d%d", &r, &c) == 2 && r != 0 && c != 0)
    {
        if (!isFirst)//控制空行
            printf("\n");
        isFirst = false;

        ++rnd;

        genSheet();

        int n;
        scanf("%d", &n);
        while (n--)
        {
            char s[5];
            scanf("%s", &s);
            char c1 = s[0], c2 = s[1];
            if (c1 == 'E' && c2 == 'X')
            {
                int r, c, tr, tc;
                scanf("%d%d%d%d", &r, &c, &tr, &tc);
                EX(r, c, tr, tc);
            }
            else
            {
                void (*fun)(int) = map[((c1 << 8) + c2) % 31];
                int a;
                scanf("%d", &a);
                int seq[12] = {0};//读所有序列
                int p = 0;//序列长度
                while (a--)
                    scanf("%d", &seq[p++]);
                //处理操作序列
                for (int i = 0; i < p; ++i)
                {
                    for (int j = 0; j < i; ++j)
                    {
                        if (seq[j] < seq[i])
                            if (c1 == 'D')
                                --seq[i];
                            else
                                ++seq[i];
                    }
                }
                for (int i = 0; i < p; ++i)
                    fun(seq[i]);
            }
        }
        scanf("%d", &n);
        int r, c, tr, tc;
        printf("Spreadsheet #%d\n", rnd);
        while (n--)
        {
            scanf("%d%d", &r, &c);
            bool b = findCell(r, c, tr, tc);
            if (b)
                printf("Cell data in (%d,%d) moved to (%d,%d)\n", r, c, tr + 1, tc + 1);
            else
                printf("Cell data in (%d,%d) GONE\n", r, c);
        }
    }

    return 0;
}
分享到