USACO18OPEN 主题模拟赛

这次的题目都不算很水，还是比较有价值的一套题来纪念一下

USACO18OPEN 主题模拟赛

T1: Out of Sorts

题意简述

sorted = false
while (not sorted):
   sorted = true
   moo++
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

给一段伪代码，求出最后答案的moo值是多少，（这段代码是根据冒泡排序改的）

题解

事实上交以上伪代码的c++版本可获得40分的好成绩，稍加一些优化有50分。

然而正解其实很玄学。

这个moo的值实际上就是离散化之后的序列中，前$i$个数中大于$i$的数的最大值。

对于一个（伪）冒泡排序的过程，以一个$i$为界限，

向后扫会保证把前 𝑖 个位置上一个值$> 𝑖$ 的数扔到后边去
向前扫会保证被换到前𝑖 个位置上的新数的值是$≤ 𝑖 $的

于是前$i$个中大于$i$的数就是需要交换的次数，扫一遍求最大值就行。

至于求法，可以模拟，也可以树状数组，我就只打了模拟。。

代码

模拟代码

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+110;
int n,m,ans,Case,tree[N],pos[N];
bool flag,vis[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void add(int x,int k)
{
    for(int i=x;i<=n;i+=i&(-i))
        tree[i]+=k;
}
int query(int x)
{
    int sum=0;
    for(int i=x;i>=0;i-=i&(-i))
        sum+=tree[i];
    return sum;
}
struct node
{
    int val,num;
    bool operator < (const node &v)const 
    {
        return val<v.val||val==v.val&&num<v.num;
    }
}a[N];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i].val=read(),a[i].num=i;
    sort(a+1,a+1+n);
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].num>i)sum++;
        if(vis[i])sum--;
        vis[a[i].num]=1;
        ans=max(ans,sum);
    }
    printf("%d",max(1,ans));//注意有可能是0
    return 0;
}

树状数组

#include<bits/stdc++.h>
#define MAXN 100005
#define LL long long
#define INF 2147483640
#define MOD 100000007
#define lowbit(x) ((x&(-x))) 
using namespace std;
const int L=1e5+5;
struct node
{
    int x,num;
};
bool cmp(const node &a,const node &b)
{
    return a.x<b.x||(a.x==b.x&&a.num<b.num);
}
int n,ans,sum[L];
node a[L];
void ins(int x)
{
    for(int i=x;i<=L;i+=lowbit(i))
        sum[i]++;
}
int ask(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=sum[i];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].x);
        a[i].num=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        ins(a[i].num);
        ans=max(ans,i-ask(i));
    }
    printf("%d",max(ans,1));
    return 0;
}

T2: Milking Order

题意简述

共有$n$头牛，给定$m$个排列顺序（可以只有部分牛），求在满足最大的x的情况下，找到最终的一个排列顺序，满足前x个给出的排列顺序，且放在前面的牛尽量小。。题意很长我尽力了。

完整版题意

题解

是一个裸的拓扑。。。

二分一个最大的x，每一次可以拓扑或tarjan判环，最后用小根堆拓扑排序一下就行。

关于每次check，可以选择每一次摧毁之前所有的边，重新建边。

也可以定一个time，一次行先建完所有的边，最后只查time<=当前x的边就行，跑的很快

代码

#include <bits/stdc++.h>

using namespace std;
const int M=5e5+110;
const int N=1e5+110;
int n,m,in[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int head[N],cnt;
struct node
{
    int nt,to;
};
node edge[M];
void add(int x,int y)
{
    edge[++cnt]=(node){head[x],y};
    head[x]=cnt;
}
vector<int>ve[M];
void build(int x)
{
    memset(head,0,sizeof(head));
    memset(in,0,sizeof(in));
    cnt=0;
    for(int i=1;i<=x;i++)
    {
        for(int j=0;j<ve[i].size()-1;j++)
        {
            add(ve[i][j],ve[i][j+1]);
            in[ve[i][j+1]]++;
        }
    }
}
bool check(int x)
{
    build(x);
    queue<int>q;
    for(int i=1;i<=n;i++)
        if(!in[i])q.push(i);
    int ans=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        ans++;
        for(int i=head[u];i;i=edge[i].nt)
        {
            int v=edge[i].to;
            in[v]--;
            if(!in[v])q.push(v);
        }
    }
    if(ans<n)return 0;
    else return 1;
}
void print(int x)
{
    build(x);
    priority_queue<int, vector<int>, greater <int > >q;
    for(int i=1;i<=n;i++)
        if(!in[i])q.push(i);
    while(!q.empty())
    {
        int u=q.top();
        q.pop();
        printf("%d ",u);
        for(int i=head[u];i;i=edge[i].nt)
        {
            int v=edge[i].to;
            in[v]--;
            if(!in[v])q.push(v);

        }
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read();
        for(int j=1;j<=x;j++)
        {
            int y=read();
            ve[i].push_back(y);
        }
    }
    int l=1,r=m;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))l=mid+1;
        else r=mid-1;
    }
    print((l+r)/2);
    return 0;
}

T3: Talent Show

题意简述

每个物品有一个$w_i,t_i$,求当总的w大于等于一个给定值$W$使$\sum_{t_i}/\sum_{w_i}$的最大值

题解

裸的01分数规划背包dp，可惜我不会，因为数据水就混到了90分。。。。

考虑$ans=\sum_{t_i}/\sum_{w_i}$ 是最优的解，Z是当前不那么优秀的解

则有$\sum_{t_i}/\sum_{w_i}>=Z$

移项得$\sum_{t_i}-\sum_{w_i} \times Z>=0$

此时一个i的贡献值就只和i有关了！！

于是可以考虑二分答案，在check的时候做一个01背包dp

设$dp[i]$表示当容量与i的时候$t[i]-w[i] \times Z$的最大值，当$dp[W]$ 为非负值时，说明此时的答案时成立的

代码

#include <bits/stdc++.h>
#define eps 1e-6
using namespace std;
const int N = 260;
const int M = 1e3+10;
const int INF=(1<<30);
int w[N],t[N],n,m,W,sum;
double dp[M],a[M];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool check(double ans)
{
    memset(dp,-0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)a[i]=t[i]-w[i]*ans;
    dp[0]=0.0;
    for(int i=1;i<=n;i++)
      for(int j=W;~j;j--)
      {
           int p=min(W,j+w[i]);
           dp[p]=max(dp[p],dp[j]+a[i]);
      }
    return dp[W]>=0;
}
int main()
{
    n=read();W=read();
    for(int i=1;i<=n;i++)w[i]=read(),t[i]=read(),sum+=t[i];
    double l=0,r=sum*1.0;
    while(r-l>=eps)
    {
        double mid=(l+r)/2;
        if(check(mid))l=mid+eps;
        else r=mid-eps;
    }
    cout<<(int)((l+r)/2*1000);
    return 0;
}