SDUTTeam172 Summer Training Practice #3

Cloned from: UESTC Summer Training #13 Division II

题目来源： Andrés Mejía-Posada, May 2012

(UVA 12461—12470)

题目依旧略水，大部分都是数学题，推公式、求概率、算约数、矩阵幂模……

PrombleA UVA 12461 Airplane

题目大意：一共有n个人和n个座位，第一个人不记得自己的座号了，他会随机坐在一个座位上，以后的人都记得自己的座号，如果他的位置被占了，他就会随机坐在一个座位上，否则就坐在自己的座位上，让求第n个人座位被占的概率。

其实，不管有多少人，第n个人座位被占的概率都是1/2(自己证明吧)

代码：

View Code

1 #include <stdio.h>
2 int main()
3 {
4     int a;
5     while(~scanf("%d",&a))
6     {
7         if(a==0)
8             break;
9         puts("1/2");
10     }
11     return 0;
12 }

ProblemC UVA 12463 Little Nephew

题目大意：有一个小孩，有a件帽子，b件上衣，c件裤子，d双袜子，e双鞋，袜子每只都不一样，袜子不分左右脚，鞋分左右脚。问一共有多少种搭配。

搭配数：a*b*c*d^2*e^2

代码：

View Code

1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 int main()
5 {
6     int a,b,c,d,e,s;
7     while(~scanf("%d%d%d%d%d",&a,&b,&c,&d,&e))
8     {
9         if(a==0&&b==0&&c==0&&d==0&&e==0)
10             break;
11         s=a*b*c*e*e*d*d;
12         printf("%d\n",s);
13     }
14     return 0;
15 }

ProblemD UVA 12464 Professor Lazy,ph.D.

找规律，cz的代码：

View Code

1 #include <stdio.h>
2 #include <string.h>
3 int main()
4 {
5     long long  a,b,n;
6     while(scanf("%lld%lld%lld",&a,&b,&n)!=EOF)
7     {
8         if(!a&&!b&&!n) break;
9         n = n%5;
10         if(n == 0)
11         printf("%lld\n",a);
12         else if(n == 1)
13         printf("%lld\n",b);
14         else if(n == 2)
15         printf("%lld\n",(1+b)/a);
16         else if(n == 3)
17         printf("%lld\n",(1+a+b)/a/b);
18         else if(n == 4)
19         printf("%lld\n",(a+1)/b);
20     }
21     return 0;
22 }

ProblemE UVA 12465 The Turanga Leela Problem

约数问题，cz的代码：

View Code

1 #include <stdio.h>
2 #include <string.h>
3 #include <math.h>
4 #define eps 0.00000001
5 int p[100001],o[4001],k[4000];
6 int main()
7 {
8     long long a,b,sum;
9     int i,j,n,z;
10     n = (int)sqrt(1000000002+eps);
11     for(i = 2; i <= n; i ++)
12     {
13         if(p[i] == 0)
14         {
15             for(j = i+i; j <= n; j += i)
16                 p[j] = 1;
17         }
18     }
19     j = 1;
20     for(i = 2; i <= n; i ++)
21     {
22         if(!p[i])
23         {
24             o[j] = i;
25             j ++;
26         }
27     }
28     while(scanf("%lld%lld",&a,&b)!=EOF)
29     {
30         if(a == 0&&b == 0)
31             break;
32         memset(k,0,sizeof(k));
33         if(a - b < 0)
34             a = b - a;
35         else
36             a = a - b;
37         if(a == 1)
38         {
39             printf("1\n");
40             continue;
41         }
42         z = 1;
43         for(i = 1; i <= j-1; i ++)
44         {
45             if(a%o[i] == 0)
46             {
47                 a = a/o[i];
48                 k[i] ++;
49                 z = 0;
50                 break;
51             }
52         }
53         if(z)
54             printf("2\n");
55         else
56         {
57             sum = 1;
58             while(a > 1)
59             {
60                 z = 1;
61                 for(i = 1; i <= j-1; i ++)
62                 {
63                     if(a%o[i] == 0)
64                     {
65                         a = a/o[i];
66                         k[i] ++;
67                         z = 0;
68                         break;
69                     }
70                 }
71                 if(z)
72                 {
73                     sum = 2;
74                     break;
75                 }
76             }
77             for(i = 1; i <= j-1; i ++)
78             {
79                 if(k[i] != 0)
80                     sum *= k[i]+1;
81             }
82             printf("%lld\n",sum);
83         }
84     }
85     return 0;
86 }

ProblemG UVA 12467 Secret Word

KMP，scf的代码：

View Code

1 #include<stdio.h>
2 #include<string.h>
3 char c1[1000011],c2[1000011];
4 int next[1000011];
5 int kmp()
6 {
7     int k = strlen(c1),i,j,y = -1;
8     memset(next,0,sizeof(next));
9     next[0] = -1;
10     for(i = 1; i < k ;i ++)
11     {
12         while(y>-1&&c1[i]!=c1[y+1])
13             y = next[y];
14         if(c1[y+1]==c1[i])
15             y++;
16         next[i] = y;
17     }
18     int max = -1;
19     y = -1;
20     for(i = 0 ; i < k ; i++)
21     {
22         while(y>-1&&c2[i]!=c1[y+1])
23         y = next[y];
24         if(c1[y+1]==c2[i])
25         {
26             y++;
27             if(max<y)
28             max = y;
29         }
30     }
31     return max;
32 }
33 int main()
34 {
35     int t,n,m,i,j,k;
36     scanf("%d%*c", &t);
37     while(t--)
38     {
39         gets(c1);
40         k = strlen(c1);
41         for(i =0 ;i <= k-1 ;i++)
42         {
43             c2[i] = c1[k-i-1];
44         }
45         n = kmp();
46         for(i = n ; i >= 0 ; i--)
47             printf("%c", c1[i]);
48         puts("");
49     }
50     return 0;
51 }

ProblemH UVA 12468 Zapping

没看，scf的代码：

View Code

1 #include <stdio.h>
2 #include <stdlib.h>
3
4 int main()
5 {
6     int a,b,min,x,y;
7     while(scanf("%d%d",&a,&b)!=EOF)
8     {
9         if(a==-1&&b==-1)
10         break;
11         if(b>a)
12         {
13             x = b-a;
14             y = a+100-b;
15             if(x<y)
16             min = x;
17             else
18             min = y;
19         }
20         else
21         {
22             x = a-b;
23             y = 100-a+b;
24             if(x<y)
25             min = x;
26             else
27             min = y;
28         }
29         printf("%d\n",min);
30     }
31     return 0;
32 }