USACO[Elite 2010 U S Open Competition/gold]

恩,第一题动态规划,用单调队列优化到O(n),第二题,树形动规。

然后重点第三题,这是APIO2010中的第三题(信号覆盖/signaling)也要用到的东西,统计平面中不包含某一点的三角形的个数。

看图:

USACO[Elite 2010 U S Open Competition/gold]解题报告 - 天之骄子 - 天之骄子的家
假设我们要求平面中不包含蓝色点的三角形个数,我们可以知道这样的三角形的三个点必定在蓝色点的一侧,所以我们可以用扫描法。
先将点按极角排序,然后对每一个点,找出在它逆时针方向180度以内(不包含180度)的点的个数。
那么,可以组合出C(个数,2),即随便选两个点和这个点搭配。
然后将所有组合加起来,就得到了平面中不包含某一点的三角形的个数。
下面给出上图的说明:
对a,b,c在逆时针方向180度以内(因为a和d刚好成180度角,所以不算d),C(2,2)=1;
对b,c,d,e在逆时针方向180度以内,C(3,2)=3;
对c,d,e,f在逆时针方向180度以内,C(3,2)=3;
对d,e,f,g在逆时针方向180度以内,C(3,2)=3;
对e,f,g,a在逆时针方向180度以内,C(3,2)=3;
对f,g,a,b在逆时针方向180度以内,C(3,2)=3;
对g,a,b,c在逆时针方向180度以内,C(3,2)=3。
总共19个三角形不包含蓝点。
包含蓝点的三角形=所有三角形的个数-不包含蓝点的三角形数目。
对于第三题,由于数据的原因(没有两点的连线过原点)所以
所有三角形的个数=C(总点数,3)-退化成一条线的三角形个数,
不包含蓝点的三角形数目=不包含蓝点的三角形数目(这里的三角形可以是退化的)-退化成一条线的三角形个数,
所以
答案=C(总点数,3)-不包含蓝点的三角形数目(这里的三角形可以是退化的)。
我要去考数学了,代码时间。
CODE:

/*

PROG: hop

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-6-3

DESCRIPTION:

TITLE: Cow Hopscotch [John Pardon, 2010]

CONTENT:

The cows have reverted to their childhood and

are playing a game similar to human hopscotch.

Their hopscotch game features a line of N (3 <=

N <= 250,000) squares conveniently labeled 1..N

that are chalked onto the grass.

Like any good game, this version of hopscotch

has prizes!  Square i is labeled with some

integer monetary value V_i (-2,000,000,000 <=

V_i <= 2,000,000,000). The cows play the game to

see who can earn the most money.

The rules are fairly simple:

    * A cow starts at square “0” (located just before square 1; it

      has no monetary value).

    * She then executes a potentially empty sequence of jumps toward

      square N. Each square she lands on can be a maximum of K (2

      <= K <= N) squares from its predecessor square (i.e., from

      square 1, she can jump outbound to squares 2 or 3 if K==2).

    * Whenever she wishes, the cow turns around and jumps back

      towards square 0, stopping when she arrives there. In addition

      to the restrictions above (including the K limit), two

      additional restrictions apply:

      * She is not allowed to land on any square she touched on her

        outbound trip (except square 0, of course).

      * Except for square 0, the squares she lands on during the

    return trip must directly precede squares she landed on

    during the outbound trip (though she might make some larger

    leaps that skip potential return squares altogether).     

She earns an amount of money equal to the sum of the monetary values

of all the squares she jumped on. Find the largest amount of cash

a cow can earn.

By way of example, consider this five box cow-hopscotch course where

K has the value 3:

Square Num:    0      1      2      3      4      5      6

             +—+  +—+  +—+  +—+  +—+  +—+  +—+

             |///|–|   |–|   |–|   |–|   |–|   |–|   |

             +—+  +—+  +—+  +—+  +—+  +—+  +—+

     Value:          0      1      2     -3      4      5

One (optimal) sequence Bessie could jump (shown with respective

bracketed monetary values) is: 1[0], 3[2], 6[5], 5[4], 2[1], 0[0]

would yield a monetary total of 0+2+5+4+1+0=12.

If Bessie jumped a sequence beginning with 0, 1, 2, 3, 4, … then

she would be unable to return since she could not legally jump back

to an untouched square.

PROBLEM NAME: hop

INPUT FORMAT:

* Line 1: Two space separated integers: N and K

* Lines 2..N+1: Line i+1 contains a single integer: V_i

SAMPLE INPUT (file hop.in):

6 3

0

1

2

-3

4

5

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the maximum

        amount of money a cow can earn

SAMPLE OUTPUT (file hop.out):

12

*/

#include <stdio.h>

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

 

const int MAXN=250000;

const long long int oo=1000000000000000000ll;

int N,K;

int V[MAXN+1];

 

long long int _sum[MAXN+2];

long long int _f[MAXN+2];

long long int answer;

 

int main()

{

    freopen(“hop.in”,“r”,stdin);

    freopen(“hop.out”,“w”,stdout);

    scanf(“%d %d\n”,&N,&K);

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

        scanf(“%d\n”,&V[i]);

   

    long long int* sum=_sum+1;

    long long int* f=_f+1;

   

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

        if (V[i]>0) sum[i]=sum[i-1]+V[i];

        else sum[i]=sum[i-1];

   

    answer=-oo;

   

    int head,tail;

    int q[MAXN];

    f[q[head=tail=0]=-1]=0;

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

    {

        long long int get=f[q[head]]-sum[q[head]+1]+sum[i-1]+V[i];

        if (get>answer) answer=get;

       

        while (q[head]+K<i) head++;

        if (i!=N) f[i]=f[q[head]]-sum[q[head]+1]+sum[i-1]+V[i]+V[i+1];

       

        while (head<=tail&&f[q[tail]]-sum[q[tail]+1]<f[i]-sum[i+1]) tail–;

        q[++tail]=i;

    }

   

    cout<<answer<<endl;

   

    fclose(stdin);

    fclose(stdout);

    return 0;

}

 

/*

PROG: slide

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-23

DESCRIPTION:

TITLE: Water Slides [John Pardon, 2010]

CONTENT:

Inspired by the new water park at Machu

Picchu in Peru, Farmer John has decided

to build one for the cows. Its biggest

attraction is to be a giant water slide

of a peculiar design.

The superslide comprises E (1 <= E <=

150,000) mini slides connecting V (2 <=

V <= 50,000) small pools conveniently

labeled 1..V. Every mini slide must be

traversed in its proper direction and

may not be traversed backwards. The

cows start at pool number 1 and

traverse successive mini slides until

they end up in the pool number V, the

final pool. Every pool (except V, the

last one and 1, the first one)

includes at least one mini slide

entering it and at least one

(different) mini slide for exiting

it.  Furthermore, a cow can reach the

end of the ride (pool V) from any

pool by going down a sequence of mini

slides. Finally, since this is a

slide, it is not possible to leave a

pool and then encounter that pool

again after traversing some set of

mini slides.

Each mini slide i runs from pool P_i to pool Q_i (1 <= P_i <= V; 1

<= Q_i <= V; P_i != Q_i) and has an associated fun value F_i (0 <=

F_i <= 2,000,000,000). Bessie’s total fun for any given trip down

the superslide is the sum of the fun values of all the mini slides

traversed.

Bessie naturally wants to have as much fun as possible, given the

long time that she spends in the slide’s queue waiting for the ride.

Generally, she carefully chooses which mini slide to follow out of

each pool. She is a cow, however, and no more than K (1 <= K <= 10)

times as she splashes down the slide, she loses control and follows

a random mini slide out of a pool (this can even happen on pool 1).

If Bessie chooses so as to maximize her fun in the worst case, how

much fun is she guaranteed to have for a given super-slide?

By way of example, consider a small park that has 3 pools (pool

id’s shown in brackets) and four mini slides; K has the value 1

(fun values shown outside of brackets):

          [1]

         /   \

   5 -> /     \ <- 9

       /       \

     [2]—3—[3]

        \__5__/

She alway starts at pool 1 and ends and pool 3. If she had her way,

she’d ride direct from pool 1 to pool 2 and then on the higher-fun

mini slide (with fun value 5) to slide 3 for a total fun value of

5+5=10. But, if she loses control at pool 1, she might slide directly

from pool 1 to pool 3 for total fun 9. If she loses control at pool

2, she could reduce her total fun to just 5+3 = 8.

Bessie wants to find the most fun she can have so she strives to

choose 1->3 for a total fun of 9. If she loses control at pool 1

and ends up on mini slide 1->2, she knows she will not lose control

at pool 2 and will end up with fun 10. Thus, she knows her minimum

fun will always be at least 9.

PROBLEM NAME: slide

INPUT FORMAT:

* Line 1: Three space separated integers: V, E, and K

* Lines 2..E + 1: Line i+1 contains three space separated integers:

        P_i, Q_i, and F_i

SAMPLE INPUT (file slide.in):

3 4 1

2 3 5

1 2 5

1 3 9

2 3 3

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the minimum fun

        that Bessie can guarantee she can have.

SAMPLE OUTPUT (file slide.out):

9

*/

#include <stdio.h>

#include <iostream>

using namespace std;

#include <vector>

using std::vector;

 

const long long int oo=1000000000000000000ll;

const long long int MAXV=50000,MAXE=150000,MAXK=10;

long long int V,E,K;

long long int P[MAXE],Q[MAXE],F[MAXE];

bool calced[MAXV+1][MAXK+1];

vector<int> child[MAXV+1],length[MAXV+1];

long long int value[MAXV+1][MAXK+1];

long long int answer;

 

long long int min(long long int a,long long int b)

{

     return a<b?a:b;

}

long long int max(long long int a,long long int b)

{

     return a>b?a:b;

}

long long int dp(int node,int k)

{

     if (!calced[node][k])

     {

        calced[node][k]=true;

        for (int i=0;i<child[node].size();i++)

            value[node][k]=max(value[node][k],

                               dp(child[node][i],k)+length[node][i]);

        if (k>0)

           for (int i=0;i<child[node].size();i++)

           {

               value[node][k]=min(value[node][k],

                                  dp(child[node][i],k-1)+length[node][i]);

           }

     }

     return value[node][k];

}

void print(long long int long_long_int)

{

     if (long_long_int>=10)

        print(long_long_int/10);

     printf(“%d”,int(long_long_int%10));

}

 

int main()

{

    freopen(“slide.in”,“r”,stdin);

    freopen(“slide.out”,“w”,stdout);

    scanf(“%d %d %d\n”,&V,&E,&K);

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

        scanf(“%d %d %d\n”,&P[i],&Q[i],&F[i]);

   

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

    {

        child[P[i]].push_back(Q[i]);

        length[P[i]].push_back(F[i]);

    }   

    answer=dp(1,K);

   

    /*

    printf(“%lld\n”,answer); //for Linux/Unix

    printf(“%I64d\n”,answer); //for Windows

    */

    //for anywhere

    print(answer);

    printf(“\n”);

   

    fclose(stdin);

    fclose(stdout);

    return 0;

}

 

/*

PROG: tricount

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-6-3

DESCRIPTION:

TITLE: Triangle Counting [Tom Conerly, 2010]

CONTENT:

Bessie is standing guard duty after

the big bad wolf was spotted stalking

cows over at Farmer Don’s spread.

Looking down from her guard tower in

utter boredom, she’s decided to

perform intellectual exercises in

order to keep awake.

After imagining the field as an X,Y

grid, she recorded the coordinates of

the N (1 <= N <= 100,000)

conveniently numbered 1..N cows as

X_i,Y_i (-100,000 <= X_i <= 100,000;

-100,000 <= Y_i <= 100,000; 1 <= i <=

N). She then mentally formed all possible triangles that could be

made from subsets of the entire set of cow coordinates. She counts

a triangle as ‘golden’ if it wholly contains the origin (0,0). The

origin does not fall on the line between any pair of cows. Additionally,

no cow is standing exactly on the origin.

Given the list of cow locations, calculate the number of ‘golden’

triangles that contain the origin so Bessie will know if she’s doing

a good job.

By way of example, consider 5 cows at these locations:

             -5,0   0,2   11,2   -11,-6   11,-5

Below is a schematic layout of the field from Betsy’s point of view:

          …………|…………

          …………*……….*.

          …………|…………

          ——-*—-+————

          …………|…………

          …………|…………

          …………|…………

          …………|…………

          …………|……….*.

          .*……….|…………

          …………|…………

All ten triangles below can be formed from the five points above:

By inspection, 5 of them contain the origin and hence are ‘golden’.

PROBLEM NAME: tricount

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Each line contains two integers, the coordinates of a

        single cow: X_i and Y_i

SAMPLE INPUT (file tricount.in):

5

-5 0

0 2

11 2

-11 -6

11 -5

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the count of the

        number of times a triangle formed by the cow locations

        contains the origin

SAMPLE OUTPUT (file tricount.out):

5

*/

#include <fstream>

using std::ifstream;

using std::ofstream;

using std::endl;

#include <utility>

using std::pair;

using std::make_pair;

#define Point pair<int,int>

#define x first

#define y second

 

struct Compare

{

       static

       inline

       long long int cross(const Point& a,const Point& b)

       {

            return (long long int)(a.x)*(long long int)(b.y)-(long long int)(b.x)*(long long int)(a.y);

       }

       static

       inline

       bool less(const Point& a,const Point& b)

       {

            return cross(a,b)>0;

       }

      

       static

       void sort(Point* l,Point* r)

       {

            Point* i=l;

            Point* j=r;

            Point mid=*(l+((r-l)>>1));

            while (i<=j)

            {

                  while (less(*i,mid)) i++;

                  while (less(mid,*j)) j–;

                  if (i<=j)

                  {

                     Point s=*i;

                     *i=*j;

                     *j=s;

                     i++;

                     j–;

                  }

            }

            if (l<j) sort(l,j);

            if (i<r) sort(i,r);

       }

};

 

class Application

{

      ifstream cin;

      ofstream cout;

      static const int MAXN=100000;

      long long int N;

      Point p[MAXN];

      public:

      Application(const char* input,const char* output)

                        :cin(input),cout(output)

      {

                        cin>>N;

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

                            cin>>p[i].x>>p[i].y;

      }

      ~Application()

      {

                    cin.close();

                    cout.close();

      }

      int run()

      {

          Compare compare;

          compare.sort(p,p+N-1);

          long long int result=0;

          for (int i=0,j=0;i<N;i++)

          {

              while (compare.less(p[i],p[(j+1)%N])) j=(j+1)%N;

              int get=(j-i+N)%N;

              if (get>=2) result+=((get)*(get-1))>>1;

          }

          cout<<(N*(N-1)*(N-2))/(3*2*1)-result<<endl;

          return 0;

      }

};

 

int main()

{

    Application app(“tricount.in”,“tricount.out”);

    return app.run();

}

 

留下评论

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