总结
代码地址 | 题目地址 | 关键算法 | 难度 |
---|---|---|---|
Q1-Allocation.cpp | Allocation | 贪心算法 | 简单 |
Q2-Plates.cpp | Plates | 动态规划 | 较简单 |
Q3-Workout.cpp | Workout | 二分法 | 较难 |
Q4-Bunding.cpp | Bunding | 前缀树+深度搜索 | 难 |
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,我之前想得是模拟这个增加的过程,然后发现超时了。
// 这里有一种二分的方法,首先对最大差值进行二分,假设二分后的差值为N,
// 然后去判断原来的数组实现最大差值为N最少需要增加几个数,如果不大于K个数,则一定能成功。
// 如果成功了,则说明最终的结果是小于N的。则再对N进行二分,直到找到能够成功的最大值。
#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;
}
0