#
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.cppblog.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.cppblog.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.cppblog.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.cppblog.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.cppblog.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.cppblog.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.cppblog.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.cppblog.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.cppblog.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.cppblog.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.cppblog.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;
}