亚洲欧洲在线观看,国产日韩亚洲欧美综合,亚洲国产精品尤物yw在线观看

Johnnx — Wed, 16 Sep 2009 09:40:00 GMT

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

�q�道题目要求�Q�选出一些行使得�q�些行构成矩�늚�每一列都有且只有一�?�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 1 #include<cstdio>
2 #include<string.h>
3 using namespace std;
4
5 int m,n,map[16][300];
6 bool used[300];
7 bool find;
8
9 bool match(){ //判断所选取的行构成的矩阉|��否符合情�?br>10     for(int i = 0;i < n;++i){
11         if(!used[i])return false;
12     }
13     return true;
14 }
15
16 bool check(int row){
17     for(int i = 0;i < n;++i){
18         if(used[i] && map[row][i])return false; //used[i]&&map[row][i]表示该列有选取的该列有不只一�?�Q�返回false攑ּ��q�种情况�?br>19     }
20     for(int i = 0;i < n;++i){
21         if(map[row][i]){
22             used[i] = true;
23         }
24     }
25     return true;
26 }
27
28 void dfs(int start){
29     if(start>m || find)return;
30     if(match()){
31         printf("Yes, I found it\n");
32         find = true;
33         return;
34     }
35     for(int i = start;i < m && !find;++i){
36         if(check(i)){
37             dfs(i+1);
38             for(int j = 0;j < n;++j){
39                 if(map[i][j])used[j] = false;
40             }
41         }
42     }
43 }
44
45 int main()
46 {
47     int i,j;
48     while(scanf("%d%d",&m,&n)!=EOF){
49         for(i = 0;i < m;++i){
50             for(j = 0;j < n;++j){
51                 scanf("%d",&map[i][j]);
52             }
53         }
54         memset(used,false,sizeof(used));
55         find = false;
56         dfs(0);
57         if(!find)printf("It is impossible\n");
58     }
59     return 0;
60 }
61

Johnnx 2009-09-16 17:40 发表评论

POJ 2528�Q�线�D�|��(w��i)+��L��化）

Johnnx — Wed, 16 Sep 2009 09:07:00 GMT

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

�q�是一道经典的�U�段�?w��i)题目�?/span>另外加上��L��化的�Ҏ(gu��)��?/div>

��L��化：(x��)�׃��题目中wall�?0000000bytes long�Q�直接线�D�|��(w��i)无疑�?x��)MLE。所以要对其��L��化，基本做法是：(x��)先对所有端点坐标进行排序，�?span style="COLOR:red">相应序号代替端点坐标构造线�D�|��(w��i)�q�行计算。这��h��大的序号也只�?*n�?/div>

在构造线�D�|��(w��i)的节点结构体�Ӟ��d��变量c。c=0时表�C�c�U�段没有贴�v报，或者脓(chu��ng)了不止一张�v报；c>0时表�C��(chu��ng)了一张�v报，�q�且c的��D��C��(chu��ng)的是�W�几张�v报�?/div>

   �U�段�?w��i)更新的基本原理��是�Q�当我们贴�v报i�Ӟ��如果遇到某一�U�段区间能够被当前�v报完全覆盖，那么我们更新到此区间卛_��Q�即让它的变量c更新为�v报i�Q�记录下i的倹{��如果不能被��h��完全覆盖�Q�则只是�q�一�U�段区间的部分区间需要修改，则更改这一区间的子区间卛_��?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; ">  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<string.h>
  5 #define MAX 20001
  6
  7 using namespace std;
  8
  9 int c,n,ls[MAX];
10 struct node{
11     int l,r;
12     int c;
13 }tree[MAX*4];
14 struct ln{
15     int li,num;//num表示�W�几张�v�?br> 16 }line[MAX];
17 int set[MAX][2];
18 bool visit[MAX];
19 int ans;
20
21 bool cmp(struct ln a,struct ln b){
22     return a.li<b.li;
23 }
24
25 void Inittree(int pos,int ll,int rr){
26     tree[pos].l = ll;
27     tree[pos].r = rr;
28     tree[pos].c = 0;
29     if(ll!=rr){
30         int mid = (ll+rr)>>1;
31         Inittree(pos*2,ll,mid);
32         Inittree(pos*2+1,mid+1,rr);
33     }
34 }
35
36 void Insert(int pos,int ll,int rr,int color){
37     if(tree[pos].l == ll && tree[pos].r == rr){
38         tree[pos].c = color;
39         return;
40     }
41     if(tree[pos].c > 0 && tree[pos].c != color){
42         tree[pos*2].c = tree[pos].c;
43         tree[pos*2+1].c = tree[pos].c;
44         tree[pos].c = 0;
45     }
46     int mid = (tree[pos].l + tree[pos].r)>>1;
47     if(rr<=mid){
48         Insert(pos*2,ll,rr,color);
49     }
50     else if(ll>mid){
51         Insert(pos*2+1,ll,rr,color);
52     }
53     else{
54         Insert(pos*2,ll,mid,color);
55         Insert(pos*2+1,mid+1,rr,color);
56     }
57 }
58
59 void Search(int pos){
60     if(tree[pos].c!=0){
61         if(!visit[tree[pos].c]){//tree[pos].c
62             visit[tree[pos].c] = true;
63             ans++;
64         }
65         return ;
66     }
67     Search(2*pos);
68     Search(2*pos+1);
69 }
70
71 int main()
72 {
73     int i;
74     while(scanf("%d",&c)!=EOF){
75         while(c--){
76             scanf("%d",&n);
77             for(i = 0;i < n;++i){//��L��?/span>
78                 scanf("%d%d",&set[i][0],&set[i][1]);
79                 line[2*i].li = set[i][0];
80                 line[2*i].num = -(i+1);//用负数表�C?�U�段��L(f��ng)��
81                 line[2*i+1].li = set[i][1];
82                 line[2*i+1].num = i+1;
83             }
84             sort(line,line+2*n,cmp);
85             int temp = line[0].li,tp = 1;
86             for(i = 0;i < 2*n;++i){
87                 if(line[i].li != temp){
88                     tp++;
89                     temp = line[i].li;
90                 }
91                 if(line[i].num < 0){
92                     set[-line[i].num-1][0] = tp;
93                 }
94                 else{
95                     set[line[i].num-1][1] = tp;
96                 }
97             }//��L��?/span>
98
99             Inittree(1,1,tp);
100             for(i = 0;i < n;++i){
101                 Insert(1,set[i][0],set[i][1],i+1);
102             }
103             memset(visit,0,sizeof(visit));
104             ans = 0;
105             Search(1);
106             printf("%d\n",ans);
107         }
108     }
109     return 0;
110 }
111

Johnnx 2009-09-16 17:07 发表评论

NKOJ 1007,1249

Johnnx — Fri, 24 Jul 2009 10:18:00 GMT

http://acm.nankai.edu.cn/p1007.html,http://acm.nankai.edu.cn/p1249.html

�q�是两个关于分解素数的问题，一个是分解为素��C��和，一个是分解为素��C��U�。自己写的总TLE�Q�于是参考了别�h的代码，感觉�Ҏ(gu��)��果然巧妙。对于素��C��和是扑ֈ�素数规律了�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; ">nkoj 1007

#include<stdio.h>
#include<stdlib.h>
int n;
int main()
{
    scanf("%d",&n);
    if(n%3){
    switch(n%3){
        case 1:printf("2 2 ");n-=4;break;
        case 2:printf("2 ");n-=2;break;
    }
    }
    while(n){
        printf("3 ");
        n-=3;
    }
    system("pause");
    return 0;
}

code

nkoj 1249

#include<stdio.h>
#include<math.h>
int n,a;
int main()
{
    scanf("%d",&n);
    while(n--){
        scanf("%d",&a);
        int i,flag = 0;
        int b=a;
        for(i = 2;i <= b/2;i++){
            if(a%i==0 && flag==0){
                flag = 1;
                a/=i;
                printf("%d",i);
            }
            while(a%i==0){
                a/=i;
                printf("*%d",i);
            }
        }
        if(flag == 0)printf("%d",a);
        printf("\n");
    }
    return 0;
}

Johnnx 2009-07-24 18:18 发表评论

POJ grids 1664

Johnnx — Mon, 20 Jul 2009 08:56:00 GMT

http://poj.grids.cn/problem?id=1664

从这道题目我认识到递归思想的强大�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; ">#include<stdio.h>
int t;
int pro(int m,int n){
    if(m == 0||n == 1)return 1;
    if(m < n)return pro(m,m);
    return pro(m,n-1)+pro(m-n,n);
}
int main()
{
    scanf("%d",&t);
    int m,n;
    while(t--){
        scanf("%d%d",&m,&n);
        printf("%d\n",pro(m,n));
    }
    return 0;
}

Johnnx 2009-07-20 16:56 发表评论

NKOJ 1019

Johnnx — Sat, 18 Jul 2009 06:18:00 GMT

http://acm.nankai.edu.cn/p1019.html

大数相加�Q�利用数�l�存储，再加上适当处理�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 1 #include<stdio.h>
2 #include<string.h>
3 char a[101],b[101];
4 int c[101];
5 int main()
6 {
7     while(scanf("%s%s",a,b) != EOF){
8         memset(c,0,sizeof(c));
9         int i,j,k;
10         for(i = strlen(a)-1,j = strlen(b)-1,k = 0;i>=0 || j>=0;k++){
11             c[k] = (i>=0?(a[i--]-'0'):0) + (j>=0?(b[j--]-'0'):0);
12         }
13         for(i = 0;i < k;++i){
14             if(c[i] > 9){
15                 c[i+1] += c[i]/10;
16                 c[i] = c[i]%10;
17             }
18         }
19         while(!c[k]){
20             k--;
21         }
22         for(i = k;i>=0;--i){
23             printf("%d",c[i]);
24         }
25         printf("\n");
26     }
27     return 0;
28 }

Johnnx 2009-07-18 14:18 发表评论

NKOJ 1002

Johnnx — Sat, 18 Jul 2009 06:14:00 GMT

http://acm.nankai.edu.cn/p1002.html

乍看不难�Q�其实也不难。就是不能用递归来做。��y妙地利用变量l来处理，体会(x��)�Q?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 1 #include<stdio.h>
2 #include<stdlib.h>
3 long n;
4 int main()
5 {
6     while(scanf("%d",&n) != EOF){
7         long l = 1;
8         while(l>0){
9             if(n >= 50025002){
10                 n -= 5;
11                 l--;
12             }
13             else{
14                 n += 2005;
15                 l++;
16             }
17         }
18         printf("%d\n",n);
19     }
20     system("pause");
21     return 0;
22 }
23

Johnnx 2009-07-18 14:14 发表评论

POJ grids 2692

Johnnx — Sat, 18 Jul 2009 06:09:00 GMT

http://poj.grids.cn/problem?id=2692

利用枚�D�Q�从'A'�?L'。判断条件是�Q�如果是'even'�Q�则天��^两边无假币；如果�?up'�Q�若为light�Q�则假币一定在天��^右侧�Q�若为heavy�Q�则假币一定在天��^左侧�Q�如果是'down'�Q�情�늛�反�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 char left[3][7],right[3][7],result[3][5];
5 bool isLight(char c);
6 bool isheavy(char c);
7 int main()
8 {
9     int n;
10     while(scanf("%d",&n) != EOF){
11         while(n--){
12             for(int i = 0;i < 3;i++)
13                 scanf("%s%s%s",left[i],right[i],result[i]);
14             char x;
15             for(x = 'A';x <= 'L';x++){
16                 if(isLight(x)){
17                     printf("%c is the counterfeit coin and it is light.\n",x);
18                     break;
19                 }
20                 if(isheavy(x)){
21                     printf("%c is the counterfeit coin and it is heavy.\n",x);
22                     break;
23                 }
24             }
25         }
26     }
27     system("pause");
28     return 0;
29 }
30
31 bool isLight(char c)
32 {
33     for(int i = 0;i < 3;i++){
34         if(!strcmp(result[i],"even"))
35             if(strchr(left[i],c) != NULL || strchr(right[i],c) != NULL)return false;
36         if(!strcmp(result[i],"up"))
37             if(strchr(right[i],c) == NULL)return false;
38         if(!strcmp(result[i],"down"))
39             if(strchr(left[i],c) == NULL)return false;
40     }
41     return true;
42 }
43
44 bool isheavy(char c)
45 {
46     for(int i = 0;i < 3;i++){
47         if(!strcmp(result[i],"even"))
48             if(strchr(left[i],c) != NULL || strchr(right[i],c) != NULL)return false;
49         if(!strcmp(result[i],"up"))
50             if(strchr(left[i],c) == NULL)return false;
51         if(!strcmp(result[i],"down"))
52             if(strchr(right[i],c) == NULL)return false;
53     }
54     return true;
55 }
56

Johnnx 2009-07-18 14:09 发表评论

POJ grids 2977

Johnnx — Sat, 18 Jul 2009 06:02:00 GMT

http://poj.grids.cn/problem?id=2977

题目是要求三个生理周期高峰出现在同一天的旉��Q�即三个数的最��公倍数�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 1 #include<stdio.h>
2 int p,e,j,d;
3 int main()
4 {
5     int k = 1;
6     int i;
7     while(scanf("%d%d%d%d",&p,&e,&j,&d) != EOF && p != -1){
8         for(i = d+1;i < 21252;++i)
9             if((i-p)%23 == 0)break;
10         for(;i < 21252;i+=23)
11             if((i-e)%28 == 0)break;
12         for(;i < 21252;i+=23*28)
13             if((i-j)%33 == 0)break;
14         printf("Case %d: the next triple peak occurs in %d days.\n",k++,i-d);
15     }
16     return 0;
17 }
18

Johnnx 2009-07-18 14:02 发表评论

POJ 1068

Johnnx — Sat, 04 Jul 2009 11:53:00 GMT

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

�q�道题目是一道模拟题。P-sequence表示�W�i�?#8216;)’之前有几�?#8216;(’�Q�W(xu��)-sequence表示�W�i�?#8216;()’包含几对‘()’�Q�要求对应P的W。题目中没有要输出S�Q�故‘(’‘)’可以分别�?�Q?来代�ѝ��根据P可以��L��知道‘)’的位�|�：(x��)location = p[i] + i。用value记录w[i]的��|��用flag记录括号是否成对�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 int t,n;
5 int s[41],p[21],w[21];
6 int main()
7 {
8     scanf("%d",&t);
9     while(t--){
10         scanf("%d",&n);
11         int temp,flag,value;
12         memset(s,0,sizeof(s));
13         for(int i = 0;i < n;++i){
14             scanf("%d",&p[i]);
15             temp = p[i] + i;
16             s[temp] = 1;
17             for(int k = temp-1,value = 1,flag = 0;k >= 0;--k){
18                 if(s[k] == 0 && flag == 0){
19                     w[i] = value;
20                     break;
21                 }
22                 else if(s[k] == 1){
23                     value++;
24                     flag++;
25                 }
26                 else if(s[k] == 0)flag--;
27             }
28         }
29         for(int i = 0;i < n;++i)printf("%d ",w[i]);
30         printf("\n");
31     }
32     system("pause");
33     return 0;
34 }
35

code

Johnnx 2009-07-04 19:53 发表评论

POJ 1008

Johnnx — Fri, 03 Jul 2009 14:28:00 GMT

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

�q�是一道关于历法�{换的问题。从�q�道题我得到2�Ҏ(gu��)��P��(x��)一、题目中月䆾或者日期是用字�W�串来表�C�的�Q�这时利用二位数�l�可以轻村֮��C��字符串到数字的�{换；二、Tzolkin中的日期和月数是�怺�独立的，可分别取余�?/div>

另外�Q�我觉得很重要的一点就是，一定要清楚题目是从0�Q�还是从1开始数的，�q�且在取余时候关于这斚w��一定要保持头脑清醒。很�Ҏ(gu��)��出错�?div style="background-color: rgb(238, 238, 238); font-size: 13px; border-left-color: rgb(204, 204, 204); padding-right: 5px; padding-bottom: 4px; padding-left: 4px; padding-top: 4px; width: 98%; word-break: break-all; "> 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 int n;
5 char haabmonth[19][10] = {"pop","no","zip","zotz","tzec","xul","yoxkin","mol","chen","yax","zac","ceh","mac","kankin","muan","pax","koyab","cumhu","uayet"};
6 char tzolkinday[20][10] = {"imix","ik","akbal","kan","chicchan","cimi","manik","lamat","muluk","ok","chuen","eb","ben","ix","mem","cib","caban","eznab","canac","ahau"};
7 int day;
8 char month[10];
9 int year;
10 int main()
11 {
12     scanf("%d",&n);
13     printf("%d\n",n);
14     for(int i = 0;i < n;++i){
15         scanf("%d. %s %d",&day,month,&year);
16         int days;
17         for(int k = 0;k < 19;++k){
18             if(!strcmp(haabmonth[k],month)){
19                 days = year * 365 + k * 20 + day;
20                 break;
21             }
22         }
23         int m = days % 260;
24         printf("%d %s %d\n",m%13+1,tzolkinday[m%20],days/260);
25     }
26     system("pause");
27     return 0;
28 }
29

code

Johnnx 2009-07-03 22:28 发表评论

亚洲欧洲在线观看,国产日韩亚洲欧美综合,亚洲国产精品尤物yw在线观看

POJ 2528�Q�线�D�|��(w��i)+���L��化）

NKOJ 1007,1249

POJ grids 1664

NKOJ 1019

NKOJ 1002

POJ grids 2692

POJ grids 2977

POJ 1068

POJ 1008

POJ 2528�Q�线�D�|��(w��i)+��L��化）