D Knapsack Cryptosystem
题意
求一个有唯一解的超大01背包的方案。
分析
使用折半搜索,前18个数先dfs爆搜求出所有可能的方案,存到map里,再爆搜后18个数,从map里查询即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll s,a[50];
map<ll,string> mp;
void dfs(int i,ll sum,string t){
if(i==n/2){
mp[sum]=t;
return;
}
dfs(i+1,sum,t+"0");
dfs(i+1,sum+a[i],t+"1");
}
bool ac=false;
int cnt=0;
void dfs2(int i,ll sum,string t){
if(ac){
return;
}
if(i==n){
if(mp.find(s-sum)!=mp.end()){
printf("%s%s\n",mp[s-sum].c_str(),t.c_str());
ac=true;
}
return;
}
dfs2(i+1,sum,t+"0");
dfs2(i+1,sum+a[i],t+"1");
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%lld",&n,&s);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
dfs(0,0,"");
dfs2(n/2,0,"");
return 0;
}
H Cutting Bamboos
题意
给n个高度,每次独立询问一个区间\([l,r]\),对于这个区间的所有高度,要求砍\(y\)次刚好全部砍完,问第\(x\)次砍的位置。
分析
- 可以二分砍的位置,计算出第\(x\)次砍掉的所有高度,进行check,所以问题就转化为如何求区间\([l,r]\)里大于某个值的高度差和。
- 显然只需要用主席树维护值域每个数的个数和加和,查询区间大于某个值\(x\)的加和,再减去大于\(x\)的个数乘以\(x\),即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
typedef long long ll;
typedef double db;
typedef pair<ll,ll> pll;
const int N=2e5+50;
const db eps=1e-8;
int n,q;
ll h[N],p[N];
int l,r;
ll x,y;
int cnt,tr[N],lr[N*40],rr[N*40];
ll num[N*40],sum[N*40];
int build(int l,int r){
int rt=++cnt;
sum[rt]=num[rt]=0;
if(l==r){
return rt;
}
lr[rt]=build(l,mid);
rr[rt]=build(mid+1,r);
return rt;
}
int insert(int pre,int l,int r,int v){
int rt=++cnt;
lr[rt]=lr[pre];
rr[rt]=rr[pre];
num[rt]=num[pre]+1;
sum[rt]=sum[pre]+v;
if(l==r){
return rt;
}
if(v<=mid){
lr[rt]=insert(lr[pre],l,mid,v);
}else{
rr[rt]=insert(rr[pre],mid+1,r,v);
}
return rt;
}
//查询区间大于等于q的h个数和总和
pll query(int u,int v,int l,int r,int q){
if(l>=q){
return {num[v]-num[u],sum[v]-sum[u]};
}
if(q<=mid){
auto p=query(lr[u],lr[v],l,mid,q);
return {p.first+num[rr[v]]-num[rr[u]],p.second+sum[rr[v]]-sum[rr[u]]};
}else{
return query(rr[u],rr[v],mid+1,r,q);
}
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&q);
ll mx=0;
for(int i=1;i<=n;i++){
scanf("%lld",&h[i]);
mx=max(mx,h[i]);
p[i]=p[i-1]+h[i];
}
tr[0]=build(1,mx);
for(int i=1;i<=n;i++){
tr[i]=insert(tr[i-1],1,mx,h[i]);
}
for(int i=0;i<q;i++){
scanf("%d%d%lld%lld",&l,&r,&x,&y);
db ned=(p[r]-p[l-1])*1.0/y*x;
db L=0.0,R=mx*1.0;
while(L+eps<=R){
db M=(L+R)/2;
auto t=query(tr[l-1],tr[r],1,mx,int(ceil(M)));
db k=t.second*1.0-t.first*M;
if(k<ned){
R=M-eps;
}else{
L=M+eps;
}
}
printf("%.12lf\n",L);
}
return 0;
}