发新随笔
发新文章 管理

#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 + 11), i = 0;
        
while (i = update(1, find((i + m) % t[1].c ? (i + m) % t[1].c : t[1].c, 1+ 11), t[1].c);
        printf(
"\n");
    }

    
return 0;
}

posted @ 2010-05-19 17:59 huicpc0860 阅读(197) | 评论 (0)编辑 收藏
 
//状态压缩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, 
0sizeof (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)编辑 收藏
 
#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, 
0sizeof (x[0]) * s);
        }
        printf(
"%lld\n",y[t]);
    }
    
return 0;
}

posted @ 2010-05-17 16:11 huicpc0860 阅读(151) | 评论 (0)编辑 收藏
 
 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 阅读(130) | 评论 (0)编辑 收藏
 
#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)编辑 收藏
仅列出标题
共2页: 1 2 
CALENDER
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿

随笔分类

随笔档案

搜索

  •  

最新随笔

最新评论


Powered By: 博客园
模板提供沪江博客