USACO 2017 December Contest,Silver

Posted by

Problem 1.My Cow Ate My Homework 题目链接:https://www.luogu.org/problemnew/show/P4086 思路:题意很好理解。本人采用前缀和+线段树维护。还有一种更优秀的做法即倒序枚举,此时区间最小值只需要每次更新即可,会更快。在这里两种写法都会呈现。 需要注意的是double变量的使用,因为涉及平均数的精度问题,因此不使用double会WA许多点。 代码一:线段树

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#define ls p<<1
#define rs p<<1|1
static const int INF=1<<30;
static const int MAXN=100050;
using namespace std;
int n,b[MAXN],sum[MAXN],a[MAXN<<2];;
double Max,res;
vector<int> Ans;
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
struct Segment_Tree{
    inline void push_up(int p){
        a[p]=min(a[ls],a[rs]);
    }
    void build(int p,int l,int r){
        if(l==r){
            a[p]=b[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(p);
    }
    int query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&qr>=r){
            return a[p];
        }
        int mid=(l+r)>>1,Min=INF;
        if(ql<=mid) Min=min(Min,query(ls,l,mid,ql,qr));
        if(qr>mid) Min=min(Min,query(rs,mid+1,r,ql,qr));
        push_up(p);
        return Min;
    }
}Tree;
int main(){
    n=read();
    for(int i=1;i<=n;i++) b[i]=read(),sum[i]=sum[i-1]+b[i];
    Tree.build(1,1,n);
    for(int i=1;i<=n-2;i++){
        res=((double)(sum[n]-sum[i])-Tree.query(1,1,n,i+1,n))/(n-i-1);
        if(res>Max){
            Max=res;
            Ans.clear();
            Ans.push_back(i);
        }
        else if(res==Max) Ans.push_back(i);
    }
    sort(Ans.begin(),Ans.end());
    for(int i=0;i<(int)Ans.size();i++) printf("%d\n",Ans[i]);
    return 0;
}
代码二:更优写法
#include <stdio.h>
#include <algorithm>
using namespace std;
const int INF=1e9;
long long n,Max=-INF,Min=INF,a[100001],k[1000001],sum,num;
long double xb;
template<class T>void read(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=n;i>=2;i--)
    {
        sum+=a[i];
        Min=min(Min,a[i]);
        if((sum-Min)/(double)(n-i)>xb)
        {
            num=1;
            k[num]=i-1;
            xb=(sum-Min)/(double)(n-i);
        }
        else if((sum-Min)/(double)(n-i)==xb)
        {
            k[++num]=i-1;
        }
    }
    for(int i=num;i>=1;i--) printf("%lld\n",k[i]);
    return 0;
}

Problem 2.Bovine Shuffle

题目链接:https://www.luogu.org/problemnew/show/P4089 思路:往图论方面去想。把每头奶牛想象成一个点,与它将要到的位置连一条有向边。不难发现答案即为图中所有环(包括自环)的长度和。证明比较显然,在此这里赘述。 因此只需要将不在环内的点(即入度为0的点)删去,然后再统计环的长度即可。 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
static const int MAXN=100050;
using namespace std;
int n,ans,a[MAXN],in[MAXN];
bool vis[MAXN],r[MAXN];
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
void dfs1(int x){
    --in[a[x]];
    vis[x]=1;
    if(!in[a[x]]) dfs1(a[x]);
}
int dfs2(int x){
    if(r[x]) return 0;
    r[x]=1;
    return dfs2(a[x])+1;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),++in[a[i]];
    for(int i=1;i<=n;i++){
        if(!in[i]&&!vis[i]) dfs1(i);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]&&!r[i]) ans+=dfs2(i);
    }
    printf("%d\n",ans);
    return 0;
}

Problem 3.Milk Measurement

题目链接:https://www.luogu.org/problemnew/show/P4087 思路:十分不喜欢这道题。很坑。 先将编号进行离散化,后使用线段树维护+复杂的情况判断。 推荐题解:https://www.luogu.org/blog/top-oier/solution-p4087 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#define ls p<<1
#define rs p<<1|1
static const int INF=1<<30;
static const int MAXN=1000050;
using namespace std;
struct node{
    int d,id,k;
}a[MAXN];
struct node1{
    int Max;
}c[MAXN<<2];
int n,m,num,cnt,ans,b[MAXN],e[MAXN],lastday,lastmax,nowmax,last;
map<int,int> ex;
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline bool cmp(node a,node b){
    return a.d<b.d;
}
struct Segment_Tree{
    inline void push_up(int p){
        c[p].Max=max(c[ls].Max,c[rs].Max);
    }
    void build(int p,int l,int r){
        if(l==r){
            c[p].Max=m;
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(p);
    }
    void update(int p,int l,int r,int x,int k){
        if(l==r){
            e[x]+=k;
            c[p].Max+=k;
            return ;
        }
        int mid=(l+r)>>1;
        if(x<=mid) update(ls,l,mid,x,k);
        if(x>mid) update(rs,mid+1,r,x,k);
        push_up(p);
    }
    int query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&qr>=r) return c[p].Max;
        int mid=(l+r)>>1,nmax=-INF;
        if(ql<=mid) nmax=max(nmax,query(ls,l,mid,ql,qr));
        if(qr>mid) nmax=max(nmax,query(rs,mid+1,r,ql,qr));
        push_up(p);
        return nmax;
    }
}Tree;
inline void Discrete(){
    sort(b+1,b+n+1);
    num=unique(b+1,b+n+1)-(b+1);
    for(int i=1;i<=n;i++) a[i].id=lower_bound(b+1,b+num+1,a[i].id)-b;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i].d=read();a[i].id=read();a[i].k=read();
        b[i]=a[i].id;
    }
    Discrete();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=num;i++) e[i]=m;
    e[num+1]=m;
    Tree.build(1,1,num+1);
    lastmax=m;lastday=-1;ex[m]=INF;
    for(int i=1;i<=n;i++){
        last=e[a[i].id];
        Tree.update(1,1,num+1,a[i].id,a[i].k);
        nowmax=Tree.query(1,1,num+1,1,num+1);
        ex[last]--;
        if(nowmax==lastmax&&last<lastmax&&e[a[i].id]==nowmax&&a[i].d!=lastday) ans++;
        if(nowmax==lastmax&&last==lastmax&&e[a[i].id]<nowmax&&a[i].d!=lastday) ans++;
        else if(nowmax>lastmax&&(last!=lastmax||ex[last])&&a[i].d!=lastday) ans++;
        else if(nowmax<lastmax&&(e[a[i].id]!=nowmax||ex[e[a[i].id]])&&a[i].d!=lastday) ans++;
        lastmax=nowmax;
        ex[e[a[i].id]]++;
        lastday=a[i].d;
    }
    printf("%d\n",ans);
    return 0;
}
  ]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注