Uva 101 The Blocks Game 个人题解
题目大意
模拟题，大意很简单，但自己要出几组数据去测，因为该题样例有点神奇，很可能怎么跑都是对的
你有 n 个方块，分别被编号了，放在一列上
就像这样
//assume n = 4
0: 0
1: 1
2: 2
3: 3
把他们想象成摞在一起的会更好理解，题意也是这样
8
5 7
0 1 2 3 4 6
-----------------
0 1 2 3 4 5 6 7 8
然后有四种操作，操作完了按格式输出就好
// assume n = 5
1 2 3 4 5
// move 5 onto 1
// 把序号为 5 和 1 的方块上的所有方块放回原先的地方，比如 3 方块就要放回 3 号格子
// 然后把序号为5的方块放在序号为 1 的方块所在的格子上
5
1 2 3 4
// move 1 over 2
// 把序号为 1 的方块上的所有方块放回原位，然后把这个方块放到序号为 2 的方块的格子上
1
2 3 4 5
// pile 3 over 2
// 把序号为 2 的方块上的所有方块放回原位，然后把序号为 3 的方块及其以上的所有放在这个方块所在的格子上（顺序不变）
3
1 2 4 5
// pile 2 onto 4
// 把序号为 2 的方块以及其上的所有方块放到 序号为 4 的方块所在的格子上
3
2
1 4 5
// 另外当 a == b 时是非法数据，不用管
一个数组，每个地方放一个链表就好，模拟也行，二维数组也行，怎么着也行，题目时间非常宽裕，只要别瞎写
吐槽一下这道题用语言自带的容器是很不舒服的，个人感觉直接手写一个应该最爽
经过本人观察（我才懒得去测），udebug的很多答案其实是错的（因为我的这个a了但是udebug是错的），但依旧可以参照，因为原题其实没有对应数据，可能是为了避免题目歧义。
歧义的数据如下:
4
3
1 5 2 6 7 8 9
-----------------
1 2 3 4 5 6 7 8 9
// move 3 onto 2
主要代码，我相信你看不下去的，因为改了一天，很多地方都惨不忍睹，发上来也懒得改了，全部代码在下面
class Blocks {
List<LinkedList<Integer>> blocks;
Blocks(int n) {
blocks = new ArrayList<>(50);
for (int i = 0; i < n; i++) {
blocks.add(new LinkedList<>());
blocks.get(i).add(i);
}
}
private int[] findBlock(int x) {
for (int i = 0; i < blocks.size(); i++) {
int j = 0;
for (Iterator<Integer> it = blocks.get(i).iterator(); it.hasNext(); j++) {
if (it.next() == x) return new int[] {i, j};
}
}
return new int[] {0, 0};
}
private boolean isIllegal(int a, int b) {
return a == b;
}
private void addVal(int idx, int val) {
blocks.get(idx).add(val);
} //这个重载方法到最后并没有用到
//avoid package class
private void addVal(int idx, Integer val) {
blocks.get(idx).add(val);
}
private Iterator<Integer> fromIt(int idx, int from) {
return blocks.get(idx).listIterator(from);
}
private void flushOut(int i, int j, int val) {
Iterator<Integer> it = fromIt(i, j);
while (it.hasNext()) {
int temp = it.next();
if (i == temp) continue;
addVal(temp, temp); it.remove();
}
}
private void flushRange(int idx, int from, int put) {
if (idx == put) return;
for (Iterator<Integer> it = fromIt(idx, from); it.hasNext(); ) {
addVal(put, it.next());
}
clearSub(idx, from);
}
private void clearSub(int idx, int from) {
if (from >= blocks.get(idx).size()) return;
blocks.get(idx).subList(from, blocks.get(idx).size()).clear(); //交给gc
}
Blocks moveOnto(int a, int b) {
if (isIllegal(a, b)) return this;
int[] idxa = findBlock(a);
flushOut(idxa[0], idxa[1], a);
int[] idxb = findBlock(b);
flushOut(idxb[0], idxb[1], b);
addVal(b, blocks.get(a).removeLast());
return this;
}
Blocks moveOver(int a, int b) {
if (isIllegal(a, b)) return this;
int[] idxa = findBlock(a);
flushOut(idxa[0], idxa[1], a);
int[] idxb = findBlock(b);
addVal(idxb[0], blocks.get(a).removeLast());
return this;
}
Blocks pileOnto(int a, int b) {
if (isIllegal(a, b)) return this;
int[] idxb = findBlock(b);
flushOut(idxb[0], idxb[1], b);
int[] idxa = findBlock(a);
flushRange(idxa[0], idxa[1], b);
return this;
}
Blocks pileOver(int a, int b) {
if (isIllegal(a, b)) return this;
int[] idxa = findBlock(a), idxb = findBlock(b);
flushRange(idxa[0], idxa[1], idxb[0]);
return this;
}
@Override
public String toString() {
StringBuilder ans = new StringBuilder();
for (int i = 0; i < blocks.size(); i++) {
ans.append(i).append(":");
LinkedList<Integer> list = blocks.get(i);
if (list.isEmpty()) {
ans.append('\n');
continue;
} else ans.append(' ');
for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
ans.append(it.next());
if (it.hasNext()) ans.append(' ');
}
ans.append('\n');
}
return ans.toString();
}
}
全部代码：
/*
@author AExiaoliou
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.*;
public class Main {
public static void main(String[] args) {
new Solver().solve().end();
}
}
class Solver {
PrintWriter out;
FastReader cd;
@SuppressWarnings("unused")
public static final int INF = 0x3f3f3f3f;
@SuppressWarnings("unused")
public static final double MINI = 1e-6, ATOM = 1e-8;
Solver() {
out = new PrintWriter(System.out, true);
cd = new FastReader();
}
class Blocks {
List<LinkedList<Integer>> blocks;
Blocks(int n) {
blocks = new ArrayList<>(50);
for (int i = 0; i < n; i++) {
blocks.add(new LinkedList<>());
blocks.get(i).add(i);
}
}
private int[] findBlock(int x) {
for (int i = 0; i < blocks.size(); i++) {
int j = 0;
for (Iterator<Integer> it = blocks.get(i).iterator(); it.hasNext(); j++) {
if (it.next() == x) return new int[] {i, j};
}
}
return new int[] {0, 0};
}
private boolean isIllegal(int a, int b) {
return a == b;
}
private void addVal(int idx, int val) {
blocks.get(idx).add(val);
}
private void addVal(int idx, Integer val) {
blocks.get(idx).add(val);
}
private Iterator<Integer> fromIt(int idx, int from) {
return blocks.get(idx).listIterator(from);
}
private void flushOut(int i, int j, int val) {
Iterator<Integer> it = fromIt(i, j);
while (it.hasNext()) {
int temp = it.next();
if (i == temp) continue;
addVal(temp, temp); it.remove();
}
}
private void flushRange(int idx, int from, int put) {
if (idx == put) return;
for (Iterator<Integer> it = fromIt(idx, from); it.hasNext(); ) {
addVal(put, it.next());
}
clearSub(idx, from);
}
private void clearSub(int idx, int from) {
if (from >= blocks.get(idx).size()) return;
blocks.get(idx).subList(from, blocks.get(idx).size()).clear();
}
Blocks moveOnto(int a, int b) {
if (isIllegal(a, b)) return this;
int[] idxa = findBlock(a);
flushOut(idxa[0], idxa[1], a);
int[] idxb = findBlock(b);
flushOut(idxb[0], idxb[1], b);
addVal(b, blocks.get(a).removeLast());
return this;
}
Blocks moveOver(int a, int b) {
if (isIllegal(a, b)) return this;
int[] idxa = findBlock(a);
flushOut(idxa[0], idxa[1], a);
int[] idxb = findBlock(b);
addVal(idxb[0], blocks.get(a).removeLast());
return this;
}
Blocks pileOnto(int a, int b) {
if (isIllegal(a, b)) return this;
int[] idxb = findBlock(b);
flushOut(idxb[0], idxb[1], b);
int[] idxa = findBlock(a);
flushRange(idxa[0], idxa[1], b);
return this;
}
Blocks pileOver(int a, int b) {
if (isIllegal(a, b)) return this;
int[] idxa = findBlock(a), idxb = findBlock(b);
flushRange(idxa[0], idxa[1], idxb[0]);
return this;
}
@Override
public String toString() {
StringBuilder ans = new StringBuilder();
for (int i = 0; i < blocks.size(); i++) {
ans.append(i).append(":");
LinkedList<Integer> list = blocks.get(i);
if (list.isEmpty()) {
ans.append('\n');
continue;
} else ans.append(' ');
for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
ans.append(it.next());
if (it.hasNext()) ans.append(' ');
}
ans.append('\n');
}
return ans.toString();
}
}
Solver solve() {
int n = cd.nextInt();
Blocks blocks = new Blocks(n);
int lines = 0;
quit:
while (true) {
int a, b;
lines += 1;
switch (cd.next()) {
case "move":
a = cd.nextInt();
switch (cd.next()) {
case "onto":
b = cd.nextInt();
blocks.moveOnto(a, b);
break;
case "over":
b = cd.nextInt();
blocks.moveOver(a, b);
break;
}
break;
case "pile":
a = cd.nextInt();
switch (cd.next()) {
case "onto":
b = cd.nextInt();
blocks.pileOnto(a, b);
break;
case "over":
b = cd.nextInt();
blocks.pileOver(a, b);
break;
}
break;
default:
break quit;
}
}
out.print(blocks.toString());
out.printf(""); //flush
return this;
}
void end() {
out.close();
cd.close();
}
@SuppressWarnings("unused")
class FastReader {
private BufferedReader in;
private StringTokenizer tokenizer;
FastReader() {
in = new BufferedReader(new InputStreamReader(System.in), 23333);
tokenizer = null;
}
String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(in.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
int[] nextInts(int len) {
int[] a = new int[len];
for (int i = 0; i < a.length; i++) {
a[i] = cd.nextInt();
}
return a;
}
double nextDouble() {
return Double.parseDouble(next());
}
void close() {
try {
in.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
}