C++博客-学习心得（code）

Clang 宏定义初探（二）

superlong — Thu, 10 Mar 2016 17:20:00 GMT

Clang 宏定义初探（二）

本篇总结下这几天看的宏的一些看到的用法。

1、参数粘结

这是一个类似 shell 之类的脚本语言的特性，可以利用这个特性完成一些重复度比较高的编码的简化。
例如，对proc文件系统进行绑定的时候，需要在/proc/test/目录下，简历3个文件接口，test1、test2、test3.
可以这样写

#define BIND(x) test##x->read_proc=test##x##_read

在使用的时候，就可以

BIND(1); //展开为test1->read_proc=test1_read;
BIND(2); //展开为test2->read_proc=test2_read;

不管是从语义还是编码复杂度，都降低了。

2、参数字符化

在使用单个 # 号，作为函数式宏的参数前缀时，可以让宏的内容变成字符串，比如说：

#define print(x) do{\
printf(#x);\
printf("=%d\n",x);\
}while(0)

使用的时候，直接写：

int t = 1;
print(t);

结果会是 t=1，这个在做日志的时候还是非常好用的。

3、do{...}while(0) 和 ({...})

可以认为是前者是 void 函数，后者是有 return 值的函数。
入2中所示，do{...}while(0) 是为了产生一个程序块，当宏里有多条需要语句需要执行时，如果不适用这种do{...}while(0)的形式，可能导致一些隐形的错误,例如：

#define print(x) {printf(#x);printf("=%d\n",x);

正常的：
print(t); 是没有问题的，但是如果放在程序段里：

if( flag )
print(t);
else
print(a);

展开之后，会发现为

if( flag )
{printf("t");printf("=%d\n",t);};
else

这个语法就错了。因此，当代码段比较多，且不需要返回值时就用 do{...}while(0)吧。
另外一种方式属于 GNU 的扩展，后续在看。

4、多重展开

还是基于打印的例子，我需要打印一些列举的参数值：

#define P(x) arg##x
#define print(x) do{printf(#P(x));printf("=%d\n",P(x));}while(0)

这个编译通不过，换成以下方式即可：

#define P(x) arg##x
#define __print(x) do{printf(#x);printf("=%d\n",x);}while(0)
#define _print(x) __print(x)
#define print(x) _print(P(x))

修改成这样，解决了想要的解决的问题：

int arg1 = 1;
print(1);

输出结果为：arg1=1
主要涉及的问题在于宏的多次展开，宏每次展开只会对当前的输入参数进行一次展开，当你的输入值也是个宏的时候，就需要使用过度宏，让你的输入接着展开。
对于多次展开没有从最根本的原理解释，只是从实验感官上对这个特性做了分析，实际上，自己也不会写出那么复杂的宏（怕中间调用出漏洞）。

宏的基本常见用法，都差不多枚举了一番，往后在见到更高级的玩法和比较精髓的写法往后再慢慢补充上来吧，另外GNU的扩展也会在后篇继续学习了解。

superlong 2016-03-11 01:20 发表评论

clang 宏定义初探（一）

superlong — Tue, 08 Mar 2016 00:44:00 GMT

Clang 宏定义初探（一）

宏的定义方法是#define
那么在什么场景下需要用到宏呢？遇到一些重复的东西，简单的有 for(i = 0; i < n; i ++) 之类的，为了减少繁琐的编码，可能使用

#define FO(i,N) for(i=0;i 为了增强可读性，比如说设置一个数组常亮大小，可以使用

#define N 1001

宏看起来感觉很好用，但是潜藏了很多问题，在实际使用中需要小心谨慎（当然带来大部分问题的，还是编码者自己或者合作方）。
例如，现在要求两个数的最小值，最初会写出如下宏：

#define MIN(A,B) A 正常情况下也是可以使用无误的：

1 #include
2 #define MIN(A,B) A 3 int main()
4 {
5 int a =5, b =6;
6 printf("%d", MIN(a, b));
7 }

然而，当你发布你的代码或者很久以后自己再去调用时，可能写成：

MIN(a<4?a:5, b)

看起来也没啥问题，实际执行一下发现，结果是5，偏离预期！事实上，宏即使单纯的代码展开，当你展开上面的式子之后会发现，实际执行的代码是

a<4?a:5 对于一直用括号来解决优先级问题的我来说，这种展开完全无法理解，于是参看了内核代码，发现更安全的写法为：

#define MIN(A,B) (A)<(B)?(A):(B)

这种写法规避了令人厌恶的优先级问题！本以为这样就完成了一个安全的宏定义，但是事实上还有其他问题！

float a = 1.0f;
float b = MIN(a++, 1.5f);
printf("a=%f, b=%f",a,b);

神秘的a++，同样按照刚才的思路展开，因为宏里面会有两次A的展开，所以a++将被执行两次，再次偏离预期。对于这种情况，我们需要用到一个GNU C的赋值扩展，即使用({...})的形式。这种形式的语句可以类似shell，在顺次执行之后，会将最后一次的表达式的赋值作为返回。举个简单的例子，下面的代码执行完毕后a的值为3，而且b和c只存在于大括号限定的代码域中：

int a = ({
    int b = 1;
    int c = 2;
    b + c;
});

结果是// => a is 3
基于这种特性，我们可以在宏里面为每个传入的参数进行一个拷贝，然后再对拷贝后的参数进行实际的比较运算，那么最终实现了一个比较安全的最小值比较的宏定义：

#define  min(x,y)  ({                   \
    typeof(x)  __min1 = (x);        \
    typeof(y) __min2 = (y);             \
    (void)  (& __min1 == & __min2);     \
    __min1 < __min2  ? __min1 :min2})

最后这一步跳跃有点大了，首先是 typeof 作用是得到参数的类型，其次是(void) (& __min1 == & __min2); 这个神秘的写法是为了验证二者的类型是否一致，当然外侧我们确实用了GNU的扩展({...})。
写到这里，涉及到了另外两个问题，GNU扩展是啥？另外我们用宏是为了节省代码，同时为了省去一些小函数的多次重复调用的参数入栈降低性能的问题，那么内联函数也有这样的效果，什么是内联函数呢？

superlong 2016-03-08 08:44 发表评论

开博

superlong — Sun, 06 Mar 2016 14:34:00 GMT

往后记录工作中开发C的知识点。

superlong 2016-03-06 22:34 发表评论

HDU2295

superlong — Mon, 16 Aug 2010 03:07:00 GMT

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int N = 55;
const double eps = 1e-7;
const int SIZE = N*N;

int n, m , k;
int L[SIZE], R[SIZE], U[SIZE], D[SIZE], Sum[SIZE], Row[SIZE], Col[SIZE];
int lenx, id, deep, anslen;
bool OK;

inline int rd() {
    char ch;
    while( ch = getchar(), ch == ' ' || ch == '\n');
    int d = ch - '0';
    while( ch = getchar(), ch <= '9' && ch >= '0' ) d = d* 10 + ch - '0';
    return d;
}

struct point {
    int x, y;
    void read() {
        x = rd(); y = rd();
    }
} city[N], radar[N];

struct circle {
    point o;
    double r;
    circle(){}
    circle(point _o, double _r) {
        o = _o;
        r = _r;
    }
    bool incircle(point q) {
        return 1.0*(o.x-q.x)*(o.x-q.x) + 1.0*(o.y-q.y)*(o.y-q.y) - r * r < eps;
    }
} Radar[N];

void init() {
    n = rd(); m = rd(); k = rd();
    for(int i = 1; i <= n; i ++) city[i].read();
    for(int i = 1; i <= m; i ++) Radar[i].o.read();
}

inline void pre(int cntcol) {
    for(int i = 0; i <= cntcol; i ++) {
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = D[i] = i;
        Sum[i] = 0;
    }
    L[0] = cntcol; R[cntcol] = 0;
    id = cntcol + 1;
}

inline void insert(int i, int *xx) {
    for(int j = 0; j < lenx; j ++, id ++) {
        int x = xx[j];
        Row[id] = i;
        Col[id] = x;
        Sum[x] ++;
        U[id] = x;
        D[id] = D[x];
        U[D[x]] = id;
        D[x] = id;
        if( j == 0 ) {
            L[id] = R[id] = id;
        } else {
            L[id] = id - 1;
            R[id] = id - j;
            R[id-1] = id;
            L[id-j] = id;
        }
    }
}

inline void remove(int &c) {
    for(int i = D[c]; i != c ; i = D[i]) {
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }
}
inline void resume(int &c) {
    for(int i = U[c]; i != c ; i = U[i]) {
        L[R[i]] = i;
        R[L[i]] = i;
    }
}

inline int Astar() {
    int res = 0;
    bool vis[N*N] = {false};
    for(int i = R[0]; i != 0; i =R[i]) {
        if( !vis[ i ] ) {
            vis[ i ] = true;
            res ++;
            for(int j = D[i]; j != i; j = D[j]) {
                for(int k = R[j]; k != j; k = R[k]) {
                    vis[ Col[k] ] = true;
                }
            }
        }
    }
    return res;
}

void dfs(int dep) {
    if( Astar() + dep > deep )    return ;
    if(R[0] == 0)    {
        anslen = dep;
        OK = true;
        return;
    }
    int idx = R[0];
    for(int i = R[0] ; i != 0 ; i = R[i]) {
        if(Sum[i] < Sum[idx]) {
            idx = i;
            if( Sum[idx] <= 1 ) break;
        }
    }
    for(int i = D[idx] ; i != idx; i = D[i]) {
        remove(i);
        for(int j = R[i] ; j != i ; j = R[j]) remove(j);
        dfs( dep + 1 );
        for(int j = L[i] ; j != i ; j = L[j]) resume(j);
        resume(i);
        if( OK ) return;
    }
}

inline void build() {
    int x[N];
    for(int i = 1; i <= m; i ++) {
        lenx = 0;
        for(int j = 1; j <= n; j ++) {
            if( Radar[i].incircle(city[j]) ) {
                x[lenx++] = j;
            }
        }
        insert(i, x);
    }
}

bool check(double R) {
    for(int i = 1; i <= m; i ++) Radar[i].r = R;
    pre(n);
    build();
    deep = 0;
    anslen = 0;
    OK = false;
    while( !OK ) {
        if( deep > k )  break;
        dfs(0);
        deep ++;
    }
    return OK;
}

void solve() {
    double left = 0, right = 1e29, mid;
    while( right - left > eps) {
        mid = (left + right) / 2;
        if( check(mid) ) {
            right = mid;
        } else {
            left = mid;
        }
    }
    printf("%lf\n", left);

}

int main() {
    int t;
    scanf("%d", &t);
    while( t -- ) {
        init();
        solve();
    }
}

superlong 2010-08-16 11:07 发表评论

fzu1686

superlong — Mon, 16 Aug 2010 01:21:00 GMT

#include <stdio.h>
#include <string.h>

const int N = 16;
const int SIZE = N*N*N*N;

int L[SIZE], R[SIZE], U[SIZE], D[SIZE], Sum[SIZE], Row[SIZE], Col[SIZE];
int lenx, id, deep, anslen;
bool OK;

int n, m, n1, m1;
int ini[N][N];

inline int read() {
    char ch;
    while( ch = getchar(), ch == ' ' || ch == '\n');
    int d = ch - '0';
    while( ch = getchar(), ch <= '9' && ch >= '0' ) d = d* 10 + ch - '0';
    return d;
}

void pre(int cntcol) {
    for(int i = 0; i <= cntcol; i ++) {
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = D[i] = i;
        Sum[i] = 0;
    }
    L[0] = cntcol; R[cntcol] = 0;
    id = cntcol + 1;
}

void init() {
    int cnt = 1;
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            ini[i][j] = read();
            if( ini[i][j] == 1 ) ini[i][j] = cnt ++;
        }
    }
    n1 = read(); m1 = read();
    pre(cnt-1);
}

inline void insert(int i, int *xx) {
    for(int j = 0; j < lenx; j ++, id ++) {
        int x = xx[j];
        Row[id] = i;
        Col[id] = x;
        Sum[x] ++;
        U[id] = x;
        D[id] = D[x];
        U[D[x]] = id;
        D[x] = id;
        if( j == 0 ) {
            L[id] = R[id] = id;
        } else {
            L[id] = id - 1;
            R[id] = id - j;
            R[id-1] = id;
            L[id-j] = id;
        }
    }
}

void build() {
    int r = 0;
    int x[N*N];
    for(int i = 0; i <= n - n1; i ++ ) {
        for(int j = 0; j <= m - m1; j ++) {
            r ++;
            lenx = 0;
            for(int p = 0; p < n1; p ++) {
                for(int q = 0; q < m1; q ++ ) {
                    if( ini[i+p][j+q] > 0 ) {
                        x[lenx++] = ini[i+p][j+q];
                    }
                }
            }
            insert(r, x);
        }
    }
}

void remove(int &c) {
    for(int i = D[c]; i != c ; i = D[i]) {
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }
}
void resume(int &c) {
    for(int i = U[c]; i != c ; i = U[i]) {
        L[R[i]] = i;
        R[L[i]] = i;
    }
}

inline int Astar() {
    int res = 0;
    bool vis[N*N] = {false};
    for(int i = R[0]; i != 0; i =R[i]) {
        if( !vis[ i ] ) {
            vis[ i ] = true;
            res ++;
            for(int j = D[i]; j != i; j = D[j]) {
                for(int k = R[j]; k != j; k = R[k]) {
                    vis[ Col[k] ] = true;
                }
            }
        }
    }
    return res;
}

void dfs(int dep) {
    if( Astar() + dep > deep )    return ;
    if(R[0] == 0)    {
        anslen = dep;
        OK = true;
        return;
    }
    int idx = R[0];
    for(int i = R[0] ; i != 0 ; i = R[i]) {
        if(Sum[i] < Sum[idx]) {
            idx = i;
            if( Sum[idx] <= 1 ) break;
        }
    }
    for(int i = D[idx] ; i != idx; i = D[i]) {
        remove(i);
        for(int j = R[i] ; j != i ; j = R[j]) remove(j);
        dfs( dep + 1 );
        for(int j = L[i] ; j != i ; j = L[j]) resume(j);
        resume(i);
        if( OK ) return;
    }
}

int main() {
    while( scanf("%d %d", &n, &m) != EOF ) {
        init();
        build();
        deep = 0;
        anslen = 0;
        OK = false;
        while( !OK ) {
            //deep ++;
            dfs(0);
            deep ++;
        }
        printf("%d\n", anslen);
    }
    //while(1);
    return 0;
}

写了个可以用作板子的DLX非精确覆盖

superlong 2010-08-16 09:21 发表评论

hdu3529

superlong — Thu, 12 Aug 2010 10:08:00 GMT

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>

const int N = 16;

int L[N*N*N], R[N*N*N], U[N*N*N], D[N*N*N], Sum[N*N*N], Row[N*N*N], Col[N*N*N];
char inimap[N][N];
int map[N][N];
int n, m, cntrow, cntcol;
int lenx, id, deep, anslen;
bool OK;
int move[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool flag[50];

void init() {
    for(int i = 0; i < n; i ++) {
        scanf("%s", inimap[i]);
    }
    memset(map, 0, sizeof(map));
    cntrow = 0;
    cntcol = 0;
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            if ( inimap[i][j] == '*') map[i][j] = -1;
            if ( inimap[i][j] == '.') map[i][j] = 300 + (++cntrow);
            if ( inimap[i][j] == '#') map[i][j] = (++cntcol);
        }
    }
//    for(int i = 0; i < n; i ++) {
//        for(int j = 0; j < m; j ++) {
//            printf("%5d", map[i][j]);
//        }puts("");
//    }
}

void pre() {
    for(int i = 0; i <= cntcol; i ++) {
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = D[i] = i;
        Sum[i] = 0;
    }
    L[0] = cntcol; R[cntcol] = 0;
    id = cntcol + 1;
}

inline void insert(int i, int *xx) {
    for(int j = 0; j < lenx; j ++, id ++) {
        int x = xx[j];
        Row[id] = i;
        Col[id] = x;
        Sum[x] ++;
        U[id] = x;
        D[id] = D[x];
        U[D[x]] = id;
        D[x] = id;
        if( j == 0 ) {
            L[id] = R[id] = id;
        } else {
            L[id] = id - 1;
            R[id] = id - j;
            R[id-1] = id;
            L[id-j] = id;
        }
    }
}

inline int expend(int i, int j, int k) {
    int t = 1;
    while(true) {
        int x = i + move[k][0] * t;
        int y = j + move[k][1] * t;
        if( x < 0 || x >= n || y < 0 || y >= m || map[x][y] == -1) return -1;
        if( map[x][y] > 0 && map[x][y] < 300 ) return map[x][y];
        t ++;
    }
}

struct node {
    int len;
    int x[5];
    bool operator < (const node a) const {
        len > a.len;
    }
};

void build() {
    int x[5], r = 0;
    node tp[15*15] ;
    int cnt = 0;
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            lenx = 0;
            if( map[i][j] > 300 ) {
                for(int k = 0; k < 4; k ++) {
                    int t = expend(i, j, k);
                    if( t == -1 ) continue;
                    x[lenx++] = t;
                }
                tp[cnt].len = lenx;
                for(int k = 0; k < lenx; k ++) tp[cnt].x[k] = x[k];
                cnt ++;
            }
        }
    }
    memset(flag, 0, sizeof( flag));
    std::sort(tp, tp + cnt);
    for(int i = 0; i < cnt; i ++) {
        int j;
        for(j = 0; j < tp[i].len; j ++) {
            if( flag[tp[i].x[j]] ) break;
            flag[tp[i].x[j]] = 1;
        }
        if( j == tp[i].len) {
            lenx = tp[i].len;
            insert(++r, tp[i].x);
        }
    }
}

void remove(int &c) {
    for(int i = D[c]; i != c ; i = D[i]) {
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }
}
void resume(int &c) {
    for(int i = U[c]; i != c ; i = U[i]) {
        L[R[i]] = i;
        R[L[i]] = i;
    }
}

inline int Astar() {
    int res = 0;
    bool vis[16] = {false};
    for(int i = R[0]; i != 0; i =R[i]) {
        if( !vis[ i ] ) {
            vis[ i ] = true;
            res ++;
            for(int j = D[i]; j != i; j = D[j]) {
                for(int k = R[j]; k != j; k = R[k]) {
                    vis[ Col[k] ] = true;
                }
            }
        }
    }
    return res;
}

void dfs(int dep) {
    //printf("%d %d %d\n", Astar(), dep, deep) ;
    //system("pause");
    if( Astar() + dep > deep )    return ;
    if(R[0] == 0)    {
        anslen = dep;
        OK = true;
        return;
    }
    int idx = R[0];
//    printf("%d\n", idx);
    for(int i = R[0] ; i != 0 ; i = R[i]) {
        if(Sum[i] < Sum[idx]) {
            idx = i;
            //if( Sum[idx] <= 1 ) break;
        }
    }
    for(int i = D[idx] ; i != idx; i = D[i]) {
        remove(i);
        for(int j = R[i] ; j != i ; j = R[j]) remove(j);
        dfs( dep + 1 );
        for(int j = L[i] ; j != i ; j = L[j]) resume(j);
        resume(i);
        if( OK ) return;
    }
}

int main() {
    while( scanf("%d %d", &n, &m) != EOF ) {
        init();
        pre();
        build();
        deep = 1;
        OK = false;
        anslen = 257;
        while( !OK ) {
            dfs(0);
            deep ++;
        }
        printf("%d\n", anslen);
    }
    //while(1);
    return 0;
}

superlong 2010-08-12 18:08 发表评论

HDU3498

superlong — Tue, 10 Aug 2010 04:30:00 GMT

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int N = 60;
const int M = N * N;

int map[N][10];
int len[N];
int L[16*N*N], R[16*N*N], U[16*N*N], D[16*N*N], Sum[16*N*N], Row[16*N*N], Col[16*N*N];
int ans[16*N];
int id, anslen, r;
int H[16*N];
bool OK;

int n, m;
int lenx;
int deep;

void pre() {
    for(int i = 0; i <= n; i ++) {
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = D[i] = i;
        Sum[i] = 0;
    }
    L[0] = n; R[n] = 0;
    id = n + 1;
}

inline void insert(int i, int *xx) {
    for(int j = 0; j < lenx; j ++, id ++) {
        int x = xx[j];
        Row[id] = i;
        Col[id] = x;
        Sum[x] ++;
        U[id] = x;
        D[id] = D[x];
        U[D[x]] = id;
        D[x] = id;
        if( j == 0 ) {
            L[id] = R[id] = id;
        } else {
            L[id] = id - 1;
            R[id] = id - j;
            R[id-1] = id;
            L[id-j] = id;
        }
    }
}
//n*2^4 * n
//void build() {
//    int x[6];
//    r = 0;
//    for(int i = 1; i <= n; i ++) {
//        for(int j = 0; j < (1<//            lenx = 0;
//            r ++;
//            x[lenx++] = i;
//            for(int k = 0; k < len[i]; k ++) {
//                if( ((1<//            }
//            //for(int i = 0; i < lenx; i ++) printf("%d ", x[i]); puts("");
//            //system("pause");
//            //H[r] = i;
//            insert(r, x);
//        }
//    }
//    //pr/intf("%d\n", r);
//}

// n * n
void build() {
    int x[6];
    for(int i = 1; i <= n; i ++) {
        lenx = 0;
        x[lenx++] = i;
        for(int j = 0; j < len[i];j ++) {
            x[lenx ++] = map[i][j];
        }
        insert(i, x);
    }
}

void remove(int &c) {
    for(int i = D[c]; i != c ; i = D[i]) {
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }
}
void resume(int &c) {
    for(int i = U[c]; i != c ; i = U[i]) {
        L[R[i]] = i;
        R[L[i]] = i;
    }
}

inline int Astar() {
    int res = 0;
    bool vis[60] = {false};
    for(int i = R[0]; i != 0; i =R[i]) {
        if( !vis[ i ] ) {
            vis[ i ] = true;
            res ++;
            for(int j = D[i]; j != i; j = D[j]) {
                for(int k = R[j]; k != j; k = R[k]) {
                    vis[ Col[k] ] = true;
                }
            }
        }
    }
    return res;
}

void dfs(int dep) {
    if( Astar() + dep > deep )    return ;
    if(R[0] == 0)    {
        anslen = dep;
        OK = true;
        return;
    }
    int i,j,idx = R[0];
    for(i = R[0] ; i != 0 ; i = R[i]) {
        if(Sum[i] < Sum[idx]) {
            idx = i;
            if( Sum[idx] <= 1 ) break;
        }
    }
    for(i = D[idx] ; i != idx; i = D[i]) {
        remove(i);
        for(j = R[i] ; j != i ; j = R[j]) remove(j);
        dfs( dep + 1 );
        for(j = L[i] ; j != i ; j = L[j]) resume(j);
        resume(i);
        if( OK ) return;
    }
}

int main() {
    freopen("in.txt","r",stdin);
    while( scanf("%d %d", &n, &m) != EOF ) {
        memset(len, 0, sizeof( len ));
        for(int i = 0; i < m; i ++) {
            int s, t;
            scanf("%d %d", &s, &t);
            map[s][len[s]++] = t;
            map[t][len[t]++] = s;
        }
        pre();
        build();
        deep = 1;
        OK = false;
        anslen = n;
        while( !OK ) {
            dfs(0);
            deep ++;
        }
        printf("%d\n", anslen);
    }
    while(1);
    return 0;
}

n*n的建模然后找最少的行数使得每一列至少有一个'1'

superlong 2010-08-10 12:30 发表评论

DLX_数独

superlong — Mon, 09 Aug 2010 10:39:00 GMT

#include <stdio.h>
#include <ctime>
#include <stdlib.h>
#include <string.h>

const int SIZE = 16;
const int N = SIZE*SIZE*SIZE;
const int M = SIZE*SIZE*4;
const char LET = 'A';

char map[SIZE+1][SIZE+1];
int L[N*M+1], R[N*M+1], U[N*M+1], D[N*M+1], Sum[N*M+1];
int x[5], lenx;
int Row[N*M+1], Col[N*M+1];
int ans[N+1], anslen;
int id;
bool OK;

void pre() {
    for(int i = 0; i <= M; i ++) {
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = D[i] = i;
        Sum[i] = 0;
    }
    L[0] = M; R[M] = 0;
    id = M + 1;
}

inline void insert(int i, int *xx) {
    for(int j = 0; j < lenx; j ++, id ++) {
        int x = xx[j]+1;
        Row[id] = i;
        Col[id] = x;
        Sum[x] ++;
        U[id] = x;
        D[id] = D[x];
        U[D[x]] = id;
        D[x] = id;
        if( j == 0 ) {
            L[id] = R[id] = id;
        } else {
            L[id] = id - 1;
            R[id] = id - j;
            R[id-1] = id;
            L[id-j] = id;
        }
    }
}

void build() {
    for(int i = 0; i < SIZE; i ++) {
        for(int j = 0; j < SIZE; j ++) {
            for(int k = 0; k < SIZE; k ++) {
                int row = k+SIZE*j+SIZE*SIZE*i+1;
                lenx = 0;
                if( map[i][j] == '-' || map[i][j] == k + 'A' ) {
                    x[lenx++] = SIZE*i + k;
                    x[lenx++] = SIZE*SIZE + SIZE*j + k;
                    int temp = (i / 4) * 4 + j / 4;
                    x[lenx++] = 2*SIZE*SIZE + temp * SIZE + k;
                    x[lenx++] = 3*SIZE*SIZE + i*SIZE + j;
                    insert(row, x);
                }
            }
        }
    }
}

inline void remove(int c) {
    R[L[c]] = R[c];
    L[R[c]] = L[c];
    for(int id = D[c]; id != c; id = D[id]) {
        for(int i = R[id]; i != id; i = R[i] ) {
            D[U[i]] = D[i];
            U[D[i]] = U[i];
            Sum[Col[i]] --;
        }
    }
}

inline void resume(int c) {
    L[R[c]] = c;
    R[L[c]] = c;
    for(int id = D[c]; id != c; id = D[id]) {
        for(int i = R[id]; i != id; i = R[i] ) {
            U[D[i]] = i;
            D[U[i]] = i;
            Sum[Col[i]] ++;
        }
    }
}

bool dfs(int deep) {
    if( R[0] == 0 ) return true;
    int column = R[0];
    for(int i = R[0]; i != 0; i = R[i]) {
        if( Sum[i] < Sum[column] ) {
            column = i;
            if( Sum[column] < 2 ) break;
        }
    }
    remove(column);
    for(int id = D[column]; id != column; id = D[id]) {
        ans[deep] = Row[id];
        for(int i = R[id]; i != id; i = R[i]) remove(Col[i]);
        if( dfs( deep + 1) ) return true;
        for(int i = L[id]; i != id; i = L[i]) resume(Col[i]);
    }
    resume(column);
    return false;
}

int main() {
    freopen("in.txt","r",stdin);
    while( scanf("%s", map[0]) != EOF ) {
        for(int i = 1; i < SIZE; i ++) scanf("%s", map[i]);
        pre();
        build();
        dfs(0);
        for(int i = 0; i < 256; i ++) {
            int r = (ans[i] - 1) / SIZE / SIZE % SIZE;
            int c = (ans[i] - 1) / SIZE % SIZE;
            int val = (ans[i] - 1) % SIZE;
            map[r][c] = val + 'A';
        }
        for(int i = 0; i < SIZE; i ++){
            for(int j = 0; j < SIZE; j ++) printf("%c",map[i][j]);
            printf("\n");
        }
        printf("\n");
    }
    while(1);
}

http://acm.pku.edu.cn/JudgeOnline/problem?id=3076

superlong 2010-08-09 18:39 发表评论

DLX

superlong — Mon, 09 Aug 2010 02:51:00 GMT

#include <stdio.h>
#include <string.h>

const int N = 1005*1005;

int L[N], R[N], U[N], D[N], C[N], Sum[N];
int Row[N], Col[N];
int ans[N], anslen;
int n, m, id;
bool OK;

void pre() {
    for(int i = 0; i <= m; i ++) {
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = D[i] = C[i] = i;
        Sum[i] = 0;
    }
    L[0] = m; R[m] = 0;
    id = m + 1;
}

void build() {
    int num, x;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &num);
        for(int j = 0; j < num; j ++, id ++) {
            scanf("%d", &x);
            Row[id] = i;
            Col[id] = x;
            Sum[x] ++;
            U[id] = x;
            D[id] = D[x];
            U[D[x]] = id;
            D[x] = id;
            if( j == 0 ) {
                L[id] = R[id] = id;
            } else {
                L[id] = id - 1;
                R[id] = id - j;
                R[id-1] = id;
                L[id-j] = id;
            }
        }
    }
}

inline void remove(int c) {
    R[L[c]] = R[c];
    L[R[c]] = L[c];
    for(int id = D[c]; id != c; id = D[id]) {
        for(int i = R[id]; i != id; i = R[i] ) {
            D[U[i]] = D[i];
            U[D[i]] = U[i];
            Sum[Col[i]] --;
        }
    }
}

inline void resume(int c) {
    L[R[c]] = c;
    R[L[c]] = c;
    for(int id = D[c]; id != c; id = D[id]) {
        for(int i = R[id]; i != id; i = R[i] ) {
            U[D[i]] = i;
            D[U[i]] = i;
            Sum[Col[i]] ++;
        }
    }
}

void dfs(int deep) {
    if( R[0] == 0 ) {
        OK = true;
        anslen = deep;
        return ;
    }
    int column = R[0];
    for(int i = D[0]; i != 0; i = D[i]) {
        if( Sum[i] <= Sum[column] ) column = i;
    }
    remove(column);
    for(int id = D[column]; id != column; id = D[id]) {
        ans[deep] = Row[id];
        for(int i = R[id]; i != id; i = R[i]) remove(Col[i]);
        dfs( deep + 1);
        if(OK) return;
        for(int i = R[id]; i != id; i = R[i]) resume(Col[i]);
    }
    resume(column);
}

int main() {
    while( ~scanf("%d %d", &n, &m) ) {
        pre();
        build();
        OK = false;
        dfs(0);
        if( OK ) {
            printf("%d", anslen);
            for(int i = 0; i < anslen; i ++) printf(" %d", ans[i]);
            puts("");
        } else {
            puts("NO");
        }
    }
}

http://acm.hust.edu.cn/thanks/problem.php?id=1017

superlong 2010-08-09 10:51 发表评论

HOJ11648

superlong — Fri, 06 Aug 2010 07:57:00 GMT

#include <stdio.h>
#define LOOP(a,b,c,d) for(a=b;a
#define L(a) LOOP(a,0,8,1)
#define ENEMY(a,b) ((a-'a')*(b-'a')<0&&a!='.'&&b!='.')
#define FRIEND(a,b) ((a-'a')*(b-'a')>0&&a!='.'&&b!='.')
int mdir[16][2]={0,1,-1,1,-1,0,-1,-1, 0,-1,1,-1,1,0,1,1,//相邻移动8个方向
                 -1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1,2,1,1,2};//马步移动8个方向
int md[5][4]={0,8,1,2, //king               md[0]-md[1]:当前棋子的移动数组的下标范围
              0,8,1,8, //queen              md[2]      :移动数组的选取间隔（1->八个方向， 2->四个方向）
              0,8,2,8, //rook               md[3]      :遍历当前棋子一次操作可以攻击的范围需要进行移动的次数
              1,8,2,8, //bishop
              8,16,1,2 //knight
            };
int KX,KY,KADD,KAT[8][2],KAL,MBLE,ATTACK[8][8],MOVE[8][8],ESC,BLE;
char map[8][10];
char BW[2]; // 当前选手
int trs(char c){
    if(c<'a')c+='a'-'A';//大写转小写
    if(c=='k')return 0;
    if(c=='q')return 1;
    if(c=='r')return 2;
    if(c=='b')return 3;
    if(c=='n')return 4;
    return -1;
    /*
    Rook    车 2
    Bishop    象 3
    Queen    后 1
    Knight    马 4
    King    王 0
    */
}
void InitMap(){
    int i,j;
    L(i)L(j)ATTACK[i][j]=MOVE[i][j]=0;MBLE=KADD=ESC=BLE=0;
    scanf("%s",BW);
    L(i)scanf("%s",map[i]);
    L(i)L(j)if(trs(map[i][j])==0&&FRIEND(map[i][j],BW[0])){
        KX=i;KY=j;i=j=8;
    }
}
int StepMove(int x,int y,int d,int l,int *m,int *n){
    *m=x+mdir[d][0]*l;*n=y+mdir[d][1]*l;
    if(*m<0||*m>7||*n<0||*n>7)return -1;
    if(map[*m][*n]=='.')return 0;
    return 1;
}
void ATT(char c,int x,int y){
    int d,l,r,s,m,n,i,sx,sy;
    r=trs(c); //当前敌人的类型
    LOOP(d,md[r][0],md[r][1],md[r][2]){
        LOOP(l,1,md[r][3],1){
            s=StepMove(x,y,d,l,&m,&n);
            if(s>=0)ATTACK[m][n]++;
            if(s)break;             //遇到一个非空的位置或者出界就停止
        }
        if(s<=0||FRIEND(map[m][n],c))continue;//当前棋子木有遇到其他棋子或者遇到的棋子是友方单位
        if(KX==m&&KY==n){                     //如果是遇到了我方的王
            KADD++;KAL=l;                     //我方王被攻击次数+1
            if(KADD==1)                       //如果问方王只是被攻击一次
                LOOP(i,0,KAL,1){              //记录攻击王的这条线路 KAT
                    KAT[i][0]=x+i*mdir[d][0];
                    KAT[i][1]=y+i*mdir[d][0];
                }
            continue;
        }
        if(r==0||r==4)continue; //如果王和马走到(m,n)那么移开自己在(m,n)上的棋子不会对王造成威胁
        LOOP(i,1,8,1)           //假设移开在(m,n)的本方棋子使得王被攻击则标记该位置为不可动(-1)
            if(s=StepMove(m,n,d,i,&sx,&sy))break;
            if(KX==sx&&KY==sy)MOVE[m][n]=-1;
    }
}
void BLOCK(char c,int x,int y){
    int d,l,r,s,m,n;
    r=trs(c);if(r==0)return;//枚举不是王且能移动的的友方单位
    LOOP(d,md[r][0],md[r][1],md[r][2]){
        LOOP(l,1,md[r][3],1){
            s=StepMove(x,y,d,l,&m,&n);
            if(s)break;
            else {MOVE[m][n]++;MBLE++;}
        }
        if(s==1&&ENEMY(map[m][n],c)){
            MBLE++;MOVE[m][n]++;
        }
    }
}
int main(){
    int i,j,t,x,y;
    scanf("%d",&t);
    while(t--){
        InitMap();//读入图以及初始化各个数组
        L(i)L(j)if(ENEMY(map[i][j],BW[0]))ATT(map[i][j],i,j);
        /*
            做了两张表ATT和MOVE
            ATT表示敌方能攻击的所有点
            MOVE[x][y] = -1 表示本方在(x,y)处的棋子无法移动
            KADD记录王被多少个敌方单位攻击到
        */
        L(i)L(j)if(FRIEND(map[i][j],BW[0])&&MOVE[i][j]!=-1)BLOCK(map[i][j],i,j);

        L(i){
            x=KX+mdir[i][0];y=KY+mdir[i][1];if(x<0||x>7||y<0||y>7)continue;
            if(ATTACK[x][y]==0&&(map[x][y]=='.'||ENEMY(map[x][y],BW[0]))){ESC++;break;}
        }//如果王走一步可以移动且不受攻击则ESC++

        if(KADD==1)LOOP(i,0,KAL,1)if(MOVE[KAT[i][0]][KAT[i][1]]){BLE=1;break;}
        printf("%s IS ",BW[0]=='B'?"BLACK":"WHITE");
        if(KADD==0&&(ESC||MBLE))printf("SAFE\n");
        else if(KADD&&(ESC||BLE))printf("CHECKED\n");
        else printf("CHECKMATED\n");
    }
    return 0;
}

题意是给定一个棋盘和谁现在出手，问他是否安全或者被将死或者被将军

superlong 2010-08-06 15:57 发表评论