首页 > ACM题库 > HDU-杭电 > hdu 4019 Batch System待解决[解题报告]C++
2015
04-15

hdu 4019 Batch System待解决[解题报告]C++

Batch System

问题描述 :

Large distributed data center so-called “bigtable” receives a huge number of update queries every minute from servers all over the world. The engineers want to make the system works more efficiency, so they come up with a batch system for bigtable.
We can denote the data in the bigtable as an infinity text data. Every client can send commands to the bigtable server to editing the text. Once the client connects to the bigtable server, the cursor for the client is positioned before the first character of the text before performing any commands. The bigtable only supports three operations below:
Parsing URL

When a new client connects the server, it sends all the operations to the bigtable. And then the next client can connect and perform its own operation list.
  The batch system is designed to save the traffic volume. It merges all the clients operation together to one equivalent operation list. But their engineers soon noticed that it is hard to make the resulted operation list shortest.
  They ask you, their senior programmer, to make up a solution, give the operation lists with minimum length and let the delete operations before the insert operations if possible.

输入:

The first line contains the number of test cases. The description of T tests follow.
  The first line of each test case contains the amount of clients n (1 <= n <= 10000). You can assume the client comes exactly in the order of the input.
The description of operation list of each client follows. The first line of each operation list contains the number of operations m first (1 <= m <= 10). The next m lines contain the description of each operation in the format given above. 1 <= k <= 100000 for R and D operations, and 1 <= k <= 10 for C operations. The strings in C operations consist of latin letters and digits only.

输出:

The first line contains the number of test cases. The description of T tests follow.
  The first line of each test case contains the amount of clients n (1 <= n <= 10000). You can assume the client comes exactly in the order of the input.
The description of operation list of each client follows. The first line of each operation list contains the number of operations m first (1 <= m <= 10). The next m lines contain the description of each operation in the format given above. 1 <= k <= 100000 for R and D operations, and 1 <= k <= 10 for C operations. The strings in C operations consist of latin letters and digits only.

样例输入:

1
2
4
R 4
C 3 abc
R 2
C 3 xyz
3
R 7
C 3 def
D 3

样例输出:

3
R 4
D 2
C 8 abcdefyz


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge