C++博客-Keep Walking

COJ入门50题

刘聪 — Sun, 20 Nov 2011 00:35:00 GMT

模拟（8）

1002 1056 1161 1176 1177 1178 1179

枚举（4）

1018 1012 1174 1175

简单计算（6）

1000 1001 1005 1006 1108 1173

数学推导（3）

1156 1158 1159

贪心（2）

1153 1163

排序（6）

1035 1040 1091 1101 1110 1118

高精度（1）

1112

字符串处理（10）

1028 1029 1073 1074 1089 1094 1105 1120 1157 1180

难度分类：

淡蓝色（一目了然的水题）

紫色（需要点技巧、公式的水题）

绿色（需要点算法，代码稍复杂）

刘聪 2011-11-20 08:35 发表评论

COJ题型和难度全总结（DreamFox版）

刘聪 — Sun, 20 Nov 2011 00:27:00 GMT

COJ全总结

(更新至1295)

模拟

1002 1017 1037 1044 1056 1071 1076 1100 1111 1119 1043

1051 1054 1059 1068 1069 1075 1099 1128 1136 1140 1149

1160 1151 1161 1176 1177 1178 1179 1237 1246 1250 1273 1279

枚举

1018 1012 1024 1031 1059 1097 1174 1175 1181 1080 1082 1086 1226 1235 1255 12661277 1279 1289 1291

简单计算

1000 1001 1005 1006 1007 1008 1014 1015 1010 1011 1020 1027

1030 1034 1047 1052 1060 1090 1107 1108 1109 1114 1117 1162

1173 1080 1083 1167 1204 1233 1244 1272 1278 1288 1290 1294

数论

1016 1041 1042 1053 1057 1106 1113 1116 1071 1076 1013 1154 1156 1158 1159 11611171 1086 1213 1215 (1222 1223 1224)(快速幂) 1225(欧几里得) 1243 1254 1263 1268 12761282 1287

组合数学

1230 1232 1242 1247 1249 1270

几何

1045 1092 1096 1098 1134（凸包） 1256(凸包）1265

搜索

1021 1061 1033 1058 1102 1124 1126 1129 1138 1139 1141 1146 1148 1155 1165

1187 1188 1189 1190 10781218 1221 1245 1255 1277

贪心

1127 1130 1135 1153 1163 1087 1088 1168 1231 1240 1252 1258 1262 1264

动态规划

1003（01背包）

1009、1032、1049、1050、1183（最长不降（升）子序列）

1026 1063 1097 1103 1121 1125 1135 1142

1184 1185 1186 1072 1079 1081 1217 1227 1234 1257(背包) 1261 1268 1269 1274 1281(记忆化搜索)

构造

1022 1041 1097 1271 1274

排序

1035 1040 1046 1091 1101 1110 1115（堆） 1118 1084 1239

高精度

1019 1067 1112 1004 1224 1247 1275

字符串处理

1023 1025 1028 1029 1038 1039 1055 1073 1074 1089 1094 1104 1105 1120 1147 1157 1180 1185 1201（KMP） 1202(KMP） 1203（后缀数组）1200 1236 1238 1248(KMP) 12671280 1283 1292 1293

简单递归

1013 1062 1093 1095 1166 1270 1294

高级数据结构（图论等）

1036(最小生成树） 1077（最短路）1123（线段树）1131 1132（简单字典树）1133（最小生成树)

1144（floyd）1145（网络最大流）1150（树同构）1164（矩阵快速幂）

1191（最小生成树） 1192 （最短路）1193（连通图）1194（二分图匹配） 1195（二分图匹配）

1172(树状数组) 1196(并查集）1197（字典树） 1198（线段树） 1199（堆） 1219（线段树）1228(并查集) 1241(floyd) 1245(floyd+拓扑排序) 1253（并查集）1264（堆||优先队列） 1265 1269（线段树||RMQ) 1284

二分查找&分治(二分答案)

1048 1179 1080 1086 1087 1152 1216 1220 1251 1261 1263

博弈

1214 1259 1260 1295

未知

1122 1143 1229(正则表达式) 1286

难度分类：

淡蓝色（一目了然的水题）

紫色（需要点技巧、公式的水题）

绿色（需要点算法，代码稍复杂）

橙色（较高级的算法）

红色（麻烦题,有可能难也有可能不太难）

注：所有分类仅供参考，很多题有多种解法，编者不一定能统计完整。

刘聪 2011-11-20 08:27 发表评论

COJ 1044 扫雷

刘聪 — Thu, 17 Nov 2011 12:53:00 GMT

1 #include <cstdlib>
2 #include <iostream>
3
4
5 using namespace std;
6
7 char b[11][11],c[11][11];
8 int main(int argc, char *argv[])
9 {
10     int n,i,j,k,loss=0;
11
12     scanf("%d",&n);
13     for(i=0;i<n;i++)
14     {
15         scanf("%s",b[i]);
16     }
17     for(i=0;i<n;i++)
18     {
19         scanf("%s",c[i]);
20     }
21
22
23     for(i=0;i<n;i++)
24     {
25         for(j=0;j<n;j++)
26         {
27             if((c[i][j]=='+')&&(b[i][j]!='*'))
28             {
29                 k=0;
30                 if(i-1>=0&&b[i-1][j]=='*')
31                 {           k++;
32                 }
33                 if(i+1<n&&b[i+1][j]=='*')
34                 {              k++;
35                 }
36                 if(j-1>=0&&b[i][j-1]=='*')
37                 {           k++;
38                 }
39                 if(j+1<n&&b[i][j+1]=='*')
40                 {           k++;
41                 }
42                 if(i-1>=0&&j-1>=0&&b[i-1][j-1]=='*')
43                 {           k++;
44                 }
45                 if(i+1<n&&j+1<n&&b[i+1][j+1]=='*')
46                 {          k++;
47                 }
48                 if(i-1>=0&&j+1<n&&b[i-1][j+1]=='*')
49                 {         k++;
50                 }
51                 if(i+1<n&&j-1>=0&&b[i+1][j-1]=='*')
52                 {           k++;
53                 }
54                 b[i][j]=k+'0';
55             }else if((c[i][j]=='+')&&(b[i][j]=='*'))
56                      loss=1;
57                 //printf("%c",b[i][j]);
58         }
59         //
60     }
61
62     for(i=0;i<n;i++)
63     {
64         for(j=0;j<n;j++)
65         {
66             if(!loss)
67             {
68                 if(b[i][j]=='*')
69                     printf("#");
70                 else
71                     printf("%c",b[i][j]);
72             }
73             else
74                 printf("%c",b[i][j]);
75         }
76         printf("\n");
77     }
78
79     system("PAUSE");
80     return EXIT_SUCCESS;
81 }
82

刘聪 2011-11-17 20:53 发表评论

COJ 1043 数根

刘聪 — Wed, 16 Nov 2011 14:33:00 GMT

1 #include <cstdlib>
2 #include <iostream>
3
4 using namespace std;
5
6 int main(int argc, char *argv[])
7 {
8     int n,a,b;
9     while(scanf("%d",&n)&&!(n==0))
10     {
11
12         do
13         {   a=0;
14             while(n!=0)
15             {
16                 a+=n%10;
17                 n/=10;
18             }
19             n=a;
20
21         }while(a/10!=0);
22         printf("%d\n",a);
23     }
24
25
26     system("PAUSE");
27     return EXIT_SUCCESS;
28 }
29

刘聪 2011-11-16 22:33 发表评论

COJ 1060 一元多项式的求导

刘聪 — Wed, 09 Nov 2011 11:05:00 GMT

1 #include <cstdlib>
2 #include <iostream>
3
4 using namespace std;
5
6
7 int main(int argc, char *argv[])
8 {
9     int t,s,a[100],n=0,i,j,k;
10     i=0;
11     while(scanf("%d%d",&a[i],&a[i+1])&&!(a[i]==-1&&a[i+1]==-1))
12     {
13
14
15         a[i]*=a[i+1];a[i+1]-=1;
16         i+=2;
17     }
18
19     n=i;
20     for(i=0;i<n;i+=2)
21     {
22         k=i+1;
23         for(j=i;j<n;j+=2)
24         {
25             if(a[k]<a[j+1])
26                 k=j+1;
27         }
28         if(k!=i)
29         {
30             t=a[k];
31             a[k]=a[i+1];
32             a[i+1]=t;
33
34             t=a[k-1];
35             a[k-1]=a[i];
36             a[i]=t;
37
38         }
39         if(a[0]==0)
40         {
41             cout<<a[0];
42             break;
43         }
44         if(a[i]!=0)
45         {
46             cout<<a[i]<<" "<<a[i+1]<<" ";
47         }
48
49     }
50     cout<<endl;
51
52     system("PAUSE");
53     return EXIT_SUCCESS;
54 }
55

刘聪 2011-11-09 19:05 发表评论

COJ 1039 Hidden CUGB 感谢某银

刘聪 — Tue, 08 Nov 2011 14:36:00 GMT

1 #include <cstdlib>
2 #include <iostream>
3 using namespace std;
4
5
6 int main(int argc, char *argv[])
7 {
8     int n,i,j,k;
9     char str[100], a[] = "CUGB";
10
11     scanf("%d",&n);
12     for(i=1;i<=n;i++)
13     {
14         memset(str,0,sizeof(str));
15         scanf("%s",str);
16         j=0;k=0;
17         while(str[j]!='\0')
18         {
19             if((str[j]==a[k])&&(a[k]!='\0'))
20             {
21                 k++;
22             }
23             j++;
24
25         }
26         if((a[k]=='\0')&&(j>4))
27         {
28             cout<<"Case "<<i<<": Yes"<<endl;
29         }
30         else
31             cout<<"Case "<<i<<": No"<<endl;
32     }
33
34     system("PAUSE");
35     return EXIT_SUCCESS;
36 }
37

刘聪 2011-11-08 22:36 发表评论

COJ 1180 查找子串 COJ 1073 COJ 1074

刘聪 — Mon, 07 Nov 2011 11:50:00 GMT

1 #include <cstdlib>
2 #include <iostream>
3
4 using namespace std;
5
6
7 int main(int argc, char *argv[])
8 {
9     char a[30], b[30];
10     int i,j,k,m;
11     cin>>a>>b;
12     k=0;
13     while(b[k]!='\0')
14         k++;
15     //cout<<"k="<
16     i=0;j=0;m=0;
17     while(a[i]!='\0')
18     {
19         //cout<
20         if((a[i]==b[j])&&b[j]!='\0')
21         {
22            i++;j++;m++;
23         }
24         else
25         {
26             i=i-m+1;j=0;m=0;
27         }
28
29         if(j==k)
30         {
31             cout<<(i-k)<<endl;
32             break;
33         }
34     }
35     if(j!=k)
36         cout<<"-1"<<endl;
37
38     system("PAUSE");
39     return EXIT_SUCCESS;
40 }
41

COJ 1073 相对改进了些

1 #include <cstdlib>
2 #include <iostream>
3 using namespace std;
4
5 char a[101], b[101];
6 int main(int argc, char *argv[])
7 {
8     int n,i,j,k;
9
10     scanf("%s%s",a,b);
11     i=0;j=0;k=0;
12     while(b[i]!='\0')
13     {
14
15         if((b[i]==a[j])&&(a[j]!='\0'))
16         {
17             i++;j++;k++;
18         }
19         else
20         {
21             i=i-k+1;j=0;k=0;
22         }
23         if(a[j]=='\0')
24         {
25             cout<<"YES"<<endl;
26             break;
27         }
28
29     }
30     if(a[j]!='\0')
31     {
32         cout<<"NO"<<endl;
33     }
34
35     system("PAUSE");
36     return EXIT_SUCCESS;
37 }
38

COJ 1074

1 #include <cstdlib>
2 #include <iostream>
3
4 using namespace std;
5
6
7 int main(int argc, char *argv[])
8 {
9     int n,i,j,k;
10     char s[100],t[100];
11     scanf("%s%s",s,t);
12     i=0;j=0;k=0;
13     while(s[i]!='\0')
14     {
15         if(t[j]!='\0')
16         {
17             if(s[i]==t[j])
18             {
19                 i++;j++;k++;
20             }
21             else
22             {
23                 i=i-k+1;j=0;k=0;
24             }
25         }
26         else//(t[j]=='\0')
27         {
28             printf("%d\n",i-k);
29             break;
30         }
31     }
32
33
34     system("PAUSE");
35     return EXIT_SUCCESS;
36 }
37

刘聪 2011-11-07 19:50 发表评论

COJ 1056 【数据结构】约瑟夫（Josephus）问题

刘聪 — Mon, 07 Nov 2011 10:12:00 GMT

1 #include <cstdlib>
2 #include <iostream>
3 #include <cstring>
4
5 using namespace std;
6
7 int a[10000];
8 int main(int argc, char *argv[])
9 {
10     int m,n,i,j,k,r;
11     //cin>>m>>n;
12     while (scanf("%d%d",&m,&n)&&!(m==0&&n==0))
13     {
14
15         for(i=0;i<=m;i++)
16             a[i]=i;
17         r=0;k=0;i=1;
18         while(r<m-1)
19         {
20
21             if(a[i]!=0)k++;
22             if(k==n)
23             {
24
25                 //cout<
26                 a[i]=0;
27                 k=0;
28                 r++;
29     //            for(j=1;j<=m;j++)
30     //                cout<
31             }
32             i++;
33             if(i==(m+1))i=1;
34         }
35         i=0;
36         while(a[i]==0)
37             i++;
38         cout<<a[i]<<endl;
39
40     }
41     system("PAUSE");
42     return EXIT_SUCCESS;
43 }
44

刘聪 2011-11-07 18:12 发表评论

质因数分解源代码

刘聪 — Sun, 06 Nov 2011 10:04:00 GMT

1 main()
2 {
3 int n,i;
4 printf("\nplease input a number:\n");
5 scanf("%d",&n);
6 printf("%d=",n);
7 for(i=2;i<=n;i++)
8  {
9   while(n!=i)
10   {
11    if(n%i==0)
12    { printf("%d*",i);
13     n=n/i;
14    }
15    else
16     break;
17   }
18 }
19 printf("%d",n);}
20 }

刘聪 2011-11-06 18:04 发表评论

COJ 1019 高精度阶乘 S=1！+2！+3！+…+n！（n≤50）可以看作是 1067的深化，但是我不明白为什么我要用long long 来定义数组，好像有点浪费

刘聪 — Mon, 31 Oct 2011 12:14:00 GMT

因为要反复求解某数的阶乘，所以求解之前要记得使用memset将数组清零

#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    long long a[30000],b[30000];
    void jiecheng(int n, long long *a);
    int n,i,j,carry;
    cin>>n;
    memset(a,0,sizeof(a));
    jiecheng(n,a);
    for(i=n-1;i>0;i--)
    {
        carry=0;memset(b,0,sizeof(b));
        jiecheng(i,b);
        for(j=1;j<=a[0];j++)
        {
            a[j]+=b[j]+carry;
            carry =a[j]/10;
            a[j]=a[j]%10;
        }
        while(carry)
        {
            a[0]++;
            a[j]=carry%10;
            carry/=10;
            j++;
        }
    }
    for(i=a[0];i>0;i--)
        cout<<a[i];
    cout<<endl;

    system("PAUSE");
    return 0;
}

void jiecheng(int n, long long *a)
{
    long long carry,i;
    int j;

    for(i=1;i<=n;i++)
    {
        carry=0;
        if(i==1)
        {
            a[0]=1;a[1]=1;
        }
        else
        {
           for(j=1;j<=a[0];j++)
           {
                a[j]=i*a[j]+carry;
                carry = a[j]/10;
                a[j]=a[j]%10;
           }
           while(carry)
            {
                a[0]++;
                a[j]=carry%10;
                carry/=10;
                j++;
            }
        }
    }
    /*for(i=a[0];i>0;i--)
        cout<     cout<*/
}

刘聪 2011-10-31 20:14 发表评论