当前位置: 首页 > article >正文

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.kler.cn/a/372582.html

相关文章:

  • ubuntu 22.04网线连接无ip、网络设置无有线网界面(netplan修复)
  • 电子电气架构 --- 车载芯片现状
  • 【界面改版】JimuReport 积木报表 v1.9.0 版本发布,填报能力和大屏能力
  • 使用VS2019将C#代码生成DLL文件在Unity3D里面使用(一)
  • 代码随想录算法训练营第十二天(补) 二叉树| 二叉树理论知识、深度优先遍历、广度优先遍历
  • 晓羽扫码点餐快销版系统源码
  • 论坛系统测试报告
  • Postgresql源码(137)执行器参数传递与使用
  • 大语言模型(LLM)快速理解
  • DOM---鼠标事件类型(移入移出)
  • 基于Unet卷积神经网络的脑肿瘤MRI分割
  • LinkedList和链表(下)
  • 豆包,攻克数字是个什么工具?《GKData-挖掘数据的无限可能》(数据爬虫采集工具)
  • Ceph 存储系统全解
  • TMUX1308PWR规格书 数据手册 具有注入电流控制功能的 5V 双向 8:1单通道和 4:1 双通道多路复用器芯片
  • Android平台RTSP|RTMP播放器高效率如何回调YUV或RGB数据?
  • asp.net core 跨域配置不起作用的原因
  • 【Java多线程】9 Java 的并发性能优化
  • 如何将钉钉付款单数据集成到MySQL数据库
  • Kafka 客户端工具使用分享【offsetexplorer】
  • Resnet搭建介绍及代码撰写详解(总结6)
  • Java Condition 目录
  • 如何在Linux系统中使用Zabbix进行监控
  • CentOS 9 Stream 上安装 JDK 17
  • day04|计算机网络重难点之HTTP/1.0和HTTP/1.1的区别、HTTP/2.0与HTTP/1.1的区别、介绍HTTP/3.0
  • 【C++刷题】力扣-#575-分糖果