usaco总结

咕噜~~

这次usaco没有打上银组真是让我尴尬，第一次打usaco，有点紧张。。。

同组第一题的传送牛粪，虽不知道何必如此大费周章，但也是一代水题

题面是这样的：

Farmer John最讨厌的农活是运输牛粪。为了精简这个过程，他制造了一个伟大的发明：便便传送门！与使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点相比，他可以使用便便传送门将牛粪从一个地点瞬间传送到另一个地点。

Farmer John的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。一个传送门可以用两个数xx和yy表示，被拖到地点xx的牛粪可以瞬间传送到地点yy，反之亦然。

Farmer John想要将牛粪从地点aa运输到地点bb，他建造了一个可能对这一过程有所帮助的传送门（当然，如果没有帮助，他也可以不用）。请帮助他求出他需要使用拖拉机运输牛粪的总距离的最小值。

输入格式（文件名：teleport.in）：

输入仅包含一行，为四个用空格分隔的整数：aa和bb，表示起始地点和结束地点，后面是xx和yy，表示传送门。所有的位置都是范围为0…1000…100的整数，不一定各不相同。

输出格式（文件名：teleport.out）：

输出一个整数，为Farmer John需要用拖拉机运输牛粪的最小距离。

输入样例：

3 10 8 2

输出样例：

在这个样例中，最佳策略是将牛粪从位置3运到位置2，传送到位置8，再运到位置10。所以需要用拖拉机的总距离为1 + 2 = 3。

这题我采用了模拟法，一遍过，代码如下

#include
using namespace std;
int a,b,x,y,i,j;
long long n=0,m=0;
int main()
{
freopen("teleport.in","r",stdin);
freopen("teleport.out","w",stdout);

cin>>a>>b>>x>>y;
if(b>a)
{
n=b-a;
if(x>y)
 {
   if(a>y)
     m+=a-y;
   else
     m+=y-a;
   if(b>x)
     m+=b-x;
   else
 m+=x-b;  
     }
else
 {
  if(a>x)
    m+=a-x;
  else
    m+=x-a;
  if(b>y)
   m+=b-y;
  else
   m+=y-b;
 }
}
else
{   
  n=a-b;
if(x>y)
 {
  if(a>x)
    m+=a-x;
  else
    m+=x-a;
  if(b>y)
   m+=b-y;
  else
   m+=y-b;
}
else
 {
 
   if(a>y)
     m+=a-y;
   else
     m+=y-a;
   if(b>x)
     m+=b-x;

   else
 m+=x-b;  
     }  
}
if(n>m)
 cout<

很长，可以简洁很多，但这样写思路会更清晰，AC后也就没想过化简。

第二题，让我崩溃了两次，死循环了3次，wa了8个点，最终终于还是AC了；

为了准备即将到来的蹄球锦标赛，Farmer John正在训练他的NN头奶牛（方便起见，编号为1…N1…N，其中1≤N≤1001≤N≤100）进行传球。这些奶牛在牛棚一侧沿直线排列，第ii号奶牛位于距离牛棚xixi的地方(1≤xi≤10001≤xi≤1000)。每头奶牛都在不同的位置上。

在训练开始的时候，Farmer John会将若干个球传给不同的奶牛。当第ii号奶牛接到球时，无论是从Farmer John或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会传给其中距左边最远的那头奶牛）。为了使所有奶牛都有机会练习到传球，Farmer John想要确保每头奶牛都持球至少一次。帮助他求出为了达到这一目的他开始时至少要传出的球的数量。假设他在开始的时候能将球传给最适当的一组奶牛。

输入格式（文件名：hoofball.in）：

输入的第一行包含NN。第二行包含NN个用空格分隔的整数，其中第ii个整数为xixi。

输出格式（文件名：hoofball.out）：

输出Farmer John开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。

输入样例：

5
7 1 3 11 4

输出样例：

在上面的样例中，Farmer John应该将球传给位于x=1x=1的奶牛和位于x=11x=11的奶牛。位于x=1x=1的奶牛会将她的球传给位于x=3x=3的奶牛，在此之后这个球会在位于x=3x=3的奶牛和位于x=4x=4的奶牛之间来回传递。位于x=11x=11的奶牛会将她的球传给位于x=7x=7的奶牛，然后球会被传给位于x=4x=4的奶牛，在此之后这个球也会在位于x=3x=3的奶牛和位于x=4x=4的奶牛之间来回传递。这样的话，所有的奶牛都会至少一次接到球（可能从Farmer John，也可能从另一头奶牛）。

可以看出，不存在这样一头奶牛，Farmer John可以将球传给她之后所有奶牛最终都能被传到球。

供题：Dhruv Rohatgi

主要代码如下

sort(c+1,c+n+1,mycmp)//从大到小

n=c[1].r;

k=1;

x=2;

while(nm+1)



{

x=i;

break;

}

else

if(c[i].r>now) now=c[i].r;

}

}

第三题，我就有点蒙了；

有时只A了两个点，有时只A了一个点。

一大清早，Farmer John就被木材破裂的声音吵醒了。是这些奶牛们干的，她们又逃出牛棚了！

Farmer John已经厌烦了奶牛在清晨出逃，他觉得受够了：是时候采取强硬措施了。他在牛棚的墙上钉了一个计数器，追踪从上次出逃开始经过的天数。所以如果某一天早上发生了出逃事件，这一天的计数器就为00；如果最近的出逃是33天前，计数器读数就为33。Farmer John一丝不苟地记录了每一天计数器的读数。

年末到了，Farmer John准备做一些统计。他说，你们这些奶牛会付出代价的！然而意想不到的是，他的记录的一些条目竟然丢失了！

Farmer John确信他是在发生出逃的某一天开始记录的。请帮助他确定，在所有与残留记录条目一致的事件序列中，基于记录的时间，最少和最多可能发生的出逃次数。

输入格式（文件名：taming.in）：

输入的第一行包含一个整数NN（1≤N≤1001≤N≤100），表示从Farmer John开始对奶牛出逃计数器进行计数以来已经经过的天数。

第二行包含NN个空格分隔的整数。第ii个整数是−1−1，表示第ii天的记录丢失了，或者是一个非负整数aiai（不超过100100），表示在第ii天计数器的数字是aiai。

输出格式（文件名：taming.out）：

如果没有事件序列与Farmer John的残留记录以及他所确定的奶牛在第11天清晨出逃这一事实相一致，输出一个整数−1−1。否则，输出两个空格分隔的整数mm和MM，其中mm为所有事件序列中出逃的最少次数，MM为最多次数。

输入样例：

4
-1 -1 -1 1

输出样例：

2 3

在这个样例中，我们可以推断第3天必然有出逃发生。我们已经知道在第1天也发生了出逃，所以最后不确定的只有第2天是否发生了出逃。因此，总共发生了2至3次出逃。

不知道思维的差错，听了高中大佬的解说我才有点理解，自己的垃圾代码我亮出来也只是个笑话，不如给你们看看大佬的解法吧

a[1]=0;

b[1]=1;

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



{

  if(a[i]>=0)



{

  b[i-a[i]]=1；

  if(a[i]!=0)



{

  for(j=i-a[i]+1;j<=i;++j)



{

if(b[j]==1)



{

cout<<"-1";exit(0);)

b[j]=-1;

}}}}

}

if(b[1]==-2)



{

cout<<"-1";exit(0);

}

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



{

if(b[i]==1)

  ans1++,ans2++;

if(b[i]==0)

 ans2++;

}

cout<

可能我错就错在-1没有判断好，才导致这样的差错吧