挑战赛#15 题解
2025-02-23 22:12:38
发布于：北京
34阅读
3回复
1点赞
T1
签到题。直接判断 的第 位即可。
AC Code:
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main(){
cin>>n>>s;
if(s[n-1]=='o') cout<<"Yes";
else cout<<"No";
return 0;
}
T2
由于只能操作一次，所以顶多交换相邻两位。所以要么是 ，要么是 且 ，其他情况输出 No 就可以了。
AC Code:
#include<bits/stdc++.h>
using namespace std;
int cnt;
string a,b;
int main(){
cin>>a>>b;
for(int i=0;i<a.size();i++){
if(a[i]==b[i]) continue;
if(i+1<a.size()){
if(a[i]==b[i+1]&&a[i+1]==b[i]) cnt++,i++;
else{
cout<<"No";
return 0;
}
}
else{
cout<<"No";
return 0;
}
}
if(cnt<=1) cout<<"Yes";
else cout<<"No";
return 0;
}
T3
优先分配更菜的源石虫，枚举所有接力点，找到第一个合适的位置即可。
AC Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e4+14;
ll n;
bool can;
ll a[MAXN],b[MAXN];
bool vis[MAXN];
int main(){
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
for(ll i=1;i<=n;i++) cin>>b[i];
sort(b+1,b+1+n);
for(ll i=1;i<=n;i++){
can=false;
for(ll j=1;j<=n;j++){
if(vis[j]) continue;
if(b[j]>=a[i]-a[i-1]){
can=vis[j]=true;
break;
}
}
if(!can){
cout<<"NO\n"<<i-1;
return 0;
}
}
cout<<"YES";
return 0;
}
T4
折半搜索板子题。
发现应当使用搜索，但是爆搜会T，而且刚好可以通过 的数据，容易联想到折半搜索。
AC Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
ll n,m,s,cnta,cntb,sum,ans;
ll a[35],b[35];
vector<ll> va,vb;
int main(){
cin>>n>>m;
for(ll i=0;i<n;i++){
cin>>s;
if(i<n>>1) a[cnta++]=s;
else b[cntb++]=s;
}
for(ll i=0;i<1<<cnta;i++){
sum=0;
for(ll j=0;j<cnta;j++){
if(i>>j&1){
sum+=a[j];
sum%=m;
}
}
va.eb(sum);
}
for(ll i=0;i<1<<cntb;i++){
sum=0;
for(ll j=0;j<cntb;j++){
if(i>>j&1){
sum+=b[j];
sum%=m;
}
}
vb.eb(sum);
}
sort(vb.begin(),vb.end());
for(auto &i:va){
auto j=lower_bound(vb.begin(),vb.end(),m-i);
if(j!=vb.begin()){
j--;
ans=max((i+*j)%m,ans);
}
ans=max((i+vb.back())%m,ans);
}
cout<<ans;
return 0;
}
T5
诗人握持。
T6
明显的二分。
注意到暴力截取字符串再判断相等的复杂度过高，所以考虑维护一个字符串哈希。
AC Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
const ull BASE=233;
ll n,l,r;
ull pows[100005],ha[100005];
string a,b;
inline ull gethash(ll l,ll r){
if(l==0) return ha[r];
return ha[r]-ha[l-1]*pows[r-l+1];
}
inline bool can(const ll &mid){
ll res=0;
string x=b.substr(0,mid);
ull xha=x[0];
for(ll i=1;i<x.size();i++) xha=xha*BASE+x[i];
for(ll i=mid-1;i<a.size();i++) if(gethash(i-mid+1,i)==xha) res++;
return res>=n;
}
int main(){
cin>>a>>b>>n;
for(ll i=0;i<a.size();i++){
if(i==0) ha[i]=a[i],pows[i]=1;
else ha[i]=ha[i-1]*BASE+a[i],pows[i]=pows[i-1]*BASE;
}
l=1,r=b.size();
while(r-l>=3){
ll mid=l+r>>1;
if(can(mid)) l=mid;
else r=mid;
}
while(l<=r){
if(can(r)){
cout<<b.substr(0,r);
return 0;
}
r--;
}
cout<<"IMPOSSIBLE";
return 0;
}
有帮助，赞一个