#
2010年03月13日星期六.sgu148.B-station 利用单调性优化dp 思考啊思考
heap + dp
题目描述：给出n层大坝，每层的现有水量，能储水量，炸毁所需的价格，求炸掉最后一层需要花费
的最小费用时的需要炸毁哪些层。
如果第i层被炸毁那么这层的水就会流到下一层，如果大于能储水量，那么这层就也被冲毁。
首先想一个朴素的想法，枚举炸哪一层
for(int i = 1;i <= n;i++) {
int cost = price[i],flow = w[i];
for(int j = i + 1;j <= n;j++) {
flow += w[j];
if(flow <= L[j]) {
cost += price[j];
}
}
if (ans > cost) {
ans = cost;
}
}
显然n = 15000,O(n^2)会超时。
观察到如果第i层被冲开之后，i+1...n中所有能被累计的水冲毁的那么1...i-1都会被自然冲开，
所以不用再被计算。
然后如果现在处理的是i点
如果 sum[i] - sum[idx] - (L[idx] - w[idx]) > 0 其中 sum[i]表示Σw[i...n]
那么 idx就能被累计的水冲开。
由于 - sum[idx] - (L[idx] - w[idx]) 是固定的，所以就可以利用堆来做
注意//!!地方的语句，这道题就是思考。nlogn 47ms
1
2 const int N = 15100;
3 int w[N], L[N], p[N], n;
4 int sum[N];
5
6 struct T {
7 int need, idx;
8 T() {
9 } T(int a, int b) {
10 need = a, idx = b;
11 }
12 };
13
14 bool operator <(T a,T b)
15 { return -a.need < -b.need; }
16 //http://www.cppblog.com/schindlerlee
17 void proc()
18 {
19 int i, j, k;
20 priority_queue < T > que;
21 for (i = n; i >= 1; i--) {
22 sum[i] = sum[i + 1] + w[i];
23 }
24 int ans = maxint, cost = 0, idx;
25 for (i = n; i >= 1; i--) {
26 cost += p[i];
27 while (!que.empty() && sum[i] - que.top().need > 0) { //!!
28 cost -= p[que.top().idx];
29 que.pop();
30 }
31 que.push(T(L[i] - w[i] + sum[i], i)); //!!
32 if (ans > cost) {
33 ans = cost;
34 idx = i;
35 }
36 }
37
38 cost = 0;
39 for (i = idx; i <= n; i++) {
40 cost += w[i];
41 if (cost <= L[i]) {
42 printf("%d\n", i);
43 }
44 }
45 }
46
47 int main()
48 {
49 int i, j, k;
50 scanf("%d", &n);
51 for (i = 1; i <= n; i++) {
52 scanf("%d %d %d", w + i, L + i, p + i);
53 }
54 proc();
55 return 0;
56 }
57
2010年03月13日星期六 Codeforces Beta Round #4 (Div. 2 Only) tutorial
我就是个sb。旁边一堆人dota，我就完全丧失思考能力了。。。。
A:不会的去撞墙
B:贪心，把所有的天都用最短的，然后将剩下的分摊到每天。（某人还说构造来着，我竟然写了个dp。。。）
C:trie or hash,map 会挂。
D:最长上升子序列。先降不能装card的剔除，然后对第一关键字升序，第二关键字降序排列。对
第二关键字求最长上升子序列。 O(n^2)即可。
下面是sgu199，要用nlogn的才行。
http://acm.sgu.ru/problem.php?contest=0&problem=199
经验:比赛时旁边一定不能有玩游戏的，而且千万不要听不在做比赛的sb随便乱讲
2010年03月04日星期四.pku1395 && nwerc2001 Cog-Wheels 动态规划
这个题其实不难，首先将所有可能的比例用二重循环求出来，然后在1~10000范围内做dp，把所有
可能的乘积都求出来，然后再看看最后所求的比例化简之后得到的两个数是否都可达。
1 const int N = 64;
2 const int inf = 1 << 30;
3 int num[N], n, m, qa, qb;
4 const int M = 10010;
5 bool stat[M];
6
7 int gcd(int a, int b)
8 {
9 if (b==0) return a;
10 return gcd(b,a%b);
11 }
12
13 bool judge(int a, int b)
14 {
15 for (int i = 1; i * a < M && i * b < M; i++) {
16 if (stat[i * a] && stat[i * b]) {
17 return true;
18 }
19 }
20 return false;
21 }
22//http://www.cppblog.com/schindlerlee
23 int fac[M],top;
24 void pre()
25 {
26 int i, j, tmp;
27 scanf("%d", &n);
28 for (i = 0; i < n; i++) {
29 scanf("%d", num + i);
30 }
31 top = 0;
32 for (i = 0; i < n; i++) {
33 for (j = 0;j < n;j++) {
34 if (i == j) { continue; }
35 if (num[i] % num[j] == 0) {
36 fac[top++] = num[i] / num[j];
37 }
38 }
39 }
40 stat[1] = 1;
41 for (i = 0; i < top; i++) {
42 for (j = 1; j < M; j++) {
43 if (stat[j]) {
44 tmp = j * fac[i];
45 if (tmp < M) {
46 stat[tmp] = 1;
47 }
48 }
49 }
50 }
51 }
52
53 int main()
54 {
55 int testcase, testid, a, b;
56 scanf("%d", &testcase);
57 for (testid = 1; testid <= testcase; testid++) {
58 pre();
59 scanf("%d", &m);
60 printf("Scenario #%d:\n", testid);
61 while (m--) {
62 scanf("%d%d", &a, &b);
63 int d = gcd(a, b);
64 qa = a / d, qb = b / d;
65 if (judge(qa, qb)) {
66 printf("Gear ratio %d:%d can be realized.\n", a, b);
67 } else {
68 printf("Gear ratio %d:%d cannot be realized.\n", a, b);
69 }
70 }
71 putchar(10);
72 if (testid < testcase) {
73 memset(stat, 0, sizeof(stat));
74 }
75 }
76
77 return 0;
78 }
79
2010年03月04日星期四.sgu249 卡诺图..
这个题是要求生成一个矩阵，要求这个矩阵的元素都只差1bit。
其实学过数字电路设计的应该知道这就是要求生成一个卡诺图。
对横坐标和纵坐标都用gray码，每个格子的值就是 (x << offset) + y
1
2 int cm, cn, m, n;
3 int main()
4 {
5 int i, j;
6 scanf("%d%d", &n, &m);
7 cm = 1 << m;
8 cn = 1 << n;
9 for (i = 0; i < cn;) {
10 for (j = 0; j < cm;) {
11 printf("%d ", (i << m) + j);
12 j ^= 1;
13 printf("%d ", (i << m) + j);
14 j ^= (j ^ (j - 1)) + 1;
15 }
16 i ^= 1;
17 putchar(10);
18 for (j = 0; j < cm;) {
19 printf("%d ", (i << m) + j);
20 j ^= 1;
21 printf("%d ", (i << m) + j);
22 j ^= (j ^ (j - 1)) + 1;
23 }
24 i ^= (i ^ (i - 1)) + 1;
25 putchar(10);
26 }
27 return 0;
28 }
29
摘要: 2010年03月04日星期四.pku1448 && nwerc 2001 cube 超麻烦的搜索pku1448:这题就两个字弓虽给出六个平面，问是不是能拼成一个立方体。每个面有8种状态， 0,90,180,270,然后还有镜面翻转之后同样的四个状态。然后可以选一个当底面，另外5个全排列。复杂度是 5! * 8 ^ 5...如果剪枝不够好的话就会TLE了。。我用的方法是把立方体按照这...
阅读全文
2010年02月28日星期日.sgu149
sgu149:tree dp
这个题想了好久，第一遍代码写的太乱了，然后就重新写了一遍，还好过了。。
思路就是每个点的最长距离有两个来源，一个是子节点，一个是父节点。
字节点的即是深度，这个好求。
如果是来自父节点，那么假定父节点的最长距离已经获得，
如果这个最长距离不是来自当前节点，就可一直接加上父节点到这个节点的边长。
如果这个最长距离恰好来自这个节点，那么可以使用父节点不来自这个节点的最长路来做同样的事情。
1
2 #define pb(x) push_back(x)
3 const int N = 10100;
4 vector<int> g[N];
5 int deep[N],n,far1[N],far2[N],branch[N],vis[N];
6 int out[N];
7
8 void dfs1(int u)
9 {
10 vis[u] = true;
11 int res = 0,idx = 0;
12 for (int i = 0;i < g[u].size();i +=2 ) {
13 int v = g[u][i];
14 int w = g[u][i+1];
15 if (!vis[v]) {
16 dfs1(v);
17 if (res < deep[v] + w) {
18 res = deep[v] + w;
19 idx = v;
20 }
21 }
22 }
23 deep[u] = res;
24 }
25
26 void dfs2(int u,int cost) // u is current // cost from parent
27 {
28 vis[u] = true;
29 branch[u] = 0;
30 far1[u] = cost;
31 far2[u] = 0;
32
33 int i,sz = g[u].size();
34 for (i = 0;i < sz;i += 2) {
35 int v = g[u][i];
36 int w = g[u][i+1];
37 if (vis[v]) { continue; } //!
38 if (far1[u] < deep[v] + w ) {
39 far2[u] = far1[u];
40 far1[u] = deep[v] + w ;
41 branch[u] = v;
42 }else if (far2[u] < deep[v] + w ) {
43 far2[u] = deep[v] + w;
44 }
45 }
46 //http://www.cppblog.com/schindlerlee
47 for (i = 0;i < sz;i += 2) {
48 int v = g[u][i];
49 int w = g[u][i+1];
50 if (vis[v]) { continue; }
51 if (v != branch[u]) {
52 dfs2(v,far1[u] + w);
53 }else {
54 dfs2(v,far2[u] + w);
55 }
56 }
57 }
58
59 int main()
60 {
61 int i,j,k,a,b;
62 scanf("%d",&n);
63 for (i = 2;i <= n;i++) {
64 scanf("%d%d",&a,&b);
65 g[i].pb(a),g[i].pb(b);
66 g[a].pb(i),g[a].pb(b);
67 }
68 dfs1(1);
69 memset(vis,0,sizeof(vis));
70 dfs2(1,0);
71 for ( i = 1; i <= n; i++) {
72 printf("%d\n",far1[i]);
73 }
74
75 return 0;
76 }
77
2010年02月28日星期日.sgu145
sgu145:dfs + 二分
话说这个思路是看别人的思路看来的，我就想A*啥的了，结果才发现是不重复的第k最短路。
没有发现还能这么搞。
二分第k长路的值，然后搜有多少条路的值小于等于k。这样能得到一个第k条最短路的值，然后再搜一次，
把这个值输出出来即可。
关键是这个思路不好想，代码的话，注意搜有多少条路小于等于k时剪枝优化。
1
2 const int N = 128;
3 int src, des, n, m, K, vis[N], cnt, mid;
4 vector < int >g[N];
5 #define pb(x) push_back(x)
6
7 void dfs(int u, int cost)
8 {
9 if (u == des) {
10 if (cost <= mid) {
11 cnt++;
12 }
13 return;
14 }
15
16 int sz = g[u].size();
17 for (int i = 0; i < sz; i += 2) {
18 int v = g[u][i];
19 int w = g[u][i + 1];
20 if (!vis[v] && cost + w <= mid) {
21 vis[v] = true;
22 dfs(v, cost + w);
23 vis[v] = false;
24 }
25 if (cnt >= K) { //pruning
26 return;
27 }
28 }
29 }
30//http://www.cppblog.com/schindlerlee
31 void pathcnt()
32 {
33 memset(vis, 0, sizeof(vis)), cnt = 0;
34 vis[src] = true;
35 dfs(src, 0);
36 }
37
38 int out[N],top,ans;
39 bool dfs2(int u, int cost)
40 {
41 if (u == des) {
42 if (cost == ans) {
43 out[top++] = u;
44 return true;
45 }
46 return false;
47 }
48
49 int sz = g[u].size();
50 for (int i = 0; i < sz; i += 2) {
51 int v = g[u][i];
52 int w = g[u][i + 1];
53 if (!vis[v] && cost + w <= ans) {
54 vis[v] = true;
55 if (dfs2(v, cost + w)) {
56 out[top++] = u;
57 return true;
58 }
59 vis[v] = false;
60 }
61 }
62 return false;
63 }
64
65
66 int main()
67 {
68 int i, j, a, b, c;
69 scanf("%d%d%d", &n, &m, &K);
70 for (i = 0; i < m; i++) {
71 scanf("%d %d %d", &a, &b, &c);
72 g[a].pb(b), g[a].pb(c);
73 g[b].pb(a), g[b].pb(c);
74 }
75
76 scanf("%d%d", &src, &des);
77 int left = 1, right = 1000001;
78 while (left < right) {
79 mid = (left + right) >> 1;
80 pathcnt();
81 if (cnt < K) {
82 left = mid + 1;
83 } else {
84 right = mid;
85 }
86 }
87 ans = left;
88 memset(vis,0,sizeof(vis)), vis[src] = true;
89 assert(dfs2(src,0));
90 printf("%d %d\n",ans,top);
91 for (i = top - 1;i >= 0;i --) {
92 printf("%d ",out[i]);
93 }
94 printf("\n");
95 return 0;
96 }
97
2010年02月23日星期二.sgu269 dp
此题和
220 Little Bishops
221 Big Bishops
基本是一样的，只不过更直接一点
要用高精度加法和乘法，所以我用c++写了个大数，弄了好几次，调了半天精度，
用滚动数组优化才过的。。。还是java大数快啊，
注意要先将输入的n个数排序，然后用递推式
This task is almost same as
220 Little Bishops
221 Big Bishops
But,it is easier than those two.
This task need Big Integer addition and multiplication,I practice writing Bignum in
c++.I changed the static array size several times,and use rolling array to get
Accepted.Due to the brief form of dp,I wrote in java again,that is easier and
quicker...
initial: dp[0][0] = 1;
for(i = 1;i <= n;i++) {
dp[i][0] = dp[i-1][0];
for(j = 1;j <= num[i] && j <= k;j++) {
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (num[i] - j + 1);
}
}
1002871 23.02.10 10:33 schindlerlee 269 .CPP Accepted 868 ms 1191 kb
1002870 23.02.10 10:32 schindlerlee 269 .JAVA Accepted 127 ms 2555 kb
c++代码
1
2 const int N = 256;
3 int n, k, num[N];
4 struct bignum {
5 int s[600], len;
6 bignum() {
7 memset(s, 0, sizeof(s));
8 len = 1, s[0] = 0;
9 } bignum(int a) {
10 memset(s, 0, sizeof(s));
11 len = 0;
12 while (a > 0) {
13 s[len++] = a % 10;
14 a /= 10;
15 }
16 }
17 }
18 //http://www.cppblog.com/schindlerlee
19 pool[2][N], *prev, *next;
20 bignum int2bignum(int a) { return bignum(a); }
21 void pr(bignum a)
22 {
23 if (a.len == 0) {
24 printf("0\n");
25 return;
26 }
27 for (int i = a.len - 1; i >= 0; i--) {
28 printf("%d", a.s[i]);
29 }
30 }
31
32 bignum operator +(bignum a, bignum b)
33 {
34 int len = max(a.len, b.len), i;
35 for (i = 0; i < len; i++) {
36 a.s[i] += b.s[i];
37 }
38 for (i = 0; i < len; i++) {
39 if (a.s[i] >= 10) {
40 a.s[i] -= 10;
41 a.s[i + 1] += 1;
42 }
43 }
44 a.len = len;
45 while (a.s[a.len] > 0) {
46 a.len++;
47 }
48 return a;
49 }
50
51 bignum operator *(bignum a, int b)
52 {
53 int i, shift = 0;
54 for (i = 0; i < a.len; i++) {
55 a.s[i] *= b;
56 }
57 for (i = 0; shift > 0 || i < a.len; i++) {
58 a.s[i] += shift, shift = 0;
59 if (a.s[i] >= 10) {
60 shift = a.s[i] / 10;
61 a.s[i] %= 10;
62 }
63 }
64 a.len = i;
65 assert(a.s[a.len] == 0);
66 return a;
67 }
68
69 int main()
70 {
71 int i, j;
72 scanf("%d%d", &n, &k);
73 for (i = 1; i <= n; i++) {
74 scanf("%d", num + i);
75 }
76 sort(num + 1, num + 1 + n);
77
78 prev = pool[0], next = pool[1];
79 prev[0] = int2bignum(1);
80 for (i = 1; i <= n; i++, swap(prev, next)) {
81 next[0] = prev[0];
82 for (j = 1; j <= num[i] && j <= k; j++) {
83 next[j] = prev[j] + (prev[j - 1] * (num[i] - j + 1));
84 }
85 }
86 pr(prev[k]);
87 putchar(10);
88 return 0;
89 }
java 代码
1 import java.util.*;
2 import java.math.*;
3 import java.io.*;
4 //http://www.cppblog.com/schindlerlee
5 public class Solution {
6 public static void main(String[] args) {
7 Scanner cin = new Scanner(
8 new BufferedReader(
9 new InputStreamReader(System.in)));
10 int i, j, n, k;
11 BigInteger dp[][] = new BigInteger[251][251];
12 int num[] = new int[256];
13 n = cin.nextInt();
14 k = cin.nextInt();
15 for (i = 1; i <= n; i++) {
16 num[i] = cin.nextInt();
17 }
18 for (i = 0; i < 251; i++) {
19 for (j = 0; j < 251; j++) {
20 dp[i][j] = BigInteger.ZERO;
21 }
22 }
23 Arrays.sort(num,1,n+1);
24 dp[0][0] = BigInteger.ONE;
25 for (i = 1; i <= n; i++) {
26 dp[i][0] = dp[i - 1][0];
27 for (j = 1; j <= k && j <= num[i]; j++) {
28 dp[i][j] = dp[i - 1][j].add(dp[i - 1][j - 1].
29 multiply(BigInteger.valueOf(num[i] - j + 1)));
30 }
31 }
32 System.out.println(dp[n][k]);
33 }
34 }
35
2010年02月21日星期日.sgu177 平面四叉树
This is my first problem solving report in English,sorry for my poor English.
sgu177: I know 3 ways to solve this problem.
1.quad tree of plane :this is a good and straight forward solution
2.segment trees covers segment trees :less efficient than quadtree,but easy to implement
3.with the special characteristic of this problem,we can dye the plane with opposite
order of the input,and if one grid is colored it cannot be colored again.
The 1st solution can be used extensively.
Quite a lot of the plane query problem can be solve by it.And it also have more
applications in real, such as 3D game programming,computational geometry.
So if you don't know it,I suggest you look the code below.It will be helpful
Though the solution is quite slow in this problem....
The 3rd solution is very smart,you can look here
http://www.briefdream.com/sgu-177/
for a complete code.
I think the original intention of this problem is to practice quadtree,the memory is
just OK when I used quadtree.
sgu177：就我所知，此题有3中解法。
1.平面四叉树：这是一个平面问题的直觉通解。
2.线段树套树，更好写一点，效率稍差，只是常数级别的差距。
3.倒序染色。从后向前染色，如果一个格子已经被染过色的，那么就不必再被染第二遍。
利用这个性质，可以得到一个聪明的解法。具体代码看这里。
http://www.briefdream.com/sgu-177/
我认为这题的本意就是为了练习一下四叉树，四叉树再平面询问的问题上，可以有非常多的应用。
有些需要很巧妙的思考的问题可以直接用四叉树暴力。
而且四叉树在编码，计算几何，计算机图形学，游戏编程上都有很广泛的应用，有可能的话，我
建议自己实现一下。
本题内存比较紧，int超内存的话，可以用short搞一下。
1
2 const int N = 1001;
3 struct node {
4 short ux, uy, dx, dy;
5 char c;
6 node *pt[4];
7 } pool[N * N * 2], *root;
8
9 int top, n, m;
10 void build(node * root, short ux, short uy, short dx, short dy)
11 {
12 //root->c = 0;
13 root->ux = ux;
14 root->uy = uy;
15 root->dx = dx;
16 root->dy = dy;
17 if (ux == dx && uy == dy) { return; }
18
19 short mx =(ux + dx) >> 1;
20 short my =(uy + dy) >> 1;
21 build(root->pt[0] = &pool[top++], ux, uy, mx, my);
22 if (uy != dy) { build(root->pt[1] = &pool[top++], ux, my + 1, mx, dy); }
23 if (ux != dx) { build(root->pt[2] = &pool[top++], mx + 1, uy, dx, my); }
24 if (ux != dx && uy != dy) {
25 build(root->pt[3] = &pool[top++], mx + 1, my + 1, dx, dy);
26 }
27 }
28
29 char color;
30 int x0,x1,y0,y1;
31 const int NEG = 2;
32 void dye(node * root)
33 {
34 if (root == 0) { return; }
35 if (x0 > root->dx || x1 < root->ux ||
36 y0 > root->dy || y1 < root->uy) { //fast exclude
37 return;
38 }
39 if (x0 <= root->ux && x1 >= root->dx &&
40 y0 <= root->uy && y1 >= root->dy) { //complete cover
41 root->c = color;
42 return;
43 }
44 for (int i = 0;i < 4;i++) { //half cover
45 if (root->pt[i]) {
46 /* I think it is the fatal statement which is used to expand the root color
47 * to the desendants */
48 if (root->c != NEG) {
49 root->pt[i]->c = root->c;
50 }
51 dye(root->pt[i]);
52 }
53 }
54 if (root->c != NEG) {
55 root->c = NEG;
56 }
57 }
58//http://www.cppblog.com/schindlerlee/
59 int statics(node * root)
60 {
61 if (root) {
62 int res = 0;
63 if (root->c == NEG) {
64 for (int i = 0;i < 4;i++) {
65 res += statics(root->pt[i]);
66 }
67 }else if (root->c == 0) {
68 res = (root->dy - root->uy + 1) * (root->dx - root->ux + 1);
69 }
70 return res;
71 }
72 return 0;
73 }
74
75 int main()
76 {
77 int i, j, k, ux,uy,dx,dy;
78 char c;
79 scanf("%d%d", &n, &m);
80 root = &pool[top++], build(root, 1, 1, n, n);
81 while (m--) {
82 scanf("%d %d %d %d %c",&ux,&uy,&dx,&dy,&c);
83 color = (c == 'b');
84 x0 = min(ux,dx), x1 = max(ux,dx);
85 y0 = min(uy,dy), y1 = max(uy,dy);
86 dye(root);
87 }
88 printf("%d\n",statics(root));
89 return 0;
90 }
91
92
2010年02月17日星期三.sgu199nlogn
最长上升子序列
sgu199: 最长上升子序列
题意：两个关键字，求对两个关键字都成立的最长上升子序列。
也就是这个序列的后一个元素的两个关键字都大于前一个的对应元素。
按照第一关键字升序排列，第二关键字降序排列。
然后对这个序列的第二关键字求最长上升子序列，即是答案。
要注意这个序列不能有等于,并且要记录这个生成的序列。
我的这个写法是一般的二分搜索，比较容易。
还有一个比较难理解的二分，看这里
http://acmicpc.org.cn/wiki/index.php?title=SGU_199_Solution
1
2 const int N = 100010;
3 struct L {
4 int v1,v2,idx;
5 }a[N];
6
7 bool cmp(const L &a,const L & b)
8 {
9 if (a.v1 != b.v1) {
10 return a.v1 < b.v1;
11 }
12 return a.v2 > b.v2;
13 }
14 int idx[N],len,n,prev[N];
15 int main()
16 {
17 int i;
18 scanf("%d",&n);
19 for (i = 1;i <= n;i++) {
20 scanf("%d %d",&a[i].v1,&a[i].v2);
21 a[i].idx = i;
22 }
23 sort(a + 1,a + 1 + n,cmp);
24 len = 1, idx[1] = 1;
25 for (i = 2;i <= n;i++) {
26 if (a[i].v2 > a[idx[len]].v2) {
27 len++;
28 idx[len] = i;
29 prev[i] = idx[len - 1];
30 continue;
31 }
32 int L = 1,R = len;
33 while (L < R) {
34 int mid = (L + R) >> 1;
35 if (a[idx[mid]].v2 < a[i].v2) {
36 L = mid + 1;
37 }else {
38 R = mid;
39 }
40 }
41 idx[L] = i;
42 prev[i] = idx[L - 1];
43 }
44
45 printf("%d\n",len);
46 for (i = idx[len];i;i = prev[i]) {
47 printf("%d ",a[i].idx);
48 }
49 putchar(10);
50 return 0;
51 }
2010年02月17日星期三.sgu197 矩阵快乘 + 高精除法 + 状态dp
sgu197:矩阵快乘 + 高精除法 + dp
题目中的m范围如此之小，一看就有问题,很容易想到状态压缩。
两行之间的不同状态表示，可以用矩阵表示两行的状态转移。
矩阵中的元素为1，表示两行状态可达，元素为0 ，表示状态非法，也就是两行状态不可达。
stat[0][0] stat[0][1] stat[0][2] stat[0][3]stat[1][0] 0 1 1 1 stat[1][1] 1 1 1 1 stat[1][2] 1 1 1 1 stat[1][3] 1 1 1 0 如果再在矩阵的右侧乘以一个列向量，每个元素是能到达这个元素所表示状态的染色方法种数，
那么乘得的一个列向量所表示的就是新的能到达新的一行的各种状态的种数。
很容易想到，对于题目中所提到的n，和转移矩阵M,
所求的结果也就是 M^(n-1) 再乘以一个全一的初始状态列向量,再求出所有元素的和即可。
而对于题目中提到的巨大的n，可以使用二分矩阵乘法来处理。
所以最后的复杂度也就是 ，矩阵乘法的复杂度*二分的复杂度。
最大的计算量 = 32 * 32 * 32 * log(10^100) = 3276800,两秒的时间，够了。
1
2 const int M = 32;
3 #define bin(x) (1 <<(x))
4 int n,m,mod,mask;
5 struct Matrix {
6 int m[M][M];
7 Matrix(){memset(m,0,sizeof(m));}
8 Matrix operator = (Matrix b) {
9 for (int i = 0;i <= mask;i++) {
10 for (int j = 0;j <= mask;j++) {
11 m[i][j] = b.m[i][j];
12 }
13 }
14 return *this;
15 }
16 }org,bas,res;
17 Matrix mul(Matrix a,Matrix b)
18 {
19 Matrix c;
20 for (int i = 0;i <= mask;i++) {
21 for (int j = 0;j <= mask;j++) {
22 for (int k = 0;k <= mask;k++) {
23 c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
24 }
25 }
26 }
27 return c;
28 }
29
30 char s[512];
31 int d[512],len;
32 int two[2048],top;
33
34 void div() {
35 int i,j,k,left = 0;
36 for (i = len - 1;i >= 0;i--,left *= 10) {
37 int tmp = d[i] + left;
38 if (tmp < 2) {
39 left = d[i];
40 d[i] = 0;
41 }else {
42 d[i] = tmp / 2;
43 left = tmp % 2;
44 }
45 }
46 while (d[len - 1] == 0 && len > 0) { len--; }
47 }
48
49 void pre()
50 {
51 int i,j,k;
52 len = strlen(s);
53 for (i = 0;i < len;i++) { d[len - 1 - i] = s[i] - '0'; }
54 while (len > 0) {
55 two[top++] = d[0] % 2;
56 div();
57 }
58 mask = bin(m) - 1;
59 for (i = 0;i <= mask;i++) {
60 for (j = 0;j <= mask;j++) {
61 int tmp = i&j;
62 if ((tmp&3) == 3 || (tmp&6) == 6 ||
63 (tmp&12) == 12 || (tmp&24) == 24) { continue; }
64 tmp = (~i & ~j) & mask;
65 if ((tmp&3) == 3 || (tmp&6) == 6 ||
66 (tmp&12) == 12 || (tmp&24) == 24) { continue; }
67 org.m[i][j] = 1;
68 }
69 }
70 }
71 //http://www.cppblog.com/schindlerlee
72 int main()
73 {
74 int i,j,k;
75 scanf("%s %d %d",s,&m,&mod);
76 pre();
77 if (len == 1 && s[0] == '1') {
78 printf("%d\n",bin(m));
79 return 0;
80 }
81 for (i = 0;two[i] == 0;i++);
82 for (two[i] = 0,j = 0;j < i;j++ ) {
83 two[j] = 1;
84 }
85 while (two[top-1] == 0) { top--; }
86
87 bas = org;
88 for (i = 0;i <= mask;i++) { res.m[i][i] = 1; }
89 for (i = 0;i < top;i++) {
90 if (two[i]) {
91 res = mul(res,bas);
92 }
93 bas = mul(bas,bas);
94 }
95 int ans = 0;
96 for (i = 0;i <= mask;i++) {
97 for (j = 0;j <= mask;j++) {
98 ans = (ans + res.m[i][j]) % mod;
99 }
100 }
101 printf("%d\n",ans);
102 return 0;
103 }
104
105
2010年02月13日星期六.sgu174
sgu174:并查集+二叉搜索树
说说题意吧。就是每次给出两个点，这两个点代表一条线段，如果这一条线段能和已经存在的线
段构成一个封闭多边形，那么就输出这是第几条线段。
很自然的能想到并查集，所差的就是为每一个点赋予一个唯一的编号。
如果线性的查找已经处理过的点，那么就每次查询的复杂度就是O(n).
而有n个这样的查询。当n如此大的时候，n^2的算法显然会超时。
我们需要提高每次查询的复杂度。
其实很容易就能想到二叉搜索树。不想写的话可以直接使用stl中的map,map是红黑树的实现，如
果不怕常数复杂度的话，这是一个很好的想法。
还有就是并查集，并查集需要加上路径压缩，不然很容易超时。
1
2 const int N = 400010;
3 struct point_t {
4 int x,y;
5 point_t(){}
6 point_t(int a,int b){x = a,y = b;}
7 }a,b;一bool operator < (point_t a,point_t b)
8 {
9 if (a.x != b.x) {
10 return a.x < b.x;
11 }
12 return a.y < b.y;
13 }
14 map<point_t,int> g;
15 int n, p[N],rank[N];
16
17 int findset(int x)
18 {
19 if (p[x] != x) {
20 p[x] = findset(p[x]);
21 }
22 return p[x];
23 }
24 //http://www.cppblog.com/schindlerlee
25 bool unionset(int x,int y)
26 {
27 x = findset(x);
28 y = findset(y);
29 if (x == y) { return true; }
30 if (rank[x] > rank[y]) {
31 p[y] = x;
32 } else if (rank[x] < rank[y]) {
33 p[x] = y;
34 } else if (rank[x] == rank[y]) {
35 p[x] = y;
36 rank[y]++;
37 }
38 return false;
39 }
40
41 int main()
42 {
43 int i,ia,ib;
44 scanf("%d",&n);
45 for (i = 0;i < N;i++) { p[i] = i; }
46 for (i = 1;i <= n;i++) {
47 scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
48 if ((ia = g[a]) == 0) { ia = g[a] = i << 1; } //from 1
49 if ((ib = g[b]) == 0) { ib = g[b] = (i << 1) + 1; }
50 if (unionset(ia,ib)) {
51 printf("%d\n",i);
52 break;
53 }
54 }
55 if (i > n) {
56 printf("0\n");
57 }
58 return 0;
59 }
60
2010年02月13日星期六.sgu183
sgu183:根据单调性优化的dp
一开始想的挺好，二维状态，第一维是染第i个，第二维表示染了第i-j个。
题目要求要在任何的连续m个球中都有两个染色的，那么边界条件就是
染了第i个，i-m个，和他们中间的某个，这样就能抱枕任何的连续m个球都有两个。
然后写了个dp，华丽丽的tle@test 50 ...
1 const int N = 10010;
2 const int M = 101;
3 const int inf = 1 << 30;
4 int cost[N], n, m;
5 int dp[N][M];
6
7 int main()
8 {
9 int i, j, k;
10 scanf("%d%d", &n, &m);
11 for (i = 1; i <= n; i++) {
12 scanf("%d", cost + i);
13 }
14 for (i = 0; i < N; i++) {
15 for (j = 0; j < M; j++) {
16 dp[i][j] = inf;
17 }
18 }
19 dp[0][0] = 0;
20 for (i = 1; i <= n + 1; i++) {
21 for (j = 0; i - j >= 0 && j <= m; j++) {
22 for (k = 0; i - j - k >= 0 && j + k <= m; k++) {
23 if (dp[i - j][k] < inf) {
24 dp[i][j] = min(dp[i][j], dp[i - j][k] + cost[i]);
25 }
26 }
27 }
28 }
29 int res = inf;
30 for (j = 0; j <= m; j++) {
31 res = min(res, dp[n + 1][j]);
32 }
33 printf("%d\n", res);
34
35 }
这也难怪，复杂度是N * M * M = 10 ^ 9;
然后我就像，可怎么办。我就开始憋。
观察上面的dp可以看出 dp[i][j]是按照从j从小到达的顺序计算的，
而k也是按照从小到达转移的，也就是
dp[i][j] 来自dp[i-j][0],dp[i-j][1]...dp[i-j][i-m]
那么我们就可以让dp[i][j] 保存dp[i][0] ...dp[i][j]的最小值，那么
在后来的转移时用到dp[i][j]当做边界时只需要O(1) 的转移了。总的复杂度就变成了
N*M = 10 ^ 7 ，恩应该没问题了。
更形象话的解释
dp[i-j][0] dp[i-j][1] ... dp[i-j][i-m]
dp[i][j]逐一检查上述的值，选出最小的。
现在dp[i][j] 表示dp[i][0 ... j]中的最小值.
dp[i][j]只要检查检查dp[i-j][i-m] 和 dp[i][j-1]即可。
1
2 const int N = 10010;
3 const int M = 101;
4 const int inf = 1 << 30;
5 int cost[N], n, m;
6 int dp[N][M];
7
8 int main()
9 {
10 int i, j, k;
11 scanf("%d%d", &n, &m);
12 for (i = 1; i <= n; i++) { scanf("%d", cost + i); }
13 for (i = 1; i < N; i++) {
14 for (j = 0; j < M; j++) {
15 dp[i][j] = inf;
16 }
17 }
18 for (j = 0; j < M; j++) { dp[0][j] = 0; }
19 for (i = 1; i <= n + 1; i++) {
20 for (j = 1; i - j >= 0 && j <= m; j++) {
21 int k = (i > m) ? m-j : i-j;
22 if (dp[i-j][k] < inf) {
23 dp[i][j] = dp[i-j][k] + cost[i];
24 }
25 if (dp[i][j] > dp[i][j-1])
26 dp[i][j] = dp[i][j-1];
27 }
28 }
29 printf("%d\n", dp[n+1][m]);
30 }
31
32
2010年02月13日星期六.sgu203 二叉堆
sgu203:堆,根据一个文章生成单词出现次数,求对这个文章进行霍夫曼编码之后的文章长度。
我郁闷，这个题想了半天，想了一个构建二叉树，然后记录叶子节点深度,之后用最大深度减去这
个深度的方法。不过，我自己都觉得这个应该过不了。。。
无意间看了一眼discuss，有一人的代码写了这么两句
a = heap.pop(),b = heap.pop();
ans = ans + a + b;
一拍大腿，原来如此啊，我咋没想到。。。
霍夫曼树选择两个最小的加到新节点上，那么也就等于到这两个小的节点的边就被加到了新节点上。
也就是，随着新节点的继续累计，这个两个节点的权并未丢失。
最后也就是，在拓展霍夫曼树的时候，只要堆大小大于2，就累加最小的两个点的值。
然后更囧的事发生了，我手写的堆超时了。。。。。
我还用这个模板ac过pku3013，那个只能手写堆才能过的dijkstra。
我记得我这个堆的写法是自己想的，当初看过一个stl中的make_heap,pop_heap,push_heap的调用，在
http://support.microsoft.com/kb/157157/zh-cn
其中有几行是这样的
push_heap(Numbers.begin(), Numbers.end()) ;
// you need to call make_heap to re-assert the
// heap property
make_heap(Numbers.begin(), Numbers.end()) ;
现在一看，这几句写错了啊。
push_heap之后再make_heap复杂度就不对了啊。
其实应该是在堆的末尾插入一个元素，沿着这个这个元素不断上翻，达到维护堆的性质的目的,而不是调用
heapify().
可叹阿，到今天才写对第一个push_heap();
1
2
3 const int N = 500100;
4 #define L(x) ((x) << 1)
5 #define R(x) (((x) << 1) + 1)
6 #define P(x) ((x) >> 1)
7
8 LL a[N],res; //a从1开始存储
9 int n;
10
11 void heapify(int x)
12 {
13 int smallest = x,l = L(x),r = R(x);
14 if (l <= n && a[l] < a[smallest]) { smallest = l; }
15 if (r <= n && a[r] < a[smallest]) { smallest = r; }
16 if (smallest != x) {
17 swap(a[smallest],a[x]);
18 heapify(smallest);
19 }
20 }
21
22 LL pop()
23 {
24 swap(a[1],a[n--]);
25 heapify(1);
26 return a[n+1];
27 }
28
29 void make_heap()
30 {
31 for (int i = P(n); i >= 1; i--) {
32 heapify(i);
33 }
34 }
35
36 void push(LL x)
37 {
38 int i = n+1;
39 for (a[++n] = x;i > 1 && a[P(i)] > x; i/= 2) {
40 a[i] = a[P(i)];
41 }
42 a[i] = x;
43 }
44
45 int main()
46 {
47 int i,j,k;
48 scanf("%d",&n);
49 for (i = 1; i < n + 1; i++) {
50 scanf("%I64d",a + i);
51 //cin >> a[i];
52 }
53 make_heap();
54 while (n > 1) {
55 LL a = pop();
56 LL b = pop();
57 res += a + b;
58 push(a + b);
59 }
60 cout << res << endl;
61 return 0;
62 }
63
64
2010年02月11日星期四.sgu155 && pku2201
笛卡尔树的构造。
将所有节点按照k的大小从小到大排序，这样就得到了整棵树的中序遍历结果。
接下来，由于a符合堆的性质，我们只要递归的寻找区间中最大的a，就能构造出整棵树了。寻找
区间最大值，也就是rmq问题，用sparse table或者线段树都可以解决，这样整个算法就完成了。
sparse table 不会的，看这里,传送门:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Sparse_Table_%28ST%29_algorithm
上面有详细的 rmq,lca问题的算法
笛卡尔树在排好序的情况下有O(n)的构造方法，不过我不会...
不过要排序，最好的复杂度都是O(nlogn),时间差不了多少....
1
2 const int N = 50010;
3 int table[24][N],pow2[24];
4 int out[N][3];
5 struct L {
6 int a,k,idx;
7 int left,right,parent;
8 L(){}
9 }data[N];
10 bool cmp(const L& v1,const L& v2) { return v1.k < v2.k; }
11 int n,deep;
12
13 int rmq(int i,int j)
14 {
15 if (j < i) { swap(i,j); }
16 int two = floor(log2(j - i + 1));
17 int idx1 = table[two][i];
18 int idx2 = table[two][j-pow2[two] + 1];
19 if (data[idx1].a < data[idx2].a) {
20 return idx1;
21 }
22 return idx2;
23 }//http://www.cppblog.com/schindlerlee
24 void build_table()
25 {
26 int i,j,k;
27 sort(data,data + n,cmp);
28 for (i = 0;i <= 20;i++) { pow2[i] = 1 << i; }
29 for (i = 0;i < n;i++) {
30 table[0][i] = i;
31 }
32 deep = floor(log2(n));
33 for (i = 1;i <= deep;i++) {
34 for (j = 0;j + pow2[i-1] < n;j++) {
35 if (data[table[i-1][j]].a > data[table[i-1][j+pow2[i-1]]].a) {
36 table[i][j] = table[i-1][j+pow2[i-1]];
37 }else {
38 table[i][j] = table[i-1][j];
39
40 }
41 }
42 }
43 }
44
45 void dfs(int u,int beg,int end)
46 {
47 if (end <= beg) { return; }
48
49 int ux = data[u].idx;
50 if (u-1 >= beg) {
51 int l = rmq(beg,u - 1);
52 int lx = data[l].idx;
53 out[ux][1] = lx;
54 out[lx][0] = ux;
55 dfs(l,beg,u-1);
56 }
57 if (end >= u+1) {
58 int r = rmq(u + 1,end);
59 int rx = data[r].idx;
60 out[ux][2] = rx;
61 out[rx][0] = ux;
62 dfs(r,u+1,end);
63
64 }
65 }
66
67 int main()
68 {
69 int i,j,k;
70 scanf("%d",&n);
71 for (i = 0;i < n;i++) {
72 scanf("%d%d",&data[i].k,&data[i].a);
73 data[i].idx = i + 1;
74 }
75 puts("YES");
76 build_table();//构造rmq用的sparse table
77 dfs(rmq(0,n-1),0,n-1); //递归构造树
78 for (i = 1;i <= n;i++) {
79 printf("%d %d %d\n",out[i][0],out[i][1],out[i][2]);
80 }
81
82 return 0;
83 }
84