暑假刷题第18天--7/30

news/2024/10/31 3:20:58/

165. 小猫爬山 - AcWing题库(dfs)

#include<iostream>
#include<string>
#include<bitset> 
#include<cstring>
#include<algorithm>
using namespace std;
const int N=18;
bool vis[N];
int a[N],n,ans,sum[N],k;
bool cmp(int x,int y){return x>y;
}
void dfs(int x,int t){if(t>=ans)return;if(x==n){ans=min(ans,t);return;}for(int i=1;i<=t;i++){//第一种选择--放到原数组if(sum[i]+a[x]<=k){sum[i]+=a[x];dfs(x+1,t);sum[i]-=a[x];}}sum[t+1]=a[x];//第二种选择放到新数组中dfs(x+1,t+1);sum[t+1]=0;
}
int main(){cin>>n>>k;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n,cmp);ans=n;dfs(0,1);cout<<ans<<endl;
}

167. 木棒 - AcWing题库(dfs+剪枝--重点理解)

#include<iostream>
#include<string>
#include<bitset> 
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int a[65];
int length,sum;
bool vis[65];
bool cmp(int x,int y){return x>y;
}
int dfs(int u,int h,int x){//u为几组木棍成功, h目前长度 ,x为枚举位置if(u*length==sum)return 1;//总长度相等就成功if(h==length)return dfs(u+1,0,0);//这组成功for(int i=x;i<n;i++){if(h+a[i]>length||vis[i])continue;vis[i]=true;//标记使用if(dfs(u,h+a[i],i+1)==1)return 1;vis[i]=false;//取消标记if(!h||a[i]+h==length)return false;//第一根失败,或最后一根失败直接失败int j=i;//长度相等的一定失败while(j<n&&a[j]==a[i])j++;i=j-1;}return false;
}
int main(){while(cin>>n&&n){memset(vis,0,sizeof(vis));sum=0;for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}sort(a,a+n,cmp);length=1;for(length=1;length<=sum;length++){if(sum%length==0&&dfs(0,0,0)){cout<<length<<endl;break;}}}
}

4974. 最长连续子序列 - AcWing题库(双指针)

#include<iostream>
#include<queue>
#include<map>
using namespace std;
map<int,int>ma;
typedef pair<int,int>PII;
int a[1000005];
int p[1000005];
int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}ma[a[0]]++;int s=1;int ans=0;for(int i=0,j=0;j<n;){if(s<=2){ans=max(ans,j-i+1);j++;if(ma[a[j]]==0)s++;ma[a[j]]++;}else {ma[a[i]]--;if(ma[a[i]]==0)s--;i++;}}cout<<ans<<endl;
}

3321. ATM队列 - AcWing题库(排序--签到)

#include<iostream>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
map<int,int>ma;
typedef pair<int,int>PII;
struct node{int x,y;
}a[1000005];
bool cmp(node q,node w){if(q.x!=w.x)return q.x<w.x;return q.y<w.y;
}
int main(){int t;cin>>t;for(int i=1;i<=t;i++){int n,k;cin>>n>>k;for(int j=0;j<n;j++){int q;cin>>q;a[j].x=q/k;if(q%k!=0)a[j].x++;a[j].y=j+1;}printf("Case #%d: ",i);sort(a,a+n,cmp);for(int j=0;j<n;j++){cout<<a[j].y<<' ';}cout<<endl;}
}


http://www.ppmy.cn/news/991371.html

相关文章

数电基础知识学习笔记

文章目录&#xff1a; 一&#xff1a;逻辑门 1.逻辑门电路的分类 1.1 按逻辑&#xff08;逻辑门&#xff09; 1.1.1 逻辑定义 1.1.2 常见数字电路相关符号 1.1.3 电路图表示 1.1.4 逻辑门电路图像符号 1.2 按电路结构 1.3 按功能特点 2.高低电平的含义 3.常见的门…

在CSDN学Golang云原生(监控解决方案Prometheus)

一&#xff0c;记录规则配置 在golang云原生中&#xff0c;通常使用日志库记录应用程序的日志。其中比较常见的有logrus、zap等日志库。这些库一般支持自定义的输出格式和级别&#xff0c;可以根据需要进行配置。 对于云原生应用程序&#xff0c;我们通常会采用容器化技术将其…

【微服务】springboot整合mongodb使用详解

目录 一、mongodb简介 1.1 什么是mongodb 1.2 mongodb特点 二、mongodb中的核心术语 2.1 mogodb与数据库对比 2.2 mongodb中的核心概念 2.3 与关系数据库的差异 2.3.1 半结构化 2.3.2 支持多级嵌套 2.3.3 关系弱化 三、mongodb 技术优势和应用场景 3.1 mongodb 技术…

SOLIDWORKS软件的优势分析 硕迪科技

在现代的机械设计领域&#xff0c;SOLIDWORKS是一款备受青睐三维设计软件&#xff0c;它具备强大的建模和设计功能&#xff0c;在全球范围内广泛应用于机械设计和工程领域&#xff0c;为用户提供了全面的工程解决方案。本文就SOLIDWORKS的优势进行详细分析。 1、易于学习和使用…

【计算机网络】10、ethtool

文章目录 一、ethtool1.1 常见操作1.1.1 展示设备属性1.1.2 改变网卡属性1.1.2.1 Auto-negotiation1.1.2.2 Speed 1.1.3 展示网卡驱动设置1.1.4 只展示 Auto-negotiation, RX and TX1.1.5 展示统计1.1.7 排除网络故障1.1.8 通过网口的 LED 区分网卡1.1.9 持久化配置&#xff08…

计算机网络知识点汇总(持续更新)

文章目录 第一章 概述1.1 计算机网络在信息时代的作用信息服务基础设施我国互联网发展状况 1.2 因特网概述网络、互联网、因特网的基本概述因特网发展的三个阶段因特网的标准化工作 1.3 三种交换方式电路交换分组交换报文交换 1.4 计算机网络的定义和分类定义分类按交换技术按使…

第六章 HL7 架构和可用工具 - 定义新的消息类型和结构类型

文章目录 第六章 HL7 架构和可用工具 - 定义新的消息类型和结构类型编辑数据结构和代码表 第六章 HL7 架构和可用工具 - 定义新的消息类型和结构类型 消息类型标识消息并与 HL7 MSH:9 字段中的值匹配。定义消息类型时&#xff0c;指定发送消息结构类型&#xff08;可能与消息类…

Linux6.2 ansible 自动化运维工具(机器管理工具)

文章目录 计算机系统5G云计算第一章 LINUX ansible 自动化运维工具&#xff08;机器管理工具&#xff09;一、概述二、ansible 环境安装部署三、ansible 命令行模块1.command 模块2.shell 模块3.cron 模块4.user 模块5.group 模块6.copy 模块7.file 模块8.hostname 模块9.ping …