清北学堂模拟赛d2t5 吃东西(eat)
2024-10-01 00:40:48
题目描述
一个神秘的村庄里有4家美食店。这四家店分别有A,B,C,D种不同的美食。LYK想在每一家店都吃其中一种美食。每种美食需要吃的时间可能是不一样的。
现在给定第1家店A种不同的美食所需要吃的时间a1,a2,…,aA。
给定第2家店B种不同的美食所需要吃的时间b1,b2,…,bB。
以及c和d。
LYK拥有n个时间,问它有几种吃的方案。
输入格式(eat.in)
第一行5个数分别表示n,A,B,C,D。
第二行A个数分别表示ai。
第三行B个数分别表示bi。
第四行C个数分别表示ci。
第五行D个数分别表示di。
输出格式(eat.out)
一个数表示答案。
输入样例
11 3 1 1 1
4 5 6
3
2
1
输出样例
2
对于30%的数据A,B,C,D<=50
对于另外30%的数据n<=1000。
对于100%的数据1<=n<=100000000,1<=A,B,C,D<=5000,0<=ai,bi,ci,di<=100000000。
分析:这道题刚开始想着用dp,但是这数据明显不可做啊,状态都开不下.其实对枚举优化一下就好了......
试考虑最暴力的做法,四重循环枚举ABCD.对于四重循环有一个常用的优化就是利用前3个数就能算出第4个数,在这道题中如果我们知道了A+B,就可以知道C+D的具体范围,那么把C+D的所有取值排序,找到第一个A+B + C+D>n的C+D的位置i,那么ans += (i - 1),所以做法就是先枚举出所有的A+B的组合,再枚举出所有C+D的组合,排个序,枚举A+B然后查找C+D的位置累加答案即可.
一个复杂度很高的枚举,如果我们能够折半搜索,复杂度就会降低很多,要熟记这些优化.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n, A, B, C, D, a[], b[], c[], d[],maxn,cur;
int f[], c1[], c2[],cnt1,cnt2;
long long ans = ; int main()
{
scanf("%d%d%d%d%d", &n, &A, &B, &C, &D);
for (int i = ; i <= A; i++)
scanf("%d", &a[i]);
for (int i = ; i <= B; i++)
scanf("%d", &b[i]);
for (int i = ; i <= C; i++)
scanf("%d", &c[i]);
for (int i = ; i <= D; i++)
scanf("%d", &d[i]);
for (int i = ; i <= A; i++)
for (int j = ; j <= B; j++)
if (a[i] + b[j] <= n)
{
f[a[i] + b[j]]++;
maxn = max(maxn, a[i] + b[j]);
}
for (int i = ; i <= maxn; i++)
while (f[i])
{
f[i]--;
c1[++cnt1] = i;
}
maxn = ;
for (int i = ; i <= C; i++)
for (int j = ; j <= D; j++)
if (c[i] + d[j] <= n)
{
f[c[i] + d[j]]++;
maxn = max(maxn, c[i] + d[j]);
}
for (int i = ; i <= maxn; i++)
while (f[i])
{
f[i]--;
c2[++cnt2] = i;
}
for (cur = cnt2; cur >= ; cur--)
if (c1[] + c2[cur] <= n)
break;
for (int i = ; i <= cnt1; i++)
{
ans += cur;
while (cur && c1[i + ] + c2[cur] > n)
cur--;
}
printf("%lld\n", ans); return ;
}
最新文章
- 改变UIButton 图片和文字的位置
- jQuery Jcrop API参数说明(中文版)(转)(图片剪切)
- php 消息队列
- 三国塔防游戏android源码
- 关于<;:if>;没有<;c:else>;解决方案
- Roseonly:互联网轻奢品牌之路-搜狐IT
- UItexfile实时验证输入字符
- JS禁用右键,禁用打印,防止另存为,IE浏览器识别(转载)
- HALCON学习-资料
- PyQt5 教程地址
- git 无法拉取新的远程分支
- boost.Asio lib
- CSS常用伪类
- day59
- 高效编写微信小程序
- demo:使用数字证书进行数字签名和加密,解密
- Jmeter入门--Badboy使用教程(转)
- java 查询solr时间格式
- SyntaxError: expected expression, got &#39;<;&#39;
- hihocoder155周 任务分配
热门文章
- bzoj1951 [Sdoi2010]古代猪文 ——数论综合
- 杂项-QXM:CFA(特许金融分析师)
- [Apple开发者帐户帮助]九、参考(6)支持的功能(watchOS)
- [Swift通天遁地]八、媒体与动画-(10)在项目中播放GIF动画
- Visual&#160;Studio&#160;Code配置GitHub(Win7环境)
- SpringBoot集成Swagger2 以及汉化 快速教程
- mybatis 中 foreach 的性能问题及调优
- 使用Quartz2.2.3做持久化,启动程序后,控制台报错问题
- 配置Oracle数据库的开机自启动
- Sql Server 如何解决多并发情况下,出现的多个相同ID数据