您的位置: 首页 > IT文章 > CCPC 2017-2018, Finals Solution

CCPC 2017-2018, Finals Solution

分类: IT文章 • 2025-01-09 08:33:51

A - Dogs and Cages

水。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int t;
 5 double n;
 6 
 7 int main()
 8 {
 9     scanf("%d", &t);
10     for (int kase = 1; kase <= t; ++kase)
11     {
12         scanf("%lf", &n);
13         printf("Case #%d: %.10f
", kase, n - 1);
14     }
15     return 0;
16 }

View Code

B - Same Digit

留坑。

C - Rich Game

题意：有两个人，A可以控制输赢，但是没有钱，B有无限的钱，他们打羽毛球，至少要获得11个点并且要比对方至少多获得两个点才能赢下当局，如果A 赢了一个点，A要给B Y元，否则 B 给A X 元求他们一共打K局的情况下，A最多可以赢多少局

思路：显然，当x > y 的时候可以赢k局

考虑 x <= y 的情况根据贪心的思路，假设A 要输 t 局

那么必然要满足 $11yt >= (k - t)(11y - 9x)$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int t, x, y, k;
 5 
 6 int main()
 7 {
 8     scanf("%d", &t);
 9     for (int kase = 1; kase <= t; ++kase)
10     {
11         printf("Case #%d: ", kase);
12         scanf("%d%d%d", &x, &y, &k);
13         if (x > y) printf("%d
", k);
14         else
15         {
16             int t = (int)ceil(k * (11 * y - 9 * x) * 1.0 / (11 * y + 2 * x));
17             printf("%d
", k - t);
18         }
19     }
20     return 0;
21 }

View Code

D - Mr. Panda and Circles

留坑。

E - Evil Forest

水。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 
 6 int t, n, sum, num;
 7 
 8 int main()
 9 {
10     scanf("%d", &t);
11     for (int kase = 1; kase <= t; ++kase)
12     {
13         scanf("%d", &n); sum = 0;
14         for (int i = 1; i <= n; ++i)
15         {
16             scanf("%d", &num);
17             sum += num;
18             sum += (num % 10) ? (num / 10) + 1 : (num / 10);
19         }
20         printf("Case #%d: %d
", kase, sum);
21     }
22     return 0;
23 }

View Code

F - Fair Lottery

留坑。

G - Alice’s Stamps

题意：给出M个区间，选择K个区间，使得选择的元素尽量多，区间可以交叉

思路：$dp[i][j]$ 表示第i位，选择k个区间的时候，数量最多是多少

三个状态转移

$dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])$

$dp[i][j +1] = max(dp[i][j], dp[i][j + 1])$

$dp[i + cnt][j + 1] = max(dp[i + cnt][j], dp[i][j] + cnt)$

cnt 为那个区间最长能到哪里

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define N 2010
 6 
 7 int dp[N][N];
 8 
 9 struct node{
10     int l, r;
11     inline node(){}
12     inline node(int l, int r) :l(l), r(r){}
13     inline bool operator < (const node &b) const
14     {
15         return l == b.l ? r > b.r : l < b.l;
16     }
17 }arr[N];
18 
19 int n, m, k;
20 int cnt, val;
21 
22 int main()
23 {
24     int t;
25     scanf("%d",&t);
26     for(int cas = 1; cas <= t; ++cas)
27     {
28         scanf("%d %d %d" , &n, &m, &k);
29         for(int i = 1; i <= m; ++i)
30         {
31             scanf("%d %d", &arr[i].l, &arr[i].r);
32         }
33         sort(arr + 1, arr + 1 + m);
34         memset(dp, 0, sizeof dp);
35         val = 0;
36         cnt = 1;
37         for(int i = 0; i < n; ++i)
38         {
39             while(cnt <= m && arr[cnt].l == i + 1)
40             {
41                 val = max(val, arr[cnt].r - arr[cnt].l + 1);
42                 cnt++;
43             }
44             for(int j = 0; j <= k; ++j)
45             {
46                 dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
47                 dp[i][j + 1] = max(dp[i][j], dp[i][j + 1]);
48                 dp[i + val][j + 1] = max(dp[i + val][j + 1], dp[i][j] + val);
49             }
50             if(val) --val;
51         }
52         printf("Case #%d: %d
", cas, dp[n][k]);
53     }
54     return 0;
55 }

View Code

H - Equidistance

留坑。

I - Inkopolis

留坑。

J - Subway Chasing

留坑。

K - Knightmare

题意：在无限大的棋盘上，马走日，有多少个点是能够走到的

思路：BFS找规律，二阶差分

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ull unsigned long long
 5 
 6 int arr[] = {1, 9, 41, 109, 205, 325, 473};
 7 
 8 int t;
 9 ull n;
10 
11 int main()
12 {
13     scanf("%d", &t);
14     for (int kase = 1; kase <= t; ++kase)
15     {
16         printf("Case #%d: ", kase);
17         scanf("%llu", &n);
18         if (n <= 6) printf("%d
", arr[n]);
19         else
20         {
21             ull sum = 473; n -= 6;
22             sum += (ull)148 * n + (ull)14 * n * (n + 1);
23             printf("%llu
", sum);
24         }
25     }
26     return 0;
27 }

View Code

CCPC 2017-2018, Finals Solution

相关推荐