vim ~/.screenrc,复制上面内容.之后就可以使用Screen了.一些常用命令如下: c-a : Ctrl + a screen -S name #开一个session screen -S name -X quit #杀死session c-a c #创建一个窗口 c-a n #next 窗口 c-a p #previous 窗口 c-a A #为窗口命名 c-a d #detach screen c-a #跳转到number的窗口 screen -ls #查看窗口 screen -r name #连接一个session screen -x name #共享session 可以参考http://hunsefee.diandian.com/post/2010-10-28/7319178
defspiral_number(N): step_x = [0, 1, 0, -1] step_y = [1, 0, -1, 0] a = [[0for j in xrange(N)] for j in xrange(N)] dir = 0 i = 0 j = 0 a[i][j] = 1 n = 2 while n <= N ** 2: x = i + step_x[dir] y = j + step_y[dir] if x >= 0and x < N and y >= 0and y < N and a[x][y] == 0: a[x][y] = n n += 1 i = x j = y else: dir = (dir + 1 + len(step_x)) % len(step_x)
for i in xrange(N): for j in xrange(N): print a[i][j], print
在pythontip上做题时,有这样一道题, 给你一个正整数N(1 <= N <= 10000000),求{1,2,3,…,N}中质数的个数。 如N=3, 输出2. 也就是求N以内质数的个数。 刚开始用以前写的筛法写了一个最初版本,
1 2 3 4 5 6 7 8 9 10 11
N = 10000000 primes = [Truefor i in xrange(N + 1)] primes[0] = primes[1] = False for i in xrange(2, N + 1): ifnot primes[i]: continue n = i * i while n < N + 1: primes[n] = False n += i print len([i for i in xrange(N + 1) if primes[i]])
发现超时,用time模块的clock测试,用了16s.之后一步一步优化,先将len([i for i in xrange(N + 1) if primes[i]])这句改成primes.count(True)时间缩短到14s,之后看了讨论组里的讨论,将
1 2 3 4
n = i * i while n < N + 1: primes[n] = False n += i
这部分改成
1
primes[i * i:N + 1:i] = [False] * ((N - i * i) / i + 1)
时间没有明显的变化,因为看到[False] ((N - i i) / i + 1),于是将[True for i in xrange(N + 1)] 这行改成[True] * (N + 1) ,速度明显加快,只用了4s,经过这样优化后,程序变成了
1 2 3 4 5 6 7 8
N = 10000000 primes = [True] * (N + 1) primes[0] = primes[1] = False for i in xrange(2, N + 1): ifnot primes[i]: continue primes[i * i:N + 1:i] = [False] * ((N - i * i) / i + 1) print primes.count(True)
之后想办法将for循环去掉。于是将它改成
1 2 3 4 5
i = 2 while i * i <= N: if primes[i]: primes[i * i:N + 1:i] = [False] * ((N - i * i) / i + 1) i += 1
最终为
1 2 3 4 5 6 7 8 9
N = 10000000 primes = [True] * (N + 1) primes[0] = primes[1] = False i = 2 while i * i <= N: if primes[i]: primes[i * i:N + 1:i] = [False] * ((N - i * i) / i + 1) i += 1 print primes.count(True)
defgetPrimes(n): primes = [True] * (n + 1) primes[0] = primes[1] = False i = 2 while i * i <= n: if primes[i]: primes[i * i:n + 1:i] = [False] * ((n - i * i) / i + 1) i += 1 return [i for i in xrange(n + 1) if primes[i]]
想了一会之后,找到了一个转化为最大连续子序列的办法。也就是先对列求和,之后再用最大连续子序列的方法。给出这个办法后,还想考虑优化,只是一直想不出来。回来之后,想起编程之美上有类似的题目,看了之后,没想到已经是最优的了。又想起以前在POJ应该做过类似的题目,于是找到了POJ1050- To The Max. 编写代码如下:
#include<stdio.h> #include<stdlib.h> #define N 100 int a[N][N]; int b[N]; intmax_sub_array(int *a, int n){ int max_sum = a[0]; int sum = a[0]; for (int i = 1; i < n; i++) { if (sum < 0) { sum = 0; } sum += a[i]; if (sum > max_sum) { max_sum = sum; } } return max_sum; } intmain(){ int n; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &a[i][j]); } } int max_sum = -127 * 100 * 100; for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { b[k] = 0; } for (int j = i; j < n; j++) { for (int k = 0; k < n; k++) { b[k] += a[j][k]; } int sum = max_sub_array(b, n); if (sum > max_sum) { max_sum = sum; } } } printf("%d\n", max_sum); return0; }
Trie又称为前缀树或字典树,它有许多重要用途,如搜索提示,以及作为AC自动机的基础。POJ2001-最短前缀这题是Trie的基础应用。 Description A prefix of a string is a substring starting at the beginning of the given string. The prefixes of “carbon” are: “c”, “ca”, “car”, “carb”, “carbo”, and “carbon”. Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, “carbohydrate” is commonly abbreviated by “carb”. In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.
In the sample input below, “carbohydrate” can be abbreviated to “carboh”, but it cannot be abbreviated to “carbo” (or anything shorter) because there are other words in the list that begin with “carbo”.
An exact match will override a prefix match. For example, the prefix “car” matches the given word “car” exactly. Therefore, it is understood without ambiguity that “car” is an abbreviation for “car” , not for “carriage” or any of the other words in the list that begins with “car”. Input The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters. Output The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word. Sample Input carbohydrate cart carburetor caramel caribou carbonic cartilage carbon carriage carton car carbonate Sample Output carbohydrate carboh cart cart carburetor carbu caramel cara caribou cari carbonic carboni cartilage carti carbon carbon carriage carr carton carto car car carbonate carbona 描述 一个字符串的前缀是从头开始的字符串的子串。”carbon”的前缀有:”c”,”ca”,”car”,”carb”,”carbo”和”carbon”.注意在这个问题中空串不认为是前缀,但是每个非空字符串自身可以认为是一个前缀。在日常用于中,我们倾向于用前缀来缩写词。例如,“carbohydrate”常缩写成”carb”.在这个问题中,我们给出一系列单词,要求能够唯一标识单词的最短前缀。
#include<stdio.h> #include<stdlib.h> voidswap(int &a, int &b){ int temp = a; a = b; b = temp; } voidadjust_heap(int *a, int cur, int n){ int left, right; while (true) { left = 2 * cur + 1; right = 2 * cur + 2; int index = cur; if (left < n && a[left] > a[index]) { index = left; } if (right < n && a[right] > a[index]) { index = right; } if (index != cur) { swap(a[cur], a[index]); cur = index; } else { break; } } } voidbuild_heap(int *a, int n){ for (int i = (n - 1) / 2; i >= 0; i--) { adjust_heap(a, i, n); } } voidheap_sort(int *a, int n){ build_heap(a, n); for (int i = n - 1; i > 0; i--) { swap(a[0], a[i]); adjust_heap(a, 0, i); } } intmain(){ int n, k, num; while(scanf("%d %d", &n, &k) != EOF) { int *a = newint[k]; for (int i = 0; i < n; i++) { scanf("%d", &num); if (i <= k - 1) { a[i] = num; if (i == k - 1) { build_heap(a, k); } } else { if (a[0] > num) { swap(a[0], num); adjust_heap(a, 0, k); } } } heap_sort(a, k); for (int i = 0; i < k - 1; i++) { printf("%d ", a[i]); } printf("%d\n", a[k - 1]); delete[] a; } return0; }
#include<stdio.h> #include<stdlib.h> voidswap(int &a, int &b){ int temp = a; a = b; b = temp; } voidadjust_heap(int *a, int cur, int n){ int left, right; while (true) { left = 2 * cur + 1; right = 2 * cur + 2; int index = cur; if (left < n && a[left] > a[index]) { index = left; } if (right < n && a[right] > a[index]) { index = right; } if (index != cur) { swap(a[cur], a[index]); cur = index; } else { break; } } } voidbuild_heap(int *a, int n){ for (int i = (n - 1) / 2; i >= 0; i--) { adjust_heap(a, i, n); } } voidheap_sort(int *a, int n){ build_heap(a, n); for (int i = n - 1; i > 0; i--) { swap(a[0], a[i]); adjust_heap(a, 0, i); } } intmain(){ int a[] = {10, 2, 5, 7, 6, 13 , 8, 7}; int n = sizeof(a) / sizeof(int); heap_sort(a, n); for (int i = 0; i < n - 1; i++) { printf("%d ", a[i]); } printf("%d\n", a[n - 1]); return0; }
There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.
You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.
input: The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.
output: For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.
你所在的大学有n个学生(0 < n <= 50000).问遍所有学生的宗教信仰是不实际的。并且,一些学生对于表达他们的信仰会觉得不舒服。一个避免这些问题的解决办法是问m(0 <= m <= n(n-1)/2)对学生,他们是否属于同一个宗教(也就是他们同时出现在相同的教堂).从这些数据里,你不能知道每一个人的信仰,但是可以知道校园里宗教数量的一个上界。你可以假设一个学生至多属于一个宗教。
输入: 输入中包含一些测试用例。每个例子由一行包含整数n和m开始。接下来的m行由两个整数i和j组成,i和j属于同一个宗教.学生从1到n编号.输入的结束由一行n = m = 0标示.