1000部精品久久久久久久久,正在播放欧美一区,亚洲视频在线观看免费

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

Clang 宏定义初探（一�Q?/h1> �?/span>的定义方法是#define
那么在什么场景下需要用到宏呢？遇到一些重复的东西�Q�简单的�?nbsp;for(i = 0; i < n; i ++) 之类的，��Z��减少�J�琐的编码，可能使用

#define FO(i,N) for(i=0;i ��Z��增强可读性，比如说设�|�一个数�l�常亮大��，可以使用

#define N 1001
宏看��h��感觉很好用，但是潜藏了很多问题，在实际��用中需要小心�}慎（当然带来大部分问题的�Q�还是编码者自己或者合作方�Q��?br /> �?/span>如，现在要求两个数的最��|��最初会写出如下宏：

#define MIN(A,B) A 正常情况下也是可以��用无误的�Q?br />
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 }
然而，当你发布你的代码或者很久以后自己再去调用时�Q�可能写成：

MIN(a<4?a:5, b)
看�v来也没啥问题�Q�实际执行一下发玎ͼ��l�果�?�Q�偏��预期！事实上，宏即使单�U�的代码展开�Q�当你展开上面的式子之后会发现�Q�实际执行的代码�?br />
a<4?a:5 对于一直用括号来解决优先��问题的我来说�Q�这�U�展开完全无法理解�Q�于是参看了内核代码�Q�发现更安全的写法�ؓ�Q?br />
#define MIN(A,B) (A)<(B)?(A):(B)
�q�种写法规避了��o人厌恶的优先�U�问题！本以��样就完成了一个安全的宏定义，但是事实上还有其他问题！

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

��秘的a++�Q�同��h��照刚才的思�\展开�Q�因为宏里面会有两次A的展开�Q�所以a++��被执行两次�Q�再�ơ偏��预期。对于这�U�情况，我们需要用��C��个GNU C的赋值扩展，即��?{...})的�Ş式。这�U��Ş式的语句可以�c�M��shell�Q�在��次执行之后�Q�会��最后一�ơ的表达式的赋��g��回。�D个简单的例子�Q�下面的代码执行完毕后a的��gؓ3�Q�而且b和c只存在于大括号限定的代码域中�Q?br />

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

�l�果�?/ => a is 3
��Z��q�种�Ҏ(gu��)��，我们可以在宏里面为每个传入的参数�q�行一个拷贝，然后再对拯��后的参数�q�行实际的比较运��，那么最�l�实��C��一个比较安全的最��值比较的宏定义：

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

最后这一步蟩跃有点大了，首先�?typeof 作用是得到参数的�c�d��Q�其�ơ是(void) (& min1 == & __min2); �q�个��秘的写法是��Z��验证二者的�c�d��是否一��_��当然外侧我们��实用了GNU的扩�?{...})�?br /> 写到�q�里�Q�涉及到了另外两个问题，GNU扩展是啥�Q�另外我们用宏是��Z��节省代码�Q�同时�ؓ了省��M��些小函数的多�ơ重复调用的参数入栈降低性能的问题，那么内联函数也有�q�样的效果，什么是内联函数呢？

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

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

往后记录工作中开发C的知识点�?img src ="http://www.shnenglu.com/superlong/aggbug/212939.html" width = "1" height = "1" />

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非精��覆�?br>

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,//盔R��U�d��8个方�?nbsp;
                 -1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1,2,1,1,2};//马步�U�d��8个方�?nbsp;
int md[5][4]={0,8,1,2, //king               md[0]-md[1]:当前��子的移动数�l�的下标范围
              0,8,1,8, //queen              md[2]      :�U�d��数组的选取间隔�Q?->八个方向�Q?nbsp;2->四个方向�Q?nbsp;
              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';//大写转小�?nbsp;
    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    �?nbsp;2
    Bishop    �?nbsp;3
    Queen    �?nbsp;1
    Knight    �?nbsp;4
    King    �?nbsp;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); //当前敌�h的类�?nbsp;
    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;             //遇到一个非�I�的位置或者出界就停止
        }
        if(s<=0||FRIEND(map[m][n],c))continue;//当前��子木有遇到其他��子或者遇到的��子是友方单�?nbsp;
        if(KX==m&&KY==n){                     //如果是遇��C��我方的王
            KADD++;KAL=l;                     //我方王被��d��ơ数+1
            if(KADD==1)                       //如果问方王只是被��d��一��?nbsp;
                LOOP(i,0,KAL,1){              //记录��d��王的�q�条�U��\ 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)那么�U�d��自己�?m,n)上的��子不会对王造成威胁
        LOOP(i,1,8,1)           //假设�U�d��?m,n)的本�Ҏ(gu��)��子��得王被攻��d��标记该位�|��ؓ不可�?-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;//枚�D不是王且能移动的的友方单�?nbsp;
    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();//��d��?nbsp;以及初始化各个数�l?nbsp;
        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)处的��子无法�U�d��
            KADD记录王被多少个敌方单位攻��d��
        */
        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;}
        }//如果王走一步可以移动且不受��d��则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 发表评论