USACO February 2021 Contest Bronze 题解

· · 个人记录

http://usaco.org/index.php?page=feb20results

T1 Year of the Cow

建出来的话应该是一棵树。但其实从后向前跑一下就能跑出来结果了。因为条件指出

The last word is the name of a cow on the farm, which is either "Bessie" or a cow that has already been mentioned in a previous line of input. The first word is the name of a cow on the farm who is not "Bessie" and who has not yet been mentioned in the input. All cow names have at most 10 characters that are in the range a..z or A..Z.

namespace solve {
    const int N = 114;
    map<string, pair<int, string> > m;
    map<string, string> q;
    int n;
    string ord[N];
    void main() {
        cin >> n;
        string s, end;
        q["Bessie"] = "Ox";
        for (int i = 1; i <= n; ++i) {
            int f = 1;
            for (int j = 1; j <= 8; ++j) {
                cin >> s;
                if (j == 1) ord[i] = s;
                if (j == 4 && s[0] == 'n') f = -1;
                if (j == 5) { end = s; q[ord[i]] = s; }
                if (j == 8)
                    for (int k = 0; k < 12; ++k) 
                        if (sign[k] == q[s]) {
                            int p = (k - f + 12) % 12, sum = 1;
                            while (sign[p] != end) { p = (p - f + 12) % 12; sum++; }
                            m[ord[i]] = mkp(f * sum, s);
                            break;
                        }
            }
        }
        string obj = "Elsie";
        int sum = 0;
        for (int i = n; i >= 1; --i) 
            if (ord[i] == obj) { sum += m[obj].first; obj = m[obj].second; }
        cout << abs(sum) << '\n';
    }
}

T2 Comfortable Cows

若一个奶牛被放入草地，受其影响的显然只是它四周的奶牛，因此我们每放入一头奶牛就检查一下它四周的奶牛以及它自己，维护出一个当前舒适奶牛的数目即可。

namespace solve {
    const int N = 1145;
    const int dx[] = { 0, 1, 0, -1 };
    const int dy[] = { 1, 0, -1, 0 };
    bool g[N][N];
    int n, x, y, sum;
    bool check(int x, int y) {
        if (x < 0 || y < 0) return 0;
        int sum = 0;
        for (int i = 0; i < 4; ++i) 
            if (x + dx[i] >= 0 && y + dy[i] >= 0)
                sum += g[x + dx[i]][y + dy[i]];
        return g[x][y] && sum == 3;
    }
    void main() {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> x >> y;
            for (int j = 0; j < 4; ++j)
                if (check(x + dx[j], y + dy[j])) sum--;
            g[x][y] = 1;
            sum += check(x, y);
            for (int j = 0; j < 4; ++j) 
                if (check(x + dx[j], y + dy[j])) sum++;
            cout << sum << '\n';
        }
    }
}

T3 Clockwise Fence

FloodFill

从题目中下面的内容获得启示。

Farmer John is curious if the path in which he laid the fence traveled clockwise (with the enclosed region on the right side of the fence as one walks along the path of the fence in the order specified by the string) or counter-clockwise (with the enclosed region on the left side of the fence).

也就是说如果当前方向的右手边是封闭区间那么就应当是顺时针，否则为逆时针。我们将奶牛的路径画下来，同时设置一个更大的边界，从左手边开始 FloodFill, 若碰到大边界，意味着封闭区间在右手边，即为顺时针，反之亦然。

namespace solve {
    int tt;
    int g[451][451];
    const int dx[] = { 0, 1, 0, -1 };
    const int dy[] = { 1, 0, -1, 0 };
    queue<pair<int, int> > q;
    bool FloodFill(int x, int y) {
        g[x][y] = 2;
        q.push(mkp(x, y));
        while (q.size()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; ++i) {
                if (x + dx[i] <= 0 || y + dy[i] <= 0 || 
                    x + dy[i] > 420 || y + dy[i] > 420) {
                    while (q.size()) q.pop();
                    return 1;
                }
                if (g[x + dx[i]][y + dy[i]]) continue;
                g[x + dx[i]][y + dy[i]] = 2;
                q.push(mkp(x + dx[i], y + dy[i]));
            }
        }
        return 0;
    }
    void main() {
        cin >> tt;
        while (tt--) {
            memset(g, 0, sizeof(g));
            int x = 210, y = 210, stx, sty;
            g[x][y] = 1;
            string s; 
            cin >> s;
            if (s[0] == 'N') stx = x - 1, sty = y + 1;
            if (s[0] == 'W') stx = x - 1, sty = y - 1;
            if (s[0] == 'S') stx = x + 1, sty = y - 1;
            if (s[0] == 'E') stx = x + 1, sty = y + 1;
            for (int i = 0; i < s.size(); ++i) {
                if (s[i] == 'N') { g[x][++y] = 1; g[x][++y] = 1; }
                if (s[i] == 'W') { g[--x][y] = 1; g[--x][y] = 1; }
                if (s[i] == 'S') { g[x][--y] = 1; g[x][--y] = 1; }
                if (s[i] == 'E') { g[++x][y] = 1; g[++x][y] = 1; }
            }
            if (FloodFill(stx, sty)) cout << "CW\n";
            else cout << "CCW\n";
            //选择左边进行填充(2)，若遇到边界则返回1,否则返回0
        }
    }
}

更加数学的方法

路径一定是一个可能包含 270\degree 角，以及一定包含 90\degree 角的封闭图形。简单来说就是这样：

黑色的表示铺设的路径。可以看出，我们可以把它补全成一个矩形（purple），而原图就相当于是矩形的某些部分凹陷下去。相较与矩形，我们发现它存在更多 90\degree 的角以及 270\degree 的角。但是经过观察，发现不管是在原矩形的边上还是在角上凹陷部分所生成的 270\degree 角（blue），都和生成的 90\degree 角（orange）的个数相等。

因此可以得出: n_{90\degree}-n_{270\degree}=4.

并且对于顺时针来说，走 90\degree 角是右转，走 270\degree 角是左转。逆时针刚好相反。

于是统计一下路径上左转右转的次数即可判断顺时针还是逆时针。

#include<bits/stdc++.h>
using namespace std;
string s,l="NWSEN";
int tt,a,b;
int main() {
    cin>>tt;
    while(tt--){
        a=b=0;
        cin>>s;
        for(int i=1;i<s.size();++i)
            if(s[i]!=s[i-1])
                if(l.find(s.substr(i-1,2))!=string::npos)a++;
                else b++;
        cout<<(a>b?"CCW":"CW")<<'\n';
    }
    return 0;
}