祖玛

IMPORTANT

开始 Lab5 前请确保提交了 Lab4，请使用 git commit --all 进行提交

使用 git pull 更新任务仓库

你可能需要使用 git pull --rebase 来处理分支冲突

双端链表

开始之前，你可能需要学习双端链表这一数据结构

比起朴素链表，双端链表额外维护了每一个节点的前继，支持我们进行更多操作

双端链表结构

• data：数据
• nxt：记录这个节点之后的节点
• pre：记录这个节点之前的节点

typedef int Type;
//Type可以是任何你需要的数据类型
struct Node{
  struct Node *pre,*nxt;
  Type data;
};
typedef struct Node node;

我们申请空间时会得到一个指向该空间的指针，所以 pre 和 nxt 的类型也是指针，指向相邻节点的地址

当我们需要遍历链表时，肯定需要有一个起点，我们称这个起点为头指针，指向最靠前的节点，该节点的 pre 为 NULL

当我们向链表插入节点时，没有特殊的要求时会将其插入到尾部，也就是最后一个节点之后，指向该节点的指针成为尾指针，该节点的 nxt 为 null

node *head = NULL, *tail = NULL;
//虽然全局变量初值皆为0，但是初始化是个好习惯🤓

双端链表操作

遍历双端链表

与朴素链表无异

/*
 * 传入位次
 * 返回指向对应节点地址的指针
 */
node *find(int rank){
  int i=0;
  node *tmp=head;
  for(;i<rank-1;i++){
    tmp = tmp->nxt;
  }
  return tmp;
}

尾部插入节点

与朴素链表几乎无异，仅需要额外更新 pre 属性

void add_tail(Type data){
  node *tmp = (node *)malloc(sizeof(node));
  tmp->data = data;
  tmp->pre = NULL;
  tmp->nxt = NULL;
  if(head == NULL){
    head = tmp;
    tail = tmp;
    return;
  }
  tail->nxt = tmp;
  tmp->pre = tail;
  tail = tmp;
  return;
}

指定节点后插入节点

与朴素链表几乎无异，仅需要额外更新 pre 属性

void add_node(node *pos,Type data){
  if(pos==tail){
    add_tail(data);
    return;
  }
  node *tmp = (node *)malloc(sizeof(node));
  tmp->data = data;
  tmp->pre = NULL;
  tmp->nxt = NULL;
  tmp->pre=pos;
  tmp->nxt=pos->nxt;
  pos->nxt->pre=tmp;
  pos->nxt=tmp;
}

删除指定节点

与朴素链表几乎无异，仅需要额外更新 pre 属性

void delete(node *pos){
  if(head==tail){
    head = NULL;
    tail = NULL;
    return;
  }else if(pos == head){
    head=pos->nxt;
    head->pre=NULL;
  }else if(pos == tail){
    tail = pos->pre;
    tail->nxt = NULL;
  }else{
    pos->nxt->pre=pos->pre;
    pos->pre->nxt=pos->nxt;
  }
  free(pos);// 不要忘！
  return;
}

题意描述

XY 最近迷上了一款老游戏 —— 祖玛

游戏的规则很简单，XY 每个轮次会发射一枚珠子，任意时刻，如果三枚及以上颜色相同的珠子连续存在，则立刻消除，XY 获得消除的珠子价值之和乘以消除连续消除轮数的分数（注意到一次消除可能会引起下一次消除），具体而言，如果这是本轮引发的第 K 次消除，消除了 N 枚珠子，第 i 枚珠子的价值为 Vi，则有分数 P：

$$P=\sum _{i=1}^N{V}_i\times K$$

具体而言，珠子有以下类型和属性：

• 普通珠
  • 颜色：单个正整数 1、2、3 表示三种颜色
  • 价值：单个正整数 V
  • 作用：任意时刻，如果三枚及以上颜色相同的普通珠连续存在，则立刻消除并获得对应的分数
• 放逐珠
  • 对当前序列第 i 个珠子发射时，将其放逐，移除该枚珠子，此行为不属于消除，不会得分且不计入当轮消除轮数（放逐行为可能会间接引发消除）
• 置顶珠
  • 对当前序列第 i 个珠子发射时，将在该珠子之前的序列按顺序移动到尾部，具体而言，若原序列为「1,2...i...n」，得到的新序列为「i,i+1...n,1,2...i-1」

如果任意时刻，场面上没有任何珠子，游戏立刻结束，且当前分数翻倍，数据保证在场面上没有任何珠子时不再给出任何操作。

输入格式

第一行给定正整数 N 表示初始局面中普通珠的数量

接下来 N 行，没行给出一个正整数 C 和一个正整数 V，以空格分隔，按顺序表示初始局面中普通珠子的颜色和价值分布，数据保证初始局面不存在消除的情况

第 N+1 行开始每行给出如下输入

每行开头给出正整数 K，如果 K 为 0 表示输入结束，否则表示对第 K 个珠子发射

以空格分隔，给出正整数 T，如果 T 为 4 表示放逐珠，T 为 5 表示置顶珠，否则 T 为普通珠的颜色（1、2、3）

如果发射的是普通珠，以空格分隔，给出正整数 V，表示普通珠的价值

输出格式

输出一个正整数 ANS，表示 XY 的最终得分

数据范围

1<=N<=1000,1<=C<=3,1<=T<=5,1<=V<=10

样例输入

见 test 目录下四组.in 文件

样例输出

见 test 目录下四组.out 文件

注意事项

已提供宝宝巴士填空版本，也可自己白手起家，但请不要在你的代码中声明任何数组

请勿修改代码名称（zuma），若白手起家请依旧命名你的代码文件为 zuma.c

运行 datamaker 可执行文件生成一组随机测试样例:randomcase.in,randomcase.out

make all            # 编译代码
make judge-case     # 运行测试样例
make judge-random   # 随机生成样例进行测试