Posted on | In

这是好久前遇到的一道非主流题，当时愣是没弄明白题意。最近闲着没事翻开来看了看，并在网上找到了某大牛写的爬虫，写的真美，顿觉的有必要收藏一下。虽然现在不能完全看懂，但是我想不久的将来，当我想系统的学Python的时候，这肯定是很有用的东西。
Hdoj3337

题目非常短，主要是这句话：

There is only one line in the input. It is a sentence which implies some integer. The length of the sentence is no more than 16. The sentence contains only letters(both uppercase and lowercase), digits, and whitespace. You may assume the given sentence is written in standard English, and always implies exactly one single integer.

意思就是给你一句话，让你写出这句话“imply”的一个数字。。。然而你并不知道imply是什么意思，所以你必须知道他给的这句话是什么，因此解决这道题的标准做法就是通过ＯＪ提供的　AC，WA，TLE，MLE 等提示来对样例进行数据挖掘，具体做法就是类似二分的东西，通过多次提交来确定每一位的字母是什么。

以下是大牛写的程序：

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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
import requests
import time
import sys
status_url = 'http://acm.hdu.edu.cn/status.php'
submit_url = 'http://acm.hdu.edu.cn/submit.php'
login_url = 'http://acm.hdu.edu.cn/userloginex.php'
homepage_url = 'http://acm.hdu.edu.cn/'
language = {}
language['G++'] = 1
language['GCC'] = 2
language['C++'] = 3
language['C'] = 4
language['Pascal'] = 5
language['Java'] = 6
language['C#'] = 7
file_data = []
previous_runid = ''
greater = 'Time Limit Exceeded'
less = 'Output Limit Exceeded'
equal = 'Wrong Answer'
username = 'your username'
userpass = 'your password'
template_input_data = '''
#include <cstdio>
#include <cstdlib>
char buffer[0x10000];//64KB
// Wrong Answer
void equal(void)
{
	printf("www.hoxily.com\n");
	exit(0);
}
// OLE
void less(void)
{
	while (true)
	{
		fwrite(buffer, sizeof(char), sizeof(buffer), stdout);
	}
}
// TLE
void greater(void)
{
	while (true)
	{
	}
}

int main(void)
{
	int ch;
	int count = 0;
	while ((ch = getchar()) != EOF)
	{
		if (ch < 0)
		{
			ch = ch + 256;
		}
		if (count == skip)
		{
			if (ch == guess)
			{
				equal();
			}
			else if (ch < guess)
			{
				less();
			}
			else
			{
				greater();
			}
		}
		count++;
	}
	return 0;
}
'''
template_input_length = '''
#include <cstdio>
#include <cstdlib>
#define MAXLEN 0x7fffffff
#define MINLEN 0
char buffer[0x10000];//64KB
// Wrong Answer
void equal(void)
{
	printf("www.hoxily.com\n");
	exit(0);
}
// OLE
void less(void)
{
	while (true)
	{
		fwrite(buffer, sizeof(char), sizeof(buffer), stdout);
	}
}
// TLE
void greater(void)
{
	while (true)
	{
	}
}

int main(void)
{
	int ch;
	int count = 0;
	while ((ch = getchar()) != EOF)
	{
		count++;
	}
	if (count < guess)
	{
		less();
	}
	else if (count == guess)
	{
		equal();
	}
	else
	{
		greater();
	}
	return 0;
}
'''
cookies = {'exesubmitlang':'0', 'CNZZDATA1254072405': '965477099-1421749361-|1427515514'}
pid = 1000
def login(referer):
    global cookies
    headers = {'referer':referer, 'user-agent':'Mozilla/5.0 (Windows NT 6.3; WOW64; rv:36.0) Gecko/20100101 Firefox/36.0'}
    r = requests.post(login_url, params={'action':'login'}, data={'username':username,'userpass':userpass, 'login':'Sign+In'}, headers = headers, cookies=cookies)
    if r.cookies.get('PHPSESSID') is not None:
        cookies['PHPSESSID'] = r.cookies.get('PHPSESSID')
    #print(repr(cookies))
def test_length_submit(guess):
    usercode = 'int guess = ' + str(guess) + ';rn' + template_input_length
    return test_submit(usercode)
def find_input_length():
    print('GUESS', 'RESULT')
    guess = 1
    left = 0
    while True:
        result = test_length_submit(guess)
        print(guess, result)
        if result == 'lt':
            break
        else:
            left = guess
            guess = guess * 2
    print('LEFT', 'RIGHT', 'GUESS', 'RESULT')
    right = guess
    while left <= right:
        guess = (left + right) // 2
        result = test_length_submit(guess)
        print(left, right, guess, result)
        if result == 'eq':
            print('length =', guess)
            break
        elif result == 'gt':
            left = guess + 1
        elif result == 'lt':
            right = guess - 1
    return guess

def test_submit(usercode):
    global cookies
    headers = {'referer':'http://acm.hdu.edu.cn/showproblem.php?pid=' + str(pid), 'user-agent':'Mozilla/5.0 (Windows NT 6.3; WOW64; rv:36.0) Gecko/20100101 Firefox/36.0'}
    r = requests.get(submit_url, params={'pid':pid}, allow_redirects=False, cookies=cookies, headers=headers)
    if r.cookies.get('PHPSESSID') is not None:
        cookies['PHPSESSID'] = r.cookies.get('PHPSESSID')
    #print(repr(cookies))
    if r.status_code == 302:
        # need login
        login(r.url)
    r = requests.post(submit_url, params={'action':'submit'}, data={'check':0, 'problemid':pid, 'language':language['C++']-1, 'usercode':usercode}, allow_redirects=False, cookies = cookies, headers=headers)
    if r.cookies.get('PHPSESSID') is not None:
        cookies['PHPSESSID'] = r.cookies.get('PHPSESSID')
    #print(repr(cookies))
    # if r.status_code != 302:
        # raise Exception(r)
    # else:
    global previous_runid
    while True:
        time.sleep(1)
        r = requests.get(status_url, params={'user':username, 'lang':0, 'status':0}, headers=headers,cookies=cookies)
        text = r.text
        try:
            index = text.index('tr align=center')
        except ValueError:
            # server is busy so that return something else.
            time.sleep(5)
            continue
        index = text.index('px>', index)
        index += len('px>')
        endIndex = text.index('</td>', index)
        runid = text[index:endIndex]
        if runid == previous_runid: # submit failed
            return test_submit(usercode)
        index = text.index('green>', index)
        index = index + len('green>')
        endIndex = text.index('</font>', index)
        status = text[index: endIndex]
        if 'Queuing' in status:
            continue
        elif 'Compiling' in status:
            continue
        elif 'Running' in status:
            continue
        elif less in status:
            previous_runid = runid
            return 'lt'
        elif greater in status:
            previous_runid = runid
            return 'gt'
        elif equal in status:
            previous_runid = runid
            return 'eq'
        else:
            raise Exception('unknow judge status: ' + status)
def test_data_submit(skip, guess):
    usercode = 'int guess = ' + str(guess) + ';rn'
    usercode = usercode + 'int skip = ' + str(skip) + ';rn'
    usercode = usercode + template_input_data
    return test_submit(usercode)
def find_input_data():
    length = find_input_length()
    print('LEFT', 'RIGHT', 'SKIP', 'GUESS', 'RESULT')
    for skip in range(length):
        left = 0
        right = 255
        while left <= right:
            guess = (left + right) // 2
            result = test_data_submit(skip, guess)
            print(left, right, skip, guess, result)
            if result == 'eq':
                file_data.append(guess)
                print(repr(file_data))
                break
            elif result == 'lt':
                right = guess -1
            elif result == 'gt':
                left = guess + 1
        if left > right:
            file_data.append('UNKNOWN')
    return file_data
if len(sys.argv) == 1:
    print('usage:ndiginput.py <pid> <username> <userpass>')
    sys.exit(1)
else:
    pid = int(sys.argv[1])
    username = sys.argv[2]
    userpass = sys.argv[3]
    find_input_data()

代码的思路也很清楚，就是对每一个字母用二分查找爬出他的值。

执行一下:
myths@myths-X450LD:~/Desktop$ python hdu.py 3337 <用户名> <密码>
等个十几分钟，大概系统提交了１００多发，得到了输出结果：

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
('GUESS', 'RESULT')
(1, 'gt')
(2, 'gt')
(4, 'gt')
(8, 'gt')
(16, 'lt')
('LEFT', 'RIGHT', 'GUESS', 'RESULT')
(8, 16, 12, 'gt')
(13, 16, 14, 'eq')
('length =', 14)
('LEFT', 'RIGHT', 'SKIP', 'GUESS', 'RESULT')
(0, 255, 0, 127, 'lt')
(0, 126, 0, 63, 'gt')
(64, 126, 0, 95, 'lt')
(64, 94, 0, 79, 'gt')
(80, 94, 0, 87, 'lt')
(80, 86, 0, 83, 'gt')
(84, 86, 0, 85, 'lt')
(84, 84, 0, 84, 'eq')
[84]
(0, 255, 1, 127, 'lt')
(0, 126, 1, 63, 'gt')
(64, 126, 1, 95, 'gt')
(96, 126, 1, 111, 'lt')
(96, 110, 1, 103, 'gt')
(104, 110, 1, 107, 'lt')
(104, 106, 1, 105, 'lt')
(104, 104, 1, 104, 'eq')
[84, 104]
(0, 255, 2, 127, 'lt')
(0, 126, 2, 63, 'gt')
(64, 126, 2, 95, 'gt')
(96, 126, 2, 111, 'lt')
(96, 110, 2, 103, 'lt')
(96, 102, 2, 99, 'gt')
(100, 102, 2, 101, 'eq')
[84, 104, 101]
(0, 255, 3, 127, 'lt')
(0, 126, 3, 63, 'lt')
(0, 62, 3, 31, 'gt')
(32, 62, 3, 47, 'lt')
(32, 46, 3, 39, 'lt')
(32, 38, 3, 35, 'lt')
(32, 34, 3, 33, 'lt')
(32, 32, 3, 32, 'eq')
[84, 104, 101, 32]
(0, 255, 4, 127, 'lt')
(0, 126, 4, 63, 'gt')
(64, 126, 4, 95, 'lt')
(64, 94, 4, 79, 'lt')
(64, 78, 4, 71, 'lt')
(64, 70, 4, 67, 'lt')
(64, 66, 4, 65, 'eq')
[84, 104, 101, 32, 65]
(0, 255, 5, 127, 'lt')
(0, 126, 5, 63, 'gt')
(64, 126, 5, 95, 'lt')
(64, 94, 5, 79, 'gt')
(80, 94, 5, 87, 'lt')
(80, 86, 5, 83, 'eq')
[84, 104, 101, 32, 65, 83]
(0, 255, 6, 127, 'lt')
(0, 126, 6, 63, 'gt')
(64, 126, 6, 95, 'lt')
(64, 94, 6, 79, 'lt')
(64, 78, 6, 71, 'lt')
(64, 70, 6, 67, 'eq')
[84, 104, 101, 32, 65, 83, 67]
(0, 255, 7, 127, 'lt')
(0, 126, 7, 63, 'gt')
(64, 126, 7, 95, 'lt')
(64, 94, 7, 79, 'lt')
(64, 78, 7, 71, 'gt')
(72, 78, 7, 75, 'lt')
(72, 74, 7, 73, 'eq')
[84, 104, 101, 32, 65, 83, 67, 73]
(0, 255, 8, 127, 'lt')
(0, 126, 8, 63, 'gt')
(64, 126, 8, 95, 'lt')
(64, 94, 8, 79, 'lt')
(64, 78, 8, 71, 'gt')
(72, 78, 8, 75, 'lt')
(72, 74, 8, 73, 'eq')
[84, 104, 101, 32, 65, 83, 67, 73, 73]
(0, 255, 9, 127, 'lt')
(0, 126, 9, 63, 'lt')
(0, 62, 9, 31, 'gt')
(32, 62, 9, 47, 'lt')
(32, 46, 9, 39, 'lt')
(32, 38, 9, 35, 'lt')
(32, 34, 9, 33, 'lt')
(32, 32, 9, 32, 'eq')
[84, 104, 101, 32, 65, 83, 67, 73, 73, 32]
(0, 255, 10, 127, 'lt')
(0, 126, 10, 63, 'gt')
(64, 126, 10, 95, 'gt')
(96, 126, 10, 111, 'eq')
[84, 104, 101, 32, 65, 83, 67, 73, 73, 32, 111]
(0, 255, 11, 127, 'lt')
(0, 126, 11, 63, 'gt')
(64, 126, 11, 95, 'gt')
(96, 126, 11, 111, 'lt')
(96, 110, 11, 103, 'lt')
(96, 102, 11, 99, 'gt')
(100, 102, 11, 101, 'gt')
(102, 102, 11, 102, 'eq')
[84, 104, 101, 32, 65, 83, 67, 73, 73, 32, 111, 102]
(0, 255, 12, 127, 'lt')
(0, 126, 12, 63, 'lt')
(0, 62, 12, 31, 'gt')
(32, 62, 12, 47, 'lt')
(32, 46, 12, 39, 'lt')
(32, 38, 12, 35, 'lt')
(32, 34, 12, 33, 'lt')
(32, 32, 12, 32, 'eq')
[84, 104, 101, 32, 65, 83, 67, 73, 73, 32, 111, 102, 32]
(0, 255, 13, 127, 'lt')
(0, 126, 13, 63, 'gt')
(64, 126, 13, 95, 'lt')
(64, 94, 13, 79, 'lt')
(64, 78, 13, 71, 'gt')
(72, 78, 13, 75, 'lt')
(72, 74, 13, 73, 'lt')
(72, 72, 13, 72, 'eq')
[84, 104, 101, 32, 65, 83, 67, 73, 73, 32, 111, 102, 32, 72]

最后的一串数字转换为ASCII码就是“The ASCII of H”了。

Posted on | In

很多情况下，想要下载某奇艺某狐的视频的时候，非得需要登陆啊，会员啊才能下载。甚至有的根本不能下载，让人十分头大。而从我们专业的角度看，网页上的视频既然被你看到了，那么实际上就是被你下载（缓存）下来了，所以他禁止你下载其实就是在忽悠你，登陆网页本身就是下载html以及其媒体的过程。因此，让我们揭穿这些视频网站的谎言，愉快的看视频吧～

Windows下路径

C:/Users/Administrator/AppData/Local/Google/Chrome/User Data/Default/Pepper Data/Shockwave Flash/

  1. 由于这个AppData目录是隐藏的，因此首先要在文件夹选项里勾选“显示隐藏的文件”选项。
  2. 找到这个目录，删掉里面的内容，然后打开需要加载的视频网页，在开始缓存视频文件的时候，这个Shockwave Flash文件夹下会出现类似”tmp”名字的文件，随着视频的缓存大小会不断加大，这个就是我们需要的缓存文件了，这里的文件在视频窗口关掉的同时就会被删除，所以别急着关视频窗口哦～等他缓冲好，拷贝出来，扩展名一改（一般的.mp4之类的都可以），直接用播放器就能看了～～

ubuntu下路径

~/.cache/google-chrome/Default/Cache
就是在用户家目录下的这个地方，跟windows有所不同，也是找了好半天的。这个文件夹删了之后好像一时半会不会恢复，所以不要乱删～

在缓存视频的时候也是会不断刷出一些名字类似内存地址名的东西，这就是缓存的视频了。这里的文件在窗口关闭的时候并不会立刻删掉，比较迟钝～最后跟windows一样拷贝下来改个扩展名用播放器直接看了～～

Posted on | In

原版ubuntu 14.04上安装的只支持的打印机版本太老了，新的打印机完全无法支持，之前每次需要打印都需要切换到windows下，甚是麻烦。后来想想，偌大的惠普怎么可能放弃Linux的打印机市场呢？所以最后终于下决心一定要找一个可用的驱动，也是累，终于找到了这个～纪念一下～～

直接上命令：
myths@myths-X450LD:~$ wget http://prdownloads.sourceforge.net/hplip/hplip-3.14.4.run
从 sourceforge 网站上找到的程序源码（其实是费劲千辛万苦百度到的）下载下来是一个可执行文件，会帮你从网上下载需要的部件，接下来给他执行权限，再执行就行了：

myths@myths-X450LD:~$ sudo chmod a+x hplip-3.14.4.run
myths@myths-X450LD:~$ ./hplip-3.14.4.run

当然，实际的下载网页是http://prdownloads.sourceforge.net/hplip/ ，这里应该是惠普官方托管Linux下驱动源码的地方，如果Ubuntu版本更新了，这里也会有更新版本的驱动。

Posted on | In

今天想写个php玩玩的结果突然发现我的apache2突然挂掉了，也不晓得怎么回事，于是就用彻底删除的命令apt-get remove --purge apache2 将他卸载然后重装。重装上去之后发现localhost可以打开了，但是php解析不了了。不光自己写的php无法解析，就连打开phpmyadmin也都变成了源码，十分的蛋疼。找了半天才发现原因是我在彻底卸载apache2的时候，–purge 参数把apache2对php5支持的模块也删掉了。。。。。所以，理所应当的死也登不上喽。

以下是解决方案，非常简单，就是安装那个迷失的模块：
myths@myths-X450LD:/etc/apache2$ sudo apt-get install libapache2-mod-php5
这个提供了apache2对php5支持的接口，有时候好像是在安装php5或者apache2的时候会默认附带的，所以很多情况下并不需要手动的去安装。但是当出了问题的时候，不晓得这个模块的存在可是非常恶心的事。。。

Posted on | In

在使用ssh登陆服务器的时候很蛋疼的事是每次登陆的时候都要输入服务器密码，而且为了安全性，密码一般都不短，大概都得十几位的样子，一不小心输错了还得重来，十分麻烦。所以实现SSH的自动登陆是一件非常方便的事情，避免了恶心蛋疼而且无聊重复的输密码环节。

当然，这种所谓的无密码登陆认证实际上是一种通过公钥加密方法来进行自动化认证的技术。所以这里也存在这公钥和私钥的说法，其中，公钥是保存在服务器中的，而私钥是保存在客户端中的。具体方法如下：

产生密钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
myths@myths-X450LD:~/.ssh$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/home/myths/.ssh/id_rsa): 
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /home/myths/.ssh/id_rsa.
Your public key has been saved in /home/myths/.ssh/id_rsa.pub.
The key fingerprint is:
dc:ee:f5:9d:c9:2d:06:65:a8:ce:ce:65:8d:5d:98:08 myths@myths-X450LD
The key's randomart image is:
+--[ RSA 2048]----+
|                 |
|                 |
|          E  .   |
|       . . ...oo |
|        S ...oo .|
|         .. .+ . |
|         o. =.o  |
|         oo+ .+.+|
|         .+  ..=o|
+-----------------+

这里使用ssh-keygen 命令，-t参数表示接下来跟的是加密类型（type），然后就是加密的算法，可以选择rsa1（老版的rsa），rsa（新版的rsa），dsa，ecdsa，ed25519　等。这里用作证书通常使用rsa算法。

然后会要求你填输出的文件夹，一般默认就摆在/home/myths/.ssh/下的id_rsa文件中吧。不过需要注意的是，如果曾经生成过密钥，现在重新生成一个的话，如果不改地址是会将原来的覆盖掉的，这样可能会惹一些麻烦的。。。

接下来你可以另外设置一个密码，这个密码相当于一个独立的连接服务器的密码，而不是服务器用户的密码。你就是相当于用这个密码来替代服务器的用户密码（这个密码的长度要大于四）。当然如果怕麻烦可以直接回车回车，表示不用这个密码。

到这一步密码就生成完了，在~/.ssh/下就有了生成的文件了：

1
2
myths@myths-X450LD:~/.ssh$ ls 
id_rsa  id_rsa.pub  known_hosts

当然这里的known_hosts 是本来就有的。生产的id_rsa为私钥，id_rsa.pub为公钥。

上传公钥

接下来只要把公钥上传到服务器的对应位置上就可以了，这里用scp上传到/.ssh/authorized_keys中：
`myths@myths-X450LD:/.ssh$ scp id_rsa.pub root@myserver:~/.ssh/authorized_keys`
当然这里这样写是因为我的服务器上并没有别的认证的密码，所以可以直接覆盖这个文件。否则就需要先上传，然后用>>添加到这个文件中了。

最后本地的id_rsa.pub文件删除即可。

关闭密码登录

做到这里，就已经完成了免密码的登陆了。不过，既然已经不用输密码登陆了，那我们就不必留下用密码登陆的这个途径了。那我们就可以直接修改服务器端的配置，使得我们的ssh不接受直接用密码登陆，这样无疑提高了整个服务器的安全性，而又不影响使用。

这个配置文件为/etc/ssh/sshd_config，打开后默认是：

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
# Package generated configuration file
# See the sshd_config(5) manpage for details

# What ports, IPs and protocols we listen for
Port 22
# Use these options to restrict which interfaces/protocols sshd will bind to
#ListenAddress ::
#ListenAddress 0.0.0.0
Protocol 2
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key
#Privilege Separation is turned on for security
UsePrivilegeSeparation yes

# Lifetime and size of ephemeral version 1 server key
KeyRegenerationInterval 3600
ServerKeyBits 1024

# Logging
LogLevel INFO

# Authentication:
LoginGraceTime 120
StrictModes yes

RSAAuthentication yes
PubkeyAuthentication yes
#AuthorizedKeysFile	%h/.ssh/authorized_keys

# Don't read the user's ~/.rhosts and ~/.shosts files
IgnoreRhosts yes
# For this to work you will also need host keys in /etc/ssh_known_hosts
RhostsRSAAuthentication no
# similar for protocol version 2
HostbasedAuthentication no
# Uncomment if you don't trust ~/.ssh/known_hosts for RhostsRSAAuthentication
#IgnoreUserKnownHosts yes

# To enable empty passwords, change to yes (NOT RECOMMENDED)
PermitEmptyPasswords no

# Change to yes to enable challenge-response passwords (beware issues with
# some PAM modules and threads)
ChallengeResponseAuthentication no

# Change to no to disable tunnelled clear text passwords

# Kerberos options
#KerberosAuthentication no
#KerberosGetAFSToken no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes

# GSSAPI options
#GSSAPIAuthentication no
#GSSAPICleanupCredentials yes

X11Forwarding yes
X11DisplayOffset 10
PrintMotd no
PrintLastLog yes
TCPKeepAlive yes
#UseLogin no

#MaxStartups 10:30:60
#Banner /etc/issue.net

# Allow client to pass locale environment variables
AcceptEnv LANG LC_*

Subsystem sftp /usr/lib/openssh/sftp-server

# Set this to 'yes' to enable PAM authentication, account processing,
# and session processing. If this is enabled, PAM authentication will
# be allowed through the ChallengeResponseAuthentication and
# PAM authentication via ChallengeResponseAuthentication may bypass
# If you just want the PAM account and session checks to run without
# and ChallengeResponseAuthentication to 'no'.
UsePAM yes
UseDNS no
AddressFamily inet
PermitRootLogin yes
SyslogFacility AUTHPRIV
PasswordAuthentication yes

这里我们只要关注
PermitRootLogin yes
这一行，把他改成no然后再把ssh重启一下就好了。

如果发现这样配置完之后，仍然不能免密码登录，那多半是因为sshd_config配置里的SAAuthentication yes和ubkeyAuthentication yes这两个选项被注释了，把他们加回来即可。

Last but not least

我一直在想，既然上述的免认证登录这么常见，为什么没有人写个脚本来帮助大家做这件事呢，然后果然在apt的软件包里找到了一个叫sh-copy-id的命令，通过ssh-copy-id user@ip能够非常方便的一次性执行上面的操作。`

Posted on | In

简述

第一次听到fork炸弹这种东西的时候以为是一个很神奇的破坏力惊人的高能脚本，然而稍微深入的了解了一下才发现这个玩意其实是个挺简单纯粹的东西，只是被一个叫Jaromil的家伙对他的精美包装给戏耍了。他在2002年给出了Linux下fork炸弹的最经典的形式：
myths@myths-X450LD:~$ :(){ :|:& };:
一段非常忽悠人的代码，只有１３个字母，乍一看完全看不懂。。但其实这个代码的思路非常简单，就是递归的开一个新的进程，不断的开不断的开，直到操作系统崩溃。中招后唯一的解决办法就是拔电源重启。

作为长期写Ｃ语言的我们来说，看这段代码有一个很大的坎，就是标识符。Ｃ语言里的标识符是不会包含” : “这个东西的，然而这里的函数名恰恰就是这个“ : ”。所谓的fork炸弹，其实就是声明了一个函数，这个函数的名字叫做” : “　他的函数体是调用它本身，并且用管道将他的输出重定向到另一个该函数，并在后台运行。最后调用这个函数。稍微清楚的写法是：

1
2
3
4
bomb(){
	bomb|bomb&
};
bomb

这样就清楚很多了，也就没啥神秘的了。

后果

这段代码执行的后果不用说，就是电脑死机。死机的原因就类似DDoS攻击一样，系统忙于处理这个垃圾程序生成的垃圾进程而无法分配给我们需要执行的程序。所以，一般没事做的话不要跑这个代码（话说我就无聊的跑了两遍）。

其实fork炸弹的危险性倒不是特别大，破坏力也不是特别强，毕竟重启一下就行了。Linux下也有其他拥有更强破坏力的命令，然而为什么都没有他有名呢？原因很简单，fork炸弹的执行不需要root权限！获取root权限实在不容易，而fork炸弹可以完全绕过这一点来对电脑进行破坏，所以这才厉害。

预防

预防fork命令的方法也很清楚，就是限制系统的最大进程数，这样就算运行了也不会死机了，就留给我们杀掉这个进程的机会了。

在这里我们可以通过ulimit命令来查看系统定义的最大进程数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
myths@myths-X450LD:~$ ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 15261
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 15261
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

注意倒数第三行，根据这一行我们就可以看到当前的最大进程数是15261，而且可以看到对应的参数是 -u，这样我们就可以进行修改了：
myths@myths-X450LD:~$ ulimit -u 200
这样下来最大进程数就是200了。

但是这样设置下来的数据只能在当前终端奏效，当关闭当前终端后，系统会重新调回默认值的。

所以最终的解决办法是修改配置文件。系统的配置文件是 /etc/security/limits.conf　：

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
myths@myths-X450LD:~$ cat /etc/security/limits.conf 
# /etc/security/limits.conf
#
#Each line describes a limit for a user in the form:
#
#<domain>        <type>  <item>  <value>
#
#Where:
#<domain> can be:
#        - a user name
#        - a group name, with @group syntax
#        - the wildcard *, for default entry
#        - the wildcard %, can be also used with %group syntax,
#                 for maxlogin limit
#        - NOTE: group and wildcard limits are not applied to root.
#          To apply a limit to the root user, <domain> must be
#          the literal username root.
#
#<type> can have the two values:
#        - "soft" for enforcing the soft limits
#        - "hard" for enforcing hard limits
#
#<item> can be one of the following:
#        - core - limits the core file size (KB)
#        - data - max data size (KB)
#        - fsize - maximum filesize (KB)
#        - memlock - max locked-in-memory address space (KB)
#        - nofile - max number of open files
#        - rss - max resident set size (KB)
#        - stack - max stack size (KB)
#        - cpu - max CPU time (MIN)
#        - nproc - max number of processes
#        - as - address space limit (KB)
#        - maxlogins - max number of logins for this user
#        - maxsyslogins - max number of logins on the system
#        - priority - the priority to run user process with
#        - locks - max number of file locks the user can hold
#        - sigpending - max number of pending signals
#        - msgqueue - max memory used by POSIX message queues (bytes)
#        - nice - max nice priority allowed to raise to values: [-20, 19]
#        - rtprio - max realtime priority
#        - chroot - change root to directory (Debian-specific)
#
#<domain>      <type>  <item>         <value>
#

#*               soft    core            0
#root            hard    core            100000
#*               hard    rss             10000
#@student        hard    nproc           20
#@faculty        soft    nproc           20
#@faculty        hard    nproc           50
#ftp             hard    nproc           0
#ftp             -       chroot          /ftp
#@student        -       maxlogins       4
# End of file

我们发现里面的说明注释还是很全的，照着弄就好了。这里我们一般是添加一句：

1
2
myths soft npro 200
myths hard npro 200

最后保存下文件并且注销下用户，重新登陆回来可以看到配置已经更改。

注：我在这里发现了一个问题，就是在我的ubuntu 14,04 上，用修改配置文件的方法修改后会导致系统崩溃。。原因不明，可能是进程数设置小了吧。

Posted on | In

作为一名C语言助教，最恶心的事情莫过于改作业了，尤其是我们学校这种对输入输出都没有严格要求的题目，不能通过类似OJ的判题系统批量批改的，原则上是只能手动批改的。但是一直做着相同的简单的劳动真的很让人发疯，而作为一名程序员，对待这样的任务很自然就想到了编程。考虑了我现在略懂的语言，对于这种直接和文件达交道的事，我很自然的选择了使用shell脚本。虽然我对shell脚本其实是一窍不通的，然而正巧身边有一本关于这个的书，就花了一个晚上的时间倒腾了一下，有问题了就翻一下资料，差不多把这个小程序弄了个框架。

其实想想，实现的东西也很简单，但是还是花了我不少的功夫。毕竟，这是我写的第一个实用的shell脚本呢。

实现的功能很简单，就是在文件夹下处理一堆的源文件，把编译之后的输出结果与标准答案(146)比较，如果包含标准答案，就判Ａ，当然如果没有加注释，就只能判为Ｂ，如果编译通过了，就判Ｃ／Ｄ，否则判Ｅ。

源码：

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
find . -name "*.cpp">mulu
sort mulu>tmp;
cp tmp mulu
rm tmp
while read line
do
	g++ $line>log
	if [ ! -s log ];then
		touch tmp;
		( ./a.out <tmp )>ans
		(cat ans | egrep "146")>tmp
		if [ -s tmp ];then
			(cat $line|egrep "//")>t1
			(cat $line|egrep "/*")>t2
			if [ -s t1 ] || [ -s t2 ];then
				echo $line is A
			else
				echo $line is B
			fi
			rm t1 t2
		else
			echo $line is C/D
		fi
		rm ans a.out tmp
	else
		echo $line is E
	fi
	rm log
done < mulu
rm mulu

这里涉及到很多的用法，我们只介绍当前用到的，就不去拓展了。

  1. find [地址] -name [正则表达式] 　该命令会搜索[地址]内符合[正则表达式]的文件名，并输出，这里我把输出重定向到mulu文件中。
  2. sort [文件]　命令，就是把文件内容排序并显示出来(不会改变源文件)，这里重定向到tmp。
  3. 重定向命令　> 表示删除写入　>>表示追加写入
  4. cat [文件] | egrep [正则表达式]　表示在[文件]中查找能匹配[正则表达式]的行，并且输出。
  5. [ -s file ]　表示判断file是否存在且非空。

逻辑还是很清楚的，写起来也很简单。

Posted on | In

Linux里文件压缩解压打包神马的还是很有用的，比如要向服务器上传一堆小东西（特别像网站的移植），挨个上传的话会特别特别的慢。这时候用一个打包命令来处理就尤为重要了。实际上这类的命令有很多（比如 cpio命令，lzma命令，gunzip命令，bunzip命令等等），但是最常用的还是今天介绍的tar命令。

首先介绍一些比较常见的用法，就是什么打包，解包，压缩，解压缩这些的一般晓得这些用法就够用了。

打包命令

tar -cvf [生成的文件] [需打包的文件1] [需打包的文件2] [需打包的文件3]...

需要说明的是这里的生成文件一般.tar结尾以让人分辨出这是个包包（特殊目的除外）。

很自然的问题是，这里带了一个-cvf参数，这是什么呢？

其实-cvf并不是一个参数，而是三个参数：

-c [–create]   表示创建新的归档文件（很明显这是很必要的，要不然电脑怎么知道你是要打包还是要解包呢？）

-v [–verbose] 显示命令的执行过程（实际上就显示下包里的文件，不是特别必要，但习惯还是写了）

-f [–file=]  指定备份文件名或设备（当然是必须的，否则怎么知道打包到哪里，这里需要注意的是，f参数后面一定是紧跟这生成的文件名的，即他必须是所有选项的最后一个）

打包基本就是这样了。

压缩命令

需要注意的是，用tar命令打包生成的文件其实只是一个包，数据并没有得到压缩。真正的压缩文件应该是需要一个压缩参数的：

  • 用gzip压缩格式进行压缩：
    tar -zcvf [生成的文件] [需打包的文件1] [需打包的文件2] [需打包的文件3]...
    -z [–gzip, –gunzip, –ungzip]  使用gzip命令处理备份文件（这时候需要注意的就是生成文件最好要以.tar.gz结尾，让人晓得你这是用啥压缩的，人家好用相应的命令解压）

  • 用bzip压缩格式进行压缩：
    tar -jcvf [生成的文件] [需打包的文件1] [需打包的文件2] [需打包的文件3]...
    -j [–I –bzip ]  使用bzip2命令处理备份文件（通常以.tar.bz2结尾）

解包命令

tar -xvf [生成的文件] [包包] 

我们把打包命令的-c参数换成-x参数就可以了。

-x [–extract, –get] 从归档文件中解析文件（用法和-c一致）

解压命令

与两种压缩方式对应的就是两种解压方式喽～

tar -zxvf [生成的文件] [包包] 

tar -jxvf [生成的文件] [包包] 

查看包包的命令

当我们想看看包里有啥却不想解压包包的时候我们可以用-t参数：

tar -tvf [你的包包] 

-t [–list] 列出归档文件内容目录（-t 参数和-c 以及-x 参数是互斥的，前面也可以搭配-z -j之类的压缩参数，这一点视情况而定）

指定解压文件夹

tar命令的解压地址实际上是按照相对路径来的，如果非得用绝对路径的话，需要加上-C参数来指定绝对路径：

tar -zxvf /tmp/etc.tar.gz -C /tmp

以上就是tar命令的基础用法，当然，tar命令还有很多高级用法，不过一般用的比较少了，这里就不详细说了，以后需要用到就去翻文档吧。

Posted on | In

简述

左偏树与二叉堆一样，是一种优先队列的实现。但是与二叉堆不一样，他不是一种完全二叉树，而是一种不平衡二叉树，这样做的目的是为了实现一个重要的性质–合并。通常的二叉堆并不能方便的实现两个堆之间的合并，而左偏树，却恰恰适合解决这样的问题。

实现功能

实现一个最小优先队列，是的插入、删除、合并等操作均在$O(logN)$的时间复杂度内完成。

实现思路

左偏树定义了一种节点叫“外节点”，即这个节点的左子树或者右子树为空。并且定义了一个性质叫“距离”，就是这个节点到他子孙中最近的外节点的距离，如果本身就是外节点，那么距离就是0，为了方便，我们把空节点的距离定义为-1。一个合法的左偏树需要满足对于任意节点，他的左子孙的距离不小于右子孙的距离，即”左偏性质“。当然，他还得有堆性质，即父亲节点的值不能大于子孙节点的值，这样才能保证优先队列的性质。同时，他还具有递归的性质，即左偏树的任意一棵子树也是左偏树。

为什么这样的结构就能实现快速合并呢？这就牵涉到我们”合并“的方法了。

当我们要合并两个左偏树的时候，我们将堆顶元素较大的那棵树与另外一棵树的右子树合并得到新树（维护堆性质），并将新树作为之前那棵树的右子树得到，如果这时右子树的距离大于左子树的距离，那么就要交换这两棵子树并将堆顶的距离重新设置（维护左偏的性质）。这是一个递归的过程，递归的终点就是合并到空节点。

由左偏树的性质可以知道，他的右子树的距离不会大于$O(logN)$，所以合并的复杂度也不会大于$O(logN)$。这就满足了快速合并的要求。

基本模版

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
#include<algorithm>
using namespace std;
const int MAXN = 100000;
struct LeftlistTree{
	int	n,		  //保存节点的个数
		v[MAXN],  //保存节点的值
		l[MAXN],  //保存左儿子的位置
		r[MAXN],  //保存右儿子的位置
		d[MAXN];  //保存节点的距离
	int merge(int x, int y);//将节点x和y的树合并
	int init(int x);        //新建一个单节点的子树，并返回他的堆顶元素的位置
	int insert(int  x, int value);//将权值为value的节点加入编号为x的左偏树中，返回新的堆顶编号
	int top(int x);			//获得堆顶元素，返回权值
	int pop(int x);         //将编号为x的树的堆顶删除
};

int LeftlistTree::merge(int x, int y){
	if (!x)
		return y;
	if (!y)
		return x;
	if (v[x] < v[y])
		swap(x, y);
	r[x] = merge(r[x], y);
	if (d[l[x]] < d[r[x]])
		swap(l[x], r[x]);
	d[x] = d[r[x]] + 1;
	return x;
}

int LeftlistTree::init(int x){
	n++;
	v[n] = x;
	l[n] = r[n] = d[n] = 0;
	return n;
}

int  LeftlistTree::insert(int x, int value){
	return merge(x, init(value));
}
int LeftlistTree::top(int x){
	return v[x];
}
int LeftlistTree::pop(int x){
	return merge(l[x], r[x]);
}

Posted on | In

简述

对于堆，我个人的理解就是一种优先队列，从队列中取元素的时候总是取出最大（或最小）的元素。二叉堆是一种堆的一种实现形式，是一棵完全二叉树。对于二叉堆，我们显然可以分成两类：大根堆和小根堆，表示他每次取出的是最大元素还是最小元素。而大根堆一定是满足这样的一个性质，即：对于任意一个节点，他一定不大于他的父亲，而且不小于他的两个儿子。小根堆反之。

实现功能

以$O(n)$的时间建树，并以$O(logn)$的复杂度实现插入、寻找最小（或最大）值，修改元素，删除元素。

实现思路（小根堆）

我们用一个数组来储存数据，下标从1开始，对于第$i$个元素，他的左儿子为$i2$，他的右儿子为$i2+1$，当然对于非根节点，他的父亲就是$i/2$。在这里，这个数组用$heap[]$表示。

同时，我们用数组$id[i]$数组来表示第(i)个元素是第几个插入的，用$pos[i]$来表示第$i$个元素是第几个插入的（很明显有$id[pos[i]]=i$）。当然，根据实际情况，这两个东西可以不要。

这里要用到的最重要的两个函数是$up(i)$和$down(i)$函数， $up(i)$函数是将第$i$个元素上移，如果他比他的父亲大，就和他的父亲交换位置，即维护他比他父亲小的性质。$down(i)$函数类似，只是比较的是两个儿子中较小的那个。

接下来是算法的核心：

  • 当加入一个元素时，我们把他加入到堆的底部，即heap数组的末尾，然后调用$up(i)$函数将其上移到合适位置。
  • 当修改一个元素时，只要直接修改，然后分别调用$down(i)$函数和$up(i)$函数找到他适合的位置。
  • 当删除堆顶元素的时候，我们只要把他和最后一个元素交换位置（这样只需要将数组大小减一就可以删掉他），然后用$down(i)$函数将堆顶元素下移到合适位置。
  • 当删除任意元素时，只需要把他赋值为负无穷，然后上浮到堆顶，再利用删除堆顶元素的方法删除他。

基本模版

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
#include<algorithm>
using namespace std;
const int MAXSIZE = 100000;
struct Heap{
	int heap[MAXSIZE];//记录堆的元素,下标从1开始
	int n;//堆中元素的个数
	int counter;//加入到堆中的元素的个数（考虑到被删除的元素）
	int id[MAXSIZE];//第i个元素是第几个加入的
	int pos[MAXSIZE];//第i个加入的元素的位置
	Heap();//一个空的Heap
	Heap(int *, int n);//用一个数组初始化Heap,数组下标从0开始
	void push(int v);//添加元素v
	void change(int i, int value);//把第i个加进去的元素修改为value
	void pop();//删掉堆顶
	void erase(int i);//删除第i个加进去的元素
	void up(int i);//将数组中第i个元素上移
	void down(int i);//将数组中第i个元素下移
	int top();//返回堆顶元素
};

Heap::Heap(){
	n = counter = 0;
}

Heap::Heap(int a[], int n){
	n = counter = 0;
	for (int i = 0; i < n; i++){
		heap[++n] = a[i];
		id[n] = pos[n] = n;
	}
	for (int i = n / 2; i >= 1; i--){
		down(i);
	}
}

void Heap::up(int i){
	int x = heap[i], y = id[i];
	for (int j = i / 2; j >= 1; j /= 2){
		if (heap[j]>x){
			heap[i] = heap[j];
			id[i] = id[j];
			pos[id[i]] = i;
			i = j;
		}
		else{
			break;
		}
		heap[i] = x;
		id[i] = y;
		pos[y] = i;
	}
}

void Heap::down(int i){
	int x = heap[i], y = id[i];
	for (int j = i * 2; j <= n; j *= 2){
		if (j<n&&heap[j]>heap[j + 1])
			j++;
		if (heap[j] < x){
			heap[i] = heap[j];
			id[i] = id[j];
			pos[id[i]] = i;
			i = j;
		}
		else{
			break;
		}
		heap[i] = x;
		id[i] = y;
		pos[y] = i;
	}
}

void Heap::push(int v){
	heap[++n] = v;
	id[n] = ++counter;
	pos[counter] = n;
	up(n);
}

int Heap::top(){
	return heap[1];
}

void Heap::pop(){
	swap(heap[1], heap[n]);
	swap(id[1], id[n--]);
	pos[id[1]] = 1;
	down(1);
}

void Heap::change(int i, int value){
	heap[pos[i]] = value;
	down(pos[i]);
	up(pos[i]);
}

void Heap::erase(int i){
	heap[pos[i]] = heap[1] - 1;
	up(pos[i]);
	pop();
}