您的位置: 首页 > IT文章 > Codeforces Round #509 (Div. 2)

Codeforces Round #509 (Div. 2)

分类: IT文章 • 2025-01-07 20:17:32

咕咕咕了好多天终于有时间写篇博客了_(:з」∠)_

打网赛打到自闭的一周，终于靠这场CF找回了一点信心...

(ans=maxleft { a_i ight }-minleft { a_i ight }+1-n)

#include<bits/stdc++.h>
using namespace std;
#define N 1001
int n,a[N],mx,mi;
int main()
{
    mi=2147483647;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i]),
      mx=max(mx,a[i]),
      mi=min(mi,a[i]);
    printf("%d
",mx-mi+1-n);
    return 0;
}

View Code

1041B - Buying a TV Set

设(d=gcd(x,y), X=frac{x}{d}, Y=frac{y}{d})，则(ans=min(frac{a}{X},frac{b}{Y}))

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL a,b,x,y;
LL gcd(LL x,LL y){return y?gcd(y,x%y):x;}
int main()
{
    scanf("%I64d%I64d%I64d%I64d",&a,&b,&x,&y);
    LL d=gcd(x,y);x/=d,y/=d;printf("%I64d
",min(a/x,b/y));
}

View Code

1041C - Coffee Break

难点在于理解题意，题意大致就是把(n)分成(x)块，使得每块里的数两两相差大于(d)，求最小的(x)

直接排序之后莽就好了，贪心是能保证正确性的

#include<bits/stdc++.h>
using namespace std;
#define N 200001
#define mp make_pair
struct rua{int v,id;}a[N];
set<pair<int,int> >s;
int n,m,d,cnt,f[N];
bool cmp(rua x,rua y){return x.v<y.v;}
int main()
{
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i].v),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    s.insert(mp(a[1].v,1)),f[a[1].id]=++cnt;
    for(int i=2;i<=n;i++)
      {
      if((*s.begin()).first+d<a[i].v)
        f[a[i].id]=(*s.begin()).second,s.erase(s.begin()),s.insert(mp(a[i].v,f[a[i].id]));
      else s.insert(mp(a[i].v,++cnt)),f[a[i].id]=cnt;
      }
    printf("%d
",cnt);
    for(int i=1;i<=n;i++)
      printf("%d%c",f[i],i<n?' ':'
');
}

View Code

1041D - Glider

显然在气流的开头跳是最优的，因此枚举在哪个气流的开头跳，二分求出能撑到第几个气流结束，通过预处理可以得到在一个区间内可以被抬多久，从而得出答案

#include<bits/stdc++.h>
using namespace std;
#define N 200001
int n,h,ans,s[N];
struct rua{int l,r;}a[N];
bool check(int st,int i,int j)
{
    return h-(a[i].r-st)+(s[i]-s[j-1])>0;
}
int get(int st,int i)
{
    int l=i,r=n;
    while(l<r)
      {
      int mid=l+r+1>>1;
      if(check(st,mid,i))l=mid;
      else r=mid-1;
      }
    return h+(s[l]-s[i-1]);
}
int main()
{
    scanf("%d%d",&n,&h);
    for(int i=1;i<=n;i++)
      scanf("%d%d",&a[i].l,&a[i].r),s[i]=s[i-1]+a[i].r-a[i].l;
    for(int i=1;i<=n;i++)
      ans=max(ans,get(a[i].l,i));
    printf("%d
",ans);
    return 0;
}

View Code

1041E - Tree Reconstruction

显然(n)这个数一定会出现(n-1)次，现在只需考虑其他数字的出现情况

考虑(n-1)这个数，它出现的次数是等于(n-1)所在点到(n)所在距离的，且在从(n)到(n-1)这条路径上出现的数字是不会在输入中出现的。若将剩余出现的数从大到小排序，则有当前数字出现次数=当前数字所在点到已知路径的距离，这里的已知路径是指已加入点之间的路径。可以发现构造一条链是足以满足题意的，对于空出的点将数字从大到小依次填入，并判断合法性即可。

代码中(c_i)为数字(i)出现的次数，(p_i)为数字(i)在答案中的位置，(x_i)则代表第(i)个位置是否已经被使用

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n,a[N],b[N],l,j=1,c[N],p[N],ans[N],f[N],g[N];
bool x[N];
int main()
{
    scanf("%d",&n),c[n]=p[n]=1,l=n,x[1]=true;
    for(int i=2;i<=n;i++)
      {
      scanf("%d%d",&a[i],&b[i]);
      if(a[i]<b[i])swap(a[i],b[i]);
      if(a[i]<n)return printf("NO
"),0;
      c[b[i]]++;
      }
    for(int i=n-1;i>=1;i--)if(c[i])
      p[i]=p[l]+c[i],l=i,x[p[i]]=true;
    for(int i=n;i>=1;i--)if(!c[i])
      {
      while(j<=n && x[j])j++;p[i]=j,x[j]=true;
      }
    for(int i=1;i<=n;i++)ans[p[i]]=i;
    for(int i=1;i<=n;i++)f[i]=max(f[i-1],ans[i]);
    for(int i=n;i>=1;i--)g[i]=max(g[i+1],ans[i]);
    for(int i=1;i<n;i++)
      {
      int A=f[i],B=g[i+1],xx=0;
      for(int j=1;j<=n;j++)
        if(A==a[j] && B==b[j])
          {a[j]=b[j]=0,xx=1;break;}
      if(!xx)return printf("NO
"),0;
      }
    printf("YES
");
    for(int i=2;i<=n;i++)printf("%d %d
",ans[i-1],ans[i]);
}

View Code

1041F - Ray in the tube

(y1)和(y2)是没用的，不用管它

由于(n)和(m)均大于等于1，因此答案至少为2，不少人因此FST

考虑射出去的线打到对面板上所需要走的距离(d)，假设出发点为0，则打在自己这边上的点的坐标为(left { 0,2d,4d,6d,8d,... ight })，打在对面板上的则是(left { d,3d,5d,7d,9d,... ight })。若将距离改为(kcdot d)，则两个点集分别为(left { 0,2kd,4kd,6kd,8kd,... ight })，(left { kd,3kd,5kd,7kd,9kd,... ight })，可以发现若(k)为奇数，两个集合中的点都只会减少不会增加，(k)为偶数时则有存在增减的情况，因此设(k=2^{l})一定是最优的

接下去就直接暴力开个map做就好了，比赛的时候害怕FST还加了个优化，就是当(k)比较小时直接从(0)到(k-1)枚举余数，(k)较大时才遍历(n+m)个坐标。后来发现这个优化只优化了100ms...

#include<bits/stdc++.h>
using namespace std;
#define N 100001
int n,m,y,a[N],b[N];
map<int,int>f,g;
int main()
{
    scanf("%d%d",&n,&y);
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i]);
    scanf("%d%d",&m,&y);
    for(int i=1;i<=m;i++)
      scanf("%d",&b[i]);
    int ans=2;
    for(int k=2;k;k*=2)
      {
      f.clear(),g.clear();
      for(int i=1;i<=n;i++)
        f[a[i]%k]++;
      for(int i=1;i<=m;i++)
        g[b[i]%k]++;
      if(k<=131072)
        for(int i=0;i<k;i++)
          ans=max(ans,f[i]+g[(i+k/2)%k]);
      else
        {
        for(auto j:f)ans=max(ans,f[j.first]+g[(j.first+k/2)%k]);
        for(auto j:g)ans=max(ans,g[j.first]+f[(j.first+k/2)%k]);
        }
      if(k==1073741824)
        break;
      }
    printf("%d
",ans);
    return 0;
}

View Code

Codeforces Round #509 (Div. 2)

相关推荐