题解：UVA1458 Exciting Time
为了方便进行整个面板的布局，不妨考虑使用链表表示面板上的方块，从而实现单行删除等功能。下面是其中一种可能的设计：
其中左侧的结点代表行，使用循环双向链表维护。每行通过 right 指针将该行所有的块串起来。需要注意的是，这些块串起来的顺序无所谓，因为这个指针主要用来删除整行。
其次，对每一列的所有块，我们使用双向链表维护，此时这些块要求有序，因为我们需要获取每行最高的位置。
在这种设计下，我们每次加入一个块时，先在列上维护双向链表，然后直接将其插入到行的 right 指针的位置。如果当前行包含的块个数等于版面宽度，首先维护左侧的行双向链表，随后通过 right 访问这一行的所有块，在其所在列上进行删除。
我们考虑如何确定每个块落下的位置。我们预处理出每个形态的块在每一列中最下面的空隙大小，例如对于下面的图形：
##
##
####
####
##..
##..我们就认为这个图形在第一列上没有空隙，而在第二列上有一个空隙（. 处）。我们确定每一列在版面上的位置，在获取最高块的位置后，顺着行的双向链表往下数 空隙个数 次之后即可找到当前块在这一列上的限制行。我们只需要将这些行取最高值，就可以知道每个块最靠下的部分落在哪一行中。
我们随后需要确定每个部分的位置并加入到链表系统中。考虑到我们使用循环双向链表处理行部分，那么加入行实际上是并不困难的，据此进行模拟即可。对于每一列，如果我们按照从低到高的顺序加入每个部分，那么在双向链表上必然是在末尾插入一个指针，实现起来会比较方便。
在最后输出时，只需要从低到高枚举所有块即可计算，不再赘述。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct LinkNode {
int id;
int row;
LinkNode *prev, *next, *right;
LinkNode(int id, int row): id(id), row(row)
,prev(nullptr), next(nullptr), right(nullptr) {}
};
struct LinkList {
int id;
LinkNode *l, *r;
LinkNode* append(int row) {
LinkNode *p = new LinkNode(id, row);
if (l == nullptr)
l = r = p;
else {
r -> next = p;
p -> prev = r;
r = p;
}
return p;
}
void remove(LinkNode *p) {
if (p == l && p == r) {
delete p;
l = r = nullptr;
return;
}
if (p == r) {
r = r -> prev;
r -> next = nullptr;
}
else if (p == l) {
l = l -> next;
l -> prev = nullptr;
}
else {
p -> prev -> next = p -> next;
p -> next -> prev = p -> prev;
}
delete p;
}
int highest() {
return r == nullptr ? 0 : r -> row;
}
} cols[30010];
int w, n;
struct RowManager {
int l[120010], r[120010];
LinkNode *head[120010];
int rcnt;
int sz[120010];
int final_ans[30010];
void init() {
rcnt = 0;
l[0] = 0;
r[0] = 0;
sz[0] = 0;
}
int new_row() {
++ rcnt;
r[rcnt] = 0;
l[rcnt] = l[0];
r[l[0]] = rcnt;
l[0] = rcnt;
head[rcnt] = 0;
sz[rcnt] = 0;
return rcnt;
}
int next_row(int x) {
if (r[x] == 0)
return new_row();
return r[x];
}
int last_row(int x) {
return x == 0 ? 0 : l[x];
}
int last_k_row(int x, int k) {
while (k --)
x = last_row(x);
return x;
}
bool add_block(int row, int col) {
LinkNode *ptr = cols[col].append(row);
ptr -> right = head[row];
head[row] = ptr;
if (++ sz[row] == w) {
ptr = head[row];
while (ptr != nullptr) {
LinkNode *temp = ptr -> right;
cols[ptr -> id].remove(ptr);
ptr = temp;
}
r[l[row]] = r[row];
l[r[row]] = l[row];
return true;
}
return false;
}
void calc_final() {
for (int i = 0; i < w; i ++)
final_ans[i] = 0;
int num = 1, cur = r[0];
while (cur != 0) {
LinkNode *ptr = head[cur];
while (ptr != nullptr) {
LinkNode *temp = ptr -> right;
final_ans[ptr -> id] = num;
delete ptr;
ptr = temp;
}
cur = r[cur];
++ num;
}
for (int i = 0; i < w; i ++)
printf("%d%c", final_ans[i], " \n"[i == w - 1]);
}
} RM;
struct Block {
int w, h;
vector<int> wlow, whigh;
} b_info[7][4];
const int scores[5] = {0, 100, 250, 400, 1000};
int main() {
// I
b_info[0][0] = {4, 1, {0, 0, 0, 0}, {0, 0, 0, 0}};
b_info[0][1] = {1, 4, {0}, {3}};
// J
b_info[1][0] = {3, 2, {0, 0, 0}, {1, 0, 0}};
b_info[1][1] = {2, 3, {0, 2}, {2, 2}};
// L
b_info[2][0] = {3, 2, {0, 0, 0}, {0, 0, 1}};
b_info[2][1] = {2, 3, {0, 0}, {2, 0}};
// O
b_info[3][0] = b_info[3][1] = {2, 2, {0, 0}, {1, 1}};
// S
b_info[4][0] = {3, 2, {0, 0, 1}, {0, 1, 1}};
b_info[4][1] = {2, 3, {1, 0}, {2, 1}};
// T
b_info[5][0] = {3, 2, {0, 0, 0}, {0, 1, 0}};
b_info[5][1] = {2, 3, {0, 1}, {2, 1}};
// Z
b_info[6][0] = {3, 2, {1, 0, 0}, {1, 1, 0}};
b_info[6][1] = {2, 3, {0, 1}, {1, 2}};
for (int i = 0; i < 7; i ++)
for (int j : {2, 3}) {
b_info[i][j].w = b_info[i][j - 2].w;
b_info[i][j].h = b_info[i][j - 2].h;
for (int k = 0; k < b_info[i][j].w; k ++) {
b_info[i][j].wlow.push_back(b_info[i][j].h - 1 - b_info[i][j - 2].whigh[b_info[i][j].w - 1 - k]),
b_info[i][j].whigh.push_back(b_info[i][j].h - 1 - b_info[i][j - 2].wlow[b_info[i][j].w - 1 - k]);
}
}
int t; scanf("%d", &t);
int curcase = 0;
while (t --) {
printf("Case #%d:\n", ++ curcase);
scanf("%d%d", &w, &n);
RM.init();
for (int i = 0; i < w; i ++)
cols[i].l = cols[i].r = nullptr, cols[i].id = i;
int tot_score = 0;
for (int i = 0; i < n; i ++) {
char ch; int pos; int rot;
scanf(" %c%d%d", &ch, &pos, &rot);
int piece_id = 0;
if (ch == 'I') piece_id = 0;
else if (ch == 'J') piece_id = 1;
else if (ch == 'L') piece_id = 2;
else if (ch == 'O') piece_id = 3;
else if (ch == 'S') piece_id = 4;
else if (ch == 'T') piece_id = 5;
else piece_id = 6;
Block &blk = b_info[piece_id][rot / 90];
int baseline = 0;
for (int u = 0; u < blk.w; u ++)
baseline = max(baseline, RM.last_k_row(cols[pos + u].highest(), blk.wlow[u]));
vector<int> H(blk.h);
for (int i = 0; i < blk.h; i ++)
H[i] = (baseline = RM.next_row(baseline));
int cnt = 0;
for (int u = 0; u < blk.w; u ++)
for (int v = blk.wlow[u]; v <= blk.whigh[u]; v ++)
cnt += RM.add_block(H[v], pos + u);
tot_score += scores[cnt];
}
printf("%d\n", tot_score);
RM.calc_final();
}
}