CTU Open Contest 2019 ABF题解

链接：https://www.jisuanke.com/contest/7321?view=challenges

A Beer Barrels

题意：用A和B组成一个有K位的数字，求里面出现了多少个C

思路：用组合数求解，求组合数的时候就用最简单的方法初始化就可以了。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 const int N = 1010;
 8 const int mod = 1e9 + 7;
 9 long long C[N][N];
10 
11 void init()
12 {
13     for (int i = 0; i < N; i ++ )
14         for (int j = 0; j <= i; j ++ )
15             if (!j) C[i][j] = 1;
16             else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
17 }
18 
19 int main(){
20     int a, b, k, c;
21     cin>>a>>b>>k>>c;
22     init();
23     long long sum = 0;
24     if(a != c && b != c){
25         cout<<0<<endl;
26         return 0;
27     }
28     else if((a == c && b != c)||(a != c && b == c)){
29         for(long long i = 0; i <= k; i ++ ){
30             sum = (sum + C[k][i] * i % mod) % mod;
31         }
32         cout<<sum<<endl;
33         return 0;
34     }
35     else if(a == c && b == c){
36         cout<<k<<endl;
37         return 0;
38     }
39 }

View Code

题意：有一种语言用来记账，格式如题，读输入，输出该格式下的总金额

思路：把格式化到最后可得：bill = (dig_1_9 dig_0_9…，-|… 或 |… ）（bill）

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 int main(){
 8     char c[1010];
 9     char str[2];
10     long long sum = 0;
11     while(scanf("%s", c) != EOF){
12         //gets(str);
13         int flag = 0;
14         int num = c[0] - '0';
15         if(c[0] != 124){
16             int i;
17             for(i = 1; c[i] != ','; i ++){
18                 num = num * 10 + c[i] - '0';
19             }
20             i += 2;
21             while(c[i] == 124)
22                 flag ++, i ++;
23             sum += num * flag;
24         }
25         else {
26             flag = strlen(c);
27             sum += flag * 42;
28         }
29     }
30     if(sum % 10 != 0)
31         sum = (sum / 10 + 1) * 10;
32     cout<<sum<<",-"<<endl;
33     return 0;
34 }

View Code

F Beer Marathon

题图突然放不上来，链接：https://nanti.jisuanke.com/t/43512

参考了题解

题意：有n个啤酒摊，要求任意两个相邻啤酒摊的距离等于给出的k值，求啤酒摊移动的总距离最少是多少

思路：二分

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 const int N = 1e6 + 10;
 8 typedef long long ll;
 9 ll a[N], n, k;
10 
11 ll cal(ll w){
12     ll ans = 0;
13     for(ll i = 0; i < n; i ++){
14         ans += abs(a[i] - w);
15         w += k;
16     }
17     return ans;
18 }
19 
20 int main(){
21     scanf("%lld %lld", &n, &k);
22     for(ll i = 0; i < n; i ++ )
23         scanf("%lld", &a[i]);
24     sort(a, a + n);
25     ll l = -1e12, r = 1e12, mid = 0, L, R, ans1, ans2, ans = 1e18;
26     for(int i = 0; i < 100; i ++){
27         mid = (l + r) / 2;
28         L = (mid + l) / 2;
29         R = (mid + r) / 2;
30         ans1 = cal(L);
31         ans2 = cal(R);
32         if(ans1 < ans2)
33             r = R;
34         else l = L;
35         ans = min(ans, min(ans1, ans2));
36     }
37     printf("%lld
", ans);
38     return 0;
39 }

View Code