【题解】P4799[CEOI2015 Day2]世界冰球锦标赛
2024-08-29 12:16:18
【题解】[P4799 CEOI2015 Day2]世界冰球锦标赛
发现买票顺序和答案无关,又发现\(n\le40\),又发现从后面往前面买可以通过\(M\)来和从前面往后面买的方案进行联系。可以知道是双搜。
从后往前搜索,\(2^{\frac{n}{2}}\)枚举记录到中间时剩下多少钱的方案,记为\(hash_1\),从前往后搜索,记录到中间花了多少钱的方案,记为\(hash_2\)。然后在\(hash_2\)中查询小于等于\(hash_{2_{i}}\)的方案有多少。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<bitset>
#include<vector>
#include<map>
#include<ctime>
#include<cstdlib>
#include<set>
#include<bitset>
#include<stack>
#include<list>
#include<cmath>
using namespace std;
#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)
#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)
#define ERP(t,a) for(int t=head[a];t;t=e[t].nx)
#define Max(a,b) ((a)<(b)?(b):(a))
#define Min(a,b) ((a)<(b)?(a):(b))
#define TMP template<class ccf>
#define lef L,R,l,mid,pos<<1
#define rgt L,R,mid+1,r,pos<<1|1
#define midd register int mid=(l+r)>>1
#define chek if(R<l||r<L)return
#define all 1,n,1
#define pushup(x) seg[(x)]=seg[(x)<<1]+seg[(x)<<1|1]
typedef long long ll;
TMP inline ccf qr(ccf k){
char c=getchar();
ccf x=0;
int q=1;
while(c<48||c>57)
q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)
x=x*10+c-48,c=getchar();
if(q==-1)
x=-x;
return x;
}
const int maxn=2097155;
ll data[45];
ll ord[maxn];
ll ans;
ll n;
ll m;int cnt;
inline ll C(ll k){
ll mid,l=1,r=cnt;
do{
mid=(l+r)>>1;
if(ord[mid]<=k)
l=mid+1;
else
r=mid-1;
}while(l<=r);
return l;
}
void dfs(int now,ll rest){
if(now>(n>>1))return void(ord[++cnt]=m-rest);
if(rest>=data[now])
dfs(now+1,rest-data[now]);
dfs(now+1,rest);
}
void dfs2(int now,ll rest){
if(now>n) return void(ans+=C(rest)-1ll);
if(rest>=data[now])
dfs2(now+1,rest-data[now]);
dfs2(now+1,rest);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=qr(1ll);
m=qr(1ll);
RP(t,1,n)
data[t]=qr(1ll);
dfs(1,m);
sort(ord+1,ord+cnt+1);
//RP(t,1,cnt)
// cout<<ord[t]<<' ';
//cout<<endl;
dfs2(n/2+1,m);
printf("%lld\n",ans);
return 0;
}
最新文章
- SpringMVC类型转换器、属性编辑器
- Java 性能分析工具 , 第 1 部分: 操作系统工具
- vc6.0快捷键大全
- Codeforces Round #345 D. Image Preview(二分)
- 关于hive的str_to_map
- 字符串集合或字符串数组转换成json数组
- js 的小效果---->;选项卡
- PLSQL_Oracle分区表和相应的分区索引管理和使用(案例)
- java工具类–自动将数据库表生成javabean
- xampp 访问出现New XAMPP security concept 或者 新しいXAMPPのセキュリティコンセプト
- JavaScript阻止事件冒泡
- jQuery 动态绑定的点击事件
- Eclipse 使用简记
- iOS 之UICollectionView 开发步骤 之 OC
- Redis【第一篇】安装
- 洛谷 P3391 【模板】文艺平衡树
- javascript学习(一)构建自己的JS库
- 在Centos中安装mysql
- 【原创】大叔经验分享(2)为什么hive在大表上加条件后执行limit很慢
- CentOS 7 zabbix添加监控服务器
热门文章
- ELK之logstash收集日志写入redis及读取redis
- Ansible之常用模块介绍
- 牛客网暑期ACM多校训练营 记录
- MyEclipse导入外部项目
- 【java】TreeMap/HashMap的循环迭代中 keySet和entrySet和forEach方式 + map的几种迭代方式
- 常用 linux操作
- 报错:LINK : fatal error LNK1123: 转换到 COFF 期间失败: 文件无效或损坏 1>;
- Activity入门(一)
- JavaScript中给二维数组动态添加元素的质朴方法
- C 标准库 - <;assert.h>;