20201012sdssy考试

· · 个人记录

sdssy20201012

实际为USACO open20 silver

充分说明N老师对于USACO的喜爱程度

感觉t2t3都很有意思，思维难度大，代码简单

t1

水题，二分就完事了。

但我这个憨批忘了排序，交了很多遍没过。。。。

所以一定要仔细看题、仔细检查。抵制样例欺诈，从我做起

代码：

struct grass{
    ll start,end;
}g[100010];
bool cmp(grass a,grass b){
    return a.start<b.start;
}
int main(){
    int n=qread(),m=qread();
    for(re int i=1;i<=m;++i){
        g[i].start=qread(),g[i].end=qread();
    }
    sort(g+1,g+1+m,cmp);
    ll lst=0,l=0,r=g[m].end,mid;
    while(l<r){
        mid=(l+r+1)>>1;
        int tm=1,pos=1;
        lst=g[1].start;
        while(lst<=g[m].end&&pos<=m){
            if(lst+mid>=g[pos].start&&lst+mid<=g[pos].end) tm++,lst+=mid;
            else if(lst+mid>g[pos].end) pos++;
            else if(lst+mid<g[pos].start)lst=g[pos].start,tm++;
        }
        if(tm>=n) l=mid;
        else r=mid=mid-1;
    }
    cout<<mid<<'\n'; 
    return 0;
}

t2

两种方法，队列维护或 抢麦子吃 从后向前扫。

队列的方法暂时没调出来，这里只放抢麦反向扫法:

int ans[100010],cnt=0,eat[100010],f[100010],s[100010];
void solve(int x,int y){//x是当前牛编号，y是麦片编号
    if(!eat[y]){
        eat[y]=x;
        cnt++;
        return;
    }
    if(eat[y]>x){
        int z=eat[y];
        eat[y]=x;
        if(y==f[z]) solve(z,s[z]);
    }
}
int main(){
    int n=qread(),m=qread();
    for(re int i=1;i<=n;++i){
        f[i]=qread(),s[i]=qread();
    }
    for(re int i=n;i>=1;--i){
        solve(i,f[i]);
        ans[i]=cnt;
    }
    for(re int i=1;i<=n;++i){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

t3

这道题转化很多：

  1. 每一组(x,y)看做平面上一点

  1. 对于每个点，左下和右上方的点与其在同一连通块中，可以连边用并查集维护森林，结论即有多少棵树,复杂度O(n^2)过不了。
  2. 其实可以维护前缀最小值和后缀最大值，对于一个点，它及前面的点的最小值大于它后面点的最大值，它就是反应完剩下的那个点，除sort外O(n)

代码：

struct node{
    int x,y;
}nd[100010];
bool cmp(node a,node b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
int mn[100010],mx[100010];
int Max(int x,int y){
    return x>y?x:y;
}
int Min(int x,int y){
    return x<y?x:y;
}
int main(){
    int n=qread();
    for(re int i=1;i<=n;++i){
        nd[i].x=qread(),nd[i].y=qread();
    }
    sort(nd+1,nd+1+n,cmp);
    mn[1]=nd[1].y;
    for(re int i=2;i<=n;++i)
        mn[i]=Min(mn[i-1],nd[i].y);
    mx[n]=nd[n].y;
    for(re int i=n-1;i>=1;--i)
        mx[i]=Max(mx[i+1],nd[i].y);
    int ans=1;
    for(re int i=1;i<=n;++i){
        if(mn[i]>mx[i+1]) ans++;
    }
    cout<<ans<<'\n';
    return 0;
}