2019.11.3xs模拟赛题解
loutianchi · · 个人记录
今天状态还行，就是需要多多注意细节，不要在一些奇奇怪怪的地方丢分，比如：
- T1里面三分的写法，需要注意是 l!=r，而且要注意x=y的情况是向左移动还是向右移动
- T2里面的位运算要好好注意一下，虽然一遍A了（左移的时候要注意用long long）
- T3里面的读入，艹。。。我读入写错使我的dfs
正解爆零（欲哭无泪
Ps:其实我的dfs是可以被hack的，但是随机的数据仿佛比较弱，很快可以过了
T1
1. 汽艇
(ship.cpp/c/pas)
【问题描述】
小泉同学和伙伴们一共n人乘坐汽艇，到了场地后，她们发现可以乘坐的汽艇只有一个。为了选出最合适的游玩人选，她们衡量了每个人游玩的兴趣值ci。
如果第ci个人单独乘坐汽艇，就能够满足ci点兴趣值。然而乘坐数量会影响汽艇的游玩体验，每多一个人乘坐汽艇，会汽艇上的任意一人的兴趣值减少di点。
小泉同学想要安排乘坐汽艇的人，使得获得的兴趣值之和最大，并在兴趣值之和的基础上，让乘坐汽艇的小伙伴数量尽量的多。
请问你能够帮小泉算出兴趣值之和的最大值，并告诉她能够乘坐汽艇的小伙伴数量吗？
【输入格式】
输入文件名为ship.in。
数据第一行一个整数n,表示小泉同学和伙伴们的总人数。
第二行包含n个数字，其中第i个数字表示第i个人的基础兴趣值ci
第二行包含 n个数字，其中第di个数字表示汽艇上每多一个，对第i个人兴趣值的减损di。
【输出格式】
输出文件名为ship.out。
输出一行两个数字，分别表示兴趣值之和的最大值，和在得到此最大值时最多的乘坐汽艇的小伙伴数量。
【输入输出样例 1】
ship1.in
4
10 10 10 10
2 2 2 2
ship2.out
18
3
见选手目录下的 ship/ship1.in 和 ship/ship1.ans。
【输入输出样例 2】
见选手目录下的ship/ship2.in 和 ship/ship2.ans。
【数据规模与约定】
对于 20% 的数据，有 n≤10，1≤ci≤di≤103;
对于 60% 的数据，有 n≤1000，1≤ci≤di≤106；
对于 100% 的数据，有 n≤10^5，1≤ci≤di≤109。我的代码：
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
long long fastread()
{
long long fh=1,x=0;
char c=getchar();
while (c!='-' && (c<'0' || c>'9'))
c=getchar();
if (c=='-')
{
fh=-1;
c=getchar();
}
while (c>='0' && c<='9')
{
x=x*10+c-48;
c=getchar();
}
return x*fh;
}
long long a[100010],d[100010],n,b[100010];
bool cmp(long long x,long long y)
{
return x>y;
}
long long suan(long long x)//用贪心来check
{
for (int i=1;i<=n;i++)
b[i]=a[i]-(x-1)*d[i];/*
for (int i=1;i<=n;i++)
cerr<<b[i]<<" ";
cerr<<endl;*/
sort(b+1,b+n+1,cmp);
long long tmp=0;
for (int i=1;i<=x;i++)
tmp+=b[i];
return tmp;
}
int main()
{
freopen("ship.in","r",stdin);
freopen("ship.out","w",stdout);
n=fastread();
for (int i=1;i<=n;i++)
a[i]=fastread();
for (int i=1;i<=n;i++)
d[i]=fastread();
long long l,r,mid_left,mid_right,d;
l=1;r=n;
long long x,y;
while (l<=r)//三分找波峰
{
d=(r-l)/3;
mid_left=l+d;
mid_right=r-d;
x=suan(mid_left);
y=suan(mid_right);/*
cerr<<l<<" "<<mid_left<<" "<<mid_right<<" "<<r<<endl;
cerr<<x<<" "<<y<<endl;*/
if (x<=y) l=mid_left+1;
else r=mid_right-1;
}
cout<<suan(l)<<endl;
if (suan(l)==suan(l+1)) cout<<l+1<<endl;
else cout<<l<<endl;
fclose(stdin);fclose(stdout);
return 0;
}
T2
2. 等式
(equation.cpp/c/pas)
【问题描述】
宇宙的真理往往蕴含在数学之中，小泉同学在吃拉面时悟到了这样一个式子： (A1 xor k)+(A2 xor k)+⋯+(An xor k)≤M
其中 xor 为按位异或运算。
当给定n个非负整数 A1,A2,⋯,An和正整数M时，小泉认为符合该等式的 k 是符合宇宙真理的，小泉想要知道，最大符合宇宙真理的 k 值是多少呢？
【输入格式】
输入文件名为equation.in。
输入包含 T 组数据。
每组数据第一行输入两个整数 n 和 M。
第二行 n 个数字，表示Ai。
【输出格式】
输出文件名为 equation.out。 输出 T 行每行一个数，表示最大的符合该等式的 k 值。 如果不存在符合等式的 k 值，则输出 -1
【输入输出样例 1】
equation1.in
2
3 27
8 2 4
6 2
5 5 1 5 1 0
equation1.out
12
-1
见选手目录下的equation/equation1.in 和equation/equation1.ans。
【输入输出样例 2】
见选手目录下的equation/equation1.in 和equation/equation2.ans。
【数据规模与约定】
对于 30% 的数据，有 1≤T≤10，1≤n≤10，1≤Ai,M≤100。
对于 60% 的数据，有 1≤T≤100，1≤n≤100，1≤Ai,M≤10^9。
对于 100% 的数据，有 1≤T≤100，1≤n≤5000，1≤Ai,M≤10^15.我的代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
long long fastread()
{
long long fh=1,x=0;
char c=getchar();
while (c!='-' && (c<'0' || c>'9'))
c=getchar();
if (c=='-')
{
fh=-1;
c=getchar();
}
while (c>='0' && c<='9')
{
x=x*10+c-48;
c=getchar();
}
return x*fh;
}
int len,n;
long long a1[64];//保存二进制中从右往左第k位的1的个数
long long a0[64];//保存二进制中从右往左第k位的0的个数
long long m;
map <long long,int> mp;
long long xz[64];
int add(long long x)
{
long long wei;
while (x)
{
wei=x^(x-1);
wei=(wei+1)/2;
a1[mp[wei]]++;
x&=x-1;
}
return 0;
}
int ws(long long x)//求在二进制下的位数
{
int tmp=0;
while (x)
{
tmp++;
x/=2;
}
return tmp;
}
long long ans;
int csh()
{
ans=-1;
for (int i=0;i<=len;i++)
a0[i]=n-a1[i];
for (int i=0;i<=len;i++)
a0[i]*=xz[i],a1[i]*=xz[i];
return 0;
}
bool dfs(int k,long long sum,long long tmp)
//现在处理第k位,现在有sum多的值，取的数是tmp
{
if (k<0)
{
if (sum<=m)
{
ans=tmp;
// cerr<<k<<" "<<sum<<" "<<tmp<<endl;
return true;//最优化剪枝
}
return false;
}
if (sum+a0[k]<=m)//剪枝1
if (dfs(k-1,sum+a0[k],(tmp|((long long)1<<k))))
return true;//选1
if (sum+a1[k]<=m)//剪枝2
if (dfs(k-1,sum+a1[k],tmp))
return true;//选0
return false;;
}
int main()
{
freopen("equation.in","r",stdin);
freopen("equation.out","w",stdout);
int T=fastread();
long long x=1;
for (int i=0;i<=52;i++)//预处理（其实可以用左移右移做，我太菜了）
{
mp[x]=i;
xz[i]=x;
x*=2;
}
for (;T;--T)
{
n=fastread();m=fastread();
len=ws(m);
memset(a0,0,sizeof(a0));
memset(a1,0,sizeof(a1));
for (int i=1;i<=n;i++)
{
x=fastread();
add(x);
}
csh();//初始化，算出a0和a1数组
// cerr<<len<<" "<<((long long)1<<len)<<endl;
dfs(len,0,0);
cout<<ans<<endl;
}
return 0;
}
T3
3. 拉面
(noodle.cpp/c/pas)
【问题描述】
小泉和悠相约到著名的一兰拉面吃拉面，她们一共点了 n 份拉面。每份拉面给小泉和悠分别带来 ai 和 bi 的饱腹度。
每份拉面可以由小泉或悠吃完，也可以她们一起吃。但是她们并不希望美味的拉面因为没人吃而浪费掉。
由于和经常小泉一起吃拉面，悠也养成和小泉一样的大胃口，只有当她们的饱腹感都不低于 H 时，她们都会感到非常满足。
请问你能够计算出有多少种吃拉面的方案，使得小泉和悠能够满足地吃掉所有的拉面？
【输入格式】
输入文件名为noodle.in。
第一行两个整数 n,H。
第二行 n 个整数，第 i 个整数 ai 表示第 i 份拉面分别对小泉的饱腹度。
第三行 n 个整数，第 i 个整数 bi 表示第 i 份拉面分别对悠的饱腹度。
【输出格式】
输出文件名为 noodle.out。
输出一行一个数字，表示能够使得小泉和悠都能够满足的方案数。
【输入输出样例 1】
noodle1.in
2 3
1 2
3 3
noodle1.out
3
见选手目录下的 noodle/noodle1.in 和noodle/noodle1.ans。
【输入输出样例 2】
见选手目录下的 noodle/noodle2.in 和noodle/noodle2.ans。
【数据规模与约定】
对于 40% 的数据，有 2≤n≤12，0≤ai,bi,H≤10^6
对于 100% 的数据，有 2≤n≤20，0≤ai,bi,H≤10^9我的代码：（其实可以hack）
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
long long fastread()
{
long long fh=1,x=0;
char c=getchar();
while (c!='-' && (c<'0' || c>'9'))
c=getchar();
if (c=='-')
{
fh=-1;
c=getchar();
}
while (c>='0' && c<='9')
{
x=x*10+c-48;
c=getchar();
}
return x*fh;
}
int n,h;
int a[30],b[30];
long long tot_a[30],tot_b[30];
//表示如果前面的（包括这个）都是a吃，有多少，都是b吃有多少
long long ans=0;
long long cf3(int k)//计算3^k
{
long long tmp=1;
for (int i=1;i<=k;i++)
tmp*=3;
return tmp;
}
int dfs(int k,long long nowa,long long nowb)
//处理第k碗面(从大到小）,a有nowa饱腹感，b有nowb饱腹感
{
if (nowa>=h && nowb>=h)//剪枝1（如果现在已经可以了，前面的随便搞，用一下乘法原理就好了）
{
ans+=cf3(k);
return 0;
}
if (k<1) return 0;
if (nowa+tot_a[k]<h) return 0;//剪枝2，如果怎么取都到不了就过了吧
if (nowb+tot_b[k]<h) return 0;//剪枝2，如果怎么取都到不了就过了吧
dfs(k-1,nowa+a[k],nowb);
dfs(k-1,nowa,nowb+b[k]);
dfs(k-1,nowa+a[k],nowb+b[k]);
return 0;
}
int main()
{
freopen("noodle.in","r",stdin);
freopen("noodle.out","w",stdout);
n=fastread();
h=fastread();
for (int i=1;i<=n;i++)
a[i]=fastread();
for (int i=1;i<=n;i++)
b[i]=fastread();
tot_a[0]=tot_b[0]=0;
for (int i=1;i<=n;i++)//预处理出前缀和
tot_a[i]=tot_a[i-1]+(long long)a[i],
tot_b[i]=tot_b[i-1]+(long long)b[i];
dfs(n,0,0);
cout<<ans<<endl;
fclose(stdin);fclose(stdout);
return 0;
}
hack数据:（我要跑4秒多，时限2秒）
20 5000
190 183 124 130 192 104 194 103 103 104 103 469 118 221 532 902 678 213 904 719
124 792 859 237 867 870 235 490 623 890 290 234 279 230 123 923 511 189 124 812