2016 Al-Baath University Training Camp Contest-1

2016 Al-Baath University Training Camp Contest-1

A题：http://codeforces.com/gym/101028/problem/A

题意：比赛初始值是1500，变化了几次，得到的正确结果和bug后的是否相等。（Tourist大佬好 Y(^o^)Y）

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int t;
 8     cin>>t;
 9     while(t--) {
10         int n,r;
11         cin>>n>>r;
12 
13         int sum = 1500;
14         for(int i=0;i<n;i++)
15         {
16             int x;
17             cin>>x;
18             sum+=x;
19         }
20 
21         if(sum==r)
22             puts("Correct");
23         else puts("Bug");
24 
25     }
26     return 0;
27 }

A. Codeforces Rating

B题：http://codeforces.com/gym/101028/problem/B

题意：b,p不分，i,e不分，大小写不分，看两个字符串是不是正确的。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 char str1[105],str2[105];
 6 
 7 int main()
 8 {
 9     int t;
10     cin>>t;
11     while(t--) {
12         scanf("%s%s",str1,str2);
13 
14         int len = strlen(str1);
15 
16         if(strlen(str1)!=strlen(str2)) {
17             puts("No");
18             continue;
19         }
20 
21         for(int i=0;i<len;i++)
22         {
23             if(str1[i]>='A'&&str1[i]<='Z')
24                 str1[i] = 'a' + str1[i] - 'A';
25 
26             if(str2[i]>='A'&&str2[i]<='Z')
27                 str2[i] = 'a' + str2[i] - 'A';
28         }
29 
30         bool flag = true;
31         for(int i=0;i<len;i++) {
32             if(str1[i]!=str2[i]) {
33                 if(str1[i]=='b'&&str2[i]=='p')
34                     continue;
35                 if(str1[i]=='p'&&str2[i]=='b')
36                     continue;
37                 if(str1[i]=='i'&&str2[i]=='e')
38                     continue;
39                 if(str1[i]=='e'&&str2[i]=='i')
40                     continue;
41                 flag = false;
42                 break;
43             }
44         }
45 
46         if(flag)
47             puts("Yes");
48         else puts("No");
49 
50 
51 
52     }
53     return 0;
54 }

B. Bonapity

C题：http://codeforces.com/gym/101028/problem/C

题意：已知A，B，求C有多少种情况满足这个式子：

比赛的时候，很多同学没有看到取模，用java干；

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int t;
 8     cin>>t;
 9     while(t--) {
10         int len;
11         cin>>len;
12         int a[105],b[105];
13         char stra[105],strb[105];
14         scanf("%s%s",stra,strb);
15         for(int i=0;i<len;i++)
16         {
17             a[i] = stra[i]-'0';
18             b[i] = strb[i]-'0';
19         }
20         unsigned long long ans = 1;
21         bool flag = true;
22         for(int i=0;i<len;i++) {
23             if(a[i]==0&&b[i]==0)
24                 continue;
25             if(a[i]==0&&b[i]==1)
26                 continue;
27             if(a[i]==1&&b[i]==0){
28                 flag = false;
29                 break;
30             }
31             if(a[i]==1&&b[i]==1)
32                 ans = ans*2%1000000007;
33         }
34         if(flag)
35             cout<<ans<<endl;
36         else puts("IMPOSSIBLE");
37     }
38 
39     return 0;
40 }

C. A or B Equals C

D题：http://codeforces.com/gym/101028/problem/D

题意：画图

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 char maps[105][105];
 6 
 7 int main()
 8 {
 9     int t;
10     scanf("%d",&t);
11     while(t--)
12     {
13         memset(maps,'.',sizeof(maps));
14 
15         int r,c,n;
16         cin>>r>>c>>n;
17 
18         while(n--)
19         {
20 
21             int r1, c1, r2, c2;
22             char x;
23             cin>>r1>>c1>>r2>>c2>>x;
24 
25             for(int i=r1; i<=r2; i++)
26             {
27                 for(int j=c1; j<=c2; j++)
28                 {
29                     maps[i][j] = x;
30                 }
31             }
32 
33 
34         }
35         for(int i=1; i<=r; i++)
36         {
37             for(int j=1; j<=c; j++)
38                 printf("%c",maps[i][j]);
39             puts("");
40         }
41 
42     }
43     return 0;
44 }

D. X and paintings

E题：http://codeforces.com/gym/101028/problem/E

题意：n个数的最大公约数

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int inf = 0x3f3f3f3f;
 6 
 7 int main()
 8 {
 9     int t;
10     int a[1005];
11     scanf("%d",&t);
12     while(t--) {
13         int minx = inf;
14         int n;
15         scanf("%d",&n);
16         for(int i=0;i<n;i++) {
17             scanf("%d",&a[i]);
18             minx = min(minx,a[i]);
19         }
20 
21         int k;
22         for(k=minx;k>=1;k--) {
23             bool flag = true;
24             for(int i=0;i<n;i++) {
25                 if(a[i]%k!=0) {
26                     flag = false;
27                     break;
28                 }
29             }
30             if(flag)
31                 break;
32         }
33         int num = 0;
34         for(int i=0;i<n;i++)
35             num+=(a[i]/k);
36         printf("%d %d
",k,num);
37 
38 
39     }
40     return 0;
41 }

E. Teams

F题：http://codeforces.com/gym/101028/problem/F

题意：字符串匹配（朴素匹配就ok了）

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 char str1[1005],str2[4];
  5 int main()
  6 {
  7     int t;
  8     cin>>t;
  9     while(t--)
 10     {
 11         scanf("%s%s",str1,str2);
 12         int len = strlen(str1);
 13 
 14         char op[4][3];
 15         memset(op,0,sizeof(op));
 16 
 17         for(int i=0; i<4; i++)
 18         {
 19             int k=0;
 20             for(int j=0; j<4; j++)
 21             {
 22                 if(i!=j)
 23                     op[i][k++] = str2[j];
 24             }
 25         }
 26 
 27         //   for(int i=0;i<4;i++) {
 28         //     for(int j=0;j<3;j++)
 29         //       printf("%c",op[i][j]);
 30         // puts("");
 31         // }
 32 
 33         bool good = false;
 34         for(int i=0; i<len-3; i++)
 35         {
 36             if(str1[i]==str2[0]&&str1[i+1]==str2[1]&&str1[i+2]==str2[2]&&str1[i+3]==str2[3])
 37             {
 38                 good = true;
 39                 break;
 40             }
 41         }
 42 
 43         if(good)
 44         {
 45             puts("good");
 46             continue;
 47         }
 48 
 49         bool al = false;
 50         for(int i=0; i<len-2; i++)
 51         {
 52             if(str1[i]==op[0][0]&&str1[i+1]==op[0][1]&&str1[i+2]==op[0][2])
 53             {
 54                 al = true;
 55                 break;
 56             }
 57         }
 58 
 59         if(al)
 60         {
 61             puts("almost good");
 62             continue;
 63         }
 64 
 65         al = false;
 66         for(int i=0; i<len-2; i++)
 67         {
 68             if(str1[i]==op[1][0]&&str1[i+1]==op[1][1]&&str1[i+2]==op[1][2])
 69             {
 70                 al = true;
 71                 break;
 72             }
 73         }
 74 
 75         if(al)
 76         {
 77             puts("almost good");
 78             continue;
 79         }
 80 
 81         al = false;
 82         for(int i=0; i<len-2; i++)
 83         {
 84             if(str1[i]==op[2][0]&&str1[i+1]==op[2][1]&&str1[i+2]==op[2][2])
 85             {
 86                 al = true;
 87                 break;
 88             }
 89         }
 90 
 91         if(al)
 92         {
 93             puts("almost good");
 94             continue;
 95         }
 96 
 97         al = false;
 98         for(int i=0; i<len-2; i++)
 99         {
100             if(str1[i]==op[3][0]&&str1[i+1]==op[3][1]&&str1[i+2]==op[3][2])
101             {
102                 al = true;
103                 break;
104             }
105         }
106 
107         if(al)
108         {
109             puts("almost good");
110             continue;
111         }
112 
113         puts("none");
114 
115     }
116     return 0;
117 }

F. Good Words

G题：http://codeforces.com/gym/101028/problem/G

题意：从左上角砸东西到目的地，途中碰壁。看可以不可以砸到目标。和省赛的球的碰撞类似。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int t;
 8     cin>>t;
 9     while(t--) {
10 
11         int h,w,d;
12         cin>>h>>w>>d;
13 
14         int x = (h-1)/(w-1); //x个单周期
15         int mod = (h-1)%(w-1);
16 
17         int md;
18         if(x%2==0)
19             md = 1 + mod;
20         else md = w - mod  ;
21 
22         if(md==d)
23             puts("Yes");
24         else puts("No");
25 
26     }
27     return 0;
28 }

G. The Tower of Evil

H题：http://codeforces.com/gym/101028/problem/H

做到这里的时候，脑子已经晕掉了，题目也没怎么看清楚。

题意：n长的河流，两个人的速度是d,r，在start的位置不标记，求第一次踩到对方标记的时间。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int v1[100005];
 6 int v2[100005];
 7 
 8 int main()
 9 {
10     int t;
11     cin>>t;
12     while(t--)
13     {
14         memset(v1,0,sizeof(v1));
15         memset(v2,0,sizeof(v2));
16         int n,d,r;
17         cin>>n>>d>>r;
18 
19         int ans = 1;
20         int td = d;
21         int tr = r;
22         v1[td] = 1;
23         v2[tr] = 1;
24         while(true)
25         {
26             if(v2[td]==true||v1[tr]==true)
27             {
28                 break;
29             }
30             ans++;
31             td = (td + d)%n;
32             tr = (tr + r)%n;
33             v1[td] = true;
34             v2[tr] = true;
35         }
36         printf("%d
",ans);
37 
38     }
39     return 0;
40 }

H. The Endless River

I题：http://codeforces.com/gym/101028/problem/I

题意：屋顶有漏洞，用k个布去补洞，其中最长的布，使其最短。

二分啊！

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int a[100005];
 6 int n,k;
 7 int maxx;
 8 bool calc(int x) {
 9     int cur = 0;
10     for(int i=0;i<k;i++) {
11         if(cur==0)
12             cur = cur + a[0] + x -1;
13         else {
14             for(int i=0;i<n;i++) {
15                 if(a[i]>cur)
16                 {
17                     cur = a[i];
18                     break;
19                 }
20             }
21             cur = cur + x -1;
22         }
23     }
24     if(cur>=a[n-1])
25         return true;
26     return false;
27 }
28 
29 int main()
30 {
31     int t;
32     cin>>t;
33     while(t--) {
34         cin>>n>>k;
35         for(int i=0;i<n;i++)
36             scanf("%d",&a[i]);
37         maxx = a[n-1];
38         int l=1;
39         int r=a[n-1]/k+1;
40         while(l<r) {
41             int m = (r+l)/2;
42             if(calc(m))
43                 r=m;
44             else l = m+1;
45         }
46         printf("%d
",l);
47     }
48     return 0;
49 }

I. March Rain

J题：http://codeforces.com/gym/101028/problem/J

题意：

一个数列a,他的最大的2ⁱ 的因子，由 i 组成的一个数列。

找一些a，他是递增的基础上，i 之和最大。

dp啊！

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int a[105];
 6 int as[105];
 7 int b[105];
 8 int dp[105];
 9 
10 int main()
11 {
12     int t;
13     cin>>t;
14     while(t--)
15     {
16         memset(b,0,sizeof(b));
17         memset(dp,0,sizeof(dp));
18 
19         int n;
20         cin>>n;
21         for(int i=0; i<n; i++) {
22             cin>>a[i];
23             as[i] = a[i];
24         }
25 
26         for(int i=0; i<n; i++)
27         {
28             while(as[i]%2==0)
29             {
30                 b[i]++;
31                 as[i] /=2;
32             }
33         }
34 
35         dp[0] = b[0];
36 
37         for(int i=1; i<n; i++)
38         {
39             int k = 0;
40             for(int j=0; j<i; j++)
41             {
42                 if(a[j]<a[i]&&k<dp[j])
43                 {
44                     k = dp[j];
45                 }
46             }
47             dp[i] = k+b[i];
48         }
49 
50         int ans = -1;
51         for(int i=0; i<n; i++)
52         {
53             ans = max(ans,dp[i]);
54         }
55         cout<<ans<<endl;
56 
57     }
58 
59     return 0;
60 }

J. X and Beasts

最后贴一下Rank.