码风丑陋，大佬勿喷
正文
C题
题目大意
给定 1 个长度为 的数组 和整数 ,求是否有二元组 （ , ）满足
思路分析
先将上述式子移项得 ，然后把 数组扫一遍，二分找有没有 即可
注意要先排序
代码部分
#include<bits/stdc++.h>
using namespace std;
int n,x;
int a[200005];
int main(){
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
int j=lower_bound(a+1,a+n+1,a[i]+x)-a;
if(a[j]-a[i]==x){
printf("Yes");
return 0;
}
}
printf("No");
}
D题
题目大意
给定两个正整数 和 ，求一个最小的数 ，满足
- 若 ，则
思路分析
如果直接枚举 ，肯定会超时，但我们可以设一个限定条件 ,因为 等于 除以 再向上取整，所以 时枚举就重复了
这样再枚举，就会有三个限制条件，不会超时了
时间复杂度
代码部分
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,f,mn=1e18;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
int o=ceil(m*1.0/i);
if(o<=n)f=1,mn=min(mn,i*o);
if(i>o)break;
}
if(!f)printf("-1");
else printf("%lld",mn);
}
E题
题目大意
高桥和青木玩 游戏，每一轮游戏，
- 青木先给定一个数
- 高桥写出一个 1 和 之间的数
- 重复 次，将 替换成
轮后，如果写着的是 ，高桥获胜；否则青木获胜
如果双方都使用最优策略，高桥能赢多少局？
思路分析
在图中将 指向 建图，则每个点出度都是 1，所以在环中时才会获胜
可以使用拓扑排序来解决本题
代码部分
#include<bits/stdc++.h>
using namespace std;
int n,s,a[200005],f[200005];
void tuopo_sort(){
queue<int>q;
for(int i=1;i<=n;i++)if(f[i]==0)q.push(i);
while(!q.empty()){
int t=q.front();q.pop();
if(f[a[t]]==1)q.push(a[t]);
f[a[t]]--;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[a[i]]++;
tuopo_sort();
for(int i=1;i<=n;i++)s+=f[i];
printf("%d",s);
}