目录
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;
}