[USACO] 2017 DEC Bronze&Silver

link:http://www.usaco.org/index.php?page=dec17results

Problem A(Bronze)

这是一道非常简单的判断重叠面积的题目，但第一次提交仍会出错，实不应该

判断的关键在于矩形A的上界要大于B的下界，且A的下界要小于B的上界，则包含了相重叠的所有情况

同时，在数据范围较小时，也可使用染色法

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int xx[],xy[],yx[],yy[];

ll cal(int n,int m)

{

    ll ret=(xy[n]-xx[n])*(yy[n]-yx[n]);

    if(xx[m]<=xy[n] && xy[m]>=xx[n] && yx[m]<=yy[n] && yy[m]>=yx[n]) //关键判断句

    {

        ll t1=min(xy[n],xy[m])-max(xx[n],xx[m]);

        ll t2=min(yy[n],yy[m])-max(yx[n],yx[m]);

        ret-=t1*t2;

    }

    return ret;

}

int main()

{

    for(int i=;i<;i++)

        cin >> xx[i] >> yx[i] >> xy[i] >> yy[i];

    ll res=cal(,);res+=cal(,);

    cout << res;

    return ;

}

Problem A

Problem B、C(Bronze)

#include <bits/stdc++.h>

using namespace std;

struct milk

{

    int day,num,change;

}dat[];

int n,res[],cnt=;

bool cmp(milk a,milk b)

{

    return a.day<b.day;

}

int main()

{

    cin >> n;

    for(int i=;i<=n;i++)

    {

        string s;

        cin >> dat[i].day >> s >> dat[i].change;

        if(s=="Bessie") dat[i].num=;

        else if(s=="Elsie") dat[i].num=;

        else dat[i].num=;

    }

    sort(dat+,dat+n+,cmp);

    int cur=;

    res[]=res[]=res[]=;

    for(int i=;i<=n;i++)

    {

        res[dat[i].num]+=dat[i].change;

        int t1=max(res[],max(res[],res[])),t2=;

        for(int j=;j<=;j++) if(res[j]==t1) t2+=(<<(j-));

        if(t2!=cur) cur=t2,cnt++;

    }

    cout << cnt;

    return ;

}

Problem B

#include <bits/stdc++.h>

using namespace std;

int n,a[],rev[],ini[],res[];

int main()

{

    cin >> n;

    for(int i=;i<=n;i++) cin >> a[i];

    for(int i=;i<=n;i++) cin >> ini[i];

    for(int i=;i<=n;i++) rev[a[i]]=i;

    for(int i=;i<=n;i++)

    {

        int t=i;

        for(int j=;j<=;j++) t=rev[t];

        res[t]=ini[i];

    }

    for(int i=;i<=n;i++) cout << res[i] << endl;

    return ;

}

Problem C

Problem A(Silver)

只要每次预处理最小值和前缀和即可

Tip:用double存储两int相除时一定要强制类型转换

#include <bits/stdc++.h>

using namespace std;

int n,a[],mmin[];

double ave[],mmax=;

int main()

{

    cin >> n;

    for(int i=;i<=n;i++) cin >> a[i];

    mmin[n]=a[n];mmax=;int sum=a[n];

    for(int i=n-;i>=;i--)

    {

        mmin[i]=min(mmin[i+],a[i]);

        sum+=a[i];ave[i]=double(sum-mmin[i])/(n-i);

                //一定要强制转换为double

        mmax=max(mmax,ave[i]);

    }

    for(int i=;i<=n-;i++) if(ave[i]==mmax) cout << i- << endl;

    return ;

}

Problem A

Problem B(Silver)

这是一道让我收获很大的题

题面：有n个起始为g的数，在m天里每天都会对其中一个数进行调整（加或减），而你要维护一个最大值列表，包括所有为当前最大值的数的编号。问此列表要改变的次数。

n<=1e9，m<=1e6

从数据范围可以看出，我们无法也不需要对每一个数进行维护，仅需对可能发生改变的1e6个数维护即可，那么为了建立每一个编号及其值之间的关系，可以用map来进行维护

那么接下来的重点就在于如何维护这些已经改变过的数的最大值，以及当前最大值的个数

一开始我并未使用数据结构，直接对最大值，次大值进行维护，但实际上当上一步的最大值进行减法时，需要再进行一次排序，因此不可行

实际上map中也是有自带的排序的，默认map<int,int,less<int> >，从而我们也可以使用greater<int>来使其降序排列，并用map.begin()来调取其最大的键所对应的值

同时，map本身内部的数据结构又是pair性质的，因此有了iterator:map.begin()后，可以使用map.begin()->first调取键，用map.begin()->second调取值

这样，我们就可以再用一个map来表示当前每种值所对应的数的个数

Tip:1、map.erase()操作不用输入iterator，只要输入键的编号即可

2、map本身和set一样，均自动排序，可用begin()调用最值

#include <bits/stdc++.h>

using namespace std;

struct milk

{

    int day,num,change;

}dat[];

int n,g;

map<int,int> mp;

map<int,int,greater<int> > cnt;

bool cmp(milk p,milk q)

{

    return p.day<q.day;

}

int main()

{

    cin >> n >> g;

    for(int i=;i<=n;i++)

    {

        cin >> dat[i].day >> dat[i].num >> dat[i].change;

        if(!mp.count(dat[i].num)) mp[dat[i].num]=g;

    } 

    sort(dat+,dat+n+,cmp);

    int res=;cnt[g]=n;

    for(int i=;i<=n;i++)

    {

        int last=mp[dat[i].num];mp[dat[i].num]+=dat[i].change;

        int lmax=cnt.begin()->first,lcnt=cnt.begin()->second; //调用最大值的键值对 

        if(cnt[last]==) cnt.erase(last);  //erase操作

        else cnt[last]--;

        cnt[mp[dat[i].num]]++;

        if(last==lmax)

        {    //如果更改后最大值的编号不变且均只有一个最大值，则不处理

            if(mp[dat[i].num]==cnt.begin()->first && cnt[mp[dat[i].num]]== && lcnt==) continue;

            res++;

        }

        else if(mp[dat[i].num]>=lmax) res++;

    }

    cout << res;

    return ;

}

Problem B

Problem C(Silver)

题意：经过分析后，其实就是求所有在环中的点的总数

我看到此题后直接无脑用了tarjan，通过求强联通分量找到所有的环

但实际上，由于此题的特殊性：每个数仅有一个儿子，因此可以使用类似于topo sort的方法来剪去所有不成环的点

原理是当一个点的入度全部为不在环上的点组成时，则其也一定不在环上

1、首先将所有入度为0的点加入队列

2、每次删去队列中的一个点并将其所有出边删除

3、将操作后入度为0的点再加入队列

#include <bits/stdc++.h>

using namespace std;

const int MAXN=;

int n,dfn[MAXN],low[MAXN],dat[MAXN],time_point=,res=;

bool vis[MAXN],instack[MAXN];

stack<int> s;

void tarjan(int node)

{

    time_point++;

    dfn[node]=low[node]=time_point;

    vis[node]=true;

    s.push(node);

    instack[node]=true;

    if(!vis[dat[node]])

    {

        tarjan(dat[node]);

        low[node]=min(low[node],low[dat[node]]);

    }

    else if(instack[dat[node]]) low[node]=min(low[node],low[dat[node]]);

    if(low[node]==dfn[node])

    {

        int temp,sum=;

        do

        {

            temp=s.top();

            res++;sum++;

            s.pop();

            instack[temp]=false;

        }

        while(temp!=node);

        if(sum== && dat[temp]!=temp) res--;

    }

}

int main()

{

    cin >> n;

    for(int i=;i<=n;i++) cin >> dat[i];

    for(int i=;i<=n;i++)

        if(!vis[i]) tarjan(i);

    cout << res;

    return ;

}

Solution A

#include <bits/stdc++.h>

using namespace std;

int in[],n;

bool res[];

vector<int> a[];

int main()

{

    memset(res,true,sizeof(res));

    int n;cin >> n;

    for(int i=;i<=n;i++)

    {

        int x;cin >> x;

        in[x]++;

        a[i].push_back(x);

    }

    queue<int> q;

    for(int i=;i<=n;i++)

        if(!in[i]) q.push(i),res[i]=false;

    while(!q.empty())

    {

        int x;x=q.front();q.pop();

        for(int i=;i<a[x].size();i++)

        {

            in[a[x][i]]--;

            if(!in[a[x][i]]) q.push(a[x][i]),res[a[x][i]]=false;

        }

    }

    int sum=;

    for(int i=;i<=n;i++) sum+=res[i];

    cout << sum;

    return ;

}

Solution B

因此可以发现拓扑排序和求环算法中的一些联系

巴特西