2012年USACO真题及解析 吃透真题临时抱佛脚也能得奖

真题对于竞赛的同学来说是最好的复习资料，USACO竞赛即将开赛，同学们的编程算法都复习好了吗？下面给大家带来的是2012年USACO真题及解析，同学们在这个倒真题能不能找出考点呢？

As is commonly known, cows are very socially polite creatures: any time twocows meet after being apart, they greet each-other with a friendly "moo".Bessie the cow and her friend, Elsie, are walking around on a longpath on Farmer John's farm. For all practical purposes, we can thinkof this path as a one-dimensional number line. Bessie and Elsie bothstart at the origin, and they both then begin walking around atidentical speeds for some amount of time. Given a description of themovements taken by each cow, please determine the number of "moos"exchanged. Bessie and Elsie can stop moving at different points in time, andneither cow will travel for more than 1,000,000 units of time.

有两头牛Bessie和Elsie，给出两个正整数B和E，分别代表Bessie和Elsie的移动情况个数，然后每一行给出一个正整数dt和一个方向dir，代表牛向左或者向右走了dt个单位时间。牛移动的速度是一样的，自从它们从同一个起点分离后一见面就会发出“moo”的声音，问它们总共发了几次声音。

INPUT FORMAT:

• Line 1: Two space-separated integers, B (1 <= B <= 50,000) and E(1 <= E <= 50,000).
  

• Lines 2..1+B: These B lines describe Bessie's movements. Each line contains a positive integer followed by either "L"or"R",indicating the distance Bessie moves in a direction that is either left or right.  
  

• Lines 2+B..1+B+E: These E lines describe Elsie's movements. Each line contains a positive integer followed by either "L" or "R", indicating the distance Elsie moves in a direction that is either left or right.

SAMPLE INPUT (file greetings.in):

4 5

3 L

5 R

1 L

2 R

4 R

1 L

3 L

4 R

2 L

INPUT DETAILS:

Bessie moves left for 3 units of time, then right for 5 units of time, thenleft for 1 unit of time, and finally right for 2 units of time; she thenstands still. Elsie moves right for 4 units of time, then left for 4 unitsof time, then right for 4 units of time, then left for 2 units of time; shethen stands still.

OUTPUT FORMAT:

Line 1: An integer specifying the number of "moos" exchanged by the two cows. Their initial shared starting position at the origin does not cause a "moo".

SAMPLE OUTPUT (file greetings.out):

3O

UTPUT DETAILS:

Bessie and Elsie meet after being temporarily apart at time 7, time 9, andtime 13.

算法思路：对每一头牛的某个时刻的移动情况进行记录，然后按时间从小到大排序。然后遍历比较。

参考程序：

#include <vector>

#include <algorithm>

#include<iostream>

using namespace std;

#define BESSIE 0

#define ELSIE 1

struct KeyPoint {

    int t;

    int cow;

    int newdir;

    KeyPoint(int t, int cow, int newdir)

        : t(t), cow(cow), newdir(newdir) { }

    bool operator<(KeyPoint const& o) const {

        return t < o.t;

    }

};

vector<KeyPoint> keyPoints;

int readKeyPoints(int n, int cow) {

    int t = 0;

    int initdir;

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

    {

        int dt;

        char c;

        scanf("%d", &dt);

        do {

            c = fgetc(stdin);

        } while (c != 'L' && c != 'R');

        int dir = (c == 'R' ? 1 : -1);

        if (t == 0)

            initdir = dir;

        else

            keyPoints.push_back(KeyPoint(t, cow, dir));

        t += dt;

    }

    keyPoints.push_back(KeyPoint(t, cow, 0));

    return initdir;

} 

int main()

{

    int nSteps1, nSteps2;

    scanf("%d", &nSteps1);

    scanf("%d", &nSteps2);

    int dir1 = readKeyPoints(nSteps1, BESSIE);

    int dir2 = readKeyPoints(nSteps2, ELSIE);

    sort(keyPoints.begin(), keyPoints.end());

    int t = 0;

    int x1 = 0;

    int x2 = 0;

    int nMoos = 0;

    for (int i = 0; i < keyPoints.size(); i++)

    {

        int new_t = keyPoints[i].t;

        int new_x1 = x1 + (new_t - t) * dir1;

        int new_x2 = x2 + (new_t - t) * dir2;

        if (x1 != x2 && (new_x1 == new_x2 || ((x1 < x2) ^ (new_x1 < new_x2))))

            nMoos++;

        t = new_t;

        x1 = new_x1;

        x2 = new_x2;

        if (keyPoints[i].cow == BESSIE)

            dir1 = keyPoints[i].newdir;

        else

            dir2 = keyPoints[i].newdir;

    }

    printf("%d\n", nMoos);

}

竞赛是进入知名大学的关键助力之一。纵观橡沐今年113位牛剑录取的学员，大部分学员手里都握着各种竞赛奖项：AMC，UKCHO，BBO等等。能申请牛剑G5的学员成绩都不会差，只有竞赛、文书、背景提升这样的软实力才能拉开差距，明年上半年就有一大波权威国际竞赛，如果你还不知道从哪里开始，就点击报名【橡沐竞赛复习班】，让知名大学海归竞赛导师带你选择最适合自己、最有利于申请的竞赛，高效梳理知识点，训练考试技巧，介绍联想、类比、归纳、转化、试误等答题技巧。

点击

计算机零基础 如何复习USACO竞赛

USACO什么难度 不会编程没有算法知识也能参加

查看更多。