526互联

The 2021 ICPC Asia Macau Regional Contest

发布时间 2023-10-26 21:00:46作者: EdGrass

\(C. Laser Trap\)

根据题意不难判断出需要极角排序，然后对于每个点寻找更小的一个 \(180\) 度的点数。即使听说是用双指针实现查找依旧没什么思路。后来看了别人的实现方法发现确实比较简单，甚至只需要维护极角就可以了。

const long double pi=acosl(-1);
void solve(){
    int n=read(),ans=n;
    vector<long double> p(n*2+2);
    for(int i=1;i<=n;i++){
        int x=read(),y=read();
        p[i]=atan2l(1.0*y,1.0*x);   //long double 的 atan2
    }
    sort(p.begin()+1,p.begin()+n+1);
    for(int i=1;i<=n;i++){
        p[i+n]=p[i]+2*pi;
    }
    for(int i=1,j=1;i<=n;i++){
        while(j<=2*n && p[j]-p[i]<pi){
            j++;
        }       
        ans=min(ans,j-i-1); 
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(G. Cyclic Buffer\)

首先我们只需要把不在区间内的下一个查询点移到区间的端点上即可。这种做法必定可以转移到所谓的更优解上。那么我们只需要模拟这个过程， 对于不在区间上的点 \(dp\) 判断是把它移到 \(1/k\) 位置上。这个比较麻烦，因为我们需要知道这个区间上已经存在的点是哪个，下一个需要查询的不在目前区间上的点是哪个。这个用线段树去维护区间上第一个不存在于区间的点，然后记录下一个需要的不在区间内的点。

int a[N], poi[N]/*i元素位置*/, f[N][2]/*i在1/k位置的移动花费*/, p[N][2]/*i在1/k位置的下一个不在可取区间的数字*/;
int n, k ;
struct Node{
    int l, r, sum;
}tr[N * 4];
void pushup(Node &u, Node &l, Node &r){
    u.sum = l.sum + r.sum;
}                     
void pushup(int u){
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r){                          
    if (l == r){
        tr[u] = (Node){l, r, 0};
        return ;
    }else{
        tr[u] = (Node){l, r, 0};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}
void modify(int u, int x, int v){   
    if (tr[u].l == x && tr[u].r == x){
        tr[u].sum+=v;
        return ;
    }else{
        int mid = tr[u<<1].r;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
int query(int u, int l, int r){
    if(tr[u].sum==tr[u].r-tr[u].l+1)return INF; //如果区间满了 返回INF
    if (tr[u].l == tr[u].r) return tr[u].l;   //如果找到为0的单点 返回点的位置
    else{
        int mid=tr[u<<1].r,res=INF;     //mid 为左儿子的右界 
        if (l <= mid)res=query(u << 1, l, r);   //如果当前的查询左界小于mid 就去查询查询
        if (r > mid && res==INF)res=query(u<<1|1,l,r);  //如果上面没找到且 需要在右界查询
        return res; 
    }
}
void solve(){
    n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        poi[a[i]]=i;
        f[i][0]=f[i][1]=INF;        
    }
    if(k==n){
        cout<<0<<'\n';
        return ;
    }
    build(1,1,n);
    int s[2]={1,k},l=1,r=k;
    for(int i=1;i<=k;i++){
        modify(1,a[i],1);
    }
    for(int i=1;i<=n;i++){  //枚举n次 一个个判断
        for(int j=0;j<=1;j++){  
            if(a[s[j]]==n)continue; //如果在1/k的位置上的是n 说明结束了 continue；
            p[a[s[j]]][j]=query(1,a[s[j]]+1,n); //查询1/k下一个不在区间内的数
        }
        modify(1,a[s[1]],-1);   //删除k位置的数
        for(int j=0;j<2;j++){   
            s[j]=(s[j]-1+n)%n;  //修改1/k位置上的数字
            if(!s[j])s[j]=n;    
        }
        modify(1,a[s[0]],1);    //增加1位置的数字
    }
    int ans=INF,sta=1;
    while(poi[sta]<=k){
        sta++;  //先过掉所有已经可查询的数字
    }
    auto get_min=[](int x,int y){   //判断x到达y的最小移动距离
        if(y<x)swap(x,y);
        return min(y-x,x+n-y);
    };
    auto get_dis=[](int x,int y){   //判段x到达y的右移的距离
        return (y-x+n)%n;
    };
    f[sta][0]=get_min(poi[sta],1);
    f[sta][1]=get_min(poi[sta],k);
    for(int i=sta;i<n;i++){
        for(int j=0;j<=1;j++){
            if(f[i][j]==INF)continue;
            if(p[i][j]>n)ans=min(ans,f[i][j]);
            else {
                int pos=poi[p[i][j]]+get_dis(poi[i],j==0?1:k);
                if(pos>n)pos-=n;
                int d0=get_min(pos,1),d1=get_min(pos,k);
                f[p[i][j]][0]=min(f[p[i][j]][0],f[i][j]+d0);
                f[p[i][j]][1]=min(f[p[i][j]][1],f[i][j]+d1);
            }
        }
    }
    ans=min({ans,f[n][0],f[n][1]});
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}