#
2010-02-01.ural1061-pku1754
簡單題，按照*分成不同的段，然后在每個段中線性掃描即可。
注意輸出的是有最小值的一段的開始位置。
1
2 const int N = 100100;
3 void ckmin(int &a,int b) { if(a > b) a = b; }
4 int n,k;
5 int s[N],top,res,rl,curl,offset;
6
7 int calc()
8 {
9 if (top < k) { return maxint; }
10 int i,j,cur = maxint,tmp = 0;
11 for (i = 0;i < k-1;i++) {
12 tmp += s[i];
13 }
14 for (i = k-1;i < top;i++) {
15 tmp += s[i];
16 if (tmp < cur) {
17 cur = tmp;
18 curl = i-k+2 + offset;
19 }
20 tmp -= s[i-k+1];
21 }
22 return cur;
23 }
24
25 char buf[N];
26 int main()
27 {
28 int i,j;
29 char t;
30 scanf("%d%d\n",&n,&k);
31 res = maxint;
32 for (i = 0;i < n;i++) {
33 t = getchar();
34 while (t == '\n' || t == '\r') {
35 t = getchar();
36 }
37 buf[i] = t;
38 }
39 buf[i] = '*';
40
41 for (i = 0;i <= n;i++) {
42 t = buf[i];
43 if (t == '*') {
44 int tmp = calc();
45 if (tmp < res) {
46 res = tmp;
47 rl = curl;
48 }
49 offset = i+1;
50 top = 0;
51 }else {
52 s[top++] = t - '0';
53 }
54 }
55 if (res == maxint) {
56 printf("0\n");
57 }else {
58 printf("%d\n",rl);
59 }
60 return 0;
61 }
62
2010年2月1日星期一.sgu152
sgu152:前兩天讀了半天題看不懂,今天看了半天別人的代碼發現是水題,
睡前寫完。
俄羅斯人寫的英語也很難理解嘛。。。
其實就是有幾個百分數，然后讓你分配他們呢的小數和，從而使他們的和是100
且得出數是原來百分數的上取整或者下取整。
1
2 const double eps = 1e-9;
3 const int N = 10100;
4 double sum;
5 double b[N];
6 int a[N],vote[N],n,isInt[N],fac;
7 int dcmp(double x) { return (x > eps) - (x < -eps);}
8 int main()
9 {//http://www.shnenglu.com/schindlerlee
10 int i,j,k;
11 scanf("%d",&n);
12 for (i = 0;i < n;i++) {
13 scanf("%d",vote + i), sum += vote[i];
14 }
15
16 for (i = 0;i < n;i++) {
17 b[i] = 100 * vote[i] / sum;
18 a[i] = (int)b[i];
19 if (dcmp(a[i] - b[i]) == 0) {
20 isInt[i] = true;
21 }
22 }
23 fac = 100;
24 for (i = 0;i < n;i++) { fac -= a[i]; }
25 for (i = 0;i < n;i++) {
26 if (fac && !isInt[i]) {
27 printf("%d ",a[i] + 1), fac--;
28 }else {
29 printf("%d ",a[i]);
30 }
31 }
32 printf("\n");
33 return 0;
34 }
35
2010年1月31日星期日.ural1067-pku1760
算是數據結構類的題吧。
其實不難只不過怪我不該不仔細讀題，然后還看了pku上僅有的兩個發言，
有一哥們說不是絕對路徑，然后我就全理解錯了。
看到
http://www.nocow.cn/index.php/URAL%E9%A2%98%E8%A7%A3
上有題解，不過是pascal的，努力看了看，才發現我理解錯了。。。
其實題目的意思是
給出從根開始的文件夾名字，讓你組建樹結構
注意：如果給出兩個路徑
a\b
b\c
那么結果應該是
a
b
b
c
而不是
a
b
c
我一開始就是這么理解的，然后錯了。。。
一個方法是按照樹的遍歷那么寫，還有一個方法還可以對每個路徑排序，然后遞歸輸出。
還有就是要注意按照字典序輸出。
還有就是pku和ural的編譯器好像都不是很標準的g++
ural的是vc++ 7.0
pku的是MinGW,和vc++ 8.0
我是在linux下用g++-4.4寫的，然后傳上去之后兩個地方全報編譯錯誤。。。
都是string 的 <運算符重載問題。
1
2 #define pb(x) push_back(x)
3 const int N = 512 * 4;
4
5 int n;
6 bool getword(char s[N])
7 {//http://www.shnenglu.com/schindlerlee
8 int i = 0;
9 char t;
10 //t = getchar();
11 scanf("%c", &t);
12 while (t != '\\' && t != '\n') {
13 s[i++] = t;
14 //t = getchar();
15 scanf("%c", &t);
16 }
17 s[i++] = 0;
18 return t == '\n';
19 }
20
21 struct L {
22 string s;
23 vector < L * >next;
24 } *root, pool[N * 10];
25 int sp, top;
26 string str[N];
27
28 bool cmp(L * a, L * b) { return strcmp((a->s).c_str() , (b->s).c_str()) < 0; }
29 void insert(L * root, int idx)
30 {
31 //printf("idx =%d\n",idx);
32 if (idx == sp) return;
33
34 int i, sz = root->next.size();
35 for (i = 0; i < sz; i++) {
36 if (!strcmp(root->next[i]->s.c_str() , str[idx].c_str())) {
37 return insert(root->next[i], idx + 1);
38 }
39 }
40 if (i == sz) {
41 pool[top].s = str[idx];
42 root->next.pb(&pool[top]);
43 insert(&pool[top++], idx + 1);
44 }
45 }
46
47 void dfs(L * root, int margin)
48 {
49 sort(root->next.begin(), root->next.end(), cmp);
50 int i, sz = root->next.size();
51 for (i = 0; i < sz; i++) {
52 int j = margin;
53 while (j--)
54 putchar(' ');
55 cout << (root->next[i]->s.c_str()) << endl;
56 dfs(root->next[i], margin + 1);
57 }
58 }
59
60 char s[N];
61 int main()
62 {
63 root = &pool[top++], root->s = "";
64 int i, j;
65 scanf("%d\n", &n);
66 for (i = 0; i < n; i++) {
67 sp = 0;
68 while (1) {
69 int isend = getword(s);
70 str[sp++] = s;
71 if (isend) break;
72 }
73 insert(root, 0);
74 }
75 dfs(root, 0);
76 return 0;
77 }
78
2010年1月31日星期日.ural1066-pku1759
一道二分的題目
由題目中的遞推式可以很容易的導出
H[i+1] = 2 * H[i] + 2 - H[i-1]
然后我們可以二分枚舉H[2]的值，判斷是否成立，并且更新B值即可。
1
2 const double eps = 1e-8;
3 const int inf = 0x7fffffff;
4 //http://www.shnenglu.com/schindlerlee
5 double B;
6 int n;
7 bool judge(double H1,double H2,int idx)
8 {
9 double H3 = 2*H2+2-H1;
10 if (H3 < 0) { return false; }
11 if(idx == n) {
12 B = min(B,H3);
13 return true;
14 }
15 return judge(H2,H3,idx + 1);
16 }
17
18 int main()
19 {
20 B = inf;
21 double A;
22 int i,j,k;
23 scanf("%d %lf",&n,&A);
24 double left = 0,right = A;
25 while (left + eps < right) {
26 double mid = (left + right) / 2;
27 if(judge(A,mid,3)) {
28 right = mid;
29 }else {
30 left = mid;
31 }
32 }
33 printf("%.2f\n",B);
34 return 0;
35 }
36
37
2010年1月31日星期日.ural1060-pku1753
Neerc2000中的一題。
題目要求:
給出一個4×4的棋盤的黑白狀態，求最少需要多少次翻轉(每次翻轉會改變當前格和周圍四個格的
狀態),使棋盤變成全黑或者全白。
貌似是這套題中最水的一題，分析一下復雜度，發現即使完全枚舉狀態，復雜度也是可以接受的，
然后就枚舉吧。
我的存儲方法是用一個int型表示棋盤狀態，黑1白0,將四行按順序連起來，寫成一個16位整數。
1
2 const int inf = 0x7fffffff;
3 #define bin(x) (1 <<(x))
4 int mask = bin(16) - 1;
5 int addr(const int &x,const int &y)
6 { return x * 4 + y; }
7 int grid;
8 //http://www.shnenglu.com/schindlerlee
9 bool flip(int press)
10 {
11 int g = grid,i;
12 for (i = 0;i < 16;i++) {
13 if(press & bin(i)) {
14 g ^= bin(i);
15 g ^= bin(i + 4);
16 g ^= bin(i - 4);
17 if (i != 3 && i!= 7 && i != 11 && i!= 15) { g ^= bin(i+1); }
18 if (i != 0 && i!= 4 && i != 8 && i!= 12) { g ^= bin(i-1); }
19 }
20 }
21 g &= mask;
22 return (g == 0) || (g == mask);
23 }
24
25 int count(int x)
26 {
27 int res = 0;
28 while(x > 0) {
29 res += x & 1;
30 x >>= 1;
31 }
32 return res;
33 }
34
35 void ckmin(int & res,int x) { if(x < res) res = x; }
36 int main()
37 {
38 char s[16];
39 int i,j;
40 for (i = 0;i < 4;i++) {
41 scanf("%s\n",s);
42 for (j = 0;j < 4;j++) {
43 if(s[j] == 'b') {
44 grid |= bin(addr(i,j));
45 }
46 }
47 }
48
49 int res = inf;
50 for (i = 0;i <= mask;i++) {
51 if (flip(i)) {
52 //printf("i=%d\n",i);
53 ckmin(res,count(i));
54 }
55 }
56 if(res == inf) {
57 printf("Impossible\n");
58 }else {
59 printf("%d\n",res);
60 }
61 return 0;
62 }
63
2010年1月30日星期六.sgu142
sgu142:枚舉
∵ (1)最長的長度是500000
∵ (2)長度為19的串總共可能有524288，
∴ 長度<=19的串中一定有原串沒有出現過的
∴ 枚舉每個長度的串然后找到一個沒有出現的即可
1
2 #define bin(x) (1 << (x))
3 #define L(x) ((x) << 1)
4 const int N = bin(20);
5 int hash[N], n;
6 int str[N], two[32];//http://www.shnenglu.com/schindlerlee/
7 bool find(int len)
8 {
9 int i, j, cur = 0, mask = two[len] - 1;
10 memset(hash, 0, sizeof(int) * two[len]);
11
12 for (i = 0; i < len - 1; i++) { cur = L(cur) + str[i]; }
13 for (i = len - 1; i < n; i++) {
14 cur = (L(cur) + str[i]) & mask;
15 hash[cur] = 1;
16 }
17
18 for (i = 0; i <= mask; i++) {
19 if (hash[i] == 0) {
20 printf("%d\n", len);
21 for (j = len - 1; j >= 0; j--) {
22 if (two[j] & i) {
23 printf("b");
24 } else {
25 printf("a");
26 }
27 }
28 putchar(10);
29 return true;
30 }
31 }
32 return false;
33 }
34
35 int main()
36 {
37 int i;
38 scanf("%d\n", &n);
39 for (i = 0; i <= 22; i++) { two[i] = bin(i); }
40 for (i = 0; i < n; i++) { str[i] = (getchar() == 'b'); }
41
42 for (i = 1;i < 20; i++) {
43 if (find(i)) {
44 break;
45 }
46 }
47 return 0;
48 }
49
50
2010年1月30日星期六.sgu143 樹狀動態規劃
sgu143:Tree DP
題目給出n(1 <= n <= 16 000)個點，n-1條邊，每個點都有一個權值，求最大連通子圖。
由于題目給出的圖邊比點少一個，隨意也就是一棵樹，所以題目所求的也就變成了最大連通子樹。
可以深搜，每個點的的最大連通子樹的權等于這個點的權值+它所有未訪問鄰接點的正權和。
1 const int N = 16100;
2 int n,val[N],vis[N],res;
3 vector<int> g[N];
4 //http://www.shnenglu.com/schindlerlee
5 int dfs(int u)
6 {
7 vis[u] = true;
8 int sz = g[u].size(),i, cur = val[u],tmp;
9 for (i = 0;i < sz;i++) {
10 if (!vis[g[u][i]] && (tmp = dfs(g[u][i])) && tmp > 0) {
11 cur += tmp;
12 }
13 }
14 if(cur > res) { res = cur; }
15 return cur;
16 }
res 初值為-inf,最后res就是結果。
2010年1月27日星期三.sgu136
sgu136:高斯消元的特殊形式
題目給出了一個n邊形每個邊的中點，也就相當于給出了兩組方程。
(+) x0 + x1 = in[0][0](-) x1 + x2 = in[1][0](+) x2 + x3 = in[2][0](-) x3 + x0 = in[3][0](+) y0 + y1 = in[0][1](-) y1 + y2 = in[1][1](+) y2 + y3 = in[2][1](-) y3 + y0 = in[3][1]然后對于這兩組方程，分別按照奇偶關系，直接將四組值奇加偶減
直接求出x0,y0,
然后分別帶入下面的式子挨個計算即可。
1 int main()
2 {
3 int i,j,k;
4 scanf("%d",&n);
5 for (i = 1;i <= n;i++) {
6 scanf("%lf %lf",x + i,y + i);
7 x[i] *= 2;
8 y[i] *= 2;
9 }
10
11 for (i = 1;i <= n;i++) {
12 if(i & 1) {
13 rx[0] += x[i];
14 ry[0] += y[i];
15 }else {
16 rx[0] -= x[i];
17 ry[0] -= y[i];
18 }
19 }
20
21 if (n & 1) {
22 puts("YES");
23 rx[0] /= 2, ry[0] /= 2;
24 for (i = 1;i < n;i++) { rx[i] = x[i] - rx[i-1]; }
25 for (i = 1;i < n;i++) { ry[i] = y[i] - ry[i-1]; }
26 for (i = 0;i < n;i++) {
27 printf("%f %f\n",rx[i],ry[i]);
28 }
29 } else if((n & 1) == 0 && rx[0] == 0 && ry[0] == 0) {
30 puts("YES");
31 for (i = 1;i < n;i++) { rx[i] = x[i] - rx[i-1]; }
32 for (i = 1;i < n;i++) { ry[i] = y[i] - ry[i-1]; }
33 for (i = 0;i < n;i++) {
34 printf("%f %f\n",rx[i],ry[i]);
35 }
36 } else {
37 printf("NO\n");
38 }
39 return 0;
40 }
41
2010年1月28日星期四.sgu137
sgu137:數學推導,模的藝術
輸入兩個數n，m
對于一個序列
A[0...n-1] = 0.....1
B[0...n-1] = 1.....0
如果(B)能由(A)左轉或者右轉形成，那么也就是說，
存在一個元素k，對于每個元素A[i]都有，A[(i+k)%n] = B[i];
由B[0] == 1可以知道，一定有A[k] == 1;
又由于中間的省略號部分元素是相同的。
所以一定有B[k] == 1,繼續推導，也一定有A[(k+k)%n] == 1,當最后推導到A[n-1] == 1時停止。
也就是最后要使 (m * k + 1) % n == 0
然后我們要做的也就是找到這個k即可。
1 const int N = 1024;
2 int n,m,off,a[N];
3 int main()
4 {
5 int i,k;
6 scanf("%d%d",&n,&m);
7 off = m / n;
8 m %= n;
9 for (k = 0;(m * k + 1) % n;k++);
10 for (i = k;m--;(i+= k) %= n) { a[i] = 1; }
11 for (i = 0;i < n;i++) {
12 printf("%d ",a[i] + off);
13 }
14 printf("\n");
15 return 0;
16 }
17
ubuntu 如何配置tty 的分辨率以及支持中文
裝兩個軟件 zhcon startupmanager
然后在startupmanager中修改分辨率，只有4:3的，寬屏的誰知道怎么調，望不吝賜教。
Ctrl-Alt-F1切換到tty
然后啟動 zhcon --utf8
中文顯示OK，中文輸入法OK
看到網上有很多自己手動配置的，我總決的自己配置不好的話，弄起來很麻煩。
裝這兩個軟件的話，至少不會出什么問題了。
sgu138:構造
我太二了，想了一個排序貪心的算法，死活過不了test 8
后來看了別人的程序，才想到，原來可以從另一個方向思考。
可以知道一共會有 sum/2場比賽，
對于每一個人，可以讓他贏到只剩一場，然后輸掉最后一場。
也就是根據題目中要求的輸出方法，選擇一場進行第一列的填充，
剩下最后一個填到第二列。然后繼續選下一個
也就是按照如下方法進行填充。
x_
x_
x_
x_
x_
x_
yx
y_
y_
y_
zy
z_
z_
然后空白的地方，隨便選一個沒用完的填上即可。
1
2 const int N = 128;
3 struct L{
4 int idx,val;
5 }a[N];
6 int n,sum,res[N*N][2];;
7 int cmp(L a,L b) { return a.val > b.val; }
8 void proc() //http://www.shnenglu.com/schindlerlee
9 {
10 int i,times = 0,j;
11 sort(a,a + n,cmp);
12 for (i = 0;i < n && times < sum;i++) {
13 while (a[i].val > 1 && times < sum) {
14 res[times++][0] = a[i].idx;
15 a[i].val--;
16 }
17 if(times < sum) {
18 res[times][1] = a[i].idx;
19 a[i].val--;
20 }
21 }
22
23 int top = 0;
24 while (a[top].val == 0) {
25 top++;
26 }
27 for (i = 0;i < sum;i++) {
28 printf("%d ",res[i][0]);
29 if (res[i][1]) {
30 printf("%d\n",res[i][1]);
31 }else {
32 printf("%d\n",a[top].idx);
33 a[top].val--;
34 if(a[top].val == 0) {top++;}
35 }
36 }
37 }
38 int main()
39 {
40 int i,j,k;
41 scanf("%d",&n);
42 for (i = 0;i < n;i++) {
43 scanf("%d",&a[i].val);
44 a[i].idx = i + 1;
45 sum += a[i].val;
46 }
47 sum /= 2;
48 printf("%d\n",sum);
49 proc();
50 return 0;
51 }
52
摘要: 2010年1月24日星期日.sgu129sgu129:其實不難，求線段在凸多邊形中的長度雖然是基礎計算幾何問題，但是請看題目通過人數:129 Inheritance 357 +在第一頁最前邊，才這么點人過，說明這道題很有點意思。我也看了網上很多人的解題報告，幾乎眾口一辭的說是精度問題，但是...
閱讀全文
2010年1月18日星期一.sgu220 sgu221
sgu220:n*n的棋盤上放k個象 (n <= 10)
終究還不全是自己想出來的，看到一個提示，放在黑格和白格上的象互不相關。
然后我就開始想狀態壓縮dp。。。
注意到
+ + + + + + ++ + + + + + ++ + + + + + ++ + + +如果想對+上邊放車的情況進行dp，可以把黑格變成這樣：
+++++++++++++++++++++++++然后就可以使用放車的方法進行二維dp了。
可惜老夫想歪了，雖然也過了，但是是狀態壓縮的，只能對于這題有用，對sgu221就不行了.
狀態壓縮見代碼:
int c[bin(N)],bsp,wsp;
LL black[N],white[N];
LL dpblack[N][N][bin(N)], cb[N];
LL dpwhite[N][N][bin(N)], cw[N];
//http://www.shnenglu.com/schindlerlee
void preproc()
{
int i;
full = bin(n) - 1;
bsp = wsp = 1;
for (i = 1; i < n; i += 2) {
black[bsp++] = rev(bin(i) - 1) & full;
black[bsp++] = rev(bin(i) - 1) & full;
}
if (i == n) { black[bsp++] = rev(bin(i) - 1) & full; }
for (i = 2; i < n; i += 2) {
white[wsp++] = rev(bin(i) - 1) & full;
white[wsp++] = rev(bin(i) - 1) & full;
}
if (i == n) { white[wsp++] = rev(bin(i) - 1) & full; }
for (i = 1;i <= full;i++) {
int t = i;
while (t > 0) {
c[i] += t & 1;
t >>= 1;
}
}
}
void proc(LL dp[N][N][bin(N)], int terrain[N], int sp,LL res[N])
{
int i, line, s;
dp[0][0][0] = 1;
for (line = 1; line <= sp; line++) {
for (s = 0; s <= full; s++) { dp[line][c[s]][s] += dp[line-1][c[s]][s]; }
for (i = 1; i <= full; i <<= 1) {
if (i & terrain[line]) continue;
for (s = 0; s <= full; s++) {
if(i & s) continue;
dp[line][c[i|s]][i|s] += dp[line-1][c[s]][s];
}
}
}
for (i = 0;i <= k && i <= sp;i++) {
for (s = 0;s <= full;s++) {
res[i] += dp[sp][i][s];
}
}
}
int main()
{
int i;
scanf("%d%d", &n, &k);
preproc();
proc(dpblack, black, bsp-1, cb);
proc(dpwhite, white, wsp-1, cw);
LL res = 0;
for (i = 0;i <= k;i++) {
if(i < bsp && k-i < wsp) // really important
res += cb[i] * cw[k-i];
}
cout << res << endl;
return 0;
}
其實可以發現
如果f(i,j)表示前i行放j個
那么f[i][j] = f[i-1][j] + f[i-1][j-1] * (n(i) - (j-1))
然后程序就變成了這個樣子。。
const int N = 101;
LL fb[N][N],fw[N][N];
LL black[N],white[N];
int wsp,bsp,n,k;
void preproc()
{
int i;
bsp = wsp = 1;
for (i = 1; i < n; i += 2) {
black[bsp++] = i;
black[bsp++] = i;
}
if (i == n) { black[bsp++] = i; }
for (i = 2; i < n; i += 2) {
white[wsp++] = i;
white[wsp++] = i;
}
if (i == n) { white[wsp++] = i; }
bsp--,wsp--;
}
void proc(LL dp[N][N],LL terrain[N],int sp)
{
int i,j;
dp[0][0] = 1;
for (i = 1;i <= sp;i++) {
for (j = 0;j <= terrain[i];j++) {
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (terrain[i] - j + 1);
}
}
}
int main()
{
int i;
scanf("%d%d",&n,&k);
preproc();
proc(fb,black,bsp);
proc(fw,white,wsp);
LL res = 0;
for (i = 0;i <= k;i++) {
res += fb[bsp][i] * fw[wsp][k-i];
}
cout << res << endl;
return 0;
}
sgu221:n*n的棋盤上放k個象 (n <= 50)
這題由于數據量變大了，所以需要高精度的模板，本人是上的java
//http://www.shnenglu.com/schindlerlee/
public class Solution {
static int black[], white[];
static int wsp, bsp, n, k;
static void preproc() {
int i;
bsp = wsp = 1;
for (i = 1; i < n; i += 2) {
black[bsp++] = i;
black[bsp++] = i;
}
if (i == n) {
black[bsp++] = i;
}
for (i = 2; i < n; i += 2) {
white[wsp++] = i;
white[wsp++] = i;
}
if (i == n) {
white[wsp++] = i;
}
bsp--;
wsp--;
}
public static void main(String[] args) {
Scanner cin = new Scanner(
new BufferedReader(
new InputStreamReader(System.in)));
int i, j;
n = cin.nextInt();
k = cin.nextInt();
if(k >= n * 2) {
System.out.println("0");
return;
}
black = new int[456];
white = new int[456];
BigInteger[][] fb = new BigInteger[456][456];
BigInteger[][] fw = new BigInteger[456][456];
preproc();
for (i = 0; i < 456; i++) {
for (j = 0; j < 456; j++) {
fb[i][j] = BigInteger.ZERO;
fw[i][j] = BigInteger.ZERO;
}
}
fb[0][0] = BigInteger.ONE;
for (i = 1; i <= bsp; i++) {
fb[i][0] = BigInteger.ONE;
for (j = 1; j <= black[i]; j++) {
BigInteger tmp = BigInteger.valueOf(black[i] - j + 1);
fb[i][j] = fb[i - 1][j].add(fb[i - 1][j - 1].multiply(tmp));
}
}
fw[0][0] = BigInteger.ONE;
for (i = 1; i <= wsp; i++) {
fw[i][0] = BigInteger.ONE;
for (j = 1; j <= white[i]; j++) {
BigInteger tmp = BigInteger.valueOf(white[i] - j + 1);
fw[i][j] = fw[i - 1][j].add(fw[i - 1][j - 1].multiply(tmp));
}
}
BigInteger res = BigInteger.ZERO;
for (i = 0; i <= k; i++) {
res = res.add(fb[bsp][i].multiply(fw[wsp][k - i]));
}
System.out.println(res);
}
}
2010年1月14日星期四.pku3254 狀態壓縮動態規劃
pku3254:狀態壓縮動態規劃
題目給出了一個m*n(m,n<=12)的矩陣，1代表此點可以放玉米，0代表不可放
求 最后可能的放置方案有多少種?
題目中給出了一個例子
2 3
1 1 1
0 1 0
對于這個例子，放置的方法一共有9種
這個題相對于1185 炮兵陣地來說要好做一些，只要記錄上一行的狀態，就可以了，不用記錄
上上行的狀態。
方法也是先枚舉出一行中的所有可行狀態。
然后根據這些可行狀態按行遞推，中間還要記得判斷狀態是否和地形不沖突。
注意運算符的優先級，按照以下形式寫成的宏定義會比較安全
#define bin(i) (1 << (i))
#define L(i) ((i) << 1)
#define R(i) ((i) >> 1)
const int N = 13;
int f[N][bin(N)];
int full,s[bin(N)],top,m,n,terrain[N];
bool contradict(int x)
{
return x & L(x);
}
bool sameRow(int a,int b)
{
return (a&b);
}
void preproc()
{
int i;
for(i = 0;i <= full;i++) {
if(!contradict(i)) {
s[top++] = i;
}
}
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
full = bin(m) - 1;
preproc();
for (i = 1;i <= n;i++) {
int tmp = 0;
for (j = 1;j <= m;j++) {
scanf("%d",&k);
tmp = L(tmp) + (1 - k);
}
terrain[i] = tmp;
}
f[0][0] = 1;
for(i = 1;i <= n;i++) {
for(j = 0;j < top;j++) {
if(s[j] & terrain[i]) continue;
for(k = 0;k < top;k++) {
if(!sameRow(s[j],s[k])) {
f[i][j] =(f[i][j] + f[i-1][k])%100000000;
}
}
}
}
//http://www.shnenglu.com/schindlerlee
int res = 0;
for(i = 0;i < top;i++) {
res =(res + f[n][i])%100000000;
}
cout << res << endl;
return 0;
}
2010年1月13日星期三.sgu224
k皇后問題的位運算優化
這個是基本上學過編程的人都會寫過的程序。
但是對于這個NP問題，只能搜索解決。如果寫的不好的話很容易超時。
今天在Matrix67的文章中看到了使用位運算的方法，本來我還想用dancing links來
搜一下呢，這個方法太精妙了！
傳送門: http://www.matrix67.com/blog/archives/266
我們知道(x&-x)是求x的最低位1，而這個操作是非常快的。
在這個遞推過程中，只保存當前行的不可行解，然后利用求反和上邊說的求最低位1的方法對當前
行的可行解進行遍歷，然后遞推求解
不過這個不是n皇后問題，是k皇后，所以還需要對算法進行一些小小的改動。
//http://www.shnenglu.com/schindlerlee/
typedef long long LL;
const int N = 16;
int n, k;
#define bin(x) (1 << (x))
#define L(x) ((x) << 1)
#define R(x) ((x) >> 1)
#define low(x) ((x) & -(x))
int res = 0, full;
//row代表列的狀態，ld代表左對角線，rd代表右對角線，cnt是已經使用的皇后數
//line是已經推到了第幾第幾行
void dfs(int row, int ld, int rd, int cnt, int line)
{
int p, t;
if (line < n && cnt < k) {
t = full & ~(row | ld | rd);
while (t != 0) {
p = low(t);
t ^= p;
dfs(row + p, L(ld + p), R(rd + p), cnt + 1, line + 1); //下一行
}
dfs(row, L(ld), R(rd), cnt, line + 1); //此行空
} else if(cnt == k){
res++;
}
}
int main()
{
int i, j;
scanf("%d%d", &n, &k);
full = bin(n) - 1;
dfs(0, 0, 0, 0, 0);
printf("%d\n", res);
return 0;
}