GAE上的microlog这回彻底歇菜了,SAE也欠费停机了,只有wordpress还能不花钱继续用=_=||;
把以前的东西转过来,继续在wp上开坑=v=//
等一下,好像丢了一些文章……不科学……刚才看到
今天,appspot被土番了。这不科学……
题目: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; }
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; } } }
题目: 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真的很不错啊~~~,感觉比SAE自带的wordpress都要强一些,GAE的速度也很给力(这不科学),而且终于有了个现成的SyntaxHighlighter,这样的组合对我这种懒人来说简直再合适不过了。
主要用来放解题报告,备忘,吐槽。
题目: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; }
参考文章:
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