首页 > 代码库 > Codeforces Round #382 (Div. 2)

Codeforces Round #382 (Div. 2)

2024-08-27 13:47:08   219人阅读

A. Ostap and Grasshopper(water)

题意：

给出一个字符串（n<=100），问从‘G’字符的位置可否每次只可恰好跳步长为k的一步（只可跳到非‘#’字符的位置且不可跳出字符串外），跳若干步到达‘T’字符的位置。

 

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n, k;
 6     char s[105];
 7     scanf("%d%d", &n, &k);
 8     scanf("%s", s);
 9     int sg, eg;
10     for(int i = 0; i < strlen(s); i++)
11     {
12         if(s[i] == ‘G‘) sg = i;
13         else if(s[i] == ‘T‘) eg = i;
14     }
15     if(sg > eg) swap(sg, eg);
16     int cnt = sg, ok = 1;
17     while(cnt < eg)
18     {
19         if(s[cnt] == ‘#‘)
20         {
21             ok = 0; break;
22         }
23         else
24         {
25             cnt += k;
26         }
27         if(cnt == eg) break;
28     }
29     if(cnt != eg)  ok = 0;
30 
31     printf("%s\n", ok ? "YES" : "NO");
32     return 0;
33 }
View Code

 

B. Urbanization(贪心+排序)

题意：

已知n个居民的财富值(<=100000)，将这n（n<=100000）个居民抽取部分（或全部）分别到容量为n1和n2的两个城市（n1+n2<=n），使得这两个城市人们的人均财富值之和尽量大，求这个最大的人均财富值之和。

思路：

贪心一下，发现把最富的人塞到较小的城市里，会使答案更优。所以排序一下搞一搞就好了。

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 100000 + 5;
 4 int a[maxn];
 5 int main()
 6 {
 7     int n, n1, n2;
 8     scanf("%d%d%d", &n, &n1, &n2);
 9     for(int i = 0; i < n; i++)
10     {
11         scanf("%d", &a[i]);
12     }
13     sort(a, a + n);
14 
15     double ans = 0;
16     long long rec = 0;
17     for(int i = n - 1; i >= n - min(n1, n2); i--)
18     {
19         rec += a[i];
20     }
21     ans = 1.0 * rec / min(n1, n2);
22     rec = 0;
23     for(int i = n - min(n1, n2) - 1; i >= n - n1 - n2; i--)
24     {
25         rec += a[i];
26     }
27     ans += 1.0 * rec / max(n1, n2);
28     printf("%f\n", ans);
29     getchar();
30     return 0;
31 }
View Code

 

C. Tennis Championship（贪心？数学）

题意：
现将举办一个锦标赛，有n个选手(2<=n<=1e18)，每场比赛都是两个选手之间进行，输的一方将被立即淘汰，但进行比赛的这两名选手，他们各自已经参加过的比赛的场数相差不可超过1,求锦标赛的冠军参加过的比赛场数最多可能为多少。

思路:

随便推几项，就发现是个斐波那契数列，然后又因为斐波那契数列增长速度非常快。实际上你会发现n=100的时候就已经很大很大了。

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 1000000 + 5;
 5 LL f[maxn];
 6 int main()
 7 {
 8     int x = 90;
 9     f[1] = 2, f[2] = 3;
10     for(int i = 3; i <= x; i++)
11     {
12         f[i] = f[i - 1] + f[i - 2];
13     }
14     LL n;
15     while(cin >> n)
16     {
17         int pos = lower_bound(f, f + x, n) - f;
18         if(f[pos] != n) pos --;
19         cout << pos << endl;
20     }
21 
22     return 0;
23 }
View Code

 

D. Taxes（数论）

题意：
一个人他赚的钱为n(2<=n<=2*10^9)，若按照税法，则需要交的税为不等于n的n的最大因数，如今这个人想偷税，他将n拆分为若干个ni的和，即n=n1+n2+...+nk（k为任意值，可等于1），但是其中ni不能等于1，拆分完后，他总共交的税即为每份ni按照税法交的税之和。求他交的税的最小值。

思路：

也就是说尽可能的拆成数量少的质数？这是一个哥德巴赫猜想，在这个数据范围内，哥德巴赫的猜想是肯定成立的。

哥德巴赫的猜想：任何大于5的奇数都是三个素数之和，任何一个大于2的偶数都是两个素数之和。

注意一下情况很容易错，

①先考虑这个数本身是质数，显然是1

②如果这个数是偶数，那么显然是2

③如果是一个非质数的奇数，看（n-2)是否为质数，如果是，就可以将其分为2和（n-2)这样两个质数，那么就输出2，如果n-2不是一个质数，那么根据哥德巴赫的猜想一定更可以分成三个质数的和，所以输出3

 

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 1000000 + 5;
 5 bool isprime(int  n)
 6 {
 7     int ok = 1;
 8     for(int i = 2; i <= sqrt(n); i++)
 9     {
10         if(n % i == 0)
11         {
12             return false;
13         }
14     }
15     return true;
16 }
17 int main()
18 {
19 
20     int n;
21     cin >> n;
22     if(isprime(n))
23     {
24         puts("1");
25     }
26     else if(n % 2 == 0)
27     {
28         puts("2");
29     }
30     else
31     {
32         if(isprime(n - 2))
33         {
34             puts("2");
35         }
36         else
37         {
38             puts("3");
39         }
40     }
41     return 0;
42 }
View Code

 

Codeforces Round #382 (Div. 2)


联系
我们