2023 春季测试 题解

幂次

这道题写了暴力,但是超时了。这道题难度还行,来分析一下。首先很显而易见,当 k ≥ 3 k≥3 k3时,是可以通过枚举底数来暴力解决的。定义 a a a作为底数,定义 b b b作为指数。通过 w h i l e while while循环每次枚举 a a a b b b次方 ( b ≥ 2 ) (b≥2) (b2),外部通过循环枚举 a a a
我们首先需要特判一下,如果k=1,那么答案一定是n,直接输出即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> vis;
int cnt=0;
signed main(){int n,k;cin>>n>>k;if(k==1){//不用说了吧 cout<<n;return 0;}int a,b;for(int i=2;i*i*i<=n;i++){//枚举底数,只看3次方就够了a=i*i;b=2;while(a<=n/i){a*=i,b++;if(vis[a]){//已经有了continue;}if(b<k){//次数不够continue;}vis[a]=1;cnt++;}}if(k>=3){cout<<cnt+1;//加1,因为1没有被判断过return 0;}return 0;
}

接下来我们要考虑怎样找平方数:
我们知道,n个数里,有 n \sqrt{n} n 个平方数,其中肯定有与可以表示成其他方式的表示方法,所以我们需要特判一下,来将多余的答案记录下来,最后减去即可。

if((int)sqrtl(a)*(int)sqrtl(a)==a){sum++;
}

c o d e code code

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> vis;
int cnt=0;
int sum=0;
signed main(){int n,k;cin>>n>>k;if(k==1){cout<<n;return 0;}int a,b;for(int i=2;i*i*i<=n;i++){//枚举底数,只看3次方就够了a=i*i;b=2;while(a<=n/i){a*=i,b++;if(vis[a]){//已经有了continue;}if(b<k){//次数不够continue;}if((int)sqrtl(a)*(int)sqrtl(a)==a){sum++;}vis[a]=1;cnt++;}}if(k>=3){cout<<cnt+1;//加1,因为1没有被判断过return 0;}cout<<(int)sqrtl(n)+cnt-sum;return 0;
}

涂色游戏

这道题还是挺简单的,我们知道一个格子的颜色是由他的行和列决定的,由于是先后涂色,所以我们用结构体记录每一行或者每一列的颜色,我们还需要记录每一行或者每一列叠加的时间,最终每个格子的颜色是由叠加的时间决定的,我们需要枚举 t , q t,q tq。由于时间复杂度不是很大,还能接受,所以我们可以直接输出。
c o d e code code

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct maxtr{int ys,tt;
}h[maxn],l[maxn];
int t,n,m,q;
int main(){scanf("%d",&t);for(int k=1;k<=t;k++){scanf("%d%d%d",&n,&m,&q);memset(h,0,sizeof h);memset(l,0,sizeof l);for(int j=1;j<=q;j++){int op,a,b;scanf("%d%d%d",&op,&a,&b);if(op==0){h[a].ys=b;h[a].tt=j;}if(op==1){l[a].ys=b;l[a].tt=j;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)if(h[i].tt>l[j].tt){cout<<h[i].ys<<" ";}else{cout<<l[j].ys<<" ";}cout<<endl;}}return 0;
}

圣诞树

我想,我有生之年怕是不会活到3202年的圣诞节了哎,不装了,我摊牌了,我是修道者,但我不过圣诞节,大家要相信科学哦
题意:给你一个平面上的 n n n个点的凸包,求 TSP 路线,即从最高点出发并遍历所有点的最短的路径。 n ≤ 1000 。 n\le 1000。 n1000
来看思路:
结论:路线不会交叉。
证明:因为凸四边形对角线长度和一定大于一组对边的长度和,所以如果 ( i , j ) (i,j) (i,j) ( a , b ) (a,b) (a,b)交叉,我们将这两条分别更换为 ( i , a ) (i,a) (i,a) ( j , b ) (j,b) (j,b)答案一定变小。
对于随意一条路径,我们使用调整法,每次随便选一组交叉的边调整至不交叉,一定可以调整到整条路径不交叉。因为每次调整都会使路径长度变短,所以调整次数有限并不会调整回之前的状态。
我们从最高点开始按顺时针给每个点重新编号,为了方便, 0 0 0号和 n n n号点都是最高点。由于路线不会交叉,所以时时刻刻没有被遍历过的结点的新编号都是一段连续的区间。
考虑设计 dp,令 f l , r , 0 / 1 f_{l,r,0/1} fl,r,0/1表示 [ l + 1 , r − 1 ] [l+1,r-1] [l+1,r1]还没有被遍历,上一个遍历的结点是 l / r l/r l/r时的最短路径。初始状态 f 0 , n , 0 = f 0 , n , 1 = 0 , f_{0,n,0}=f_{0,n,1}=0, f0,n,0=f0,n,1=0一次转移就是 f l , r , 1 = min ⁡ ( f l , r + 1 , 0 + dis ( l , r ) , f l , r + 1 , 1 + dis ( r , r + 1 ) ) f_{l,r,1}=\min(f_{l,r+1,0}+\text{dis}(l,r),f_{l,r+1,1}+\text{dis}(r,r+1)) fl,r,1=min(fl,r+1,0+dis(l,r),fl,r+1,1+dis(r,r+1))
要输出方案就记录一下决策就好了。
c o d e code code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
void write(int x) {if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');
}
const int N = 1e3 + 10;
const ld INF = 1e18;
int n, k, g[N][N][2], p[N];
ld px[N], py[N], f[N][N][2];
inline ld sqr(ld x) {return x * x;
}
inline ld dis(int x, int y) {return sqrt(sqr(px[p[x]] - px[p[y]]) + sqr(py[p[x]] - py[p[y]]));
}
inline void answer(int l, int r, int t) {if (l < 0 || r > n) return ;if (t == 0) {if (g[l][r][0]) answer(l - 1, r, 1);else answer(l - 1, r, 0);} else {if (g[l][r][1]) answer(l, r + 1, 1);else answer(l, r + 1, 0);}write(t ? p[r] : p[l]), putchar(' ');
}
int main() {scanf("%d", &n);ld tmp = -INF;for (int i = 1; i <= n; i++) {scanf("%Lf %Lf", px + i, py + i);if (py[i] > tmp) tmp = py[i], k = i;}for (int i = k; i <= n; i++)p[i - k] = i;for (int i = 1; i <= k; i++)p[i + n - k] = i;for (int l = 0; l <= n; l++)for (int r = l; r <= n; r++)f[l][r][0] = f[l][r][1] = INF;f[0][n][0] = f[0][n][1] = 0;for (int l = 0; l <= n; l++)for (int r = n; r > l + 1; r--) {ld LL = f[l][r][0] + dis(l, l + 1), LR = f[l][r][1] + dis(r, l + 1);if (LL < LR) f[l + 1][r][0] = LL;else f[l + 1][r][0] = LR, g[l + 1][r][0] = 1;ld RL = f[l][r][0] + dis(l, r - 1), RR = f[l][r][1] + dis(r, r - 1);if (RL < RR) f[l][r - 1][1] = RL;else f[l][r - 1][1] = RR, g[l][r - 1][1] = 1;}ld ans = INF;int pos = 0, qwq = 0;for (int i = 0; i < n; i++)for (int j = 0; j <= 1; j++) {if (f[i][i + 1][j] < ans) {ans = f[i][i + 1][j];pos = i, qwq = j;}}answer(pos, pos + 1, qwq);return 0;
}

密码锁

这道题…还不会,看不太懂。
准备打打暴力。
重新看了遍题,发现 k = 1 k=1 k=1是很好做出来的,直接用最大值减去最小值就可以了,这样可以通过#1,#2得到 10 p t s 10pts 10pts

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, b[N];
const int mxn1=0,min1=0x3f3f3f3f;
int maxn1,main1;
int main() {int t, k;cin >> t >> k;while (t--) {maxn1=mxn1;main1=min1;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for(int i=1;i<=n;i++){maxn1=max(a[i],maxn1);main1=min(a[i],main1);}cout<<maxn1-main1<<endl;}return 0;
}

现在来思考 k = 2 k=2 k=2是什么怎么个事。
我们注意到我们所求答案的最大值为最大值减去最小值,如果想使答案低于这个最大值,就必须让最大值跟最小值不在同一行。
我们可以设最大值 m a x n maxn maxn在第一行,最小值 m i n n minn minn在第二行,二分极差的最大值为 m i d mid mid。对于第一行,判定条件为 m a x n − a i ≤ m i d , maxn-a_i≤mid, maxnaimid,第二行则是 a i − m i n n ≤ m i d 。 a_i-minn≤mid。 aiminnmid
时间复杂度为 O ( n l o g n ) 。 O(n log n)。 O(nlogn)
40 p t s 40pts 40pts

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 50010, M = 10;
int a[M][N];
int maxx[M][N], minn[M][N];
int t, n, m;
int ans = 0x3f3f3f3f;
void dfs(int deep){if(deep == n + 1){int res = 0;for(int i = 1; i <= m; i ++){res = max(res, maxx[i][n] - minn[i][n]);}ans = min(ans, res);return;}for(int j = 0; j < m; j ++){for(int i = 1; i <= m; i ++){int mid;if(i + j > m)mid = i + j - m;else mid = i + j;maxx[i][deep] = max(maxx[mid][deep - 1], a[i][deep]);minn[i][deep] = min(minn[mid][deep - 1], a[i][deep]);}dfs(deep + 1);}
}
signed main(){cin >> t >> m;if(m == 1){while(t --){cin >> n;int maxxx = 0, minnn = 0x3f3f3f3f;for(int i = 1; i <= n; i ++){int a;cin >> a;maxxx = max(maxxx, a);minnn = min(minnn, a);}cout << maxxx - minnn << endl;;}return 0;}while(t --){cin >> n;ans = 0x3f3f3f3f;for(int i = 1; i <= m; i ++){for(int j = 1; j <= n; j ++){cin >> a[i][j];maxx[i][j] = 0;minn[i][j] = 0x3f3f3f3f;}minn[i][0] = 0x3f3f3f3f;maxx[i][0] = 0;}dfs(1);cout << ans << endl;}return 0;
}

剩下的两种情况原谅在下能力有限,不能讲述完整。

但贴心的善良的我给大家找了看似好理解的博客点这里

c o d e code code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10, inf = INT_MAX;
int n, k, t;
int mx1, mn1;
int a[maxn + 10][6]/*a[n][k] n列n串*/;
int mx[maxn + 10], mn[maxn + 10];
int main() {cin >> t >> k;if (k == 1) {while (t--) {cin >> n;int mx1 = 0, mn1 = INT_MAX, a1;while (n--)cin >> a1, mn1 = min(mn1, a1), mx1 = max(mx1, a1);cout << mx1 - mn1 << "\n";}return 0;}int cnt = (k == 4 ? 124 : 40);while (t--) {cin >> n;int ans = inf;for (int i = 0; i < k; ++i)for (int j = 1; j <= n; ++j)cin >> a[j][i];for (int H = 1; H < cnt; ++H) {random_shuffle(a + 1, a + 1 + n); //打乱n串顺序memset(mx, -0x3f, sizeof mx);memset(mn, 0x3f, sizeof mn); //每行极值for (int i = n; i >= 1; --i) { //正在贪i列int lst = inf, pos = 0;for (int op = 1; op <= k; ++op) { //转op次int res = 0;for (int j = 0; j < k; ++j) {int tmp = (op + j) % k;res = max(res, max(mx[tmp], a[i][j]) - min(mn[tmp], a[i][j]));}if (lst > res)lst = res, pos = op;}for (int j = 0; j < k; ++j) {int tmp = (pos + j) % k;mx[tmp] = max(mx[tmp], a[i][j]);mn[tmp] = min(mn[tmp], a[i][j]);}}int res = 0;for (int i = 0; i < k; ++i)res = max(res, mx[i] - mn[i]);ans = min(ans, res);}cout << ans << "\n";}return 0;
}

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

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

相关文章

windows下安装python库wordCloud报错

换电脑安装wordcloud半天安装失败&#xff0c;记录一下遇到的坑&#xff0c;也给大家节省点时间。 方法1&#xff1a; 错误呢就是下面这个&#xff0c;说没c编译器&#xff0c;要不就去他给的地址上安装一下&#xff0c;我安装了一下好像没什么用&#xff0c;也没太敢勾选&am…

未来之维,陈欣的智能CAD

第一章 新世界的曙光 在不远的未来&#xff0c;人类科技取得了前所未有的进步。人工智能不仅渗透到了生活的每一个角落&#xff0c;而且开始在科学研究、艺术创作乃至人类情感交流中扮演重要角色。在这个充满无限可能的时代&#xff0c;有一位年轻的女工程师——陈欣&#xff…

目前最新最好用 NET 混淆工具 .NET Reactor V6.9.8

目前最新最好用 NET 混淆工具 .NET Reactor V6.9.8 1、.NET Reactor V6.9.8 功能简介2、官方下载 1、.NET Reactor V6.9.8 功能简介 业界领先的源代码保护 .NET Reactor通过多种方法来防止反编译&#xff0c;这些方法会将 .NET 程序集转换为任何现有工具都无法反编译的进程。…

2024 Rust现代实用教程:1.2编译器与包管理工具以及开发环境搭建

文章目录 一、Rust的编译器rustc二、开发环境搭建三、Rust的包管理工具Cargo四、项目结构1.Cargo.toml文件2.创建一个可执行文件项目3.创建一个库项目 参考 一、Rust的编译器rustc 查看版本 rustc-version编译生成二进制文件 rustc -o output filename filename.rs编译生成库…

macOS Sonoma 14.7.1 (23H222) Boot ISO 原版可引导镜像下载

macOS Sonoma 14.7.1 (23H222) Boot ISO 原版可引导镜像下载 2024 年 10 月 28 日&#xff0c;Apple 智能今日登陆 iPhone、iPad 和 Mac。用户现可借助 Apple 智能优化写作&#xff0c;为通知、邮件和消息生成摘要&#xff0c;体验交互更自然、功能更丰富的 Siri&#xff0c;使…

Kafka相关API开发

(一)引入依赖 用API直接去操作kafka(读写数据)在实际开发中用的并不多&#xff0c;学习它主要还是为了加深对Kafka功能的理解。kafka的读写操作&#xff0c;实际开发中&#xff0c;是通过各类更上层的组件去实现。而这些组件在读写kafka数据时&#xff0c;用的当然是kafka的jav…

Backtrader 数据篇 02

Backtrader 数据篇 本系列是使用Backtrader在量化领域的学习与实践&#xff0c;着重介绍Backtrader的使用。Backtrader 中几个核心组件&#xff1a; Cerebro&#xff1a;BackTrader的基石&#xff0c;所有的操作都是基于Cerebro的。Feed&#xff1a;将运行策略所需的基础数据…

Leetcode224 -- 基本计算器及其拓展

题目分析&#xff1a; 其实这个计算器的实现并不难&#xff0c;因为除了括号就剩下加减法嘛&#xff0c;括号肯定比加减法先执行&#xff0c;但是加减法是同级的&#xff0c;只是会改变数字的正负号而已&#xff0c;所以实现的逻辑并不是很难&#xff0c;我们只需要一个栈&…

【jvm】为什么Xms和Xmx的值通常设置为相同的?

目录 1. 说明2. 避免性能开销3. 提升稳定性4. 简化配置5. 优化垃圾收集6. 获取参数6.1 代码示例6.2 结果示例 1. 说明 1.-Xms 和 -Xmx 参数分别用于设置堆内存的初始大小&#xff08;最小值&#xff09;和最大大小。2.在开发环境中&#xff0c;开发人员可能希望快速启动应用程…

瑞芯微RK3566/RK3568 Android11下该如何默认屏蔽导航栏/状态栏?看这篇文章就懂了

本文介绍瑞芯微RK3566/RK3568在Android11系统下&#xff0c;默认屏蔽导航栏/状态栏方法&#xff0c;使用触觉智能Purple Pi OH鸿蒙开发板演示&#xff0c;搭载了瑞芯微RK3566芯片&#xff0c;类树莓派设计&#xff0c;Laval官方社区主荐&#xff0c;已适配全新OpenHarmony5.0 R…

使用AIM对SAP PO核心指标的自动化巡检监控

一、背景 由于SAP PO系统维护成本较高&#xff0c;各类型异常报错等都需要人员进行时刻监控和响应&#xff0c;遂由AIM平台进行自动化巡检SAP PO的各指标&#xff0c;然后告警通知用户&#xff0c;节省维护成本和提高工作效率 二、核心指标监控 SAP PO失败消息 适用于S…

openpnp - 手工修改配置文件(元件高度,size,吸嘴)

文章目录 openpnp - 手工修改配置文件(元件高度,size,吸嘴)概述笔记parts.xmlpackages.xml 手工将已经存在的NT1,NT2拷贝出来改名备注END openpnp - 手工修改配置文件(元件高度,size,吸嘴) 概述 载入新板子贴片准备时&#xff0c;除了引入Named CSV文件&#xff0c;还要在ope…

Centos下安装Maven(无坑版)

Linux 安装 Maven Maven 压缩包下载与解压 华为云下载源&#xff0c;自行选择版本 下面的示例使用的是 3.8.1 版本 wget https://repo.huaweicloud.com/apache/maven/maven-3/3.8.1/binaries/apache-maven-3.8.1-bin.tar.gz解压 tar -zxvf apache-maven-3.8.1-bin.tar.gz移…

算法:排序

排序算法 1. 简单排序1.1 直接插入排序1.2 冒泡排序1.3 简单选择排序 2. 希尔排序3. 快速排序4. 堆排序5. 归并排序 将文件的内容按照某种规则进行排列。 排序算法的稳定判定&#xff1a;若在待排序的一个序列中&#xff0c; R i R_i Ri​和 R j R_j Rj​的关键码相同&#xf…

Topaz Photo AI for Mac人工智能图像降噪软件 安装教程【保姆级教程,简单操作轻松上手】

Mac分享吧 文章目录 Topaz Photo AI for Mac人工智能图像降噪软件 安装完成&#xff0c;软件打开效果一、Topaz Photo AI 人工智能图像降噪软件 Mac电脑版——v3.3.0⚠️注意事项&#xff1a;1️⃣&#xff1a;下载软件2️⃣&#xff1a;安装软件&#xff0c;根据步骤完成操作…

k8s部署redis远程连接示例

一、环境 节点 IP 服务 master 192.168.126.46 docker、kubeadm、kubelet、kubectl、flannel、telnet node1 192.168.126.47 docker、kubeadm、kubelet、kubectl、flannel、telnet node2 192.168.126.48 docker、kubeadm、kubelet、kubectl、flannel、telnet ubunt…

ubuntu内核更新导致显卡驱动掉的解决办法

方法1&#xff0c;DKMS指定内核版本 用第一个就行 1&#xff0c;借鉴别人博客解决方法 2&#xff0c;借鉴别人博客解决方法 方法2&#xff0c;删除多于内核的方法 系统版本&#xff1a;ubuntu20.24 这个方法是下下策&#xff0c;如果重装驱动还是不行&#xff0c;就删内核在…

Apache Hive分布式容错数据仓库系统

Apache Hive™是一个分布式的、容错的数据仓库系统&#xff0c;它支持大规模的分析&#xff0c;并使用SQL方便地读取、写入和管理驻留在分布式存储中的pb级数据。 Apache Hive Apache Hive是什么 Apache Hive是一个分布式的、容错的数据仓库系统&#xff0c;支持大规模的分析…

运用AI视频拍摄技术生成3D场景:适用于建模、XR及文旅项目Demo制作

利用AI技术从拍摄的视频中生成3D场景&#xff0c;这种创新方法非常适合用于快速构建高质量的3D模型。生成的3D场景不仅能够用于建筑和设计行业的模型展示&#xff0c;还能应用于扩展现实&#xff08;XR&#xff09;技术的大空间体验开发。此外&#xff0c;在文化旅游领域&#…

论文提交步骤 | 2024年第五届MathorCup大数据竞赛

2024年第五届MathorCup数学应用挑战赛—大数据竞赛于2024年10月25日下午6点正式开赛。 论文和承诺书、支撑材料&#xff08;可选&#xff09;及计算结果文档由各参赛队队长电脑登录下方报名主页提交&#xff1a; https://www.saikr.com/vse/bigdata2024 初赛作品提交截止时间为…