1. Toy模板网首页
  2. > Toy博客

HUT23级训练赛

10月前 作者：Unlimitedz 分类：Toy博客 阅读(30) 违法举报

这篇具有很好参考价值的文章主要介绍了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 - 帮帮神君先生

思路：考察最基本的二分算法。把题意抽象一下，就是对于每一个,求在a数组中有多少个比小的数，因为a数组和b数组都是2e5的大小，所以我们对于每一个，每次去遍历一遍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;
}


 文章来源地址https://www.toymoban.com/news/detail-680282.html

到了这里，关于HUT23级训练赛的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • Coggle 30 Days of ML（23年7月）任务六：训练FastText、Word2Vec词向量

    Coggle 30 Days of ML（23年7月）任务六：训练FastText、Word2Vec词向量

    任务六：学会训练FastText、Word2Vec词向量 说明：在这个任务中，你将学习如何训练FastText和Word2Vec词向量模型，这些词向量模型可以捕捉文本中的语义信息。 实践步骤： 准备大规模文本语料库。 使用FastText或gensim库中的Word2Vec类，设置相应的参数（如词向量维度、窗口大小、训

    2024年02月16日
    浏览(44)
  • 算法学习 day23

    算法学习 day23

    669. 修剪二叉搜索树 给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high 。通过修剪二叉搜索树，使得所有节点的值在 [low, high] 中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在

    2024年02月15日
    浏览(32)

  • 每日算法打卡：移动距离 day 23

    1219. 移动距离 题目难度：简单 题目来源：第六届蓝桥杯省赛C++ B组,第六届蓝桥杯省赛Java A/C组 X星球居民小区的楼房全是一样的，并且按矩阵样式排列。 其楼房的编号为 1,2,3… 当排满一行时，从下一行相邻的楼往反方向排号。 比如：当小区排号宽度为 6 时，开始情形如下：

    2024年01月24日
    浏览(73)
  • 智能优化算法比较：常用的23组测试函数

    智能优化算法比较：常用的23组测试函数

    在智能优化算法的性能比较过程中，经常会需要用到一些测试函数，进行算法的性能比较。CEC(国际进化计算会议) 测试函数，常用的23组整理如下。

    2024年02月11日
    浏览(42)
  • 19ContraBERT：顶会ICSE23 数据增强+对比学习+代码预训练模型，提升NLP模型性能与鲁棒性：处理程序变异（变量重命名）【网安AIGC专题11.15】

    19ContraBERT：顶会ICSE23 数据增强+对比学习+代码预训练模型，提升NLP模型性能与鲁棒性：处理程序变异（变量重命名）【网安AIGC专题11.15】

    随着大规模代码的崛起， 无监督学习 成为了提高代码预训练模型性能的有效手段。这些预训练模型在广泛的下游任务中表现出色，如自然语言处理和程序语言处理。例如，像CodeBERT和GraphCodeBERT这样的模型在预训练阶段通过大规模代码数据学到通用的表示，并在下游任务上进

    2024年02月05日
    浏览(79)
  • 【算法题解】23. 「滑动窗口最大值」单调队列解法

    【算法题解】23. 「滑动窗口最大值」单调队列解法

    这是一道 困难 题 题目来自：https://leetcode.cn/problems/sliding-window-maximum/ 给你一个整数数组 nums ，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1： 示

    2023年04月11日
    浏览(54)

  • 算法学习笔记(23): 马尔可夫链中的期望问题

    这个问题是我在做 [ZJOI2013] 抛硬币 - 洛谷 这道题的时候了解的一个概念。 在网上也只找到了一篇相关的内容：# 马尔可夫链中的期望问题 故在这里来分享一下其中的期望问题。 目录 马尔可夫链中的期望问题 马尔可夫链 概率转移矩阵 转移矩阵的修订 状态中的期望 期望线性

    2024年02月07日
    浏览(39)

  • 第23天-代码随想录刷题训练-第六章 ● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

    - LeetCode 链接 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。 修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在唯一的答案

    2024年02月05日
    浏览(43)
  • 【23-24 秋学期】NNDL 作业13 优化算法3D可视化

    【23-24 秋学期】NNDL 作业13 优化算法3D可视化

    分别画出  和  的3D图 代码如下： 分别画出  和  的3D轨迹图 （1） 结果如下：  （2） 结合3D动画，用自己的语言，从轨迹、速度等多个角度讲解各个算法优缺点 Animations that may help your intuitions about the learning process dynamics.  Left: Contours of a loss surface and time evolution of different

    2024年02月04日
    浏览(42)
  • 数据结构与算法基础-学习-23-图之邻接矩阵与邻接表

    数据结构与算法基础-学习-23-图之邻接矩阵与邻接表

    目录 一、定义和术语 二、存储结构 1、邻接矩阵 1.1、邻接矩阵优点 1.2、邻接矩阵缺点 2、邻接表 3、邻接矩阵和邻接表的区别和用途 3.1、区别 3.2、用途 三、宏定义 四、结构体定义 1、邻接矩阵 2、邻接表 3、网数据类型（造测试数据） 五、函数定义 1、使用邻接矩阵创建无

    2024年02月14日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包