huicpc0860 - C++博客

whu 1071 Joseph problem

#include <stdio.h>

struct xx {

int l, r, m, c;

} t[9000000];

int n, m, i;

void make(int l, int r, int i) {

t[i].l = l, t[i].r = r, t[i].m = (l + r) >> 1, t[i].c = r - l;

if (l + 1 != r) {

make(l, t[i].m, i << 1);

make(t[i].m, r, (i << 1) + 1);

}

int update(int l, int r, int i) {

if (t[i].l == l && t[i].r == r) return t[i].c;

if (r <= t[i].m) return update(l, r, i << 1);

if (l >= t[i].m) return update(l, r, (i << 1) + 1);

return update(l, t[i].m, i << 1) + update(t[i].m, r, (i << 1) + 1);

}

int find(int k, int i) {

t[i].c--;

if (t[i].l == t[i].m) {

printf("%d ", t[i].l);

return t[i].l;

}

int s = t[i << 1].c;

if (k <= s) return find(k, i << 1);

return find(k - s, (i << 1) + 1);

}

int main() {

while (scanf("%d%d", &n, &m) != EOF) {

make(1, n + 1, 1), i = 0;

while (i = update(1, find((i + m) % t[1].c ? (i + m) % t[1].c : t[1].c, 1) + 1, 1), t[1].c);

printf("\n");

}

return 0;

}

posted @ 2010-05-19 17:59 huicpc0860 阅读(196) | 评论 (0) | 编辑收藏

poj 2978 Colored stones

//状态压缩dp
#include <stdio.h>
#include <string.h>
int dp[101][6][160];

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int m, k;
    while (scanf("%d%d", &m, &k), m || k) {
        memset(dp, 0, sizeof (dp));
        int n = 1 << k, ans = 0, a;
        for (int i = 1; i <= m; i++) {
            scanf("%d", &a);
            a--;
            for (int j = 0; j < k; j++)
                for (int s = 0; s < n; s++)
                    if ((s >> a)&1) {
                        if (a == j) dp[i][j][s] = max(dp[i][j][s], dp[i - 1][j][s] + 1);
                        else dp[i][j][s] = max(dp[i][j][s], dp[i - 1][j][s]);
                    } else {
                        dp[i][a][s | (1 << a)] = max(dp[i][a][s | (1 << a)], dp[i - 1][j][s] + 1);
                        dp[i][j][s] = max(dp[i][j][s], dp[i - 1][j][s]);
                    }
        }
        for (int i = 0; i < k; i++)
            for (int j = 0; j < n; j++)
                ans = max(ans, dp[m][i][j]);
        printf("%d\n", m - ans);
    }
    return 0;
}

posted @ 2010-05-18 16:42 huicpc0860 阅读(199) | 评论 (0) | 编辑收藏

poj 2411 Mondriaan's Dream

#include <stdio.h>
#include <string.h>
const int N = 1 << 11;
long long x[N], y[N];
int n, m, t;

bool check(int x) {
    while (x) {
        if (x & 1) {
            x >>= 1;
            if (x & 1)x >>= 1;
            else return 0;
        } else x >>= 1;
    }
    return 1;
}

bool judge(int now, int last) {
    int tmp = t & (~last);
    if ((now & tmp) == tmp && check(now - tmp))return 1;
    return 0;
}

int main() {
    while (scanf("%d%d", &n, &m), n || m) {
        if ((n & 1) && (m & 1)) {
            puts("0");
            continue;
        }
        if (n < m)n ^= m, m ^= n, n ^= m;
        int s = 1 << m;
        t = s - 1;
        for (int i = 0; i < s; i++)y[i] = check(i);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < s; j++)
                for (int k = 0; k < s; k++)
                    if (judge(j, k))x[j] += y[k];
            memcpy(y, x, sizeof (x[0]) * s);
            memset(x, 0, sizeof (x[0]) * s);
        }
        printf("%lld\n",y[t]);
    }
    return 0;
}

posted @ 2010-05-17 16:11 huicpc0860 阅读(151) | 评论 (0) | 编辑收藏

poj 1988 Cube Stacking

1 #include <stdio.h>
2 int r[30010] = {0}, p[30010], n, x, y, d[30010];
3 char s[3];
4
5 int find(int x) {
6     if (x != p[x]) {
7         int t = p[x];
8         p[x] = find(p[x]);
9         r[x] += r[t];
10     }
11     return p[x];
12 }
13
14 int main() {
15     for (int i = 1; i < 30010; i++)p[i] = i, d[i] = 1;
16     scanf("%d", &n);
17     while (n--) {
18         scanf("%s%d", s, &x);
19         if (s[0] == 'M') {
20             scanf("%d", &y);
21             x = find(x), y = find(y);
22             p[x] = y;
23             r[x] = d[y];
24             d[y] += d[x];
25         } else {
26             find(x);
27             printf("%d\n", r[x]);
28         }
29     }
30     return 0;
31 }

posted @ 2010-05-15 21:18 huicpc0860 阅读(129) | 评论 (0) | 编辑收藏

poj 1228 Grandpa's Estate

#include <stdio.h>
#include <algorithm>
using namespace std;

struct point {
    int x, y;
};

bool cmp(point p1, point p2) {
    return p1.y < p2.y || p1.y == p2.y && p1.x < p2.x;
}

int cross(point p0, point p1, point p2) {
    return (p1.x - p0.x)*(p2.y - p0.y)-(p1.y - p0.y)*(p2.x - p0.x);
}

void tubao(point *p, int n, point *ch, int &m) {
    int i, k;
    sort(p, p + n, cmp);
    for (m = i = 0; i < n; i++) {
        while (m > 1 && cross(ch[m - 2], ch[m - 1], p[i]) < 0)m--;
        ch[m++] = p[i];
    }
    if (n = m)return;
    k = m;
    for (i = n - 2; i >= 0; i--) {
        while (m > k && cross(ch[m - 2], ch[m - 1], p[i]) < 0)m--;
        ch[m++] = p[i];
    }
    if (n > 1)m--;
}

bool judge(point *p, int n) {
    if (n < 6)return 0;
    for (int i = 2; i < n; i++)
        if (cross(p[0], p[1], p[i]) != 0)return 1;
    return 0;
}

int main() {
    point p[1010], ch[1010];
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d%d", &p[i].x, &p[i].y);
        bool flag = judge(p, n);
        if (flag) {
            tubao(p, n, ch, n);
            ch[n] = ch[0];
            point a, b;
            for (int i = 1; flag && i < n;) {
                a = ch[i - 1], b = ch[i++];
                flag = 0;
                while (i <= n && cross(a, b, ch[i]) == 0) {
                    flag = 1;
                    i++;
                }
            }
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

posted @ 2010-05-15 21:07 huicpc0860 阅读(264) | 评论 (0) | 编辑收藏

常用链接

留言簿

随笔分类

随笔档案

搜索

最新随笔

最新评论