HUT23级训练赛

目录

A - tmn学长的字符串1

B - 帮帮神君先生

C - z学长的猫

D - 这题用来防ak

E - 这题考察FFT卷积

 F - 这题考察二进制

 G - 这题考察高精度

H - 这题考察签到

I - 爱派克斯,启动!

J - tmn学长的字符串2

K - 秋奕来买瓜


A - tmn学长的字符串1

思路:字符串模拟。

对于第一类字符串,其组成一定是合法的数字,第二类字符串则是其他剩余的情况。

对于字符串的处理:我们开一个string去记录每段字符串,对于一段字符串的记录:因为会出现空串的情况,所以我们在记录字符串时,加入一个特殊符号,在最后输出的时候特判即可。

因为是字符串模拟,所以不涉及算法,具体思路看代码注释:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
const int maxv = 4e6 + 5;
typedef pair<ll, ll> pll;


bool check(string s)//判断是否为数字字符串
{
	for(int i=0;i<s.size();i++){
		if(s[0]=='0'&&s.size()!=1){
			return false;
		}
		if(s[i]<'0'||s[i]>'9') return false;
	}
	return true;
}

void solve()
{
	string s;
	cin>>s;
	s+=";";
	vector<string> c1,c2;//使用vector去储存每个字符串
	string t;
	for(int i=0;i<s.size();i++){
		if(s[i]==','||s[i]==';'){//我们把题目给定的','和';'称为终止符,当我们遇见终止符时,就进行判断
			if(t.empty()) t.push_back('#');//如果当前用于储存的字符串t为空,那么我们就放入一个特殊字符,特殊字符只是用于应对空串的情况,其他情况不会出现特殊字符
			if(check(t)){//去检验目前字符串是否合法
				c1.push_back(t);//合法,即全为数字,那么存入1
			}
			else{
				c2.push_back(t);//否则存入2
			}
			t="";//将t清空
		}
		else t+=s[i];//如果当前不是终止符,直接将该字符加入t即可
	}
	if(c1.size()){//因为c1是储存的数字,所以不可能出现空串的情况
		cout<<"\"";
		for(int i=0;i<c1.size();i++){
            cout<<c1[i];
            if(i!=c1.size()-1) cout<<",";
		}
		cout<<"\"";
	}
	else{
		cout<<"-";
	}
	cout<<endl;
	if(c2.size()){//c2储存的其他情况的字符串,所以需要进行特判
		cout<<"\"";
		if(c2[0]!="#") cout<<c2[0];//特判特殊字符
		for(int i=1;i<c2.size();i++){
			cout<<",";
			if(c2[i]!="#") cout<<c2[i];
		}
		cout<<"\"";
	}
	else{
		cout<<"-";
	}

	cout<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	system("pause");
	return 0;
}

B - 帮帮神君先生

思路:考察最基本的二分算法。把题意抽象一下,就是对于每一个b_i,求在a数组中有多少个比b_i小的数,因为a数组和b数组都是2e5的大小,所以我们对于每一个b_i,每次去遍历一遍a数组,会超时,因为这时候我们的时间复杂度相当于是2e5*2e5,而c一秒只能跑1e8左右,所以需要算法对其进行优化。运用二分算法即可成功解决此题

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
const int maxv = 4e6 + 5;
typedef pair<ll, ll> pll;




void solve()
{
	int n,m;
	cin>>n>>m;
	vector<int> a(n),b(m);
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<m;i++) cin>>b[i];
	sort(a.begin(),a.end());
	for(int i=0;i<m;i++){
		int t=upper_bound(a.begin(),a.end(),b[i])-a.begin()-1;
		if(t>=0){
			cout<<t+1<<" ";
		}
		else cout<<0<<" ";
	}
	cout<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	system("pause");
	return 0;
}

C - z学长的猫

思路:题目要我们先删除,但先排序后删除本质上是一样的,所以先将数组进行排序,由此,此题转化为了在有序数组中寻找最大的一段符合条件的的区间,即区间中后一个数减前一个的差不能超过k,因为题目要求剩余区间全部合法,所以我们只用求出最大合法区间,然后把其他的全部删去就好。

#include<bits/stdc++.h>
 
using namespace std;
const int N=1e5+5;
typedef long long ll;
typedef pair<ll,ll> pll;
 
void solve()
{	
	int n,k;
	cin>>n>>k;
	vector<int> a(n+5);
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a.begin()+1,a.begin()+1+n);
	int cnt=1;
	int res=0;
	for(int i=1;i<n;i++){
		int x=a[i+1]-a[i];
		if(x<=k){
			cnt++;
		}
		else{
			res=max(res,cnt);
			cnt=1;
		}
	}
	res=max(res,cnt);
	cout<<n-res<<endl;
 
 
 
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	while(t--){
		solve();
	}
	system("pause");
	return 0;
}

D - 这题用来防ak

思路:签到题,,判断最大的两个数相加是否大于等于10即可。

#include<bits/stdc++.h>

using namespace std;
const int N=1e5+5;
typedef long long ll;
typedef pair<ll,ll> pll;


void solve()
{	
	int a,b,c;
	cin>>a>>b>>c;
	vector<int> s;
	s.push_back(a),s.push_back(b),s.push_back(c);
	sort(s.begin(),s.end());
	if(s[2]+s[1]>=10) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;


}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	while(t--){
		solve();
	}
	system("pause");
	return 0;
}

E - 这题考察FFT卷积

思路:将题意抽象为:给定一个n,要求输出1-n范围内,只含有一个非0数字的个数。

我们从规律入手,我们可以发现1-9的范围内,有9个数(1-9本身),10-90的范围内有9个数 (10,20,30……90)以此类推,100到900之间也存在9个数,我们可以发现,9的个数,是和n的位数挂钩的,并且最高位为多少,就会多加几个数字。因此我们可以将n的位数求出来,并且求出n的最高位,就可以得到答案。
其实我们发现,如果是两位数的话,最后的数字为从9开始加,所以位数减一就为9的组数,比如3位数就有2组9,也就是18。此时刚好分解得到最高位,再加上最高位就可以了。

#include<iostream>
#include<algorithm>

typedef long long ll;
const int N=1e5+5;
using namespace std;

 
 
int main()
{    
    int t;
    scanf("%d",&t);
    while (t--)
    {   
        int n;
        cin>>n;
        int cnt=0;
        if(n<=9){
            cout<<n<<endl;
            continue;
        }
        while(n>10){
            n/=10;
            cnt++;
        }
        cout<<n+cnt*9<<endl;
    } 
    return 0;
 
}

 F - 这题考察二进制

思路:签到题,按题意模拟即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<ll,int> pll;




void solve()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int cnt=0;
    for(int i=0;i<n;i++){
        int res=0;
        if(a[i]==0){
            for(int j=i;j<n;j++){
                if(a[j]==0){
                    res++;
                }
                else break;
            }
            cnt=max(cnt,res);
        }
    }
    cout<<cnt<<endl;


}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    system("pause");
    return 0;
}

 G - 这题考察高精度

思路:签到,诈骗题,其实根本用不上高精度,我们求前n项和,然后减去所有2的幂次方的两倍即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll ;
const int maxv=4e6+5;
typedef pair<ll,ll> pll;
 

void solve()
{
    ll n;
    cin>>n;
    ll res=(n+1)*n/2;
    for(int i=0;;i++){
        ll x=1ll<<i;//求2的幂次方,使用其他方法也可以,比如循环或者直接调用pow函数
        if(x<=n) res-=x*2;
        else break;
    }
    cout<<res<<endl;





}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
	cin>>t;
    while(t--){
        solve();
    }
    system("pause");
    return 0;
}

H - 这题考察签到

思路:二分答案,防ak题

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
const int maxv = 4e6 + 5;
typedef pair<ll, ll> pll;
typedef array<ll,3> p3;

ll n,m,k,s;
vector<int> a(N),b(N);
vector<pll> am(N),bm(N);
vector<pll> w(N);

bool check(int x)
{
	ll res=0;
	vector<ll> v;
	for(int i=0;i<m;i++){
		auto [t,c]=w[i];
		if(t==1){
			v.push_back(am[x].first*c);
		}
		else{
			v.push_back(bm[x].first*c);
		}
	}
	sort(v.begin(),v.end());
	for(int i=0;i<k;i++) res+=v[i];
	return res<=s;

}


void solve()
{
	cin>>n>>m>>k>>s;
	int c=2e9;
	int day=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<c){
			c=a[i];
			day=i;
		}
		am[i]={c,day};
	}
	c=2e9,day=1;
	for(int i=1;i<=n;i++){
		cin>>b[i];
		if(b[i]<c){
			c=b[i];
			day=i;
		}
		bm[i]={c,day};
	}
	for(int i=0;i<m;i++){
		int t,c;
		cin>>t>>c;
		w[i]={t,c};
	}
	int l=1,r=n;
	int ans=-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	if(ans==-1){
		cout<<-1<<endl;
		return ;
	}
	cout<<ans<<endl;
	vector<p3> v;
	for(int i=0;i<m;i++){
		auto [t,c]=w[i];
		if(t==1){
			v.push_back({am[ans].first*c,am[ans].second,i+1});
		}
		else v.push_back({bm[ans].first*c,bm[ans].second,i+1});
	}
	sort(v.begin(),v.end(),[](p3 x,p3 y){
		if(x[0]==y[0]) return x[1]<y[1];
		return x[0]<y[0];
	});
	vector<pll> cur;
	int cnt=1;
	for(int i=0;i<k;i++){
		auto [x,y,id]=v[i];
		cur.push_back({id,y});
		cnt++;
	}
	for(auto [x,y]: cur) cout<<x<<" "<<y<<"\n";



}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	system("pause");
	return 0;
}

I - 爱派克斯,启动!

思路:签到。

统计每组的和是否大于等于2即可。

#include<bits/stdc++.h>

using namespace std;
const int N=1e5+5;
typedef long long ll;

void solve()
{	
    int cnt=0;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(a+b+c>=2) cnt++;
    }
    cout<<cnt<<endl;


}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	system("pause");
	return 0;
}

J - tmn学长的字符串2

思路:字符串模拟。

将题意抽象一下:给定一个字符串,将指定区域的字符串循环移动k次。

因为k的范围位1e9,所以不可能去一次次的进行暴力移动, 我们可以发现,当一个子串的循环移动次数为该串的长度时,子串复原,所以我们只需要去对子串进行k%len(子串长度)次的移动即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll ;
const int maxv=4e6+5;
typedef pair<ll,ll> pll;
 

void solve()
{
    string s;
    cin>>s;
    int q;
    cin>>q;
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        int len=r-l+1;
        k%=len;
        string a=s.substr(0,l-1);
        string b=s.substr(l-1,r-l+1);
        string c=s.substr(r);
        string x=b.substr(0,len-k);
        string y=b.substr(len-k);
        s=a+y+x+c;
    }
    cout<<s<<endl;

}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
	//cin>>t;
    while(t--){
        solve();
    }
    system("pause");
    return 0;
}

给出第二种题解:

模拟操作,把区间内的每个字母向右移动k位即可
假设区间为[1, 5],区间内字符串为12345
向右移动2位的话就是45123,
向右移动5位的话还是12345,相当于没变 ,
所以向右移动7位和向右移动2位的效果是一致的
所以每次操作时先把k模一下区间长度即可

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;

const int N = 110;

int main()
{
	IOS
	string s;
	cin >> s;
	
	int Q;
	cin >> Q;
	while(Q --)
	{
		int l, r, k;
		cin >> l >> r >> k;
		
		string tmp = s;
		for(int i = l; i <= r; i ++)
		{//ne表示移动后在字符串中所处的下标, i - l 表示在所选区间内的第几位 
			int ne = l - 1 + (i - l + k) % (r - l + 1);//(r - l + 1)是区间长度,(i - l + k) % (r - l + 1)是移动后所处在区间中第几个位置(从0开始算) 
			tmp[ne] = s[i - 1];
		}
		s = tmp;
	}
	
	cout << s << endl;
	
	return 0;
}

K - 秋奕来买瓜

思路:签到,判断奇偶即可,注意特判2的情况。

#include<iostream>
using namespace std;
typedef long long ll;


int main()
{
    int n;
    cin>>n;
    if(n%2!=0||n==2){
        cout<<"NO"<<endl;
    }
    else{
        cout<<"YES"<<endl;
    }
    return 0;
}


 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

华为OD机试 - VLAN资源池 - 回溯、双指针(Java 2023 B卷 100分)

目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路1、核心思想2、具体解题思路 五、Java算法源码六、效果展示1、输入2、输出 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&…

什么是NetDevOps

NetDevOps 是一种新兴的方法&#xff0c;它结合了 NetOps 和 DevOps 的流程&#xff0c;即将网络自动化集成到开发过程中。NetDevOps 的目标是将虚拟化、自动化和 API 集成到网络基础架构中&#xff0c;并实现开发和运营团队之间的无缝协作。 开发运营&#xff08;DevOps&…

敏捷研发管理软件及敏捷管理流程

Scrum中非常强调公开、透明、直接有效的沟通&#xff0c;这也是“可视化的管理工具”在敏捷开发中如此重要的原因之一。通过“可视化的管理工具”让所有人直观的看到需求&#xff0c;故事&#xff0c;任务之间的流转状态&#xff0c;可以使团队成员更加快速适应敏捷开发流程。 …

JVM知识点(二)

1、G1垃圾收集器 -XX:MaxGCPauseMillis10&#xff0c;G1的参数&#xff0c;表示在任意1s时间内&#xff0c;停顿时间不能超过10ms&#xff1b;G1将堆切分成很多小堆区&#xff08;Region&#xff09;&#xff0c;每一个Region可以是Eden、Survivor或Old区&#xff1b;这些区在…

【MySQL系列】MySQL复合查询的学习 _ 多表查询 | 自连接 | 子查询 | 合并查询

「前言」文章内容大致是对MySQL复合查询的学习。 「归属专栏」MySQL 「主页链接」个人主页 「笔者」枫叶先生(fy) 目录 一、基本查询回顾二、多表查询三、自连接四、子查询4.1 单行子查询4.2 多行子查询4.3 多列子查询4.4 在from子句中使用子查询 五、合并查询 一、基本查询回顾…

解密算法与数据结构面试:程序员如何应对挑战

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…

Windows版本Docker安装详细步骤

文章目录 下载地址安装异常处理docker desktop requires a newer wsl 下载地址 https://desktop.docker.com/win/stable/Docker%20Desktop%20Installer.exe 安装 双击下载的文件Docker Desktop Installer.exe进行安装 点击OK 开始安装 安装完成点击Close and restart&…

电脑不安装软件,怎么将手机文件传输到电脑?

很多人都知道&#xff0c;AirDroid有网页版&#xff08;web.airdroid.com&#xff09;。 想要文件传输&#xff0c;却不想在电脑安装软件时&#xff0c;AirDroid的网页版其实也可以传输文件。 然而&#xff0c;要将文件从手机传输文件到网页端所在的电脑时&#xff0c;如果按…

“惠医通-医院挂号订单平台”

结合已学习过的vue3和TS完成的项目&#xff0c;便于患者对自己想要就诊的科室进行挂号&#xff0c;付款 一&#xff1a;项目简介 前端技术栈 Vue3 TS vue-router Element-ui Axios Pinia 项目架构 二&#xff1a;主要模块 1. axios二次封装 1.1 创建实例 //利用axios.creat…

视频融合平台EasyCVR视频汇聚平台关于小区高空坠物安全实施应用方案设计

近年来&#xff0c;随着我国城市化建设的推进&#xff0c;高楼大厦越来越多&#xff0c;高空坠物导致的伤害也屡见不鲜&#xff0c;严重的影响到人们的生命安全。像在日常生活中一些不起眼的小东西如烟头、鸡蛋、果核、易拉罐&#xff0c;看似伤害不大&#xff0c;但只要降落的…

Go【gin和gorm框架】实现紧急事件登记的接口

简单来说&#xff0c;就是接受前端微信小程序发来的数据保存到数据库&#xff0c;这是我写的第二个接口&#xff0c;相比前一个要稍微简单一些&#xff0c;而且因为前端页面也是我写的&#xff0c;参数类型自然是无缝对接_ 前端页面大概长这个样子 先用apifox模拟发送请求测试…

①matlab的命令掌握

目录 输入命令 命名变量 保存和加载变量 使用内置的函数和常量 输入命令 1.您可以通过在命令行窗口中 MATLAB 提示符 (>>) 后输入命令 任务 使用命令 3*5 将数值 3 和 5 相乘。 答案 3*5 2.除非另有指定&#xff0c;否则 MATLAB 会将计算结果存储在一个名为 ans…

美团面试拷打:ConcurrentHashMap 为何不能插入 null?HashMap 为何可以?

周末的时候,有一位小伙伴提了一些关于 ConcurrentHashMap 的问题,都是他最近面试遇到的。原提问如下(星球原贴地址:https://t.zsxq.com/11jcuezQs ): 整个提问看着非常复杂,其实归纳来说就是两个问题: ConcurrentHashMap 为什么 key 和 value 不能为 null?ConcurrentH…

MongoDB Long 类型 shell 查询

场景 1、某数据ID为Long类型&#xff0c;JAVA 定义实体类 Id Long id 2、查询数据库&#xff0c;此数据存在 3、使用 shell 查询&#xff0c;查不到数据 4、JAVA代码查询Query.query 不受任何影响 分析 尝试解决&#xff08;一&#xff09; long 在 mongo中为 int64 类型…

clickhouse(十四、分布式DDL阻塞及同步阻塞问题)

文章目录 一、分布式ddl 阻塞、超时现象验证方法解决方案 二、副本同步阻塞现象验证解决方案 一、分布式ddl 阻塞、超时 现象 在clickhouse 集群的操作中&#xff0c;如果同时执行一些重量级变更语句&#xff0c;往往会引起阻塞。 一般是由于节点堆积过多耗时的ddl。然后抛出…

论文阅读:Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks

前言 要弄清MAML怎么做&#xff0c;为什么这么做&#xff0c;就要看懂这两张图。先说MAML**在做什么&#xff1f;**它是打着Mate-Learing的旗号干的是few-shot multi-task Learning的事情。具体而言就是想训练一个模型能够使用很少的新样本&#xff0c;快速适应新的任务。 定…

PCB电路板电压电流监测软件

PCB电路板电流监测软件详细设计说明书是一个详细描述软件系统设计和实现的文档&#xff0c;它提供了软件系统的架构、功能模块、接口设计、数据存储和处理、界面设计、数据库设计、系统测试、部署和维护计划等方面的详细信息。模拟量采集/老化房采集软件 该文档的目的是为了确保…

深入解析文件系统原理(inode,软硬链接区别)

第四阶段提升 时 间&#xff1a;2023年8月29日 参加人&#xff1a;全班人员 内 容&#xff1a; 深入解析文件系统原理 目录 一、Inode and Block概述 &#xff08;一&#xff09;查看文件的inode信息&#xff1a;stat &#xff08;二&#xff09;Atime、Mtime、Ctime详…

计算机网络aaaaaaa

差错检测 在一段时间内&#xff0c;传输错误的比特占所传输比特总数的比率称为误码率BER(Bit Error Rate) 11111111111111111111111111111111111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111111111111111111111111111…

「Vue|网页开发|前端开发」02 从单页面到多页面网站:使用路由实现网站多个页面的展示和跳转

本文主要介绍如何使用路由控制来实现将一个单页面网站扩展成多页面网站&#xff0c;包括页面扩展的逻辑&#xff0c;vue的官方路由vue-router的基本用法以及扩展用法 文章目录 本系列前文传送门一、场景说明二、基本的页面扩展页面扩展是在扩什么创建新页面的代码&#xff0c;…