8.17模拟赛题解

在这里插入图片描述
先考虑空间能不能把N个座位放好 最优的方式就是挨着摆放
那么一排能摆放Q=L/x的商个椅子 ,然后计算摆放完N个座位需要多少排,N/Q 向上取整
计算所需要的排总共占据多宽,讨论有没有超过W,然后讨论剩余空间还能放几条走廊
如果走廊数量为0,那么无解。最后一条走廊理论上可以挨着两排位置,所以说只需要计算理论上最多能有多少座位挨着走廊,然后跟实际座位数取min即可 ,注意一排可能一个座位也放不了,要讨论

#include <bits/stdc++.h>
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("output/out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef long double ld;int n,l,w,x,y,a;int main()
{// freopen("aisle.in","r",stdin);//freopen("aisle.out","w",stdout);cin>>n>>l>>w>>x>>y>>a;int numl=l/x;int numr;if (numl==0) {puts("-1");return 0;}if (n%numl==0) numr=n/numl;else numr=n/numl+1;int z=numr*y;if (w-z>=a){int num=(w-z)/a;if (num<=numr/2) printf("%d\n",min(n,numl*2*num));else printf("%d\n",n);}else puts("-1");return 0;
}

在这里插入图片描述
首先要明白,B进制下D位数的范围是哪到哪,不清楚的可以拿十进制推一推
最小值就是BD-1 ,最大值是BD -1
所以要想知道有多少个数满足两个条件,相当于取区间交的长度 计算L R做比较即可
注意超过1e18都不算,为了防止计算溢出,通常使用除法来判断。左端点溢出一定无解,右端点溢出就让它成为1e18

当然,本题可以难度继续升级,移除1e18限制 。

#include<bits/stdc++.h>
using namespace std;
int j,b1,d1,b2,d2;
unsigned long long l1=1,r1,l2=1,r2;
bool f;
int main() {cin>>b1>>d1>>b2>>d2;r1=r2=1;for(int i=2; i<=d1; i++) {if(l1<=1e18/b1)l1*=b1;else {cout<<0;return 0;}}for(int i=1; i<=d1; i++)if(r1<=1e18/b1)r1*=b1;else {r1=1e18;r1++;break;}r1--;for(int i=2; i<=d2; i++) {if(l2<=1e18/b2)l2*=b2;else {cout<<0;return 0;}}for(int i=1; i<=d2; i++)if(r2<=1e18/b2)r2*=b2;else {r2=1e18;r2++;break;}r2--;if(l1>l2) {swap(l1,l2);swap(r1,r2);}if(l1<=l2&&r2<=r1)cout<<r2-l2+1;else if(l2<=l1&&r1<=r2)cout<<r1-l1+1;else if(r1>=l2)cout<<r1-l2+1;else cout<<0;return 0;
}

在这里插入图片描述
相信学了DFS的同学多少还是能做一点分数的,暴力DFS 相当于求12的排列然后代入对应编号的边去检查,小范围内还是可以拿分的。

实际上本题T组数据,每次都这样子去DFS肯定行不通的,我们考虑对12的排列的寻找进行优化

考虑编号摆放
1 2 3 4 5 6 7 8 9 10 11 12
3 2 1 6 5 4 9 8 7 12 11 10
10 11 12 7 8 9 6 5 4 1 2 3

不难发现这几种不同的排列,实际上产生的四个三角形是一模一样的所以说我们要尽量剔除这种本质相同的排列情况。如何DFS剪枝?
回忆一下最初的一个问题,N个数选R个数并且要求都按字典序输出,保证不重复不遗漏,所以说我们DFS寻找本质不同的12排列时,外部4个块要保证有序,且每个块内部也要保证有序,这样子就能不重复不遗漏。
预处理DFS寻找本质不同的12排列存起来,每次查询的时候直接枚举排列带进去检查

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<ctime>
#define LL long long
#define inf 0x3f3f3f3f
#define P pair<int,int>using namespace std;inline char nc(){/* static char buf[100000],*p1=buf,*p2=buf;if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }return *p1++;*/return getchar();
}inline void read(int &x){char c=nc();int b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}inline void read(LL &x){char c=nc();LL b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}inline void read(char &x){for (x=nc();!(x=='('||x==')');x=nc());
}inline int read(char *s)
{char c=nc();int len=1;for(;!(c=='0'||c=='1');c=nc()) if (c==EOF) return 0;for(;(c=='0'||c=='1');s[len++]=c,c=nc());s[len++]='\0';return len-2;
}
int wt,ss[19];
inline void print(int x){if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){if (x<0) x=-x,putchar('-');if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}int T,n,m,s,a[20],b[5],res,ans[5][5];
int f[15500*24][20];bool check(int x,int y,int z)
{if (x+y<=z) return false;if (x+z<=y) return false;if (y+z<=x) return false;return true;
}void dfs(int x)
{if (x==13){if (a[1]<a[4]&&a[4]<a[7]&&a[7]<a[10]){s++;for (int i=1;i<=12;i++)f[s][i]=a[i];}return ;}for (int i=1;i<=12;i++)if (b[i]==0){b[i]=1;a[x]=i;if (x%3==0){if (a[x]>a[x-1]&&a[x-1]>a[x-2]) dfs(x+1);}else dfs(x+1);b[i]=0;}
}void solve(int b[])
{int s=0;for(int i=1;i<=4;i++)if (check(a[b[i*3-2]],a[b[i*3-1]],a[b[i*3]])) s++;if (s>res){res=s;    }
}int main()
{read(T);int p=0;s=0;dfs(1);while(T--){for (int i=1;i<=12;i++)read(a[i]);res=0;for (int i=1;i<=s;i++)solve(f[i]);printf("%d\n",res);}return 0;
}

在这里插入图片描述
一定要把题目读懂,题目的要求是什么,操作又是什么。
题目最终想让
A [ 1 ] = A [ m + 1 ] A[1]=A[m+1] A[1]=A[m+1]
A [ 2 ] = A [ m + 2 ] A[2]=A[m+2] A[2]=A[m+2]
A [ m + 1 ] = A [ 2 m + 1 ] A[m+1]=A[2m+1] A[m+1]=A[2m+1]
A [ n − m ] = A [ n ] A[n-m]=A[n] A[nm]=A[n]
相当于每M个数为一个块,每个块内的第 i i i个位置最终都要变得一样
观察数据范围
在这里插入图片描述
凭直接来讲应该也是有40分是白送的(实际上也确实是暴力得分)
两个操作,一个是单点修改,一个是前缀区间翻转
不难发现完全没必要把同一段前缀区间做翻转两次,因为相当于没翻转
所以我们可以选择翻转M,2M,3M…KM 注意KM ≥ ≥ N
所以当M ≥ ≥ n \sqrt{n} n 时,K ≤ ≤ n \sqrt{n} n 所以小范围的时候,可以暴力DFS检查翻转哪些前缀区间,然后剩下不一样的点直接暴力修改,统计答案 40分到手。

但是当M ≤ ≤ n \sqrt{n} n 时就不能暴力搜索了 ,我们考虑状态转移
定义 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1]表示处理完第 i 最后一块 i~最后一块 i 最后一块并且都使得块内状态为 j 状态压缩 j状态压缩 j状态压缩 并且有没有使用区间翻转的最优操作次数
首先计算我们有多少块,直接按 N / M N/M N/M划分一下得到 K K K

在不使用操作2的情况下,既然 j j j是状态压缩后的结果,所以我们要讨论本状态下,块内的每个位置到底最终是放的是什么,如果跟本位置的符号不一样,那么就要使用操作1修改为 j j j状态对应的结果
最终得到 d p [ K ] [ j ] [ 0 ] dp[K][j][0] dp[K][j][0]的值

同理,在使用操作2的情况下,既然 j j j是状态压缩后的结果,所以我们要讨论本状态下,块内的每个位置到底最终是放的是什么,如果跟本位置的符号一样,因为现在使用了翻转 K ∗ M K*M KM这一段,所以如果未操作前 j j j状态对于某些位上的值已经匹配了,翻转后会变得不匹配,需要单点修改,那么就要使用操作1修改为 j j j状态对应的结果 。
举个例子, j j j状态为10101010 字符串当前这一段内容为10101010,虽然现在跟 j j j状态都是匹配的,但是翻转后,会全部失效,所以说本情况,匹配的时候反而需要修改。
最终得到 d p [ K ] [ j ] [ 1 ] dp[K][j][1] dp[K][j][1]的值

考虑如何向前面的块转移?倒着继续枚举K-1 K-2 …1
按照上面的方法计算,枚举最终状态,然后枚举对应的块内位置以及字符串内的实际位置
先统计单点修改的次数,考虑合并状态转移

 dp[k][j][0]=min(dp[k+1][j][0]+ans,dp[k+1][j][1]+1+ans);  [第K块] [k+1~最后一块] 进行合并     如果[k+1~最后一块]没使用前缀区间翻转就变成了j状态那么合并成[k~最后一块]没前缀区间翻转就变成了j状态的最小次数就有了一种方案 dp[k+1][j][0]+ans但是还有另一种情况,[k+1~最后一块]使用了前缀区间翻转才变成了j状态,
因为会连带翻转第K块,所以要翻转另一段前缀区间抵消这个翻转,所以操作+1
然后再合并本块的操作次数ans  

后面的转移就同理了
最后最终状态一定在 d p [ 1 ] [ j ] [ 0 / 1 ] dp[1][j][0/1] dp[1][j][0/1]上,表示把[1~最后一块]翻转成为 j j j状态的最优次数 取min即可

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<ctime>
#define LL long long
#define inf 0x3f3f3f3f
#define P pair<int,int>using namespace std;inline char nc(){/* static char buf[100000],*p1=buf,*p2=buf;if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }return *p1++;*/return getchar();
}inline void read(int &x){char c=nc();int b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}inline void read(LL &x){char c=nc();LL b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}inline void read(char &x){for (x=nc();!(x=='('||x==')');x=nc());
}inline int read(char *s)
{char c=nc();int len=1;for(;!(c=='0'||c=='1');c=nc()) if (c==EOF) return 0;for(;(c=='0'||c=='1');s[len++]=c,c=nc());s[len++]='\0';return len-2;
}
int wt,ss[19];
inline void print(int x){if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){if (x<0) x=-x,putchar('-');if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}int n,m,k,f[310][27000][2],ans,a[20];
char s[310];void dfs(int x)
{if (x==k+1){int zero[310],one[310],flag=0;for (int i=1;i<=m;i++)zero[i]=0,one[i]=0;for (int i=k;i>=1;i--){	//检查要不要翻转一下 i*m   if (a[i]) flag=1-flag;if (flag==1){					//某一段m翻转内  统计本段本位翻转后有多少0  1 for (int p=1,j=(i-1)*m+1;j<=min(n,i*m);j++,p++)if (s[j]=='0') one[p]++;else zero[p]++;}else	//不翻 {for (int p=1,j=(i-1)*m+1;j<=min(n,i*m);j++,p++)if (s[j]=='1') one[p]++;else zero[p]++;}}int res=0;for (int i=1;i<=m;i++){res+=min(zero[i],one[i]);// else 	    res+=min(zero[i],one[i]);}for (int i=1;i<=k;i++)if (a[i]) res++;ans=min(ans,res);return ;}for (int i=0;i<=1;i++)a[x]=i,dfs(x+1);//处理第x段的反转   翻转还是不翻转  
}int main()
{n=read(s);read(m);if (m<=sqrt(n)){int k=n/m;if (n%m!=0) k++;for (int i=0;i<(1<<m);i++){int ans=0;for (int p=0,j=(k-1)*m+1;j<=min(n,k*m);j++,p++){if ((i&(1<<p))){if (s[j]=='0') ans++;}else {if (s[j]=='1') ans++;}}f[k][i][0]=ans;ans=1;for (int p=0,j=(k-1)*m+1;j<=min(n,k*m);j++,p++)if ((i&(1<<p))){if (s[j]=='1') ans++;}else {if (s[j]=='0') ans++;}f[k][i][1]=ans;}for (k--;k>=1;k--)for (int i=0;i<(1<<m);i++){int ans=0;for (int p=0,j=(k-1)*m+1;j<=min(n,k*m);j++,p++)if ((i&(1<<p))){if (s[j]=='0') ans++;}else {if (s[j]=='1') ans++;}f[k][i][0]=min(f[k+1][i][0]+ans,f[k+1][i][1]+1+ans);ans=0;for (int p=0,j=(k-1)*m+1;j<=min(n,k*m);j++,p++)if ((i&(1<<p))){if (s[j]=='1') ans++;}else {if (s[j]=='0') ans++;}f[k][i][1]=min(f[k+1][i][1]+ans,f[k+1][i][0]+1+ans);}int ans=min(f[1][0][0],f[1][0][1]);for (int i=0;i<(1<<m);i++)ans=min(ans,f[1][i][0]),ans=min(ans,f[1][i][1]);print(ans),puts("");}else{	//暴力反转  枚举   k=n/m;//  n/m检查最多把前k*m段翻转 if (n%m!=0) k++;ans=n;dfs(1);print(ans),puts("");}return 0;
}

路漫漫其修远兮,学习还需踏实勤奋

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/404009.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Datawhale AI夏令营第四期】 魔搭-大模型应用开发方向笔记 Task04 RAG模型 人话八股文Bakwaan_Buddy项目创空间部署

【Datawhale AI夏令营第四期】 魔搭-大模型应用开发方向笔记 Task04 RAG模型 人话八股文Bakwaan_Buddy项目创空间部署 什么是RAG&#xff1a; 我能把这个过程理解为Kimi.ai每次都能列出的一大堆网页参考资料吗&#xff1f;Kimi学了这些资料以后&#xff0c;根据这里面的信息综…

Leading SAFe领导大规模敏捷认证公开课

课程简介 SAFe – Scaled Agile Framework是目前全球最广泛使用的大规模敏捷框架&#xff0c;也是全球敏捷相关认证中增长最快、最受认可的规模化敏捷认证。全球已有超过120万名SAFe认证专业人士。据官方统计&#xff0c;获得SAFe认证的IT专业人士平均工资增长13,000美元&…

澎湃认证显实力,浪潮信息存储兼容新篇章

浪潮信息在存储技术兼容性领域取得新突破&#xff0c;其集中式存储HF/AS系列与长擎安全操作系统24强强联合&#xff0c;成功完成澎湃技术认证。此次合作不仅验证了双方产品的无缝对接能力&#xff0c;更体现了浪潮信息在推动全产业链共建共享方面的坚定决心。 浪潮信息澎湃技术…

python人工智能001:NumPy科学计算库说明与安装

1. NumPy说明 NumPy&#xff08;Numerical Python&#xff09;是Python的一个开源数值计算扩展库。它提供了一个强大的N维数组对象ndarray&#xff0c;以及用于对这些数组进行操作的函数。NumPy的数组和数组操作是Python数据分析、机器学习、科学计算等领域的基础。 NumPy的主…

Linux 配置定时任务

Linux定时任务&#xff0c;通常被称为Cron Jobs&#xff0c;在系统管理和运维自动化领域中扮演着至关重要的角色&#xff0c;并且在日常的服务器维护活动中也展现出了广泛而深远的应用价值。这种强大的工具允许用户按照预定的时间周期自动执行各种任务&#xff0c;如数据备份、…

从零开始掌握限流技术:计数器、滑动窗口、漏桶与令牌桶详解

为什么需要限流呢&#xff1f; &#x1f539;想象一下&#xff0c;你的服务器就像一个繁忙的餐馆&#xff0c;而你的应用就像是餐馆的服务员。餐馆里人山人海&#xff0c;每个人都在争先恐后地想要点餐。这时候&#xff0c;如果没有一个好的限流机制&#xff0c;会发生什么呢&…

京东2025届秋招 算法开发工程师 第2批笔试

目录 1. 第一题2. 第二题3. 第三题 ⏰ 时间&#xff1a;2024/08/17 &#x1f504; 输入输出&#xff1a;ACM格式 ⏳ 时长&#xff1a;2h 本试卷还有选择题部分&#xff0c;但这部分比较简单就不再展示。 1. 第一题 村子里有一些桩子&#xff0c;从左到右高度依次为 1 , 1 2…

【免费】企业级大模型应用推荐:星环科技无涯·问知

无涯问知是星环科技发布的大模型应用系统&#xff0c;那么我们先简单了解下星环科技吧&#xff01; 星环科技&#xff08;股票代码&#xff1a;688031&#xff09;致力于打造企业级大数据和人工智能基础软件&#xff0c;围绕数据的集成、存储、治理、建模、分析、挖掘和流通等数…

这个是git使用的合集

如果遇到了关于git和github的bug就会写这里 2024/8/16 github一直没有打卡和上传代码是因为感觉除了做项目的情况&#xff0c;普通的学习和普通的笔记没必要记在github里&#xff1b;如果是笔记类的东西为什么不记在csdn上呢&#xff1f;如果是算法题算法网站上回有记录啊&am…

CAD图纸加密软件哪个好?(这六款大众好评度高!)

在CAD图纸加密软件领域&#xff0c;有多款软件因其高效、安全、易用等特点而广受好评。 以下是六款大众好评度较高的CAD图纸加密软件&#xff0c;它们各自具有独特的功能和优势&#xff1a; 1.安企神 特点&#xff1a;它以其强大的透明加密技术和精细化的权限管理功能著称。 …

python爬虫爬取某图书网页实例

文章目录 导入相应的库正确地设置代码的基础部分设置循环遍历遍历URL保存图片和文档全部代码即详细注释 下面是通过requests库来对ajax页面进行爬取的案例&#xff0c;与正常页面不同&#xff0c;这里我们获取url的方式也会不同&#xff0c;这里我们通过爬取一个简单的ajax小说…

MPU6050详细介绍

一、MPU6050介绍 MPU6050是由三个陀螺仪和三个加速度传感器组成的6轴运动处理组件 内部主要结构&#xff1a;陀螺仪、加速度计、数字运动处理器DMP&#xff08;Digital Motion Processor&#xff09; MPU6050有两个IIC接口&#xff0c;第一IIC接口可作为主接口给单片机传输数…

CSP-CCF 202012-1 期末预测之安全指数

一、问题描述 二、解答 #include<iostream> using namespace std; int main() {int n;cin >> n;int w[100001] { 0 };int score[100001] { 0 };for (int i 1; i < n; i){cin >> w[i] >> score[i];}int y 0;for (int i 1; i < n; i){y y …

电脑监控软件有哪些,哪款更好用?一网打尽!电脑监控软件大搜罗,总有一款适合你!

甲&#xff1a;哎&#xff0c;您听说了吗&#xff1f;这年头&#xff0c;电脑监控软件那是五花八门&#xff0c;跟变戏法似的&#xff01; 乙&#xff1a;哦&#xff1f;怎么个五花八门法&#xff1f; 甲&#xff1a;嘿&#xff0c;您还别说&#xff0c;从实时监控到网络追踪…

在HFSS中对曲线等结构进行分割(Split)

在HFSS中对曲线进行分割 我们往往需要把DXF等其他类型文件导入HFSS进行分析&#xff0c;但是有时需要对某一个曲线单独进行分割成两段修改。 如果是使用HFSS绘制的曲线&#xff0c;我们修改起来非常方便&#xff0c;修改参数即可。但是如果是导入的曲线&#xff0c;则需要使用…

js实现图片以鼠标为中心滚轮缩放-vue

功能背景 实现以鼠标在图中的位置为中心进行图片的滚轮缩放&#xff0c;现在是无论鼠标位置在哪都以图片中心进行缩放&#xff0c;这不符合预期&#xff1b; 关键点 缩放前鼠标在的位置是 A&#xff08;clinetX,clientY&#xff09; 点&#xff0c;缩放后鼠标的位置是 A’&a…

技术分享-商城篇-订单支付微信篇(十二)

B2C商城微信支付全解析&#xff1a;H5支付、小程序支付、JSAPI支付与APP支付 引言 在之前的文章中&#xff0c;我们聊了B2B2C的商城相关功能模块&#xff0c;如&#xff1a;首页布局、商品、购物车、购物结算、订单支付等&#xff0c;但是B2C商城的订单支付方式的选择&#x…

【Docker】Centos系统没有Vpn时候安装Docker

【Docker】没有Vpn时候安装Docker 背景1.安装docker之前先卸载2.基础配置3.安装docker5. 问题解决6.配置docker镜像源&#xff0c;解决网络超时 背景 工作中习惯VPN或者服务器节点为国外或者香港节点&#xff0c;最近买了一台国内服务器网络受到各种限制。 1.安装docker之前先…

uniapp/vue个性化单选、复选组件

个性化单选和复选组件在网页设计中非常常见&#xff0c;它们不仅能够提升用户界面的美观度&#xff0c;还能改善用户体验。此组件是使用vue uniapp实现的个性化单选复选组件。设计完成后&#xff0c;点击生成源码即可。 拖动组件过设计区 每行显示数量 默认支持每行三个&#…

扎心“我学了六个月 Python,怎么还是会找不到工作”

前言 &#x1f449; 小编已经为大家准备好了完整的代码和完整的Python学习资料&#xff0c;朋友们如果需要可以扫描下方CSDN官方认证二维码或者点击链接免费领取【保证100%免费】 在编程界&#xff0c;Python是一种神奇的存在。有人认为&#xff0c;只有用Python才能优雅写代码…