How to AK ABC255

· · 个人记录

题外话

赛时 C 题先是被卡了 40min，然后感觉没希望滚去做 E，然后没做出来，又跳回 C，又思考了 10min，找不出错，随手输入了一组数据结果 Successful hack，然后我对着这组 hack 数据改，最终将其 AC。此时还剩下 7min，去看了下 D，看上去很简单的样子，可是没时间做了。赛后把 D 题切了

又掉了大分

A

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    int a[3][3];
    int r,c;
    void main()
    {
        cin>>r>>c;
        cin>>a[1][1]>>a[1][2];
        cin>>a[2][1]>>a[2][2];
        cout<<a[r][c];
    }
}
int main()
{
    Main::main();
    return 0;
}

B

对于每个人，O(k) 计算照亮他的最小光照半径，记为 p_i。
答案就 p 数组的最大值 

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=1005;
    int a[maxn];
    ll x[maxn],y[maxn];
    map<int,bool> im;
    double problem[maxn];
    int n,k;
    double dis(ll x,ll y,ll x2,ll y2)
    {
        double c1=double(x-x2);
        double c2=double(y-y2);
        return sqrt(c1*c1+c2*c2);
    }
    void main()
    {
        cin>>n>>k;
        for(int i=1;i<=k;i++)
        {
            cin>>a[i];
            im[a[i]]=1;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>x[i]>>y[i];
            problem[i]=1e9; 
        }
        double ans=0.0;
        for(int i=1;i<=k;i++)
        {
            double col=0;
            problem[a[i]]=0;
            for(int j=1;j<=n;j++)
            {
                if(im[j])continue;
                problem[j]=min(problem[j],dis(x[j],y[j],x[a[i]],y[a[i]]));
            }
        }
        for(int i=1;i<=n;i++)
        {
            ans=max(ans,problem[i]);
        }
        printf("%.10lf",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}

C

这道题需要分成 d \ge 0 和 d \le 0 两种情况讨论

代码（赛时的代码不是给人看的，格式化了一下）： 

#include <bits/stdc++.h>
using namespace std;
namespace Main {
    typedef __int128 ll;
    void main() {
        long long x,a,d,n;
        cin>>x>>a>>d>>n;
        if(d>=0) {
            ll imax=a+ll(n-1)*(ll)d;
            //-----------极端情况---------- 
            if(x<=a) {
                cout<<(long long)(a-x);
                return;
            }
            if(x>=imax) {
                cout<<(long long)(x-imax);
                return;
            }
            //-----------蒲通的情况------------- 
            ll ans1=(x-a)%d;//靠左 
            ll ans2=abs(d-(x-a)%d);//靠右 
            cout<<(long long)(min(ans1,ans2));
        } else {//d<0
            ll imin=a+ll(n-1)*(ll)d;
            if(x>=a) {
                cout<<(long long)(x-a);
                return;
            }
            if(x<=imin) {
                cout<<(long long)(imin-x);
                return;
            }
            ll ans1=abs((x-a)%d);
            ll ans2=abs(abs(d)-abs((x-a)%d));
            cout<<(long long)(min(ans1,ans2));
        }
    }
}
int main() {
    Main::main();
    return 0;
}

D

这道题看完了之后，肯定感觉：“要是所有的元素全都大于等于 x_i 或者全都小于 x_i 就好了”
为了创建这种条件，考虑将它们分成两组，一组全部大于等于 x_i，一组全部小于 x_i。 现在的瓶颈就在于如何快速分开。显然如果暴力分的话是 O(n) 的，乘上 q 就爆了。
但是如果预先排一下序，那么每次询问就能以 O(logn) 的复杂度找到分割点。 然后这道题就做出来了

代码： 

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=2e5+5;
    int n,q;
    ll a[maxn];
    ll qzh[maxn];
    void main()
    {
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            qzh[i]=qzh[i-1]+a[i];
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
        {
            qzh[i]=qzh[i-1]+a[i];
        }
        ll xi;
        for(int i=1;i<=q;i++)
        {
            scanf("%lld",&xi);
            int pos=lower_bound(a+1,a+n+1,xi)-a;
            if(pos==-1)
            {
                ll ans=(xi*n)-qzh[n];
                printf("%lld\n",ans);
                continue;
            }
            ll ans=0;
            ans+=xi*(pos-1)-qzh[pos-1];
            ans+=(qzh[n]-qzh[pos-1])-xi*(n-pos+1);
            printf("%lld\n",ans);
        }
    } 
}
int main()
{
    Main::main();
    return 0;   
}