A
题意
给你一个数列，对于其中任何子数列中的最大数，你需要找出一个\(k\)，保证\(k\)都严格小于他们。
方法
不难想到，都是由二位串构成，计算每一个二位串的最大数，然后选择最小的，减去1即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
std::vector<ll> a(n,0);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
std::vector<ll> b(n,0);
for(int i=1;i<n;i++)
{
b[i]=max(a[i-1],a[i]);
}
ll minn=1e9;
for(int i=1;i<n;i++)
{
minn=min(minn,b[i]);
}
cout<<minn-1<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
B
题意
给你一个\(x,y\)，要求你对\(a,b\)进行以下操作：$a_i=i x, b_j=j y \(，你需要找出最长的连续一段，使得以上条件一直成立，输出长度。\)a,b$都是从1开始的自然数序列。
方法
不难得到：\(i \oplus x = j \oplus
y\)，利用异或运算的性质，我们可以得到\(i \oplus j= x \oplus y\)。\(x \oplus y\)
是已知的，我们需要的是\((i+1) \oplus (j+1)=
x \oplus y\)也成立，尽可能延申下去。
可以发现，每一次加一，都是对应位改变：
\(0 \oplus 0=0,1 \oplus
1=0\)，这样\(i\oplus
j\)不变，如果发生了进位，那么会影响到后面的改变，\(i \oplus j\)也就不等于\(x \oplus
y\)，我们只需要从头开始找最低的1位即可。
这里可以使用\(lowbit(x)\)进行计算。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
ll x,y; cin>>x>>y;
x^=y;
cout<<(x&(-x))<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
C
题意
给你若干个\(k_i\)，要求你每次对\(k_i\)进行下注\(num\)，保证收获\(k_i *num\)大于全部\(num\)的总和。\(num\)就是你针对每一个\(k_i\)的赌注。
方法
不难想到，可以利用他们的最小公倍数进行分配，然后计算如何成立即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
std::vector<ll> v(n,0);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
ll sum=1;
for(int i=0;i<n;i++)
{
sum=sum*v[i]/gcd(sum,v[i]);
}
ll ans=0;
std::vector<ll> a(n,0);
for(int i=0;i<n;i++)
{
a[i]=sum/v[i];
ans+=a[i];
}
if(ans<sum)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" \n"[i==n-1];
}
}
else cout<<-1<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
D
题意
给你一个二进制串，你可以选择一个位置\(p\)，将\(s[1······p]\)进行反转，然后\(s[p+1······n]\)接到\(s[1······p]\)前面，要求你将其进行操作后，满足\(k\)个0或者1循环出现。如果可以，输出位置，否则输出\(-1\)。
方法
不难想到，我们直接找第一个不符合的情况，然后确定反转的位置进行操作得到对应的字符串，然后再进行检验：判断是否符合要求。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n,k; cin>>n>>k;
string s; cin>>s;
int pos=0;
int cur=1;
int i=0;
for(i;i<n;)
{
cur=1;
char ch=s[i++];
while(i<n && s[i]==ch)
{
cur++;
i++;
}
if(cur==k) continue;
else if(cur<k)
{
pos=i;
break;
}
else
{
pos=i-k;
break;
}
}
if(pos==0)
{
pos=n;
}
string tmp=s.substr(0,pos);
reverse(tmp.begin(),tmp.end());
string t=s.substr(pos)+tmp;
bool ok=true;
for(int i=1;i<k;i++)
{
if(t[i]!=t[0])
{
ok=false;
break;
}
}
for(int i=0;i+k<n;i++)
{
if(t[i]==t[i+k])
{
ok=false;
break;
}
}
if(ok)
{
cout<<pos<<"\n";
}
else cout<<-1<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
E
题意
给你若干个点，你需要找出是否存在三个点，彼此之间的距离都是\(k\)，这里的距离是曼哈顿距离。
方法
由于距离是确定的，范围又很大，我们采取二分。
研究样例可以发现：符合情况的：必定存在两点：\((x,y),(x+\frac{d}{2},y-\frac{d}{2})\)，可能有相关的变形，后面处理即可。
可以进行如下操作，我们先查询每一点距离最近的，\(s\)距离不变且\(x\)距离等于增加了\(\frac{k}{2}\)的点，然后将其加入到新的数组中，再从这个数组中进行二分，查找\(s\)距离增加了\(\frac{k}{2}\)，\(x\)距离小于\(x+\frac{d}{2}\)的点，如果存在，则是一组合法的解，否则交换坐标进行计算。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
int d; cin>>d;
std::vector<int> x(n),y(n);
for(int i=0;i<n;i++) cin>>x[i]>>y[i];
int A=0,B=0,C=0;
auto work=[&]()
{
std::vector<std::array<int,3>> a(n);
for(int i=0;i<n;i++)
{
a[i]={x[i]+y[i],x[i],i};
}
sort(a.begin(),a.end());
std::vector<std::array<int,4>> v;
for(auto [s,x,i]: a)
{
auto it=lower_bound(a.begin(),a.end(),std::array{s,x+d/2,0});
if(it!=a.end() && (*it)[0]==s && (*it)[1]==x+d/2)
{
v.push_back({s,x,i,(*it)[2]});
}
}
for(auto [s,x,i]: a)
{
auto it=lower_bound(v.begin(),v.end(),std::array{s+d,x,0,0});
if(it!=v.end() && (*it)[0]==s+d && (*it)[1]<=x+d/2)
{
A=i+1;
B=(*it)[2]+1;
C=(*it)[3]+1;
return;
}
}
};
for(int i=0;i<4;i++)
{
work();
if(A>0) break;
for(int j=0;j<n;j++)
{
swap(x[j],y[j]);
x[j]*=-1;
}
}
cout<<A<<" "<<B<<" "<<C<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
