“微博直播开房”局长被停职：宝贝，我一直在市长那汇报工作 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

“微博直播开房”局长被停职：宝贝，我一直在市长那汇报工作

“微博直播开房”局长被停职：宝贝，我一直在市长那汇报工作# Joke - 肚皮舞运动

b*y2011-06-22 07:06

1 楼

是样题，然后还是45分钟倒计时的
可以用各种语言编写
感觉这种题目，用C或者java写是不是编程时间上比不过python？
单单看题目本身也很难啊，像是hannoi，但比它难多了，不知道有什么思路？
There are K pegs. Each peg can hold discs in decreasing order of radius when
looked from bottom to top of the peg. There are N discs who have radius 1
to N; Given the initial configuration of the pegs and the final
configuration of the pegs, output the moves required to transform from the
initial to final configuration. You are required to do the transformations
in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and
placing it on top of anyother peg. At anypoint of time, the decreasing
radius property of all the pegs must be maintained.
Constraints:
1<= N<=8
3<= K<=5
Input Format:
NK
2nd line contains N integers, each in the range 1 to K, the i-th integer
denotes, the peg to which disc of radius i is present in the initial
configuration.
3rd line denotes the final configuration in a format similar to the initial
configuration.
Output Format:
The first line contains M - The minimal number of moves required to complete
the transformation.
The following M lines describe a move, by a peg number to pick from and a
peg number to place on.
If there are more than one solutions, it's sufficient to output any one of
them. You can assume, there is always a solution with less than 7 moves and
the initial confirguration will not be same as the final one.
Sample Input #00:
2 3
1 1
2 2
Sample Output #00:
3
1 3
1 2
3 2
Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1

d*f2011-06-22 07:06

2 楼

中国江苏溧阳卫生局局长通过“微博”约一女子开房的消息，经媒体曝光后，引起广泛
关注。据中新社21日最新消息，记者从溧阳纪检部门获知纪检部门刚刚做出对溧阳卫生
局局长谢志强停职的决定。
“宝贝，我上午一直在市长那汇报工作。”“我先把房卡给你，你先去休息一下，等会
我去。好吗？”“房卡怎么给我？我不到前台拿”……20日下午，这段打情骂俏般的微
博对话，让网友怀疑两人在相约“开房”，同时微博信息也透露出对话者的身份是政府
官员。相关微博对话迅速在网上传播。根据当事人微博头像，有网友指认出是溧阳卫生
局局长谢志强。
21日，记者赶赴相关部门了解情况，据知情人介绍，该局长才学会玩微博不久，以为微
博是很私密的网上聊天工具。根本没想到自己的微博对话会在网上散播出去。后得知微
博内容被网友转载后，已删掉微博内容，并主动向当地纪检部门说明情况。
此间，溧阳纪检部门的相关负责人告诉记者，目前已做出对谢志强停职的决定，对微博
涉及内容将进一步调查。
21日，网上曝出江苏常州溧阳市卫生局长的微博对话引来网友关注，从打情骂俏般的对
话中，似乎是两人在相约“开房”，据网友指认，“为了你5123”是溧阳卫生局局长谢
志强。溧阳纪委的相关负责人透露情况属实，正在进一步调查中。

l*n2011-06-22 07:06

3 楼

dp
没看懂
23
11
22

when

【在 b*******y 的大作中提到】

: 是样题，然后还是45分钟倒计时的
: 可以用各种语言编写
: 感觉这种题目，用C或者java写是不是编程时间上比不过python？
: 单单看题目本身也很难啊，像是hannoi，但比它难多了，不知道有什么思路？
: There are K pegs. Each peg can hold discs in decreasing order of radius when
: looked from bottom to top of the peg. There are N discs who have radius 1
: to N; Given the initial configuration of the pegs and the final
: configuration of the pegs, output the moves required to transform from the
: initial to final configuration. You are required to do the transformations
: in minimal number of moves.

h*n2011-06-22 07:06

4 楼

可以坦白是去检查个人卫生。

【在 d********f 的大作中提到】

: 中国江苏溧阳卫生局局长通过“微博”约一女子开房的消息，经媒体曝光后，引起广泛
: 关注。据中新社21日最新消息，记者从溧阳纪检部门获知纪检部门刚刚做出对溧阳卫生
: 局局长谢志强停职的决定。
: “宝贝，我上午一直在市长那汇报工作。”“我先把房卡给你，你先去休息一下，等会
: 我去。好吗？”“房卡怎么给我？我不到前台拿”……20日下午，这段打情骂俏般的微
: 博对话，让网友怀疑两人在相约“开房”，同时微博信息也透露出对话者的身份是政府
: 官员。相关微博对话迅速在网上传播。根据当事人微博头像，有网友指认出是溧阳卫生
: 局局长谢志强。
: 21日，记者赶赴相关部门了解情况，据知情人介绍，该局长才学会玩微博不久，以为微
: 博是很私密的网上聊天工具。根本没想到自己的微博对话会在网上散播出去。后得知微

b*y2011-06-22 07:06

5 楼

sorry，粘贴的时候没空格了，已经在正文中改了，数字之间都有空格

【在 l******n 的大作中提到】

: dp
: 没看懂
: 23
: 11
: 22
:
: when

l*i2011-06-22 07:06

6 楼

You can use BFS, each node is a configuration, each edge is a valid move.
Each configuration is an array of length at most 8, a[i]=peg that disc[i] is
at. So you have at most 5^8=10^6 configurations, which fits in memory. And
from each configuration you can make a move to next configuration using
those moves. Since you have only 5 pegs, you can have at most 4*5=20 valid
moves. Your total running time is then at most 10^6 states times at most 20
moves from each state, which is at most 10^8 and it should be pretty fast.

b*y2011-06-22 07:06

7 楼

Dynamic Programming做的话，configuration的indexing好像就不是那么清晰了。
例如我不知道下一个要算的configuration是什么...
也许，你说的Dynamic Programming是用了BFS的，这样，可以知道接下来要算的一组元
素。
不过要给每个configuration标记是否已经被访问过
好像这题也可以用DFS来做，就是遍历各种情况，因为题目告诉我们可以assume最短布
数在7步之内，而且很多move可以直接看出违反“小在上，大在下”的规律的。

is
And
20

【在 l***i 的大作中提到】

: You can use BFS, each node is a configuration, each edge is a valid move.
: Each configuration is an array of length at most 8, a[i]=peg that disc[i] is
: at. So you have at most 5^8=10^6 configurations, which fits in memory. And
: from each configuration you can make a move to next configuration using
: those moves. Since you have only 5 pegs, you can have at most 4*5=20 valid
: moves. Your total running time is then at most 10^6 states times at most 20
: moves from each state, which is at most 10^8 and it should be pretty fast.

g*y2011-06-22 07:06

8 楼

这个题不好写的是状态保存和转换。
最多5个peg, 8个disc, 所以可以用long(64-bit)来保存状态，转换需要位操作。
这是我的写法，欢迎改进：
public class KPeg {
public void move(int N, int K, int[] begin, int[] end) {
long s0 = stateToLong(begin);
long sn = stateToLong(end);

ArrayList visited = new ArrayList();
visited.add(new Node(s0, 0, 0, -1));

Deque dq = new ArrayDeque();
dq.add(0);

while (!dq.isEmpty()) {
int current = dq.remove();
for (int i=0; ifor (int j=0; jlong next = move(visited.get(current).state, i, j);
if (next == sn) {
visited.add(new Node(next, i+1, j+1, current));
printSolution(visited, current);
return;
}

if (next > 0 && !seen(visited, next)) {
visited.add(new Node(next, i+1, j+1, current));
dq.add(visited.size() - 1);
}
}
}
}
}

private boolean seen(ArrayList visited, long state) {
for (Node node : visited) if (node.state == state) return true;
return false;
}

private long stateToLong(int[] state) {
long s = 0;
for (int i=0; is |= (1 << i) << (8*state[i] - 8);
}
return s;
}

private long move(long state, int from, int to) {
if (from == to) return -1;
int pegFrom = (int) ((state >> 8*from) & 0xff);
int pegTo = (int) ((state >> 8*to) & 0xff);
for (int i=0; i<8; i++) {
if ((pegFrom >> i & 1) > 0) {
state &= ~((1L << i) << 8*from);
state |= (1L << i) << 8*to;
return state;
}
if ((pegTo >> i & 1) > 0) return -1;
}
return -1;
}

private void printSolution(ArrayList visited, int current) {
Stack stack = new Stack();
stack.push(visited.size()-1);
while (current > 0) {
stack.push(current);
current = visited.get(current).parent;
}
System.out.println(stack.size());
while (!stack.isEmpty()) {
int t = stack.pop();
System.out.println(visited.get(t).from + " " + visited.get(t).to
);
}
}

private class Node {
long state;
int from;
int to;
int parent;
public Node(long state, int from, int to , int parent) {
this.state = state;
this.from = from;
this.to = to;
this.parent = parent;
}
}

public static void main(String[] args) {
KPeg k = new KPeg();
// k.move(2, 3, new int[]{1, 1}, new int[]{2, 2});
k.move(6, 4, new int[]{4, 2, 4, 3, 1, 1}, new int[]{1, 1, 1, 1, 1, 1
});
}
}

l*y2011-06-22 07:06

9 楼

顺手写了一个，46min整。也没用状态压缩，待会看一下gloomyturkey的code。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 9;
const int maxk = 6;
int N, K;
struct State {
State() {
for (int i = 0; i < maxk; i++) {
for (int j = 0; j < maxn; j++) {
array[i][j] = false;
}
}
step.clear();
}
bool array[maxk][maxn];
vector > step;
};
bool operator==(const State& s1, const State& s2)
{
for (int i = 0; i < maxk; i++) {
for (int j = 0; j < maxn; j++) {
if (s1.array[i][j] != s2.array[i][j]) return false;
}
}
return true;
}
bool operator< (const State& s1, const State& s2)
{
for (int i = 0; i < maxk; i++) {
for (int j = 0; j < maxn; j++) {
if (s1.array[i][j] != s2.array[i][j]) {
return s1.array[i][j] < s2.array[i][j];
}
}
}
return false;
}
void BFS(State& init, State& final)
{
queue myqueue;
set myset;
myqueue.push(init);
myset.insert(init);
while (! myqueue.empty()) {
State state = myqueue.front();
myqueue.pop();
if (state == final) {
final.step = state.step;
return;
}
for (int i = 1; i <= K; i++) {
int index = -1;
for (int j = 1; j <= N; j++) {
if (state.array[i][j]) {
index = j;
break;
}
}
if (index > 0) {
for (int j = 1; j <= K; j++) {
if (j == i) continue;
State next = state;
next.array[i][index] = false;
bool islegal = true;
for (int k = 1; k < index; k++) {
if (next.array[j][k]) {
islegal = false;
break;
}
}
if (islegal) {
next.array[j][index] = true;
next.step.push_back(make_pair(i, j));
if (myset.find(next) == myset.end()) {
myset.insert(next);
myqueue.push(next);
}
}
}
}
}
}
}
int main() {
freopen("input","r",stdin);
while (cin >> N >> K) {
State init;
int num;
for (int i = 1; i <= N; i++) {
cin >> num;
init.array[num][i] = true;
}
State final;
for (int i = 1; i <= N; i++) {
cin >> num;
final.array[num][i] = true;
}
BFS(init, final);
cout << final.step.size() << endl;
for (int i = 0; i < final.step.size(); i++) {
cout << final.step[i].first << " " << final.step[i].second <<
endl;
}
}
return 0;
}

C*l2011-06-22 07:06

10 楼

是onsite时做还是过后回家做？

d*l2011-06-22 07:06

11 楼

这学期试着在学习python，用python也写了一个。力求简练，效率应该不怎么高。
def getpath(now, visited, steps):
if now == visited[h(now)]:
print steps;
return ;
prev = visited[h(now)];
p = [i for i in xrange(0, len(now)) if now[i] != prev[i]][0];
getpath(prev, visited, steps + 1);
print prev[p], now[p];
def h(node):
return ''.join([str(n) for n in node]);

def solve(N, K, init, target):
q = [init];
visited = {h(init):init};
while q != []:
now = q.pop(0);
if now == target:
getpath(now, visited, 0);
for i in [j for j in xrange(0, N) if [k for k in xrange(j) if now[k]
== now[j]] == []]:
for j in [k for k in xrange(1, K + 1) if [l for l in xrange(i)
if now[l] == k] == []]:
next = now[:];
next[i] = j;
if not visited.has_key(h(next)):
visited[h(next)] = now;
q.append(next);
if __name__ == '__main__':
(N, K) = map(int, raw_input().split(' '));
init = map(int, raw_input().split(' '));
target = map(int, raw_input().split(' '));
solve(N, K, init, target);

d*l2011-06-22 07:06

12 楼

主要要解决的问题就像上面说的是状态的表示和move。我得思路是，其实输入的那种格
式就可以很好的表示状态，即从小到大N个disc的位置构成的向量。每次move的时候，
从小到大试着移动disc，如果某个disc之前有和它位置相同的，那就说明它无法移动。
确定可以移动之后，枚举所有可能位置，如果它之前有在这个位置上的，就不能移动到
这个位置。这里说的“之前”就是在向量中下标比它小的那些元素。

b*y2011-06-22 07:06

13 楼

学习了，
python编写严格限时完成的题目的时候，比c++有很大优势

【在 d*******l 的大作中提到】

: 这学期试着在学习python，用python也写了一个。力求简练，效率应该不怎么高。
: def getpath(now, visited, steps):
: if now == visited[h(now)]:
: print steps;
: return ;
: prev = visited[h(now)];
: p = [i for i in xrange(0, len(now)) if now[i] != prev[i]][0];
: getpath(prev, visited, steps + 1);
: print prev[p], now[p];
: def h(node):