USACO 2017 Dec Silver

1. My Cow Ate My Homework

题目链接

https://www.luogu.org/problem/P4086

题解

首先，我们从后向前遍历数组，求出后缀和和后缀最小值。

然后，枚举 \(k\) 的值即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int mins[100005],a[100005],post[100005],re[100005],cnt,n;
long double ans;
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
 mins[n]=post[n]=a[n];
 for(int i=n-1;i>=1;i--)
 {
  mins[i]=min(mins[i+1],a[i]);
  post[i]=post[i+1]+a[i];
 }
 for(int k=1;k<=n-2;k++)
 {
  long double cur=((long double)post[k+1]-mins[k+1])/(n-k-1);
  if(ans<cur)
  {
   ans=cur;
   memset(re,0,sizeof(re));
   re[cnt=1]=k;
  }
  else if(ans==cur)re[++cnt]=k;
 }
 for(int i=1;i<=cnt;i++)
  printf("%d\n",re[i]);
 return 0;
}

2. Milk Measurement

题目链接

https://www.luogu.org/problem/P4087

题解

（先咕着，因为这题我才拿了40）

3. The Bovine Shuffle

题目链接

https://www.luogu.org/problem/P4089

题解

先放一个非正解，就是暴力模拟。

把整个过程模拟上一定次数，然后判断各个位置上是否有奶牛即可。

（模拟次数少了容易WA，次数多了会TLE）

#include <stdio.h>
#include <string.h>
int a[100005],b[100005],c[100005];
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  a[i]=1;
 for(int i=1;i<=n;i++)
  scanf("%d",&c[i]);
 for(int i=1;i<=500;i++)//最慢的点跑了328ms
 {
  for(int i=1;i<=n;i++)
   b[c[i]]+=a[i];
  memset(a,0,sizeof(a));
  for(int i=1;i<=n;i++)
   a[c[i]]+=b[i];
  memset(b,0,sizeof(b));
 }
 int ans=0;
 for(int i=1;i<=n;i++)
  if(a[i])ans++;
 printf("%d",ans);
 return 0;
}

（正解先咕着）