kk Blog —— 通用基础


date [-d @int|str] [+%s|"+%F %T"]
netstat -ltunp

异或值最大

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=18669

http://acm.sgu.ru/problem.php?contest=0&problem=275

275. To xor or not to xor

time limit per test: 0.5 sec.
memory limit per test: 65536 KB

input: standard
output: standard

The sequence of non-negative integers A1, A2, …, AN is given. You are to find some subsequence Ai1, Ai2, …, Aik(1 <= i1< i2< … < ik<= N) such, that Ai1XOR Ai2XOR … XOR Aikhas a maximum value.

Input

The first line of the input file contains the integer number N (1 <= N <= 100). The second line contains the sequence A1, A2, …, AN (0 <= Ai <= 1018).

Output

Write to the output file a single integer number – the maximum possible value of Ai1XOR Ai2XOR … XOR Aik.

Sample test(s)
Input

3 11 9 5

Output

14

从n个数中选出若干个使得异或的值最大

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

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
priority_queue<__int64> q;
int main() {
	int n;
	__int64 ans, pre, i;
	while (scanf("%d", &n) != EOF) {
	    while (n--) {
	        scanf("%I64d", &i);
	        q.push(i);
	    }
	    ans = 0;
	    pre = 0;
	    while (!q.empty()) {
	        i = q.top();
	        q.pop();
	        if ((pre ^ i) != 0 && (pre ^ i) < pre && (pre ^ i) < i) {
	            q.push(pre ^ i);
	        } else {
	            if ((ans ^ i) > ans) {
	                ans ^= i;
	            }
	            pre = i;
	        }
	    }
	    printf("%I64d\n", ans);
	}
}

二分图匹配, 二分图的最大独立集

POJ 3692 Kindergarten（二分图匹配）
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

Kindergarten
Time Limit: 2000MS           Memory Limit: 65536K
Total Submissions: 3866          Accepted: 1832

Description

In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys know each other. Now the teachers want to pick some kids to play a game, which need that all players know each other. You are to help to find maximum number of kids the teacher can pick.

Input

The input consists of multiple test cases. Each test case starts with a line containing three integers
G, B (1 ≤ G, B ≤ 200) and M (0 ≤ M ≤ G × B), which is the number of girls, the number of boys and
the number of pairs of girl and boy who know each other, respectively.
Each of the following M lines contains two integers X and Y (1 ≤ X≤ G,1 ≤ Y ≤ B), which indicates that girl X and boy Y know each other.
The girls are numbered from 1 to G and the boys are numbered from 1 to B.

The last test case is followed by a line containing three zeros.

Output

For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the maximum number of kids the teacher can pick.

Sample Input

2 3 3
1 1
1 2
2 3
2 3 5
1 1
1 2
2 1
2 2
2 3
0 0 0

Sample Output

Case 1: 3
Case 2: 4

Source
2008 Asia Hefei Regional Contest Online by USTC

幼儿园有g个女孩和b个男孩，同性之间互相认识，而且男孩和女孩之间有的也互相认识。现在要选出来最多的孩子，他们之间都互相认识。

一道基础的二分图最大独立集问题。
二分图的最大独立集 = n-最小覆盖集 = n-完美匹配数。

所以就转化成了二分图匹配，用匈牙利算法实现即可。

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

/*
POJ 3692
反过来建图，建立不认识的图，就变成求最大独立集了。
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

/* **************************************************************************
//二分图匹配（匈牙利算法的DFS实现）
//初始化：g[][]两边顶点的划分情况
//建立g[i][j]表示i->j的有向边就可以了，是左边向右边的匹配
//g没有边相连则初始化为0
//uN是匹配左边的顶点数，vN是匹配右边的顶点数
//调用：res=hungary();输出最大匹配数
//优点：适用于稠密图，DFS找增广路，实现简洁易于理解
//时间复杂度:O(VE)
//***************************************************************************/
//顶点编号从0开始的
const int MAXN=510;
int uN,vN;//u,v数目
int g[MAXN][MAXN];
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)//从左边开始找增广路径
{
	int v;
	for(v=0;v<vN;v++)//这个顶点编号从0开始，若要从1开始需要修改
		if(g[u][v]&&!used[v])
		{
			used[v]=true;
			if(linker[v]==-1||dfs(linker[v]))
			{//找增广路，反向
				linker[v]=u;
				return true;
			}
		}
	return false;//这个不要忘了，经常忘记这句
}
int hungary()
{
	int res=0;
	int u;
	memset(linker,-1,sizeof(linker));
	for(u=0;u<uN;u++)
	{
		memset(used,0,sizeof(used));
		if(dfs(u)) res++;
	}
	return res;
}

int main()
{
	int m;
	int u,v;
	int iCase=0;
	while(scanf("%d%d%d",&uN,&vN,&m)!=EOF)
	{
		iCase++;
		if(uN==0&&vN==0&&m==0)break;
		for(int i=0;i<uN;i++)
			for(int j=0;j<vN;j++)
				g[i][j]=1;
		while(m--)
		{
			scanf("%d%d",&u,&v);
			u--;
			v--;
			g[u][v]=0;
		}
		printf("Case %d: %d\n",iCase,uN+vN-hungary());
	}
	return 0;
}

php基础

php读取标准输入的方式

1
2
3
4
5
6

<?php
$fp = fopen("/dev/stdin", "r");
while($input = fgets($fp)) {
   echo $input;
}
?>

php ‘all’==0

1
2
3

<?php
    var_dump('all'==0);
?>

输出 bool(true)

git建库，配置颜色分支名

建一个库

服务器
1
2
3

mkdir allgit
cd allgit
git --bare init
客户端
1
2
3
4

git clone username@192.168.1.2:/home/abc/allgit allgit
cd allgit
...
git push origin master // 第一次的时候用， 以后直接用 git push

配置颜色分支名

git 配色

/home/username/.gitconfig

1
2
3
4
5
6

[color]
	branch = auto
	status = auto
	diff = auto
	log = auto
	grep = auto
bash 显示分支名

/home/username/.bash_profile 或 /home/username/.bashrc ？

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

function parse_git_branch {
	git branch --no-color 2> /dev/null | sed -e '/^[^*]/d' -e 's/* \(.*\)/(\1)/'
}

function proml {
	local YELLOW="\[\033[01;32m\]"
	local WHITE="\[\033[01;00m\]"
#  local YELLOW="\[\033[0;33m\]"
#  local WHITE="\[\033[1;37m\]"
#  local cyan="\[\033[1;36m\]"
	case $TERM in
		xterm*)
		TITLEBAR='\[\033]0;\u@\h:\w\007\]'
		;;
		*)
		TITLEBAR=""
		;;
	esac
	PS1="${TITLEBAR}\
	$WHITE\u@\h:\w$YELLOW\$(parse_git_branch)\
	$WHITE\$ "
	PS2='> '
	PS4='+ '
}
proml

避免僵死进程

一、两次fork避免僵死进程

如果在一个进程A中启动了一个子进程B，但是B的执行时间可能很长，也可能很短。因此，既不希望A调用wait或者waitpid来等待B的完成（如果B执行时间太长，A的时间就耗费在等待B的完成了，虽然waitpid有WNOHANG选项，但免不了多次调用waitpid来看B是否完成）；也不希望如果B执行时间太短了，然后A又不用wait或waitpid去获取B的退出状态，那么B就一直处于僵死状态直到A终止（这样造成了资源的浪费）。

此时，可以使用一个小trick。就是调用两次fork，让B的父进程变成init进程（pid=1的那个进程，所有孤儿进程的父进程）。这样，A进程可以想干嘛干嘛去，B进程也可以想执行多久就执行多久了。

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

#include <unistd.h>
#include <sys/wait.h>
int main()
{
	pid_t pid;
	if ((pid=fork()) < 0) {
		printf("fork 1 error\n");
		exit(-1);
	} else if(pid==0）{ //第一个子进程
		if ((pid=fork()) < 0) {
			printf("fork 2 error\n");
			exit(-1);
		} else if(pid>0) {
			//第二次fork产生的子进程（第二个子进程）的父进程，其实就是第一次fork产生的子进程（第一个子进程）
			exit(0); //第一个子进程结束，那么它的子进程（第二个子进程）将由init进程领养，init进程成为第二个子进程的父进程
		}
		//第二个子进程（就是我们前面说的B进程）可以做他想做的事情了
		................
	}
	if (waitpid(pid,NULL,0) != pid) //获取第一个子进程的终止状态，不让它变成僵死进程
		printf("waitpid error\n");
	//父进程（就是我们前面说的A进程）也可以做他想做的事情了
	.........
	return 0;
}

二、通过信号机制

子进程退出时向父进程发送SIGCHILD信号，父进程处理SIGCHILD信号。在信号处理函数中调用wait进行处理僵尸进程。测试程序如下所示：

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

#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <stdlib.h>
#include <signal.h>

static void sig_child(int signo)
{
	pid_t pid;
	int stat;
	//处理僵尸进程
	while ((pid = waitpid(-1, &stat, WNOHANG)) >0)
		printf("child %d terminated.\n", pid);
}

int main()
{
	pid_t pid;
	//创建捕捉子进程退出信号
	signal(SIGCHLD, sig_child);
	pid = fork();
	if (pid < 0) {
		perror("fork error:");
		exit(1);
	} else if (pid == 0) {
		printf("I am child process,pid id %d.I am exiting.\n",getpid());
		exit(0);
	}
	printf("I am father process.I will sleep two seconds\n");
	//等待子进程先退出
	sleep(2);
	//输出进程信息
	system("ps -o pid,ppid,state,tty,command");
	printf("father process is exiting.\n");
	return 0;
}

三

父进程可以忽略 SIGCLD 软中断而不必要 wait()。可以这样做到(在支持它的系统上,比如Linux):　

1
2
3
4
5
6
7
8

int main()
{
	signal(SIGCLD, SIG_IGN); /* now I don't have to wait()! */
	.......
	fork();
	fork();
	fork(); /* Rabbits, rabbits, rabbits! */
}