感觉这场CF偏水QAQ
恭喜$fuge$喜提紫名
A Heist
题目大意
一堆数,要你找出从小到大排序后中间缺少了多少个数
题解
。
代码
# include<bits/stdc++.h>
using namespace std;
const int MAX=1e4+1;
int n;
int a[MAX];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
int ans=0;
for(int i=2;i<=n;++i)
ans+=a[i]-a[i-1]-1;
return printf("%d",ans),0;
}
B Buying a TV Set
题目大意
给你$a,b,c,d$,求满足$\frac{x}{y}=\frac{c}{d},x\leq a,y\leq b$的$x,y$的对数
题解
。。
代码
# include<bits/stdc++.h>
# define LL long long
using namespace std;
LL a,b,x,y;
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
int main()
{
cin>>a>>b>>x>>y;
LL GCD=gcd(x,y);
x=x/GCD,y=y/GCD;
LL A1=a/x,B1=b/y;
return cout<<min(A1,B1),0;
}
C Coffee Break
题目大意
给定$n$个数和一个$k$,每次从还存在的数里面选一个数$a$,去掉$a$,然后可以任意一个$b(b>a+k)$,然后去掉任意一个$c(c>b+k)$,以此类推
问最少能选多少个$a$,然后输出每个数都是选第几个$a$的时候被去掉的
题解
根据贪心的思想,每次选的$a,b,c…$肯定要往小里面选
排下序,拿个并查集存大于这个数$+k$后第一个没被选过的点,这样就形成一片并查集森林
统计森林里有几棵树即可,开始数组开小了RE
了QAQ
代码
# include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+5;
struct p{
int x,id;
bool operator< (const p &a)
const{
return x<a.x;
}
}a[MAX];
int n,m,d;
int fa[MAX],ID[MAX],IID[MAX],ans[MAX];
bool use[MAX];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=n;++i)
scanf("%d",&a[i].x),a[i].id=i,fa[i]=i;
int L=1;
sort(a+1,a+1+n);
for(int i=1;i<=n;++i)
{
ID[i]=a[i].id,++L;
while(L<=n&&a[L].x<=a[i].x+d) ++L;
if(L<=n)
{
int r1=find(a[i].id),r2=find(a[L].id);
fa[r2]=r1;
}
}
int num=0;
for(int i=1;i<=n;++i)
{
int r1=find(a[i].id);
if(!use[r1]) use[r1]=1,IID[r1]=++num;
}
printf("%d\n",num);
for(int i=1;i<=n;++i)
{
int r1=find(ID[i]);
ans[ID[i]]=IID[r1];
}
for(int i=1;i<=n;++i)
printf("%d ",ans[i]);
return 0;
}
D Glider
题目大意
有$n$个从$x_i$到$y_i$的上升气流,飞机在上升气流里水平飞行,否则每往前飞行一个单位长度机身就向下掉一个单位长度
飞机可以在任意一个位置以高度$h$出发,问最多能飞多远
题解
求一个前缀和,双指针随便搞搞就好了……
代码
# include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+5;
struct p{
int x,y,l;
}a[MAX];
int n,h;
int sum[MAX];
int main()
{
scanf("%d%d",&n,&h);
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i].x,&a[i].y),a[i].l=a[i].y-a[i].x,sum[i]=sum[i-1]+a[i].x-a[i-1].y;
int L=2,ans=h;
for(int i=1;i<=n;++i)
{
while(L<=n&&sum[L]-sum[i]<=h) ++L;
--L;
if(sum[L]-sum[i]==h) ans=max(ans,a[L].x-a[i].x);
else ans=max(ans,a[L].x-a[i].x+a[L].l+h-sum[L]+sum[i]);
}
return printf("%d",ans),0;
}
E Tree Reconstruction
题目大意
有一棵树,现在给你每条树边被去掉时,形成的两个联通块中点的最大的编号分别是多少,问满足条件的树存不存在
题解
显然如果能构成的话某个正确答案肯定是一条链,并且给出的两个数肯定有一个是$n$(可以判能否构成答案)
如果我们把$n$放在链尾,如果数$a$出现过,$a$前面的数肯定都小于$a$;如果一个数$b$出现了多次,说明ta挤掉了某些数,被挤掉的数肯定小于$b$并且在$b$后面
代码
# include<bits/stdc++.h>
using namespace std;
const int MAX=1e3+1;
int n,num;
int a[MAX],ans[MAX],unuse[MAX];
bool use[MAX];
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<n;++i)
{
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
if(y!=n) return printf("NO"),0;
a[i]=x,use[x]=1;
}
sort(a+1,a+n);
for(int i=1;i<n;++i)
if(!use[i]) unuse[++num]=i;
int L=0;
for(int i=1;i<n;++i)
if(a[i]==a[i-1])
{
ans[i]=unuse[++L];
if(unuse[L]>a[i]) return printf("NO"),0;
}
else ans[i]=a[i];
printf("YES\n");
for(int i=1;i<n-1;++i)
printf("%d %d\n",ans[i],ans[i+1]);
return printf("%d %d",ans[n-1],n),0;
}
F Ray in the tube
题目大意
下边界有$n$个给定点,上边界有$m$个给定点,可以从任意一个点发出一条激光,激光碰到边界会反射
激光到达边界必须打到整数点,问最多可以打到几个给定点
题解
发现以$2^n$为步长发射激光肯定是最优的,因为点坐标的奇偶性肯定能找出奇$\rightarrow$奇或者偶$\rightarrow$偶这种组合……好吧具体我也不会证QAQ
注意有步长为$0$这种情况
代码
# include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+1;
int n,m,y,_y,ans;
int x[MAX],_x[MAX];
map<int,int> ma,Ma;
int main()
{
scanf("%d%d",&n,&y);
for(int i=1;i<=n;++i)
scanf("%d",&x[i]),Ma[x[i]]=1;
scanf("%d%d",&m,&_y);
for(int i=1;i<=m;++i)
{
scanf("%d",&_x[i]);
if(Ma[_x[i]]==1) ans=2;
}
for(int tt=2;tt<=1e9;tt<<=1)
{
ma.clear();
for(int i=1;i<=n;++i)
ans=max(ans,++ma[x[i]%tt]);
for(int i=1;i<=m;++i)
ans=max(ans,++ma[(_x[i]+(tt>>1))%tt]);
}
return printf("%d",ans),0;
}