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()
{IOSstring 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;
}