此题没有要求 的前后位置,所以我们可以在排序后用 set
来查找数是否出现过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,a[N],x;
set<int> s;
signed main(){
cin>>n>>x;
for(int i=1;i<=n;++i){
cin>>a[i];
s.insert(a[i]);
}
for(int i=1;i<=n;++i){
if(s.find(a[i]+x)!=s.end()||s.find(a[i]-x)!=s.end()){
cout<<"Yes";
return 0;
}
}
cout<<"No";
return 0;
}
这一题确定 时,显然 ,如果爆搜,那么 肯定是不行的。
我们可以令 ,那么 的上限为 ,就可以了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,x=-1;
signed main(){
int a,b;
cin>>n>>m;
for(int a=1;a<=n;++a){
b=ceil(m*1.0/a);
if(b<=n){
if(x==-1) x=a*b;
else x=min(x,a*b);
}
if(a>b) break;
}
cout<<x;
return 0;
}
按 建图,答案就是环上节点的个数。
注意到这里的图比较特殊,每个点的出度都为 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],n,df[N],d,ans;
void dfs(int i,int s){
if(df[i]!=0){
if(df[i]>s) ans+=d-df[i]+1;
return;
}
df[i]=++d;
dfs(a[i],s);
}
signed main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n;++i){
if(df[i]==0){
dfs(i,d);
}
}
cout<<ans;
return 0;
}