GAE上的microlog这回彻底歇菜了，SAE也欠费停机了，只有wordpress还能不花钱继续用=_=||；
把以前的东西转过来，继续在wp上开坑=v=//
等一下，好像丢了一些文章……不科学……刚才看到
Author Archives: bulletnoid
[FML] 今天，appspot被土番了。
今天，appspot被土番了。这不科学……
ZOJ 3662 Math Magic | The 2012 ACM-ICPC Asia Changchun Regional Contest – H
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3662
LCM的状态一定是M的约数，每次加入的数也是M的约数；
可以压缩LCM的状态到M的约数个； 需要预处理LCM；
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
using namespace std;
#define MOD 1000000007
int N, M, K;
int restore[1010], compress[1010];
int dp[2][1010][110];
int LCM[1010][1010];
int cnt;
int gcd (int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int lcm (int a, int b)
{
return a / gcd(a, b) * b;
}
int main()
{
for (int i = 1; i <= 1000; i++)
for (int j = 1; j <= 1000; j++)
LCM[i][j] = lcm(i, j);
while (scanf("%d%d%d", &N, &M, &K) == 3)
{
memset(compress, -1, sizeof(compress));
memset(restore, -1, sizeof(restore));
cnt = 0;
for (int i = 1; i <= M; i++)
if (M % i == 0)
{
restore[cnt] = i;
compress[i] = cnt++;
}
memset(dp[0], -1, sizeof(dp[0]));
dp[0][0][0] = 1;
for (int i = 1; i <= K; i++)
{
memset(dp[i&1], -1, sizeof(dp[i&1]));
for (int j = i-1; j <= N; j++)
{
for (int k = 0; k < cnt; k++)
{
if (dp[(i+1)&1][j][k] == -1) continue;
for (int r = 0; r < cnt && j+restore[r] <= N; r++)
{
int jj = j + restore[r];
int kk = LCM[ restore[k] ][ restore[r] ];
if (kk <= M && compress[kk] != -1)
{
kk = compress[kk];
if (dp[i&1][jj][kk] == -1) dp[i&1][jj][kk] = 0;
dp[i&1][jj][kk] += dp[(i+1)&1][j][k];
if (dp[i&1][jj][kk] >= MOD) dp[i&1][jj][kk] %= MOD;
}
}
}
}
}
printf("%dn", dp[K&1][N][compress[M]] == -1 ? 0 : dp[K&1][N][compress[M]]);
}
return 0;
}
[备忘] Manacher算法
A simple linear time algorithm for finding longest palindrome sub-string
August 2, 2009 by stone
Given a string S, we are to find the longest sub-string s of S such that the reverse of s is exactly the same as s. First insert a special character ‘#’ between each pair of adjacent characters of S, in front of S and at the back of S. After that, we only need to check palindrome sub-strings of odd length. Let P[i] be the largest integer d such that S[i-d,…,i+d] is a palindrome. We calculate all P[i]s from left to right. When calculating P[i], we have to compare S[i+1] with S[i-1], S[i+2] with S[i-2] and so on. A comparison is successful if two characters are the same, otherwise it is unsuccessful. In fact, we can possibly skip some unnecessary comparisons utilizing the previously calculated P[i]s. Assume P[a]+a=max{ P[j]+j : j= i, then we have P[i] >= min{ P[2*a-i], 2*a-i-(a- P[a])}. Is it the algorithm linear time? The answer is yes. First the overall number of unsuccessful comparisons is obviously at most N. A more careful analysis show that S[i] would never be compared successfully with any S[j](j So the number of overall comparisons is a most 2N.
引入‘#’去除奇、偶分别；
记录之前比较回文串扩展到右端的最大下标 P[a]+a = max{ P[j]+j : j<i }
则 P[i] >= min{ P[2*a-i], 2*a-i-(a- P[a])}
使 P[i] = min{ P[2*a-i], 2*a-i-(a- P[a])} 可去除多余比较，直接进行有用的扩展； 贴代码备忘：
void manacher()
{
int i;
int mx = 0;
int id;
for (i=1; i<n; i++)
{
if ( mx > i )
p[i] = min( p[2*id-i], mx-i );
else
p[i] = 1;
for (; str[i+p[i]] == str[i-p[i]]; p[i]++)
;
if ( p[i] + i > mx )
{
mx = p[i] + i;
id = i;
}
}
}
ZOJ 3664 Split the Rectangle | The 2012 ACM-ICPC Asia Changchun Regional Contest – J
题目： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3664
矩形间的包含关系可以用一棵二叉树来表示（像线段树），最后去掉的矩形是A， B所在的最小矩形的LCA的所有子节点；
对每个矩形存其子节点的个数，每次询问时dfs找到A，B的LCA（第一次搜到的A，B不在一起的矩形），答案就是N-这个LCA的子节点数+1；
这换行略奇葩啊=_=!!
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
using namespace std;
#define MAXN 4010
struct Rectangle {
int xl, yl, xr, yr, l, r, cnt;
}rect[MAXN];
struct Segment {
int xl, yl, xr, yr;
}seg[MAXN];
struct Point {
int x, y;
}A, B;
int N, Q, cnt;
inline bool is_in(int l, int m, int r) {
return (l < m && m < r);
}
int build(Rectangle node, int vertical) {
rect[cnt] = node;
rect[cnt].l = rect[cnt].r = -1;
rect[cnt].cnt = 0;
int res = cnt++;
for (int i = 0; i < N; i++) {
if ( (seg[i].yl == seg[i].yr) ^ vertical) {
if (vertical) {
if (is_in(node.xl, seg[i].xl, node.xr) && seg[i].yl == node.yl && seg[i].yr == node.yr) {
Rectangle tmp = node;
tmp.xr = seg[i].xl;
rect[res].l = build(tmp, vertical^1);
tmp = node;
tmp.xl = seg[i].xl;
rect[res].r = build(tmp, vertical^1);
}
} else {
if (is_in(node.yl, seg[i].yl, node.yr) && seg[i].xl == node.xl && seg[i].xr == node.xr) {
Rectangle tmp = node;
tmp.yr = seg[i].yl;
rect[res].l = build(tmp, vertical^1);
tmp = node;
tmp.yl = seg[i].yl;
rect[res].r = build(tmp, vertical^1);
}
}
}
}
if (rect[res].l == -1 && rect[res].r == -1)
rect[res].cnt = 1;
else {
if (rect[res].l != -1) rect[res].cnt += rect[rect[res].l].cnt;
if (rect[res].r != -1) rect[res].cnt += rect[rect[res].r].cnt;
}
return res;
}
bool is_contain(Rectangle r, Point a) {
return r.xl < a.x && a.x < r.xr && r.yl < a.y && a.y < r.yr;
}
int dfs(Rectangle node) {
if (node.l != -1) {
if (is_contain(rect[node.l], A) && is_contain(rect[node.l], B))
return dfs(rect[node.l]);
}
if (node.r != -1) {
if (is_contain(rect[node.r], A) && is_contain(rect[node.r], B))
return dfs(rect[node.r]);
}
return node.cnt;
}
int main()
{
while (scanf("%d%d%d%d", &rect[0].xl, &rect[0].yl, &rect[0].xr, &rect[0].yr) == 4) {
scanf("%d%d", &N, &Q);
for (int i = 0; i < N ; i++) {
scanf("%d%d%d%d", &seg[i].xl, &seg[i].yl, &seg[i].xr, &seg[i].yr);
if (seg[i].xl > seg[i].xr) swap(seg[i].xl, seg[i].xr);
if (seg[i].yl > seg[i].yr) swap(seg[i].yl, seg[i].yr);
}
cnt = 0;
build(rect[0], 0);
for (int i = 0 ; i < Q; i++) {
scanf("%d%d%d%d", &A.x, &A.y, &B.x, &B.y);
printf ("%dn", N+2-dfs(rect[0]));
}
}
return 0;
}
[开坑] micolog+GAE
micolog真的很不错啊~~~，感觉比SAE自带的wordpress都要强一些，GAE的速度也很给力（这不科学），而且终于有了个现成的SyntaxHighlighter，这样的组合对我这种懒人来说简直再合适不过了。
主要用来放解题报告，备忘，吐槽。
ZOJ 3656 Bit Magic | The 2012 ACM-ICPC Asia Changchun Regional Contest – B
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3656
针对数组A中所有数的的32位分别作satisfaction判定，每位有0-1两种取法，可以看出是2-sat模型；
建图参考：
a AND b = 1 <==> _a->a _b->b a AND b = 0 <==> a->_b b->_a a OR b = 1 <==> _a->b _b->a a OR b = 0 <==> a->_a b->_b a XOR b = 1 <==> _a->b a->_b _b->a b->_a a XOR b = 0 <==> a->b _a->_b b->a _b->_a
六种情况都给用了……
贴代码；SyntaxHighlighter版本略低啊~~~~~~~~
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
using namespace std;
#define MAXN 1010
int b[MAXN][MAXN], g[MAXN][MAXN];
int type[MAXN], stk[MAXN], dfn[MAXN], low[MAXN], depth, top, id;
bool instk[MAXN];
int n;
void build_map(int k)
{
memset(g, 0, sizeof(g));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j) continue;
else if (i % 2 == 1 && j % 2 == 1) {
if (b[i][j] & (1 << k)) {
g[i][j+n] = 1;
g[j][i+n] = 1;
}
else {
g[i+n][i] = 1;
g[j+n][j] = 1;
}
}
else if (i % 2 == 0 && j % 2 == 0) {
if (b[i][j] & (1 << k)) {
g[i][i+n] = 1;
g[j][j+n] = 1;
}
else {
g[j+n][i] = 1;
g[i+n][j] = 1;
}
}
else {
if (b[i][j] & (1 << k)) {
g[i][j+n] = g[j+n][i] = 1;
g[j][i+n] = g[i+n][j] = 1;
}
else {
g[i][j] = g[j][i] = 1;
g[i+n][j+n] = g[j+n][i+n] = 1;
}
}
}
}
void tarjan(int i)
{
dfn[i] = low[i] = ++depth;
stk[++top] = i;
instk[i] = 1;
for (int j = 0; j < n*2; j++) {
if (g[i][j]) {
if (!dfn[j]) {
tarjan(j);
low[i] = min(low[i], low[j]);
}
else {
if (instk[j])
low[i] = min(low[i], dfn[j]);
}
}
}
int j;
if (dfn[i] == low[i]) {
id++;
do {
j = stk[top--];
type[j] = id;
instk[j] = 0;
} while (i != j);
}
}
void solve()
{
for (int i = 0; i < 32; i++)
{
build_map(i);
memset(type, 0, sizeof(type));
memset(stk, 0, sizeof(stk));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(instk, 0, sizeof(instk));
depth = top = id = 0;
for (int j = 0; j < n*2; j++)
if (!dfn[j])
tarjan(j);
for (int i = 0; i < n; i++)
if (type[i] == type[i+n])
{
printf("NOn");
return;
}
}
printf("YESn");
}
int main()
{
while (scanf("%d", &n) == 1) {
memset(type, 0, sizeof(type));
memset(b, 0, sizeof(b));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &b[i][j]);
bool flag = 0;
for (int i = 0; i < n; i++)
if (b[i][i]) {
flag = 1;
break;
}
if (flag) {
printf("NOn");
continue;
}
solve();
}
return 0;
}
Install Xen on Ubuntu 11.10 — 在 Ubuntu11.10 上安装 Xen
参考文章：
http://www.beyondlinux.com/2011/11/02/install-xen-4-1-and-setup-your-cloud-os-on-ubuntu-11-10/
http://bderzhavets.wordpress.com/2011/07/23/build-xen-4-1-1-on-ubuntu-11-10 (GFWed)
ubuntu从11.10开始内核版本号到3了，也从这个版本内核开始重新支持xen了，不必重新编译内核了.
1：准备工作
32位下：因为xen需要开启pae，默认是没有开启的，所以32位ubuntu首先得执行下面这个命令（64位无需此步）：
# sudo apt-get install linux-image-server
bulletnoid 