AKSZ-月赛题解
2024-04-12 20:34:43
发布于：广东
14阅读
0回复
0点赞
1.机器猫与猫粮
题目大意
给定n，输入数组a[n]，求一共有多少个子集使该子集的和位于[l,r]之间
数据分析
| 测试点 | n |
|---|---|
| 1-5 | 1<=n<=5 |
| 6-10 | 1<=n<=10 |
| 11-15 | 1<=n<=20 |
| 16-25 | 1<=n<=40 |
| 容易想到，当n<=20时，直接枚举子集即可，也就是60分做法 | |
| 那n<=40时呢？ | |
| 其实本题正解是dp | |
| 不过没学也没关系qwq |
思路
可以通过将数组分成两半来枚举
把前一半的每个子集之和存在sum1数组中，后一半存在sum2中
然后sort(sum1)，sort(sum2)(升序)再扫一遍sum1，用upper_bound-1找到最大的不大于r的数据的下标存在id中
再for(int i=1;i<=id;i++)
用lower_bound和upper_bound找到sum2数组中>（l-sum1[i]） && <(r-sum1[i])的数据的下标范围
左下标存在id1中，右下标存在id2中
if(id2>=id1){
ans+=id2-id1+1;
}
然后再特判一下如果sum1[i]本身就大于l,ans++;
100分代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5*1e6+5;//2的20次方约等于10^6,子集的数量不大于它
int a[maxn],b[maxn],c[maxn];
long long sum1[maxn],sum2[maxn],sum[maxn],ans;
int n,l,r;
bool cmp(int a,int b){
return a<b;
}
void subset(int n,int s){
for(int i=0;i<n;i++){
if(s&(1<<i))sum[s]+=a[n-i];
}
}
void subset1(int n,int s){
for(int i=0;i<n;i++){
if(s&(1<<i))sum1[s]+=b[n-i];
}
}
void subset2(int n,int s){
for(int i=0;i<n;i++){
if(s&(1<<i))sum2[s]+=c[n-i];
}
}
void check(int k1){
sort(sum1****um1+(1<<k1)+1,cmp);
sort(sum2****um2+(1<<(n-k1))+1,cmp);
int id=upper_bound(sum1****um1+(1<<k1)+1,r)-sum1;//找到sum1中最高的不大于r的下标
for(int i=1;i<id;i++){
int id1=lower_bound(sum2****um2+(1<<k1)+1,l-sum1[i])-sum2;//最小下标
int id2=(upper_bound(sum2****um2+(1<<(n-k1))+1,r-sum1[i])-sum2)-1;//最大下标
if(id2>=id1)ans+=id2-id1+1;//累加答案
}
}
int main(){
freopen("catfood.in","r",stdin);
freopen("catfood.out","w",stdout);
cin>>n>>l>>r;
for(int i=1;i<=n;i++)
cin>>a[i];
int k1=n/2;
int k2=k1+1;
if(n<=25){//如果n<=20直接枚举子集
for(int i=0;i<(1<<n);i++){
subset(n,i);
}
for(int i=0;i<(1<<n);i++){
if(sum[i]>=l && sum[i]<=r)ans++;
}
cout<<ans<<endl;
return 0;
}
for(int i=1;i<=k1;i++){
b[i]=a[i];
}
for(int i=k2;i<=n;i++){
c[i-k2+1]=a[i];
}
for(int i=0;i<(1<<k1);i++){
subset1(k1,i);
}
for(int i=0;i<(1<<(n-k1));i++){
subset2(n-k1,i);
}
check(k1);
cout<<ans<<endl;
return 0;
}
2.制定新的税法
题目大意
从数组a[n]和b[n]中，找出x1,x2,x3.......xk
使(a[x1]+a[x2]+.......+a[xk])/(b[x1]+b[x2]+......b[xk])的值最大
有special judge(误差应小于1e-4)
数据分析
对于100%的数据，1<=n<=1e5
也就是说本题的时间复杂度应该优化到O(n*sqrt(n))或O(nlogn);
也就容易想到二分答案；
思路分析
关键在于check函数怎么写……
观察一下这个式子(a[x1]+a[x2]+.......+a[xk])/(b[x1]+b[x2]+......b[xk])
让它=mid
则如果check成功：(a[x1]+a[x2]+.......+a[xk])/(b[x1]+b[x2]+......b[xk])>=mid;
移项得a[x1]+a[x2]+a[x3]+……+a[xk]>=mid(b[x1]+b[x2]+……+b[xk])
展开得a[x1]+a[x2]+a[x3]+……+a[xk]>=midb[x1]+midb[x2]+……midb[xk];
也就是a[x1]-midb[x1]+a[x2]-midb[x2]+……+a[xk]-midb[xk]>=0;
那就很简单了，只要二分mid,再把1-n扫一遍，把每一个a[i]-mid*b[i]存入c[i]中
然后sort一下(升序)，取c[]数组中的前k项
看这个式子a[x1]-midb[x1]+a[x2]-midb[x2]+……+a[xk]-mid*b[xk]>=0是否成立即可
注：由于是小数二分，所以要注意二分的写法
100昏代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,k;
int a[maxn],b[maxn];
double c[maxn];
double eps = 1e-6;//二分误差范围
bool cmp(double x, double y){
return x - y > eps;
}
bool check(double mid){
for(int i = 1; i <= n; i++){
c[i] = a[i] - mid*b[i];
}
sort(c+1,c+1+n,cmp);
double ret = 0.0;
for(int i = 1 ; i <= k ;i++){
ret += c[i];
}
return ret >= eps;//如果大于误差范围，check成功
}
int main(){
freopen("moretaxes.in","r",stdin);
freopen("moretaxes.out","w",stdout);
ios::sync_with_stdio(0);//小快读
cin.tie(0);
cin >> n >> k;
for(int i =1 ; i <= n;i++){
cin >> a[i] >> b[i];
}
double l = 0.0 , r = 1e10;//二分范围，r的精度应该大一些
double ans = 0.0;
while( abs(r-l) > eps){
double mid = (l+r) / 2.0;
if( check(mid)){
ans = mid;
l = mid;
}else{
r = mid;
}
}
printf("%.6lf\n",ans);//保留6位输出
return 0;//养成好习惯
}
3.德州扑克
对于本题，最直接的方法就是模拟算牌力的过程
牌力由大到小依次判断，如果符合要求直接break
数据分析
| 测试点 | 扑克牌情况 | 手牌组合情况 |
|---|---|---|
| [1,5] | 扑克牌只包含一种花色,且不包含 A | 保证不使用手牌最强 |
| [6,10] | 扑克牌只包含一种花色 | 保证不使用手牌最强 |
| [11,15] | 扑克牌不包含 A ,且不包含 「顺子」 | 无限制 |
| [16,20] | 随机生成，等概率选取 | 无限制 |
| [[21,25] | 无限制 | 无限制 |
| 可见，拿到部分分数还是比较容易的，只要判断几次即可 | ||
| 对于前10个数据点，直接扫一遍牌河即可 | ||
| 对于10-15数据点，我们无需考虑a的情况 | ||
| 对于16-20数据点，因为是等概率选取，所以不会有特别阴间的数据，正常写也可以拿分 | ||
| 但是本题想要拿到全部分数非常考验代码能力 |
思路整理
可以想到，对于所有的扑克牌，我们应该统计他们的花色和点数。
然后对点数进p[]进行排序
花色存入c[]数组里H，S，C，D 表示为 0,1,2,3
判断是否有的c[x]==5即可
参考代码
#include<bits/stdc++.h>
using namespace std;
int a[10]; // 组成的手牌情况
int tot; // a 里有几个元素
int p[20]; // 扑克牌点数（point) 计数 1 ~ 14 代表点数出现的个数。
int c[10]; // 扑克牌花色(color) 计数 0，1，2，3 代表黑桃、红桃、梅花、方块出现的个数。
int cnt2,cnt3,cnt4;// 有2，3，4张牌相同的情况数
int flu;//是否为同花
int stg; // 是否是顺子
int maxx; // 最大牌力
string h[5]; // 手牌 hand
string r[10]; // 牌河 river
void init(){ // 初始化清空 a,p,c 数组
memset(a,0,sizeof(a));
memset(p,0,sizeof(p));
memset(c,0,sizeof(c));
tot = 0;
}
int changeP(char tmp, int A){ // 将字符转为点数 ， 并且将 A 看作是几？
int point;
if(tmp>='0' && tmp <= '9')point = tmp - '0';
else if(tmp == 'T')point = 10;
else if(tmp == 'J')point = 11;
else if(tmp == 'Q')point = 12;
else if(tmp == 'K')point = 13;
else if(tmp == 'A')point = A;
return point;
}
int changeC(char tmp){ // 将花色转化为数字
if(tmp == 'S')return 0;
else if(tmp == 'H')return 1;
else if(tmp == 'C')return 2;
else return 3;
}
void record(string s,int A){
int point = changeP(s[0],A); // 将点数转化为数字 A 看做几
int color = changeC(s[1]); // 将花色转化为数字
a[tot++] = point;
p[point] ++;
c[color] ++;
}
void count()//统计
{
cnt2 = cnt3 = cnt4 = 0;
for(int i = 1; i <= 14; i++){
if(p[i] == 2) cnt2 ++;
else if(p[i] == 3) cnt3 ++;
else if(p[i] == 4) cnt4 ++;
} //对子，三条，四条判断
stg = 1; // 是否为顺子
sort(a,a+5);
for(int i = 1 ;i < 5;i++){
if(a[i] != a[i-1] + 1){
stg = 0;
break;
}
} // 判断是否为顺子
flu = 0; // 是否为同花
for(int i = 0 ;i < 4;i++){
if(c[i] == 5){
flu = 1;
break;
}
}
}
void check(){ //检查牌力
if(flu && stg && a[0] == 10){ // 皇家同花顺判断
maxx = min(1,maxx); // 更新牌力
return;
}
if(flu && stg){ // 同花顺判断
maxx = min(2,maxx); // 更新牌力
return;
}
if(cnt4){ // 四条判断
maxx = min(3,maxx);
return;
}
if(cnt3 && cnt2){ //葫芦判断
maxx = min(4,maxx);
return;
}
if(flu){ // 同花判断
maxx = min(5,maxx);
return;
}
if(stg){ // 顺子判断
maxx = min(6,maxx);
return;
}
if(cnt3){ // 三条判断
maxx = min(7,maxx);
return;
}
if(cnt2 == 2){ //两对判断
maxx = min(8,maxx);
return;
}
if(cnt2 == 1){ // 一对判断
maxx = min(9,maxx);
return;
}
// 剩下就是单张的情况
maxx = min(10,maxx);
return;
}
void solve0(int A) // 一张手牌都不用的情况，并且将 A 看成几
{
init();
for(int i = 0; i < 5; i++){
record(r[i],A); // 将 A 看作是几
}
count();
check();
}
void solve1(string tmp, int A){ // 恰好使用一张手牌
for(int i = 0 ; i < 5 ;i++){
init();
record(tmp,A);
for(int j = 0; j < 5 ;j++ ){
if(i == j) continue;
record(r[j],A);
}
count();
check();
}
}
void solve2(int A){ // 恰好使用两张手牌
for(int i = 0 ;i < 5; i++){
for(int j = i + 1 ;j < 5; j++){
init();
record(h[0],A);
record(h[1],A);
for(int k = 0 ; k < 5 ; k++){
if(k == i || k == j){
continue;
}
record(r[k],A);
}
count();
check();
}
}
}
// 答案数组
string ans[] = {"","ROYAL FLUSH",
"STRAIGHT FLUSH",
"FOUR OF A KIND",
"FULL HOUSE",
"FLUSH",
"STRAIGHT",
"THREE OF KIND",
"TWO PAIR",
"ONE PAIR",
"HIGH CARD"};
int main(){
freopen("poker.in","r",stdin);
freopen("poker.out","w",stdout);
int T;
cin>>T;
while(T--){
maxx = 10;// 最大牌力初始化是单牌
for(int i = 0 ; i <2 ;i++)cin>>h[i];
for(int i = 0 ; i <5 ;i++)cin>>r[i];
// 一张牌都不用的情况
solve0(1);
solve0(14);
// 用一张牌的 情况， 枚举使用手里哪一张 , 将 A 看作几
solve1(h[0],1);
solve1(h[1],1);
solve1(h[0],14);
solve1(h[1],14);
// 用两张牌的情况, 将 A 看作几
solve2(1);
solve2(14);
cout << ans[maxx] << endl;
}
return 0;
}
4.青蛙跳荷叶
这个题目不太好解释，建议先读完题再看
数据
对于1-5数据点，y1,y2在x不同两边
则直接扫一遍(y1-y2)的所有数据的差值每次更新最大值即可（假设y1<y2），20分
对于1-20数据点，1<=n<=1e5
又看到最大值最小，想到二分答案，80分
但是对于21-25数据点，n<=5*1e6
那O(nlogn)肯定是过不了的
只能是O(n);
是的，正解是贪心思想，只要想到怎么贪就简单了
思路
对于y1,y2在x同边的情况，假设y1离x更近
首先直接忽略比y2还远的点 和 x另一侧的点，因为对答案没有贡献
y1-y2中间的点肯定是交给y2比较好
扫完之后让y2离y1差1,（比y1远）
通过简单推导可得，一定是隔一个跳一下最好
因为如果离一个落脚点较近的青蛙跳了，
则另一个青蛙下一次就要隔2个跳一下，这个值一定是比隔一个跳一下大的
就会使最大值更大
详细的证明过程还请读者自行思考
还是不懂的看代码注释
最后贴上ac代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+19;
int n,maxx;
int a[maxn],x,k1,k2;//因为用了万能头包含cmath，定义y1会报错
inline int read(){//输入有5*10e6，用快读优化读入
int x = 0, f = 1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main(){
freopen("frogKingdom.in","r",stdin);
freopen("frogKingdom.out","w",stdout);
n=read();
maxx=-1;
for(int i=1;i<=n;i++)
a[i]=read();
x=read();
k1=read();
k2=read();
if((x>k1) ^ (x>k2)){//异或判断，如果异边，直接扫y1-y2
if(k1>k2)
swap(k1,k2);
for(int i=k1;i<k2;i++)
maxx=max(maxx,a[i+1]-a[i]);
cout<<maxx<<endl;
return 0;//直接结束
}else{//k1,k2同边
if(x<k1){
if(k1>k2)swap(k1,k2);//让k1离x更近
for(int i=k1+2;i<=k2;i++){//先处理y1-y2中间的点
maxx=max(maxx,a[i]-a[i-1]);
}
k2=k1+1;
int now1=k1,now2=k2;
for(int i=k1-1;i>=x;i--){//隔一个跳一下
if(now1<now2){
maxx=max(maxx,a[now2]-a[i]);
now2=i;
}
else{
maxx=max(maxx,a[now1]-a[i]);
now1=i;
}
}
}else{
if(k1<k2)swap(k1,k2);//让k1离x更近
for(int i=k1-2;i>=k2;i--){//先处理y1-y2中间的点
maxx=max(maxx,a[i+1]-a[i]);
}
k2=k1-1;
int now1=k1,now2=k2;
for(int i=k1+1;i<=x;i++){//隔一个跳一下
if(now1>now2){
maxx=max(maxx,a[i]-a[now2]);
now2=i;
}
else{
maxx=max(maxx,a[i]-a[now1]);
now1=i;
}
}
}
cout<<maxx<<endl;
}
return 0;//好习惯
}
有帮助，赞一个