Codeforces Round #638 (Div. 2)

Contest Info

Solved	A	B	C	D	E	F
4/6	O	O	Ø	Ø

O 在比赛中通过
Ø 赛后通过
! 尝试了但是失败了
- 没有尝试

Solutions

C.Phoenix and Distribution

题意：

将字符串 $s$ 分为 $k$ 个非空串，找出使得$ k$ 个非空串中字典序最大的字符串字典序最小的方案

思路：

求最大值的最小值，那么对某种分配来说，求字典序最大时要保证$k$个序列每个都尽可能小，这样最后求出来的最小值才尽可能的小。

由于要求$k$个串是非空的，那么对原串先排序，取前$k$个分配给$k$个字符串。

此时如果只剩下一种字母，给字典序最小的一些字符串循环分配即可。

如果剩下的字母多于一种，则全部分给一个字符串，因为这样分较大的字母最靠后，字典序最小。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e5+100;

int T, n, k;

char s[maxn];

int main(){

    scanf("%d", &T);

    while(T--){

        scanf("%d%d %s", &n, &k, s+1);

        sort(s+1, s+1+n);

        bool flag1 = false, flag2 = false;

        for(int i = 1; i <= k-1; i++)

            if(s[i]!=s[i+1]){

                flag1 = true;

                break;

            }

        if(flag1){

            printf("%c\n", s[k]);

            continue;

        }

        for(int i = k+1; i <= n-1; i++)

            if(s[i]!=s[i+1]){

                flag2 = true;

                break;

            }

        if(flag2) printf("%c%s\n", s[1], s+k+1);

        else printf("%c%s\n", s[1], s+1+n-(n-1)/k);

    }

}

D.Phoenix and Science

题意：

开始时有 $1$ 个质量为 $1$ 的细菌，白天可以选择部分细菌分裂，晚上每个细菌的质量增加 $1$，问最少需要多少天总质量能达到 $m$，输出分裂方案

思路：

由于求最少天数，我们考虑质量增长最快的方式——指数增长：每个白天所有的细菌都分裂，这样每晚增加的质量(当前细菌数目)即为一个 $a_0=1, q=2$ 的等比数列，求出和小于等于 $m$的最长等比数列，将多出来的质量分进其中的某一天即可，相邻两晚的质量之差即为白天分裂的个数.

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

int T, n;

int main(){

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        vector<int> g;

        for(int i = 1; i <= n; i *= 2){

            g.push_back(i);

            n -= i;

        }

        if(n>0){

            g.push_back(n);

            sort(g.begin(), g.end());

        }

        printf("%d\n", g.size()-1);

        for(int i = 1; i < g.size(); i++)

            printf("%d ", g[i]-g[i-1]);

        printf("\n");

    }

}

我可能脑子有点糊，我读完题后想成$x$个细菌分裂会变成$2^x$个细菌，实际上是变成$2*x$，分裂多少个就增加多少个细菌，之后要更加细心

Refrence：

https://www.cnblogs.com/Kanoon/p/12815637.html

https://www.cnblogs.com/kikokiko/p/12815671.html

巴特西

Codeforces Round #638 (Div. 2)

Contest Info

Solutions

最新文章

热门文章