总结

Q1-Allocation

典型的贪心算法，直接遍历+贪心即可。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int main()
{
    int T,t,N,n,B,temp;
    int maxx;
    int cost[100000];
    scanf("%d", &T);
    for(t=0; t<T; t++)
    {
        scanf("%d", &N);
        scanf("%d", &B);
        for(n=0; n<N; n++)
        {
            scanf("%d", &temp);
            cost[n] = temp;
        }
        sort(cost, cost+N);
        maxx = 0;
        for(n=0; n<N; n++)
        {
            if(cost[n]<=B)
            {
                maxx += 1;
                B -= cost[n];
            }
            else
                break;
        }
        printf("Case #%d: %d\n", t+1, maxx);
    }

    return 0;
}

Q2-Plates

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

// 我的思路基本是对的：动态规划思想
// 用beauty[i][j]表示第i摞中，取前j个盘子的魅力值。
// 用maxb[i][j]表示前i摞中取j个盘子，能够获得的最大魅力值。
// 1.对于maxb[1][0]到maxb[1][p]来说，因为只有1摞，则只需要依次相加即可。
// 2.对于第2摞来说，可以选择第2摞的0个盘子，或1个盘子，或2个盘子，则需要遍历，直到min(第2摞盘子数，需要的盘子数)结束。
//   对于第2摞，假设需要P个盘子，第2摞中取cnt个盘子，则其魅力值为: beauty[2][cnt]+maxb[1][P-cnt],遍历取最大值即可。
// 3.对于第i摞，遍历求beauty[j][cnt]+maxb[j-1][P-cnt]的最大值。


#define maxN 60     // 很生气，第一次开到（50+1）竟然没有过，害得找了半天代码的错误，建议以后做题开大些
#define maxP 1520
int main()
{
    int T,t,N,n,K,k,P;
    int beauty[maxN][maxP];
    int maxb[maxN][maxP];
    int max_temp = 0;
    int cnt;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        memset(beauty, 0, sizeof(beauty));
        memset(maxb, 0, sizeof(maxb));
        scanf("%d %d %d", &N, &K, &P);

        // 输入魅力值
        for(n=1; n<=N; n++)
        {
            for(k=1; k<=K; k++)
            {
                scanf("%d", &beauty[n][k]);
            }
        }


        // 第i摞中，取前j个盘子的魅力值
        for(n=1; n<=N; n++)
        {
            for(k=1; k<=P; k++)
            {
                // 依次相加
                beauty[n][k] += beauty[n][k-1];
                /* printf("%d ", beauty[n][k]); */ 
            }
            /* printf("\n"); */ 
        }

        // 计算前i摞中，去j个盘子，能够获得的最大魅力值
        for(n=1; n<=N; n++)
        {
            for(k=1; k<=P; k++)
            {
               // 依次遍历，使用第j摞的0个盘子，1个盘子，2个盘子，...，min(k,K)个盘子  求最大值
                //maxb[n][k] = maxb[n-1][k];
               for(cnt=0; cnt<=min(k,K); cnt++)
               {
                    maxb[n][k] = max(maxb[n][k], beauty[n][cnt]+maxb[n-1][k-cnt]);
               }
               /* printf("%d ", maxb[n][k]); */   
            }
            /* printf("\n"); */ 
        }

        printf("Case #%d: %d\n", t, maxb[N][P]);
    }

    return 0;
}

Q3-Workout

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

// 使用二分的方法来解决此问题。
// 如果K=1，则只增加一个数，则这个数一定是增加到间隔最大的两个数之间。
// 对于K>1，我之前想得是模拟这个增加的过程，然后发现超时了。
// 这里有一种二分的方法，首先对最大差值进行二分，假设二分后的差值为Ｎ，
// 然后去判断原来的数组实现最大差值为Ｎ最少需要增加几个数，如果不大于Ｋ个数，则一定能成功。
// 如果成功了，则说明最终的结果是小于Ｎ的。则再对Ｎ进行二分，直到找到能够成功的最大值。
#define maxN 100000+50

int diff[maxN];
// 通过二分法判断能够成功的最大值。
int check(int left, int right, int numb, int K)
{
    int i = 0;
    int mid;
    int cnt;
    int ans;
    while(left<=right)    
    {
        cnt = K;
        /* printf("1.left is %d right is %d\n", left, right); */
        mid = (left+right)/2;
        // 判断实现数组最大间隔为mid，需要多少次，如果在cnt次能成功，则继续二分
        for(i=0; i<numb-1; i++)
        {
            // 如果当前间隔大于mid，则需要添加数字
            if(diff[i]>mid)
            {
                // 如果是mid的倍数，则需要增加(diff[i]/mid)-1个数字即可
                if(diff[i]%mid == 0)
                    cnt -= (diff[i]/mid-1);
                // 如果不是mid的倍数，则需要增加(diff[1]/mid)个数字
                else
                    cnt -= diff[i]/mid;
            }

            // 如果cnt小于0，则说明不能成功，则退出
            if(cnt<0)
            {
                //printf("mid is %d, cnt is %d\n", mid, cnt);
                break;
            }
        }
        /* printf("mid is %d, cnt is %d\n", mid, cnt); */
        // cnt小于0,说明最终的结果在mid和right之间
        if(cnt<0)
        {
            left = mid+1;
        }
        else
        {
            ans = mid;
            right = mid-1;
        }
        /* printf("2.left is %d right is %d\n", left, right); */   
    }
    return ans;
}
int main()
{
    int T,t,N,n,K;
    int num1,num2;
    //int diff[maxN];
    int max_diff = 0;
    //memset(diff, 0, sizeof(diff));
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        memset(diff, 0, sizeof(diff));
        scanf("%d %d", &N, &K);
        scanf("%d", &num1);
        for(n=0; n<N-1; n++)
        {
            scanf("%d", &num2);
            diff[n] = num2-num1;
            /* printf("%d ", diff[n]); */
            max_diff = max(max_diff, diff[n]);
            num1 = num2;
        }
        /* printf("%d\n", max_diff); */
        printf("Case #%d: %d\n", t, check(1,max_diff,N,K));
    }
    /* std::cout << "Hello world" << std::endl; */
    return 0;
}

Q4-Bunding

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef long long ll;

// 看到前缀二字就想到了字典树
// 首先建立一个字典树,然后从叶子节点开始,从下往上遍历,对每个子节点遍历
// 对每个子节点计算分成K组字符串的最大的value值
// 可以参考一位UP的视频讲解:https://www.youtube.com/watch?v=2Kb_QyPEMd0&feature=youtu.be&ab_channel=FluentAlgorithms
//
// 第一次提交之后,Test1通过,Test2运行错误
// 原因有两个方面:
// 1.字符串的长度未知,如果用char不知道开多少够,这里使用string类型.
// 2.有一些数据可能int类型不够,因此采用longlong型存储.
//
#define size 26


struct node{
    // 同一前缀的字符串个数
    ll pre;
    // 以该字符串结尾的字符串个数
    ll cnt;
    struct node *children[size];
};

node *root;

// 创建字典树的一个节点
node* createNode()
{
    int i;
    struct node *newnode;
    newnode = (struct node*)malloc(sizeof(node));
    newnode->pre = 0;
    newnode->cnt = 0;
    for(i=0; i<size; i++)
    {
        newnode->children[i] = NULL;
    }
    return newnode;
}

// 在字典树中增加一个节点
void insertNode(const std::string s)
{
    //cout<<"The string is "<<s<<endl;
    ll len = s.length();
    ll i;
    struct node *temp;
    temp = root;
    temp->pre++;
    for(i=0; i<len; i++)
    {
        if(temp->children[s[i]-'A']==NULL)
        {
            temp->children[s[i]-'A'] = createNode();
        }
        temp = temp->children[s[i]-'A'];
        temp->pre++;
    }
    temp->cnt++;
}

// 深搜 求结果
ll dfs(node *root, ll K, ll depth)
{
    ll ans=0;
    ll here = root->cnt;
    struct node *child;
    int i;
    if(root->pre<K)
    {
        return 0;
    }
    for(i=0; i<size; i++)
    {
        child = root->children[i];
        if(child==NULL)
            continue;
        // 加上叶子节点的分数
        ans += dfs(child, K, depth+1);
        // 叶子节点分成K组后,剩余的未加入组的节点,加到其父节点中
        here += (child->pre%K);
    }
    // depth即字符串长度 here/k 得出可以分为多少组
    ans += (here/K)*depth;
    return ans;
}

// 释放建立字典树所使用的指针
void deleteTree(struct node *root)
{   
    int i;
    if(root!=NULL)
    {
        for(i=0; i<size; i++)
        {
            deleteTree(root->children[i]);
        }
        free(root);
    }   
}

int main()
{
    int t,T;
    string s;
    ll N,n,K;
    ll ans=0;
    //root = createNode();
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        root = createNode();
        scanf("%lld %lld", &N, &K);
        for(n=1; n<=N; n++)
        {
            //scanf("%s", s);
            cin>>s;
            insertNode(s);
        }
        ans = dfs(root, K, 0);
        printf("Case #%d: %lld\n", t, ans);
    }
    /* std::cout << "Hello world" << std::endl; */
    return 0;
}