地铁难挤: 400 描述

米特尼克需要用社工办法 拿到THU安全专家的磁盘镜像以了解更多信息，于是他收买了THU专家的博士生，来到BJ市需要与博士生当面联系。但是，来到BJ市之后遇到的第一个问题 就是交通。BJ市人满为患，上下地铁时人们也不先下后上，而是互相挤。左边的人想挤到右边下车，右边的人也想挤到左边上车。你作为米特尼克在BJ的一位小 伙伴，能否帮他和所有乘客设计一个尽量少移动次数的方案，使得需要上车的人都上车，需要下车的人都下车。218.2.197.242:6000 or 218.2.197.243:6000

提示

此题是PPC 1. 地铁和车都是背景描述而已，和题目没关系，本题的目标就是让左边的人 L 都到 右边去，右边的人 R 都到左边来 2. 人的移动规则和游戏规则需要大家遍历出来，每次输入一个数字(20以内) 都不知道PPC什么意思。。反正先连接上去看看 要算一个sha1，先写了个python跑了一次X是三位的，但是发现每次连接字符串都会变。。。只能取得了再跑，后来发现用python写的会超时。。。然后尝试用hashcat来破 命令如下command = ‘cudaHashcat64 –custom-charset1 ?l?u?d -m 100 -a 3 “+result+” “+base+”?1?1?1?1”‘ 连上之后是一个什么游戏。。。 玩了半天，再根据题意。规则是空格分隔左右两边，最后要让L都到右边，R都到左边。 一次输入一个数字，代表这个字符串的第几个位置（空格也算一个位置），让这个位置上的人往另外一侧移动 一次最多只能移动两个人 如LRLRLRLRL R 输入9,，就变成LRLRLRLR LR 如LRLRLRLRL R 输入8，就变成LRLRLRL LRR，即两个人都到另一侧，并且互换位置 若输入不合法则返回wrong answer游戏失败。 下面就是游戏的算法啦 xin5739写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
//xin5739
#include <iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include "queue"
#define INF 100000000
using namespace std;
int sta\[1<<22\]\[22\];
int opp\[1<<22\]\[22\],ops\[1<<22\]\[22\],anss\[1<<22\]\[22\];
int len;
int judge(int s,int p)//判断是否达到目标,p是空格位置
{
     for (int i=0;i<len;i++)
     {
           if(i<p&&(s&(1<<i))==0) return 0;
           if(i>p&&(s&(1<<i))==1) return 0;
     }
     return 1;
}
int check(int s,int &p,int &now)//检查是否是合法移动,p是空格位置
{
       int x,y;
       x=p;y=now;
       if(x==y) return -1;
       int f0=0,f1=0;
       if(x>y)
       {
             x--;
             int t=x;x=y;y=t;
       }
       else x++;
       for (int i=x;i<=y;i++)
       {
            if(s&(1<<i)) f1=1;
            else f0=1;
       }
       if(f1==1&&f0==1)
       {
            if(y-x+1>2) return -1;
            if(p<x)//pxy->yxp
            {
                  if(s&(1<<y))
                  {
                      s|=(1<<p);
                      s^=(1<<y);
                  }
                  else if(s&(1<<p)) s^=(1<<p);
                  now=p;
                  p=y;
            }
            else //xyp->pyx
            {
                if(s&(1<<x))
                {
                    s|=(1<<p);
                    s^=(1<<x);
                }
                 else if(s&(1<<p)) s^=(1<<p);
                 now=p;
                p=x;
            }
            return s;
       }
       else
       {
           if(p<x) //pxxxx->xxxxp
           {
                 for (int j=p;j<y;j++)
                 {
                      if(s&(1<<(j+1)))
                      {
                            s|=(1<<j);
                      }
                      else if(s&(1<<j)) s^=(1<<j); 
                 }
                 if(s&(1<<y)) s^=(1<<y);
                 now=p;
                 p=y;
           }
           else //xxxxp->pxxxx
           {
              // if(p!=y+1) printf("1111213123");
                for (int j=p;j>x;j--)
                {
                    if(s&(1<<(j-1)))
                    {
                        s|=(1<<j);
                    }
                    else if(s&(1<<j)) s^=(1<<j);
                }
                if(s&(1<<x)) s^=(1<<x);
                now=p;
                p=x;
           }
           return s;
       }
       return -1;
}
struct node
{
    int s,p;
};
void bin2str(int s,int p)
{
    for (int i=0;i<len;i++)
    {
        if(i==p) printf(" ");
        else if(s&(1<<i)) printf("R");
        else printf("L");
    }
    printf("n");
}
void bfs()
{
    queue<node>q;
    node z;
    memset(sta,-1,sizeof(sta));
    int i;
    int s,p;
    for (i=0;i<len;i++)
    {
        s=0;p=i;
        int j;
        for(j=0;j<p;j++) s|=(1<<j);
        z.s=s;z.p=p;
        q.push(z);
    //  bin2str(s,p);
        sta\[s\]\[p\]=0;
    }
    while(!q.empty())
    {
        z=q.front();
        q.pop();
        for (i=0;i<len;i++)
        {
              int t=z.p,now=i;
              int x=check(z.s,t,now);
              if(sta\[x\]\[t\]==-1||sta\[z.s\]\[z.p\]+1<sta\[x\]\[t\])
              {
                    node a;
                    sta\[x\]\[t\]=sta\[z.s\]\[z.p\]+1;
                    a.s=x;a.p=t;
                    opp\[x\]\[t\]=z.p; ops\[x\]\[t\]=z.s;anss\[x\]\[t\]=now;
                    q.push(a);
//                  bin2str(x,t);
//                  x=check(x,t,now);
//                  printf("%dn",now);
//                  bin2str(x,t);
              }
        }
    }
}
void solve(int s,int p)
{
     if(sta\[s\]\[p\]==0) 
     {
    //    bin2str(s,p);
        // //if(judge(s,p))printf("11111n");
         return;
     }
//   bin2str(s,p);
     printf("%dn",anss\[s\]\[p\]+1);
     solve(ops\[s\]\[p\],opp\[s\]\[p\]);
}
int main() {
//  freopen("E:\\in.txt","r",stdin);
//  freopen("E:\\out.txt","w",stdout);
    char str\[22\];
    gets(str);
    //printf("%sn",str);
    len=strlen(str);
    int s=0,p;
    for (int i=0;i<len;i++)
    {
          if(str\[i\]==' ') p=i;
          else if(str\[i\]=='R') s|=(1<<i);
    }
//  printf("%d %dn",s,p);
//  int now=8;
//  s=check(s,p,now);
//  bin2str(s,p);
    bfs();
//  printf("%dn",sta\[s\]\[p\]);
    solve(s,p);
    return 0;
}

后来我写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//ROIS_yufan
//BCTF_crypto400
#include "stdio.h"
#include "string.h"
char czInput\[20\];
const int len = 16;
void PrintQueue()
{
    //printf("%sn", czInput);
}
void PrintRst(int rst)
{
    printf("%dn", rst + 1);
}
void ShiftSpace(int iWhere)
{
    int iSpace;
    for (iSpace = 0; iSpace < len; iSpace++)
    {
        if (czInput\[iSpace\] == ' ')
        {
            break;
        }
    }
    if (iSpace < iWhere)
    {
        while (iSpace != iWhere)
        {
            iSpace++;
            PrintRst(iSpace);
            czInput\[iSpace - 1\] = czInput\[iSpace\];
            czInput\[iSpace\] = ' ';
            PrintQueue();
        }
    }
    else if (iSpace > iWhere)
    {
        while (iSpace != iWhere)
        {
            iSpace--;
            PrintRst(iSpace);
            czInput\[iSpace + 1\] = czInput\[iSpace\];
            czInput\[iSpace\] = ' ';
            PrintQueue();
        }
    }
}
void RoolL(int curL)
{
    if (curL > 0)
    {
        ShiftSpace(curL + 1);
    }
    //最左的L特例
    else
    {
        ShiftSpace(curL + 2);
    }
}
void SwapToRight(int iSpace)
{
    //最左的L特例
    if (iSpace == 1)
    {
        iSpace++;
    }
    PrintRst(iSpace - 2);
    czInput\[iSpace\] = czInput\[iSpace - 2\];
    czInput\[iSpace - 2\] = ' ';
    PrintQueue();
}
void main()
{
    gets(czInput);
    int i;
    for (i = len - 1; i >= 0; i--)
    {
        if (czInput\[i\] != 'L')
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (czInput\[j\] == 'L')
                {
                    RoolL(j);
                    SwapToRight(j + 1);
                    i = len;
                    break;
                }
            }
        }
    }
    for (i = 0; i < len; i++)
    {
        if (czInput\[i\] == ' ')
        {
            PrintRst(i + 1);
            break;
        }
    }
}

然后写个脚本玩游戏就好啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#!/usr/bin/env python  
#\-\*\- coding:utf-8 -*-
"""
BCTF_crypto300
ROIS_yufan
"""
import sys
import os
import base64,binascii,zlib
import hashlib
import re, socket
command = 'cudaHashcat64 --custom-charset1 ?l?u?d -m 100 -a 3 "+result+" "+base+"?1?1?1?1"'
def run(result, base):
    f = os.popen("oclHashcat-1.01cudaHashcat64.exe --custom-charset1 ?l?u?d -m 100 -a 3 "+result+" "+base+"?1?1?1?1");
    return f.read()
def getrst(str, result, base):
    partten = re.compile(result + r':('+base+'....'+')')
    return str\[str.find(result)+41:str.find(result)+61\]
def main():
    HOST = '218.2.197.242'    # The remote host
    PORT = 6000              # The same port as used by the server
    s = socket.socket(socket.AF\_INET, socket.SOCK\_STREAM)
    s.connect((HOST, PORT))
    print s.recv(1024)
    strrecv = s.recv(1024)
    print strrecv
\#    strrecv = 'SHA1("5kEQPr0sul1aWUBb" + X).hexdigest() == "952792a53660aac0cc4d9eb1277f9b00d0ebf48c", X is a string of alphanumeric'
    partten = re.compile(r'SHA1("(.*)" ')
    base = partten.findall(strrecv)\[0\]
    partten = re.compile(r'== "(.*)"')
    result = partten.findall(strrecv)\[0\]
    print base
    print result
\#    result = '848656a9e7f76052e8a73d42d17ec02400732e06'
\#    base = 'rVYQ76B4IJdCzy8m'
    rst = getrst(run(result, base), result, base)
    print rst
    s.sendall(rst\[-4:\]+'n')
    print s.recv(1024)
    while(1):
        strrecv = s.recv(1024)
        print repr(strrecv)
        pattern = re.compile(r'\[LR \]+n')
        if not pattern.search(strrecv):
            strrecv = s.recv(1024)
        strrecv = pattern.findall(strrecv)\[0\]
        print strrecv
        f = os.popen("c4.exe "+strrecv.replace(' ', '*'))
        for line in f:
            print repr(line)
            s.sendall(line)
            strrecv = s.recv(1024)
    #        pattern = re.compile(r'\[LR \]+n')
    #        strrecv = pattern.findall(strrecv)\[0\]
            print strrecv
    print s.recv(1024)
\#    while len(strrecv):
\#        input = raw_input()
\#        s.sendall(input+'n')
\#        strrecv = s.recv(1024)
\#        pattern = re.compile(r'\[LR \]+n')
\#        strrecv = pattern.findall(strrecv)\[0\]
\#        print strrecv
    return
if \_\_name\_\_ == '\_\_main\_\_':
    main()